/usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.use.bitabs.translation false -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.4-tmp.fs.bitabs-eval-d9c3e40-m [2023-12-21 07:19:39,192 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-12-21 07:19:39,264 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-32bit-Automizer_Default.epf [2023-12-21 07:19:39,266 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-12-21 07:19:39,266 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-12-21 07:19:39,289 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-12-21 07:19:39,290 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-12-21 07:19:39,291 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-12-21 07:19:39,291 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-12-21 07:19:39,294 INFO L153 SettingsManager]: * Use memory slicer=true [2023-12-21 07:19:39,294 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-12-21 07:19:39,294 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-12-21 07:19:39,295 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-12-21 07:19:39,296 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-12-21 07:19:39,296 INFO L153 SettingsManager]: * Use SBE=true [2023-12-21 07:19:39,296 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-12-21 07:19:39,296 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-12-21 07:19:39,296 INFO L153 SettingsManager]: * sizeof long=4 [2023-12-21 07:19:39,296 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-12-21 07:19:39,297 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-12-21 07:19:39,297 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-12-21 07:19:39,297 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-12-21 07:19:39,297 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-12-21 07:19:39,297 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-12-21 07:19:39,298 INFO L153 SettingsManager]: * Allow undefined functions=false [2023-12-21 07:19:39,298 INFO L153 SettingsManager]: * sizeof long double=12 [2023-12-21 07:19:39,298 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-12-21 07:19:39,298 INFO L153 SettingsManager]: * Use constant arrays=true [2023-12-21 07:19:39,298 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-12-21 07:19:39,299 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-12-21 07:19:39,299 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-12-21 07:19:39,300 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-12-21 07:19:39,300 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-21 07:19:39,300 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-12-21 07:19:39,300 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-12-21 07:19:39,300 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-12-21 07:19:39,300 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-12-21 07:19:39,300 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-12-21 07:19:39,300 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-12-21 07:19:39,301 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-12-21 07:19:39,301 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-12-21 07:19:39,301 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-12-21 07:19:39,301 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-12-21 07:19:39,301 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Use bitabs translation -> false [2023-12-21 07:19:39,465 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-12-21 07:19:39,480 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-12-21 07:19:39,482 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-12-21 07:19:39,482 INFO L270 PluginConnector]: Initializing CDTParser... [2023-12-21 07:19:39,483 INFO L274 PluginConnector]: CDTParser initialized [2023-12-21 07:19:39,483 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound50.c [2023-12-21 07:19:40,434 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-12-21 07:19:40,595 INFO L384 CDTParser]: Found 1 translation units. [2023-12-21 07:19:40,595 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound50.c [2023-12-21 07:19:40,600 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e8c22575c/8afa6e4490ef405a874689b9c70becf9/FLAGe54d78f8d [2023-12-21 07:19:40,610 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e8c22575c/8afa6e4490ef405a874689b9c70becf9 [2023-12-21 07:19:40,611 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-12-21 07:19:40,612 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2023-12-21 07:19:40,613 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-12-21 07:19:40,613 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-12-21 07:19:40,620 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-12-21 07:19:40,621 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,622 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3a78a1d6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40, skipping insertion in model container [2023-12-21 07:19:40,622 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,635 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-12-21 07:19:40,756 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound50.c[537,550] [2023-12-21 07:19:40,776 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-21 07:19:40,783 INFO L202 MainTranslator]: Completed pre-run [2023-12-21 07:19:40,793 WARN L239 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-u_unwindbound50.c[537,550] [2023-12-21 07:19:40,807 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-12-21 07:19:40,817 INFO L206 MainTranslator]: Completed translation [2023-12-21 07:19:40,817 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40 WrapperNode [2023-12-21 07:19:40,817 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-12-21 07:19:40,818 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-12-21 07:19:40,818 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-12-21 07:19:40,818 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-12-21 07:19:40,822 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,827 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,841 INFO L138 Inliner]: procedures = 14, calls = 15, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 66 [2023-12-21 07:19:40,842 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-12-21 07:19:40,842 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-12-21 07:19:40,842 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-12-21 07:19:40,842 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-12-21 07:19:40,849 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,849 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,855 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,865 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2023-12-21 07:19:40,865 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,865 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,873 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,875 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,879 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,880 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,882 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-12-21 07:19:40,883 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-12-21 07:19:40,883 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-12-21 07:19:40,883 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-12-21 07:19:40,884 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (1/1) ... [2023-12-21 07:19:40,887 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2023-12-21 07:19:40,893 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:40,909 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2023-12-21 07:19:40,962 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2023-12-21 07:19:40,967 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-12-21 07:19:40,967 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-12-21 07:19:40,967 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-12-21 07:19:40,967 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-12-21 07:19:40,967 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-12-21 07:19:40,967 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-12-21 07:19:41,009 INFO L241 CfgBuilder]: Building ICFG [2023-12-21 07:19:41,010 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-12-21 07:19:41,169 INFO L282 CfgBuilder]: Performing block encoding [2023-12-21 07:19:41,182 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-12-21 07:19:41,182 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-12-21 07:19:41,182 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 07:19:41 BoogieIcfgContainer [2023-12-21 07:19:41,182 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-12-21 07:19:41,184 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-12-21 07:19:41,184 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-12-21 07:19:41,186 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-12-21 07:19:41,186 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.12 07:19:40" (1/3) ... [2023-12-21 07:19:41,186 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5aa223c7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 07:19:41, skipping insertion in model container [2023-12-21 07:19:41,186 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 07:19:40" (2/3) ... [2023-12-21 07:19:41,186 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5aa223c7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 07:19:41, skipping insertion in model container [2023-12-21 07:19:41,186 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 07:19:41" (3/3) ... [2023-12-21 07:19:41,188 INFO L112 eAbstractionObserver]: Analyzing ICFG hard-u_unwindbound50.c [2023-12-21 07:19:41,199 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-12-21 07:19:41,199 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-12-21 07:19:41,253 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-12-21 07:19:41,258 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@36e271a6, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-12-21 07:19:41,258 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-12-21 07:19:41,262 INFO L276 IsEmpty]: Start isEmpty. Operand has 25 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 16 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-12-21 07:19:41,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-21 07:19:41,267 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:41,268 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:41,268 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:41,274 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:41,274 INFO L85 PathProgramCache]: Analyzing trace with hash 65649153, now seen corresponding path program 1 times [2023-12-21 07:19:41,280 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:41,280 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [51418090] [2023-12-21 07:19:41,280 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:41,281 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:41,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:41,359 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:41,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [51418090] [2023-12-21 07:19:41,360 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-21 07:19:41,360 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2015041637] [2023-12-21 07:19:41,360 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:41,360 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:41,360 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:41,363 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:41,364 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-12-21 07:19:41,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:41,433 INFO L262 TraceCheckSpWp]: Trace formula consists of 47 conjuncts, 1 conjunts are in the unsatisfiable core [2023-12-21 07:19:41,435 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:41,447 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 07:19:41,447 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:19:41,448 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2015041637] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:41,448 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:41,455 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-12-21 07:19:41,457 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2113004878] [2023-12-21 07:19:41,458 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:41,484 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-12-21 07:19:41,485 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:41,528 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-12-21 07:19:41,529 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-21 07:19:41,531 INFO L87 Difference]: Start difference. First operand has 25 states, 15 states have (on average 1.6666666666666667) internal successors, (25), 16 states have internal predecessors, (25), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:41,562 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:41,562 INFO L93 Difference]: Finished difference Result 48 states and 82 transitions. [2023-12-21 07:19:41,563 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-12-21 07:19:41,564 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-12-21 07:19:41,564 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:41,568 INFO L225 Difference]: With dead ends: 48 [2023-12-21 07:19:41,568 INFO L226 Difference]: Without dead ends: 23 [2023-12-21 07:19:41,571 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-12-21 07:19:41,574 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 2 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 33 SdHoareTripleChecker+Invalid, 2 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 2 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:41,575 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 33 Invalid, 2 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 2 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:19:41,585 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2023-12-21 07:19:41,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2023-12-21 07:19:41,596 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 7 states have call successors, (7), 1 states have call predecessors, (7), 1 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-21 07:19:41,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 33 transitions. [2023-12-21 07:19:41,597 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 33 transitions. Word has length 9 [2023-12-21 07:19:41,597 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:41,597 INFO L495 AbstractCegarLoop]: Abstraction has 23 states and 33 transitions. [2023-12-21 07:19:41,597 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:41,598 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 33 transitions. [2023-12-21 07:19:41,598 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2023-12-21 07:19:41,598 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:41,598 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:41,605 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2023-12-21 07:19:41,803 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-12-21 07:19:41,803 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:41,804 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:41,804 INFO L85 PathProgramCache]: Analyzing trace with hash -1205755883, now seen corresponding path program 1 times [2023-12-21 07:19:41,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:41,804 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [126523378] [2023-12-21 07:19:41,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:41,805 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:41,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:41,956 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 07:19:41,956 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:41,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [126523378] [2023-12-21 07:19:41,956 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [126523378] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:41,956 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:41,956 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-21 07:19:41,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1406990426] [2023-12-21 07:19:41,957 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:41,957 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 07:19:41,957 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:41,958 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 07:19:41,958 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:19:41,958 INFO L87 Difference]: Start difference. First operand 23 states and 33 transitions. Second operand has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:42,014 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:42,015 INFO L93 Difference]: Finished difference Result 37 states and 52 transitions. [2023-12-21 07:19:42,016 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-21 07:19:42,016 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2023-12-21 07:19:42,016 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:42,017 INFO L225 Difference]: With dead ends: 37 [2023-12-21 07:19:42,017 INFO L226 Difference]: Without dead ends: 35 [2023-12-21 07:19:42,017 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:19:42,018 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 15 mSDsluCounter, 68 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:42,018 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [21 Valid, 96 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:19:42,020 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2023-12-21 07:19:42,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 27. [2023-12-21 07:19:42,025 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-21 07:19:42,025 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 36 transitions. [2023-12-21 07:19:42,026 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 36 transitions. Word has length 9 [2023-12-21 07:19:42,026 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:42,026 INFO L495 AbstractCegarLoop]: Abstraction has 27 states and 36 transitions. [2023-12-21 07:19:42,026 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.6) internal successors, (8), 4 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:42,026 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 36 transitions. [2023-12-21 07:19:42,026 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2023-12-21 07:19:42,026 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:42,027 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:42,027 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-12-21 07:19:42,027 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:42,027 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:42,027 INFO L85 PathProgramCache]: Analyzing trace with hash -2004332404, now seen corresponding path program 1 times [2023-12-21 07:19:42,027 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:42,027 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [415165880] [2023-12-21 07:19:42,028 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:42,028 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:42,047 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:42,073 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:42,073 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [415165880] [2023-12-21 07:19:42,073 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-12-21 07:19:42,073 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [375320707] [2023-12-21 07:19:42,074 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:42,074 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:42,074 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:42,086 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:42,096 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-12-21 07:19:42,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:42,124 INFO L262 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 3 conjunts are in the unsatisfiable core [2023-12-21 07:19:42,125 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:42,150 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 07:19:42,151 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:19:42,151 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [375320707] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:42,151 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:42,151 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-12-21 07:19:42,151 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [437579121] [2023-12-21 07:19:42,151 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:42,151 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-12-21 07:19:42,152 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:42,152 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-12-21 07:19:42,152 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-21 07:19:42,152 INFO L87 Difference]: Start difference. First operand 27 states and 36 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:42,163 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:42,163 INFO L93 Difference]: Finished difference Result 43 states and 58 transitions. [2023-12-21 07:19:42,163 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-12-21 07:19:42,164 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2023-12-21 07:19:42,164 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:42,164 INFO L225 Difference]: With dead ends: 43 [2023-12-21 07:19:42,164 INFO L226 Difference]: Without dead ends: 29 [2023-12-21 07:19:42,164 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-12-21 07:19:42,165 INFO L413 NwaCegarLoop]: 30 mSDtfsCounter, 0 mSDsluCounter, 56 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:42,166 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 86 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:19:42,166 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2023-12-21 07:19:42,169 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2023-12-21 07:19:42,169 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 7 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-21 07:19:42,170 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 38 transitions. [2023-12-21 07:19:42,170 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 38 transitions. Word has length 11 [2023-12-21 07:19:42,170 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:42,170 INFO L495 AbstractCegarLoop]: Abstraction has 29 states and 38 transitions. [2023-12-21 07:19:42,170 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2023-12-21 07:19:42,170 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 38 transitions. [2023-12-21 07:19:42,171 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2023-12-21 07:19:42,171 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:42,171 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:42,180 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2023-12-21 07:19:42,375 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2023-12-21 07:19:42,375 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:42,376 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:42,376 INFO L85 PathProgramCache]: Analyzing trace with hash 1962237034, now seen corresponding path program 1 times [2023-12-21 07:19:42,376 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:42,376 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1559525848] [2023-12-21 07:19:42,376 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:42,376 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:42,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:42,654 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 5 [2023-12-21 07:19:42,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:42,661 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-12-21 07:19:42,662 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:42,662 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1559525848] [2023-12-21 07:19:42,662 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1559525848] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:19:42,663 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:19:42,663 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-12-21 07:19:42,663 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1952544989] [2023-12-21 07:19:42,664 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:19:42,665 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 07:19:42,665 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:42,667 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 07:19:42,667 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:19:42,667 INFO L87 Difference]: Start difference. First operand 29 states and 38 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-21 07:19:42,746 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:19:42,746 INFO L93 Difference]: Finished difference Result 43 states and 57 transitions. [2023-12-21 07:19:42,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-21 07:19:42,746 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2023-12-21 07:19:42,746 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:19:42,747 INFO L225 Difference]: With dead ends: 43 [2023-12-21 07:19:42,747 INFO L226 Difference]: Without dead ends: 41 [2023-12-21 07:19:42,747 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:19:42,748 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 13 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:19:42,748 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [18 Valid, 92 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:19:42,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2023-12-21 07:19:42,752 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 33. [2023-12-21 07:19:42,753 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 23 states have internal predecessors, (28), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2023-12-21 07:19:42,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 41 transitions. [2023-12-21 07:19:42,753 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 41 transitions. Word has length 14 [2023-12-21 07:19:42,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:19:42,754 INFO L495 AbstractCegarLoop]: Abstraction has 33 states and 41 transitions. [2023-12-21 07:19:42,754 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2023-12-21 07:19:42,754 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 41 transitions. [2023-12-21 07:19:42,754 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-12-21 07:19:42,754 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:19:42,754 INFO L195 NwaCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:19:42,754 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2023-12-21 07:19:42,754 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:19:42,755 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:19:42,755 INFO L85 PathProgramCache]: Analyzing trace with hash 608183541, now seen corresponding path program 1 times [2023-12-21 07:19:42,755 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:19:42,755 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [757505752] [2023-12-21 07:19:42,755 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:42,755 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:19:42,761 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:19:42,761 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [965477297] [2023-12-21 07:19:42,762 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:19:42,762 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:19:42,762 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:19:42,785 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:19:42,785 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-12-21 07:19:42,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:19:42,815 INFO L262 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 17 conjunts are in the unsatisfiable core [2023-12-21 07:19:42,817 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:19:42,961 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-21 07:19:42,962 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:19:43,131 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-12-21 07:19:43,131 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:19:43,131 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [757505752] [2023-12-21 07:19:43,131 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:19:43,131 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [965477297] [2023-12-21 07:19:43,132 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [965477297] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:19:43,132 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:19:43,132 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 12 [2023-12-21 07:19:43,132 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [773390610] [2023-12-21 07:19:43,132 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:19:43,133 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-12-21 07:19:43,133 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:19:43,134 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-12-21 07:19:43,134 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=100, Unknown=0, NotChecked=0, Total=132 [2023-12-21 07:19:43,135 INFO L87 Difference]: Start difference. First operand 33 states and 41 transitions. Second operand has 12 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-21 07:19:47,635 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:19:51,642 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:19:55,982 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:19:59,987 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:00,086 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:20:00,086 INFO L93 Difference]: Finished difference Result 77 states and 106 transitions. [2023-12-21 07:20:00,086 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-21 07:20:00,087 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) Word has length 19 [2023-12-21 07:20:00,087 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:20:00,088 INFO L225 Difference]: With dead ends: 77 [2023-12-21 07:20:00,089 INFO L226 Difference]: Without dead ends: 62 [2023-12-21 07:20:00,090 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2023-12-21 07:20:00,090 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 39 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 150 mSolverCounterSat, 25 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 131 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 150 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 16.9s IncrementalHoareTripleChecker+Time [2023-12-21 07:20:00,091 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 131 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 150 Invalid, 4 Unknown, 0 Unchecked, 16.9s Time] [2023-12-21 07:20:00,091 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2023-12-21 07:20:00,098 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 60. [2023-12-21 07:20:00,099 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 36 states have (on average 1.2777777777777777) internal successors, (46), 40 states have internal predecessors, (46), 18 states have call successors, (18), 5 states have call predecessors, (18), 5 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2023-12-21 07:20:00,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 80 transitions. [2023-12-21 07:20:00,108 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 80 transitions. Word has length 19 [2023-12-21 07:20:00,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:20:00,108 INFO L495 AbstractCegarLoop]: Abstraction has 60 states and 80 transitions. [2023-12-21 07:20:00,108 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 2.1) internal successors, (21), 9 states have internal predecessors, (21), 4 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2023-12-21 07:20:00,108 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 80 transitions. [2023-12-21 07:20:00,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-21 07:20:00,109 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:20:00,110 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:20:00,129 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-12-21 07:20:00,315 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:00,315 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:20:00,316 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:20:00,316 INFO L85 PathProgramCache]: Analyzing trace with hash 560729168, now seen corresponding path program 1 times [2023-12-21 07:20:00,317 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:20:00,317 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1051150800] [2023-12-21 07:20:00,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:00,317 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:20:00,325 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:20:00,326 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [851877812] [2023-12-21 07:20:00,326 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:00,326 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:00,326 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:20:00,337 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:20:00,388 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-12-21 07:20:00,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:20:00,421 INFO L262 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-21 07:20:00,423 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:20:00,482 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:20:00,482 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:20:00,482 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:20:00,482 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1051150800] [2023-12-21 07:20:00,482 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:20:00,483 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [851877812] [2023-12-21 07:20:00,483 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [851877812] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:20:00,483 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:20:00,483 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-12-21 07:20:00,483 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1368776256] [2023-12-21 07:20:00,483 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:20:00,483 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-12-21 07:20:00,483 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:20:00,484 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-12-21 07:20:00,484 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:20:00,484 INFO L87 Difference]: Start difference. First operand 60 states and 80 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:20:00,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:20:00,516 INFO L93 Difference]: Finished difference Result 75 states and 92 transitions. [2023-12-21 07:20:00,517 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-12-21 07:20:00,517 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 27 [2023-12-21 07:20:00,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:20:00,517 INFO L225 Difference]: With dead ends: 75 [2023-12-21 07:20:00,517 INFO L226 Difference]: Without dead ends: 68 [2023-12-21 07:20:00,518 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-12-21 07:20:00,518 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 1 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:20:00,518 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 105 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:20:00,519 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 68 states. [2023-12-21 07:20:00,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 68 to 68. [2023-12-21 07:20:00,526 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 42 states have (on average 1.2142857142857142) internal successors, (51), 46 states have internal predecessors, (51), 18 states have call successors, (18), 7 states have call predecessors, (18), 7 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2023-12-21 07:20:00,527 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 85 transitions. [2023-12-21 07:20:00,527 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 85 transitions. Word has length 27 [2023-12-21 07:20:00,527 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:20:00,527 INFO L495 AbstractCegarLoop]: Abstraction has 68 states and 85 transitions. [2023-12-21 07:20:00,528 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:20:00,528 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 85 transitions. [2023-12-21 07:20:00,528 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2023-12-21 07:20:00,528 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:20:00,528 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:20:00,552 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-12-21 07:20:00,739 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:00,740 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:20:00,740 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:20:00,740 INFO L85 PathProgramCache]: Analyzing trace with hash 562457046, now seen corresponding path program 1 times [2023-12-21 07:20:00,740 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:20:00,740 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1767754741] [2023-12-21 07:20:00,741 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:00,741 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:20:00,765 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:20:00,765 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1077366791] [2023-12-21 07:20:00,766 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:00,766 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:00,766 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:20:00,767 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:20:00,799 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-12-21 07:20:00,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:20:00,820 INFO L262 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 18 conjunts are in the unsatisfiable core [2023-12-21 07:20:00,823 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:20:00,997 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:20:00,998 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:20:00,998 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:20:00,998 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1767754741] [2023-12-21 07:20:00,999 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:20:00,999 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1077366791] [2023-12-21 07:20:00,999 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1077366791] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:20:00,999 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:20:00,999 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2023-12-21 07:20:00,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1539831278] [2023-12-21 07:20:01,000 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:20:01,000 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-21 07:20:01,000 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:20:01,002 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-21 07:20:01,002 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2023-12-21 07:20:01,002 INFO L87 Difference]: Start difference. First operand 68 states and 85 transitions. Second operand has 8 states, 8 states have (on average 1.75) internal successors, (14), 7 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:20:01,324 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:20:01,325 INFO L93 Difference]: Finished difference Result 74 states and 90 transitions. [2023-12-21 07:20:01,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-12-21 07:20:01,325 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 1.75) internal successors, (14), 7 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 27 [2023-12-21 07:20:01,325 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:20:01,326 INFO L225 Difference]: With dead ends: 74 [2023-12-21 07:20:01,326 INFO L226 Difference]: Without dead ends: 62 [2023-12-21 07:20:01,326 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2023-12-21 07:20:01,327 INFO L413 NwaCegarLoop]: 24 mSDtfsCounter, 25 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 75 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 75 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-12-21 07:20:01,327 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [31 Valid, 111 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 75 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-12-21 07:20:01,327 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2023-12-21 07:20:01,335 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 62. [2023-12-21 07:20:01,335 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 39 states have (on average 1.205128205128205) internal successors, (47), 42 states have internal predecessors, (47), 15 states have call successors, (15), 7 states have call predecessors, (15), 7 states have return successors, (14), 12 states have call predecessors, (14), 14 states have call successors, (14) [2023-12-21 07:20:01,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 76 transitions. [2023-12-21 07:20:01,336 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 76 transitions. Word has length 27 [2023-12-21 07:20:01,336 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:20:01,336 INFO L495 AbstractCegarLoop]: Abstraction has 62 states and 76 transitions. [2023-12-21 07:20:01,336 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 1.75) internal successors, (14), 7 states have internal predecessors, (14), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-12-21 07:20:01,336 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 76 transitions. [2023-12-21 07:20:01,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2023-12-21 07:20:01,337 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:20:01,337 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:20:01,346 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-12-21 07:20:01,541 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:01,542 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:20:01,542 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:20:01,542 INFO L85 PathProgramCache]: Analyzing trace with hash 177821141, now seen corresponding path program 1 times [2023-12-21 07:20:01,543 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:20:01,543 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1051639651] [2023-12-21 07:20:01,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:01,543 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:20:01,548 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:20:01,549 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1057977809] [2023-12-21 07:20:01,549 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:01,549 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:01,549 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:20:01,550 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:20:01,557 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-12-21 07:20:01,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:20:01,579 INFO L262 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 5 conjunts are in the unsatisfiable core [2023-12-21 07:20:01,580 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:20:01,609 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:20:01,609 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:20:01,640 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2023-12-21 07:20:01,640 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:20:01,640 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1051639651] [2023-12-21 07:20:01,640 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:20:01,640 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1057977809] [2023-12-21 07:20:01,640 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1057977809] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:20:01,640 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:20:01,643 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 5] total 8 [2023-12-21 07:20:01,643 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1061738722] [2023-12-21 07:20:01,643 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:20:01,643 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-21 07:20:01,644 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:20:01,644 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-21 07:20:01,644 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2023-12-21 07:20:01,644 INFO L87 Difference]: Start difference. First operand 62 states and 76 transitions. Second operand has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-21 07:20:01,720 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:20:01,720 INFO L93 Difference]: Finished difference Result 133 states and 160 transitions. [2023-12-21 07:20:01,721 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-12-21 07:20:01,721 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 29 [2023-12-21 07:20:01,722 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:20:01,725 INFO L225 Difference]: With dead ends: 133 [2023-12-21 07:20:01,725 INFO L226 Difference]: Without dead ends: 111 [2023-12-21 07:20:01,727 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2023-12-21 07:20:01,728 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 34 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:20:01,728 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 144 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-12-21 07:20:01,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 111 states. [2023-12-21 07:20:01,745 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 111 to 106. [2023-12-21 07:20:01,745 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 69 states have (on average 1.173913043478261) internal successors, (81), 72 states have internal predecessors, (81), 22 states have call successors, (22), 14 states have call predecessors, (22), 14 states have return successors, (20), 19 states have call predecessors, (20), 20 states have call successors, (20) [2023-12-21 07:20:01,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 123 transitions. [2023-12-21 07:20:01,746 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 123 transitions. Word has length 29 [2023-12-21 07:20:01,746 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:20:01,746 INFO L495 AbstractCegarLoop]: Abstraction has 106 states and 123 transitions. [2023-12-21 07:20:01,746 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.375) internal successors, (27), 8 states have internal predecessors, (27), 3 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-12-21 07:20:01,746 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 123 transitions. [2023-12-21 07:20:01,747 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-12-21 07:20:01,747 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:20:01,747 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:20:01,772 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-12-21 07:20:01,954 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:01,954 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:20:01,954 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:20:01,954 INFO L85 PathProgramCache]: Analyzing trace with hash -1287430247, now seen corresponding path program 1 times [2023-12-21 07:20:01,954 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:20:01,955 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1906361308] [2023-12-21 07:20:01,955 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:01,955 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:20:01,960 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:20:01,960 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1141857892] [2023-12-21 07:20:01,960 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:01,961 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:01,961 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:20:01,976 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:20:01,992 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-12-21 07:20:02,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:20:02,025 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 7 conjunts are in the unsatisfiable core [2023-12-21 07:20:02,029 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:20:02,078 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-12-21 07:20:02,079 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:20:02,130 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2023-12-21 07:20:02,130 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:20:02,130 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1906361308] [2023-12-21 07:20:02,130 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:20:02,130 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1141857892] [2023-12-21 07:20:02,130 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1141857892] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:20:02,130 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:20:02,130 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2023-12-21 07:20:02,130 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [677419899] [2023-12-21 07:20:02,131 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:20:02,132 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-12-21 07:20:02,132 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:20:02,133 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-12-21 07:20:02,133 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2023-12-21 07:20:02,133 INFO L87 Difference]: Start difference. First operand 106 states and 123 transitions. Second operand has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-21 07:20:02,253 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:20:02,253 INFO L93 Difference]: Finished difference Result 198 states and 237 transitions. [2023-12-21 07:20:02,254 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-12-21 07:20:02,254 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 45 [2023-12-21 07:20:02,254 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:20:02,256 INFO L225 Difference]: With dead ends: 198 [2023-12-21 07:20:02,256 INFO L226 Difference]: Without dead ends: 184 [2023-12-21 07:20:02,256 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2023-12-21 07:20:02,257 INFO L413 NwaCegarLoop]: 29 mSDtfsCounter, 82 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 174 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 07:20:02,258 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [82 Valid, 174 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 07:20:02,259 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2023-12-21 07:20:02,287 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 177. [2023-12-21 07:20:02,289 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 177 states, 114 states have (on average 1.1842105263157894) internal successors, (135), 121 states have internal predecessors, (135), 40 states have call successors, (40), 22 states have call predecessors, (40), 22 states have return successors, (36), 33 states have call predecessors, (36), 36 states have call successors, (36) [2023-12-21 07:20:02,294 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 177 states to 177 states and 211 transitions. [2023-12-21 07:20:02,294 INFO L78 Accepts]: Start accepts. Automaton has 177 states and 211 transitions. Word has length 45 [2023-12-21 07:20:02,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:20:02,294 INFO L495 AbstractCegarLoop]: Abstraction has 177 states and 211 transitions. [2023-12-21 07:20:02,294 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.4) internal successors, (34), 10 states have internal predecessors, (34), 5 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2023-12-21 07:20:02,294 INFO L276 IsEmpty]: Start isEmpty. Operand 177 states and 211 transitions. [2023-12-21 07:20:02,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-12-21 07:20:02,296 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:20:02,296 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:20:02,328 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2023-12-21 07:20:02,513 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:02,513 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:20:02,514 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:20:02,514 INFO L85 PathProgramCache]: Analyzing trace with hash -1285702369, now seen corresponding path program 1 times [2023-12-21 07:20:02,514 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:20:02,514 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [776829464] [2023-12-21 07:20:02,514 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:02,514 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:20:02,522 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:20:02,522 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [309818934] [2023-12-21 07:20:02,522 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:02,522 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:02,522 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:20:02,536 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:20:02,539 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-12-21 07:20:02,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:20:02,589 INFO L262 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 15 conjunts are in the unsatisfiable core [2023-12-21 07:20:02,591 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:20:02,682 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 14 proven. 13 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2023-12-21 07:20:02,682 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:20:02,730 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:20:02,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [776829464] [2023-12-21 07:20:02,730 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:20:02,730 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [309818934] [2023-12-21 07:20:02,730 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [309818934] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-21 07:20:02,730 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-21 07:20:02,730 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2023-12-21 07:20:02,730 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2131345220] [2023-12-21 07:20:02,730 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-21 07:20:02,730 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-12-21 07:20:02,730 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:20:02,731 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-12-21 07:20:02,731 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2023-12-21 07:20:02,731 INFO L87 Difference]: Start difference. First operand 177 states and 211 transitions. Second operand has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-21 07:20:02,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:20:02,941 INFO L93 Difference]: Finished difference Result 221 states and 270 transitions. [2023-12-21 07:20:02,941 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-12-21 07:20:02,941 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 45 [2023-12-21 07:20:02,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:20:02,942 INFO L225 Difference]: With dead ends: 221 [2023-12-21 07:20:02,942 INFO L226 Difference]: Without dead ends: 219 [2023-12-21 07:20:02,943 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2023-12-21 07:20:02,943 INFO L413 NwaCegarLoop]: 20 mSDtfsCounter, 16 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 92 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 92 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-12-21 07:20:02,943 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 91 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 92 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-12-21 07:20:02,944 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 219 states. [2023-12-21 07:20:02,955 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 219 to 216. [2023-12-21 07:20:02,955 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 216 states, 140 states have (on average 1.2) internal successors, (168), 150 states have internal predecessors, (168), 49 states have call successors, (49), 26 states have call predecessors, (49), 26 states have return successors, (45), 39 states have call predecessors, (45), 45 states have call successors, (45) [2023-12-21 07:20:02,956 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 216 states to 216 states and 262 transitions. [2023-12-21 07:20:02,956 INFO L78 Accepts]: Start accepts. Automaton has 216 states and 262 transitions. Word has length 45 [2023-12-21 07:20:02,956 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:20:02,956 INFO L495 AbstractCegarLoop]: Abstraction has 216 states and 262 transitions. [2023-12-21 07:20:02,956 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2023-12-21 07:20:02,956 INFO L276 IsEmpty]: Start isEmpty. Operand 216 states and 262 transitions. [2023-12-21 07:20:02,957 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2023-12-21 07:20:02,957 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:20:02,957 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1] [2023-12-21 07:20:02,963 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-12-21 07:20:03,163 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-12-21 07:20:03,163 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:20:03,163 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:20:03,164 INFO L85 PathProgramCache]: Analyzing trace with hash -1354605241, now seen corresponding path program 1 times [2023-12-21 07:20:03,164 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:20:03,164 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1752832824] [2023-12-21 07:20:03,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:03,164 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:20:03,168 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:20:03,168 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1763195185] [2023-12-21 07:20:03,169 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:03,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:03,169 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:20:03,171 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:20:03,171 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-12-21 07:20:03,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:20:03,303 INFO L262 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 30 conjunts are in the unsatisfiable core [2023-12-21 07:20:03,305 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:20:03,417 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 29 proven. 39 refuted. 0 times theorem prover too weak. 76 trivial. 0 not checked. [2023-12-21 07:20:03,417 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:20:03,780 INFO L134 CoverageAnalysis]: Checked inductivity of 144 backedges. 41 proven. 7 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2023-12-21 07:20:03,780 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:20:03,780 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1752832824] [2023-12-21 07:20:03,780 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:20:03,780 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1763195185] [2023-12-21 07:20:03,781 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1763195185] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:20:03,781 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:20:03,781 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 7] total 14 [2023-12-21 07:20:03,781 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1764402213] [2023-12-21 07:20:03,781 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:20:03,782 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-12-21 07:20:03,782 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:20:03,782 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-12-21 07:20:03,782 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2023-12-21 07:20:03,782 INFO L87 Difference]: Start difference. First operand 216 states and 262 transitions. Second operand has 14 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 11 states have internal predecessors, (31), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 7 states have call predecessors, (14), 6 states have call successors, (14) [2023-12-21 07:20:10,672 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:11,821 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:20:11,821 INFO L93 Difference]: Finished difference Result 267 states and 322 transitions. [2023-12-21 07:20:11,822 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-12-21 07:20:11,822 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 11 states have internal predecessors, (31), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 7 states have call predecessors, (14), 6 states have call successors, (14) Word has length 55 [2023-12-21 07:20:11,822 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:20:11,823 INFO L225 Difference]: With dead ends: 267 [2023-12-21 07:20:11,823 INFO L226 Difference]: Without dead ends: 245 [2023-12-21 07:20:11,824 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 96 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=55, Invalid=185, Unknown=0, NotChecked=0, Total=240 [2023-12-21 07:20:11,824 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 32 mSDsluCounter, 193 mSDsCounter, 0 mSdLazyCounter, 283 mSolverCounterSat, 16 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 8.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 227 SdHoareTripleChecker+Invalid, 300 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 283 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.0s IncrementalHoareTripleChecker+Time [2023-12-21 07:20:11,824 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 227 Invalid, 300 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 283 Invalid, 1 Unknown, 0 Unchecked, 8.0s Time] [2023-12-21 07:20:11,824 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 245 states. [2023-12-21 07:20:11,862 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 245 to 233. [2023-12-21 07:20:11,862 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 233 states, 154 states have (on average 1.1753246753246753) internal successors, (181), 163 states have internal predecessors, (181), 49 states have call successors, (49), 29 states have call predecessors, (49), 29 states have return successors, (46), 40 states have call predecessors, (46), 46 states have call successors, (46) [2023-12-21 07:20:11,864 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 233 states to 233 states and 276 transitions. [2023-12-21 07:20:11,864 INFO L78 Accepts]: Start accepts. Automaton has 233 states and 276 transitions. Word has length 55 [2023-12-21 07:20:11,864 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:20:11,864 INFO L495 AbstractCegarLoop]: Abstraction has 233 states and 276 transitions. [2023-12-21 07:20:11,864 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.2142857142857144) internal successors, (31), 11 states have internal predecessors, (31), 6 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (14), 7 states have call predecessors, (14), 6 states have call successors, (14) [2023-12-21 07:20:11,864 INFO L276 IsEmpty]: Start isEmpty. Operand 233 states and 276 transitions. [2023-12-21 07:20:11,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2023-12-21 07:20:11,866 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:20:11,866 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:20:11,884 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-12-21 07:20:12,070 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:12,071 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:20:12,071 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:20:12,071 INFO L85 PathProgramCache]: Analyzing trace with hash -293585845, now seen corresponding path program 1 times [2023-12-21 07:20:12,071 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:20:12,071 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [33924739] [2023-12-21 07:20:12,071 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:12,071 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:20:12,078 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:20:12,078 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1981032052] [2023-12-21 07:20:12,078 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:20:12,078 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:20:12,078 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:20:12,099 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:20:12,101 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-12-21 07:20:15,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:20:15,581 INFO L262 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 40 conjunts are in the unsatisfiable core [2023-12-21 07:20:15,582 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:20:16,157 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-21 07:20:16,157 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:20:39,416 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 18 proven. 28 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2023-12-21 07:20:39,416 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:20:39,416 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [33924739] [2023-12-21 07:20:39,416 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:20:39,416 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1981032052] [2023-12-21 07:20:39,416 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1981032052] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:20:39,416 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:20:39,416 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 21 [2023-12-21 07:20:39,416 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [875416023] [2023-12-21 07:20:39,416 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:20:39,417 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-12-21 07:20:39,417 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:20:39,417 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-12-21 07:20:39,417 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=343, Unknown=1, NotChecked=0, Total=420 [2023-12-21 07:20:39,418 INFO L87 Difference]: Start difference. First operand 233 states and 276 transitions. Second operand has 21 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 19 states have internal predecessors, (43), 9 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2023-12-21 07:20:43,425 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:48,165 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:20:49,986 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.36s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:01,406 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:06,863 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:10,888 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:26,538 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.16s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:30,619 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:32,073 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.45s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:36,456 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:21:42,335 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:25,364 WARN L293 SmtUtils]: Spent 38.88s on a formula simplification. DAG size of input: 55 DAG size of output: 54 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:22:47,622 WARN L293 SmtUtils]: Spent 17.42s on a formula simplification that was a NOOP. DAG size: 51 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:22:51,626 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:55,640 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:22:58,469 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.83s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:02,474 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:09,795 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:13,901 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:15,105 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.15s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:26,016 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:27,814 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.80s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:31,823 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:35,832 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:40,262 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:23:44,442 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:03,490 WARN L293 SmtUtils]: Spent 11.83s on a formula simplification. DAG size of input: 43 DAG size of output: 42 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:24:07,656 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:11,664 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:32,185 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:34,032 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.85s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:38,035 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:24:42,040 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:07,953 WARN L293 SmtUtils]: Spent 9.05s on a formula simplification that was a NOOP. DAG size: 39 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:25:12,426 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.21s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:17,340 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:21,497 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:25,504 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:29,613 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:33,637 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:36,054 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.41s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:40,176 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:44,718 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:25:48,728 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:15,556 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.58s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:19,561 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:24,038 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:27,173 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.23s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:31,177 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:35,941 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:39,945 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:43,949 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:49,156 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:53,167 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.64s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:58,036 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:26:58,320 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:26:58,321 INFO L93 Difference]: Finished difference Result 354 states and 437 transitions. [2023-12-21 07:26:58,321 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2023-12-21 07:26:58,322 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 19 states have internal predecessors, (43), 9 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) Word has length 59 [2023-12-21 07:26:58,322 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:26:58,323 INFO L225 Difference]: With dead ends: 354 [2023-12-21 07:26:58,323 INFO L226 Difference]: Without dead ends: 286 [2023-12-21 07:26:58,324 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 99 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 196 ImplicationChecksByTransitivity, 195.0s TimeCoverageRelationStatistics Valid=216, Invalid=889, Unknown=17, NotChecked=0, Total=1122 [2023-12-21 07:26:58,324 INFO L413 NwaCegarLoop]: 27 mSDtfsCounter, 108 mSDsluCounter, 304 mSDsCounter, 0 mSdLazyCounter, 441 mSolverCounterSat, 93 mSolverCounterUnsat, 40 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 201.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 110 SdHoareTripleChecker+Valid, 331 SdHoareTripleChecker+Invalid, 574 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 93 IncrementalHoareTripleChecker+Valid, 441 IncrementalHoareTripleChecker+Invalid, 40 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 201.6s IncrementalHoareTripleChecker+Time [2023-12-21 07:26:58,324 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [110 Valid, 331 Invalid, 574 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [93 Valid, 441 Invalid, 40 Unknown, 0 Unchecked, 201.6s Time] [2023-12-21 07:26:58,325 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2023-12-21 07:26:58,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 252. [2023-12-21 07:26:58,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 252 states, 170 states have (on average 1.1529411764705881) internal successors, (196), 179 states have internal predecessors, (196), 47 states have call successors, (47), 34 states have call predecessors, (47), 34 states have return successors, (44), 38 states have call predecessors, (44), 44 states have call successors, (44) [2023-12-21 07:26:58,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 252 states to 252 states and 287 transitions. [2023-12-21 07:26:58,365 INFO L78 Accepts]: Start accepts. Automaton has 252 states and 287 transitions. Word has length 59 [2023-12-21 07:26:58,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:26:58,365 INFO L495 AbstractCegarLoop]: Abstraction has 252 states and 287 transitions. [2023-12-21 07:26:58,365 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 19 states have internal predecessors, (43), 9 states have call successors, (18), 3 states have call predecessors, (18), 2 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2023-12-21 07:26:58,366 INFO L276 IsEmpty]: Start isEmpty. Operand 252 states and 287 transitions. [2023-12-21 07:26:58,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2023-12-21 07:26:58,368 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:26:58,368 INFO L195 NwaCegarLoop]: trace histogram [10, 9, 9, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:26:58,379 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2023-12-21 07:26:58,575 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-12-21 07:26:58,575 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:26:58,575 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:26:58,575 INFO L85 PathProgramCache]: Analyzing trace with hash 433404212, now seen corresponding path program 2 times [2023-12-21 07:26:58,575 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:26:58,576 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [311991666] [2023-12-21 07:26:58,576 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:26:58,576 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:26:58,583 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:26:58,583 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1535380493] [2023-12-21 07:26:58,583 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 07:26:58,583 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:26:58,584 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:26:58,600 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:26:58,604 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-12-21 07:26:58,895 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 07:26:58,895 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 07:26:58,896 INFO L262 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 34 conjunts are in the unsatisfiable core [2023-12-21 07:26:58,898 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:26:59,275 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 20 proven. 32 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2023-12-21 07:26:59,275 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:27:21,506 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 20 proven. 32 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2023-12-21 07:27:21,506 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:27:21,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [311991666] [2023-12-21 07:27:21,506 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:27:21,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1535380493] [2023-12-21 07:27:21,506 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1535380493] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:27:21,506 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:27:21,506 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 22 [2023-12-21 07:27:21,506 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [344369730] [2023-12-21 07:27:21,506 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:27:21,507 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-12-21 07:27:21,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:27:21,508 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-12-21 07:27:21,508 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=366, Unknown=3, NotChecked=0, Total=462 [2023-12-21 07:27:21,508 INFO L87 Difference]: Start difference. First operand 252 states and 287 transitions. Second operand has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 10 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) [2023-12-21 07:27:25,516 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2023-12-21 07:27:29,521 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2023-12-21 07:27:33,573 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2023-12-21 07:27:39,356 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:27:41,329 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.39s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:27:45,334 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:28:12,742 WARN L293 SmtUtils]: Spent 26.49s on a formula simplification that was a NOOP. DAG size: 41 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:28:16,924 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:28:48,943 WARN L293 SmtUtils]: Spent 31.25s on a formula simplification that was a NOOP. DAG size: 37 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:29:39,214 WARN L293 SmtUtils]: Spent 47.05s on a formula simplification that was a NOOP. DAG size: 36 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:29:43,217 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:47,225 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:51,231 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:55,239 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:29:59,809 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.68s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:03,961 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:05,373 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.41s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:09,377 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:11,220 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.03s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:16,180 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:26,941 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:29,243 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.30s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:30:58,362 WARN L293 SmtUtils]: Spent 25.91s on a formula simplification that was a NOOP. DAG size: 27 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:31:02,366 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:06,725 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:10,732 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:13,961 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 3.23s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:17,965 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:22,777 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:26,783 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:31:57,371 WARN L293 SmtUtils]: Spent 16.64s on a formula simplification that was a NOOP. DAG size: 26 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:32:01,521 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:32:05,529 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:32:51,502 WARN L293 SmtUtils]: Spent 16.49s on a formula simplification that was a NOOP. DAG size: 25 (called from [L 391] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-12-21 07:32:56,061 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:00,064 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:04,068 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:08,447 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:12,670 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:16,676 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:21,596 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:25,974 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:29,987 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:34,385 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:38,580 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:43,505 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:47,511 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:52,510 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-12-21 07:33:53,137 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:33:53,137 INFO L93 Difference]: Finished difference Result 326 states and 385 transitions. [2023-12-21 07:33:53,139 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2023-12-21 07:33:53,139 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 10 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) Word has length 64 [2023-12-21 07:33:53,139 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:33:53,140 INFO L225 Difference]: With dead ends: 326 [2023-12-21 07:33:53,140 INFO L226 Difference]: Without dead ends: 281 [2023-12-21 07:33:53,141 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 106 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 216 ImplicationChecksByTransitivity, 246.1s TimeCoverageRelationStatistics Valid=265, Invalid=911, Unknown=14, NotChecked=0, Total=1190 [2023-12-21 07:33:53,141 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 68 mSDsluCounter, 325 mSDsCounter, 0 mSdLazyCounter, 386 mSolverCounterSat, 65 mSolverCounterUnsat, 35 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 166.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 78 SdHoareTripleChecker+Valid, 353 SdHoareTripleChecker+Invalid, 486 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 65 IncrementalHoareTripleChecker+Valid, 386 IncrementalHoareTripleChecker+Invalid, 35 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 166.4s IncrementalHoareTripleChecker+Time [2023-12-21 07:33:53,142 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [78 Valid, 353 Invalid, 486 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [65 Valid, 386 Invalid, 35 Unknown, 0 Unchecked, 166.4s Time] [2023-12-21 07:33:53,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 281 states. [2023-12-21 07:33:53,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 281 to 266. [2023-12-21 07:33:53,197 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 266 states, 181 states have (on average 1.138121546961326) internal successors, (206), 189 states have internal predecessors, (206), 48 states have call successors, (48), 37 states have call predecessors, (48), 36 states have return successors, (45), 39 states have call predecessors, (45), 45 states have call successors, (45) [2023-12-21 07:33:53,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 266 states to 266 states and 299 transitions. [2023-12-21 07:33:53,198 INFO L78 Accepts]: Start accepts. Automaton has 266 states and 299 transitions. Word has length 64 [2023-12-21 07:33:53,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:33:53,199 INFO L495 AbstractCegarLoop]: Abstraction has 266 states and 299 transitions. [2023-12-21 07:33:53,199 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 1.9545454545454546) internal successors, (43), 19 states have internal predecessors, (43), 10 states have call successors, (20), 3 states have call predecessors, (20), 2 states have return successors, (18), 10 states have call predecessors, (18), 10 states have call successors, (18) [2023-12-21 07:33:53,199 INFO L276 IsEmpty]: Start isEmpty. Operand 266 states and 299 transitions. [2023-12-21 07:33:53,200 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2023-12-21 07:33:53,200 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:33:53,200 INFO L195 NwaCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:33:53,205 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-12-21 07:33:53,405 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-12-21 07:33:53,405 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:33:53,406 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:33:53,406 INFO L85 PathProgramCache]: Analyzing trace with hash 1181721499, now seen corresponding path program 1 times [2023-12-21 07:33:53,406 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:33:53,406 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [981158683] [2023-12-21 07:33:53,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:33:53,406 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:33:53,417 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:33:53,417 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1465615000] [2023-12-21 07:33:53,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:33:53,417 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:33:53,417 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:33:53,422 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:33:53,424 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-12-21 07:33:53,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:33:53,604 INFO L262 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 36 conjunts are in the unsatisfiable core [2023-12-21 07:33:53,606 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:33:53,875 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 22 proven. 36 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2023-12-21 07:33:53,875 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:33:58,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:33:58,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [981158683] [2023-12-21 07:33:58,563 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:33:58,563 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1465615000] [2023-12-21 07:33:58,563 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1465615000] provided 0 perfect and 1 imperfect interpolant sequences [2023-12-21 07:33:58,563 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-12-21 07:33:58,563 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2023-12-21 07:33:58,563 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1199260315] [2023-12-21 07:33:58,563 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-12-21 07:33:58,563 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-12-21 07:33:58,563 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:33:58,564 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-12-21 07:33:58,564 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=251, Unknown=1, NotChecked=0, Total=306 [2023-12-21 07:33:58,564 INFO L87 Difference]: Start difference. First operand 266 states and 299 transitions. Second operand has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-12-21 07:33:59,401 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:33:59,401 INFO L93 Difference]: Finished difference Result 268 states and 300 transitions. [2023-12-21 07:33:59,401 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2023-12-21 07:33:59,401 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) Word has length 70 [2023-12-21 07:33:59,402 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:33:59,403 INFO L225 Difference]: With dead ends: 268 [2023-12-21 07:33:59,403 INFO L226 Difference]: Without dead ends: 236 [2023-12-21 07:33:59,404 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=103, Invalid=496, Unknown=1, NotChecked=0, Total=600 [2023-12-21 07:33:59,404 INFO L413 NwaCegarLoop]: 25 mSDtfsCounter, 41 mSDsluCounter, 199 mSDsCounter, 0 mSdLazyCounter, 240 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 47 SdHoareTripleChecker+Valid, 224 SdHoareTripleChecker+Invalid, 260 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 240 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2023-12-21 07:33:59,405 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [47 Valid, 224 Invalid, 260 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 240 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2023-12-21 07:33:59,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 236 states. [2023-12-21 07:33:59,445 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 236 to 236. [2023-12-21 07:33:59,445 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 236 states, 160 states have (on average 1.15) internal successors, (184), 168 states have internal predecessors, (184), 43 states have call successors, (43), 32 states have call predecessors, (43), 32 states have return successors, (41), 35 states have call predecessors, (41), 41 states have call successors, (41) [2023-12-21 07:33:59,446 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 236 states to 236 states and 268 transitions. [2023-12-21 07:33:59,446 INFO L78 Accepts]: Start accepts. Automaton has 236 states and 268 transitions. Word has length 70 [2023-12-21 07:33:59,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:33:59,446 INFO L495 AbstractCegarLoop]: Abstraction has 236 states and 268 transitions. [2023-12-21 07:33:59,446 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 12 states have internal predecessors, (25), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 3 states have call predecessors, (10), 3 states have call successors, (10) [2023-12-21 07:33:59,446 INFO L276 IsEmpty]: Start isEmpty. Operand 236 states and 268 transitions. [2023-12-21 07:33:59,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2023-12-21 07:33:59,447 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:33:59,447 INFO L195 NwaCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:33:59,458 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-12-21 07:33:59,652 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2023-12-21 07:33:59,652 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:33:59,652 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:33:59,652 INFO L85 PathProgramCache]: Analyzing trace with hash 1259846217, now seen corresponding path program 1 times [2023-12-21 07:33:59,652 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:33:59,652 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [491902363] [2023-12-21 07:33:59,653 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:33:59,653 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:33:59,658 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:33:59,658 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [125750906] [2023-12-21 07:33:59,658 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:33:59,658 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:33:59,658 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:33:59,659 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:33:59,687 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-12-21 07:33:59,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-12-21 07:33:59,858 INFO L262 TraceCheckSpWp]: Trace formula consists of 195 conjuncts, 13 conjunts are in the unsatisfiable core [2023-12-21 07:33:59,860 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:34:00,120 INFO L134 CoverageAnalysis]: Checked inductivity of 310 backedges. 88 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2023-12-21 07:34:00,120 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-12-21 07:34:00,120 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:34:00,120 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [491902363] [2023-12-21 07:34:00,120 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:34:00,120 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [125750906] [2023-12-21 07:34:00,120 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [125750906] provided 1 perfect and 0 imperfect interpolant sequences [2023-12-21 07:34:00,120 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-12-21 07:34:00,120 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-12-21 07:34:00,121 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [463151753] [2023-12-21 07:34:00,121 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-12-21 07:34:00,121 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-12-21 07:34:00,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:34:00,121 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-12-21 07:34:00,121 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:34:00,121 INFO L87 Difference]: Start difference. First operand 236 states and 268 transitions. Second operand has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-12-21 07:34:00,550 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:34:00,550 INFO L93 Difference]: Finished difference Result 310 states and 367 transitions. [2023-12-21 07:34:00,551 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-12-21 07:34:00,551 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 82 [2023-12-21 07:34:00,551 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:34:00,552 INFO L225 Difference]: With dead ends: 310 [2023-12-21 07:34:00,552 INFO L226 Difference]: Without dead ends: 250 [2023-12-21 07:34:00,554 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 77 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2023-12-21 07:34:00,554 INFO L413 NwaCegarLoop]: 51 mSDtfsCounter, 15 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2023-12-21 07:34:00,555 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 135 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2023-12-21 07:34:00,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 250 states. [2023-12-21 07:34:00,591 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 250 to 230. [2023-12-21 07:34:00,592 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 230 states, 156 states have (on average 1.1346153846153846) internal successors, (177), 163 states have internal predecessors, (177), 41 states have call successors, (41), 32 states have call predecessors, (41), 32 states have return successors, (39), 34 states have call predecessors, (39), 39 states have call successors, (39) [2023-12-21 07:34:00,594 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 230 states to 230 states and 257 transitions. [2023-12-21 07:34:00,594 INFO L78 Accepts]: Start accepts. Automaton has 230 states and 257 transitions. Word has length 82 [2023-12-21 07:34:00,594 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:34:00,594 INFO L495 AbstractCegarLoop]: Abstraction has 230 states and 257 transitions. [2023-12-21 07:34:00,594 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.333333333333333) internal successors, (26), 6 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2023-12-21 07:34:00,595 INFO L276 IsEmpty]: Start isEmpty. Operand 230 states and 257 transitions. [2023-12-21 07:34:00,598 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2023-12-21 07:34:00,598 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:34:00,598 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:34:00,605 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-12-21 07:34:00,805 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-12-21 07:34:00,806 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:34:00,806 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:34:00,806 INFO L85 PathProgramCache]: Analyzing trace with hash -808682318, now seen corresponding path program 2 times [2023-12-21 07:34:00,806 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:34:00,806 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1707181432] [2023-12-21 07:34:00,806 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:34:00,806 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:34:00,815 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:34:00,815 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2062111252] [2023-12-21 07:34:00,815 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2023-12-21 07:34:00,816 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:34:00,816 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:34:00,816 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:34:00,819 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-12-21 07:34:00,871 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2023-12-21 07:34:00,871 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-12-21 07:34:00,872 INFO L262 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 10 conjunts are in the unsatisfiable core [2023-12-21 07:34:00,891 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-12-21 07:34:00,934 INFO L134 CoverageAnalysis]: Checked inductivity of 361 backedges. 26 proven. 23 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2023-12-21 07:34:00,934 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-12-21 07:34:01,035 INFO L134 CoverageAnalysis]: Checked inductivity of 361 backedges. 38 proven. 11 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2023-12-21 07:34:01,036 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-12-21 07:34:01,036 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1707181432] [2023-12-21 07:34:01,036 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-12-21 07:34:01,036 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2062111252] [2023-12-21 07:34:01,036 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2062111252] provided 0 perfect and 2 imperfect interpolant sequences [2023-12-21 07:34:01,036 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-12-21 07:34:01,036 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2023-12-21 07:34:01,036 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [709958648] [2023-12-21 07:34:01,036 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-12-21 07:34:01,037 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-12-21 07:34:01,037 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-12-21 07:34:01,037 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-12-21 07:34:01,037 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2023-12-21 07:34:01,038 INFO L87 Difference]: Start difference. First operand 230 states and 257 transitions. Second operand has 8 states, 8 states have (on average 5.25) internal successors, (42), 8 states have internal predecessors, (42), 8 states have call successors, (27), 2 states have call predecessors, (27), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) [2023-12-21 07:34:01,218 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-12-21 07:34:01,218 INFO L93 Difference]: Finished difference Result 282 states and 335 transitions. [2023-12-21 07:34:01,219 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-12-21 07:34:01,219 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 5.25) internal successors, (42), 8 states have internal predecessors, (42), 8 states have call successors, (27), 2 states have call predecessors, (27), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) Word has length 88 [2023-12-21 07:34:01,219 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-12-21 07:34:01,220 INFO L225 Difference]: With dead ends: 282 [2023-12-21 07:34:01,220 INFO L226 Difference]: Without dead ends: 245 [2023-12-21 07:34:01,220 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 169 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=46, Unknown=0, NotChecked=0, Total=72 [2023-12-21 07:34:01,221 INFO L413 NwaCegarLoop]: 64 mSDtfsCounter, 19 mSDsluCounter, 162 mSDsCounter, 0 mSdLazyCounter, 88 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 226 SdHoareTripleChecker+Invalid, 97 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 88 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-12-21 07:34:01,222 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [26 Valid, 226 Invalid, 97 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 88 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-12-21 07:34:01,223 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 245 states. [2023-12-21 07:34:01,270 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 245 to 235. [2023-12-21 07:34:01,271 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 159 states have (on average 1.1257861635220126) internal successors, (179), 164 states have internal predecessors, (179), 45 states have call successors, (45), 30 states have call predecessors, (45), 30 states have return successors, (44), 40 states have call predecessors, (44), 44 states have call successors, (44) [2023-12-21 07:34:01,271 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 268 transitions. [2023-12-21 07:34:01,271 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 268 transitions. Word has length 88 [2023-12-21 07:34:01,272 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-12-21 07:34:01,272 INFO L495 AbstractCegarLoop]: Abstraction has 235 states and 268 transitions. [2023-12-21 07:34:01,272 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 5.25) internal successors, (42), 8 states have internal predecessors, (42), 8 states have call successors, (27), 2 states have call predecessors, (27), 1 states have return successors, (26), 7 states have call predecessors, (26), 7 states have call successors, (26) [2023-12-21 07:34:01,272 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 268 transitions. [2023-12-21 07:34:01,272 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2023-12-21 07:34:01,272 INFO L187 NwaCegarLoop]: Found error trace [2023-12-21 07:34:01,272 INFO L195 NwaCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2023-12-21 07:34:01,279 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2023-12-21 07:34:01,473 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable15,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:34:01,473 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-12-21 07:34:01,481 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-12-21 07:34:01,481 INFO L85 PathProgramCache]: Analyzing trace with hash 1566685696, now seen corresponding path program 3 times [2023-12-21 07:34:01,481 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-12-21 07:34:01,481 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [885296279] [2023-12-21 07:34:01,481 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-12-21 07:34:01,481 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-12-21 07:34:01,486 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-12-21 07:34:01,486 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2069579200] [2023-12-21 07:34:01,486 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-12-21 07:34:01,486 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-12-21 07:34:01,486 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-12-21 07:34:01,489 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-12-21 07:34:01,513 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-12-21 07:34:19,155 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2023-12-21 07:34:19,155 INFO L229 tOrderPrioritization]: Conjunction of SSA is sat [2023-12-21 07:34:19,155 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. Received shutdown request... [2023-12-21 07:34:25,896 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-21 07:34:25,936 WARN L340 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Timeout while monitored process is still running, waiting 1000 ms for graceful end [2023-12-21 07:34:27,097 WARN L435 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forcibly destroying the process [2023-12-21 07:34:27,101 ERROR L246 FreeRefinementEngine]: Caught known exception: Timeout or Toolchain cancelled by user [2023-12-21 07:34:27,103 INFO L805 garLoopResultBuilder]: Registering result TIMEOUT for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2023-12-21 07:34:27,105 WARN L435 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forcibly destroying the process [2023-12-21 07:34:27,106 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-12-21 07:34:27,106 WARN L619 AbstractCegarLoop]: Verification canceled: while NwaCegarLoop was analyzing trace of length 92 with TraceHistMax 14,while AutomatonFreeRefinementEngine was Timeout during CAMEL. [2023-12-21 07:34:27,108 INFO L445 BasicCegarLoop]: Path program histogram: [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-12-21 07:34:27,112 INFO L179 ceAbstractionStarter]: Computing trace abstraction results [2023-12-21 07:34:27,114 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 21.12 07:34:27 BoogieIcfgContainer [2023-12-21 07:34:27,114 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2023-12-21 07:34:27,115 INFO L158 Benchmark]: Toolchain (without parser) took 886502.37ms. Allocated memory was 174.1MB in the beginning and 219.2MB in the end (delta: 45.1MB). Free memory was 139.5MB in the beginning and 181.8MB in the end (delta: -42.3MB). Peak memory consumption was 3.7MB. Max. memory is 8.0GB. [2023-12-21 07:34:27,115 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 174.1MB. Free memory was 132.5MB in the beginning and 132.4MB in the end (delta: 90.1kB). There was no memory consumed. Max. memory is 8.0GB. [2023-12-21 07:34:27,116 INFO L158 Benchmark]: CACSL2BoogieTranslator took 204.20ms. Allocated memory is still 174.1MB. Free memory was 139.5MB in the beginning and 128.3MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2023-12-21 07:34:27,119 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.95ms. Allocated memory is still 174.1MB. Free memory was 128.3MB in the beginning and 126.9MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2023-12-21 07:34:27,122 INFO L158 Benchmark]: Boogie Preprocessor took 39.87ms. Allocated memory is still 174.1MB. Free memory was 126.9MB in the beginning and 124.8MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2023-12-21 07:34:27,123 INFO L158 Benchmark]: RCFGBuilder took 299.28ms. Allocated memory is still 174.1MB. Free memory was 124.8MB in the beginning and 113.1MB in the end (delta: 11.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2023-12-21 07:34:27,124 INFO L158 Benchmark]: TraceAbstraction took 885930.69ms. Allocated memory was 174.1MB in the beginning and 219.2MB in the end (delta: 45.1MB). Free memory was 112.2MB in the beginning and 181.8MB in the end (delta: -69.6MB). There was no memory consumed. Max. memory is 8.0GB. [2023-12-21 07:34:27,128 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.09ms. Allocated memory is still 174.1MB. Free memory was 132.5MB in the beginning and 132.4MB in the end (delta: 90.1kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 204.20ms. Allocated memory is still 174.1MB. Free memory was 139.5MB in the beginning and 128.3MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Procedure Inliner took 23.95ms. Allocated memory is still 174.1MB. Free memory was 128.3MB in the beginning and 126.9MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * Boogie Preprocessor took 39.87ms. Allocated memory is still 174.1MB. Free memory was 126.9MB in the beginning and 124.8MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 299.28ms. Allocated memory is still 174.1MB. Free memory was 124.8MB in the beginning and 113.1MB in the end (delta: 11.7MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 885930.69ms. Allocated memory was 174.1MB in the beginning and 219.2MB in the end (delta: 45.1MB). Free memory was 112.2MB in the beginning and 181.8MB in the end (delta: -69.6MB). There was no memory consumed. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - TimeoutResultAtElement [Line: 17]: Timeout (TraceAbstraction) Unable to prove that a call to reach_error is unreachable (line 17). Cancelled while NwaCegarLoop was analyzing trace of length 92 with TraceHistMax 14,while AutomatonFreeRefinementEngine was Timeout during CAMEL. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 25 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 885.9s, OverallIterations: 17, TraceHistogramMax: 14, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 798.0s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 80 mSolverCounterUnknown, 582 SdHoareTripleChecker+Valid, 394.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 508 mSDsluCounter, 2559 SdHoareTripleChecker+Invalid, 393.7s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 2059 mSDsCounter, 261 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2050 IncrementalHoareTripleChecker+Invalid, 2391 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 261 mSolverCounterUnsat, 500 mSDtfsCounter, 2050 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 80 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1062 GetRequests, 886 SyntacticMatches, 0 SemanticMatches, 176 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 524 ImplicationChecksByTransitivity, 446.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=266occurred in iteration=13, InterpolantAutomatonStates: 155, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.4s AutomataMinimizationTime, 16 MinimizatonAttempts, 124 StatesRemovedByMinimization, 11 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 4.4s SatisfiabilityAnalysisTime, 53.6s InterpolantComputationTime, 673 NumberOfCodeBlocks, 673 NumberOfCodeBlocksAsserted, 20 NumberOfCheckSat, 989 ConstructedInterpolants, 0 QuantifiedInterpolants, 5357 SizeOfPredicates, 42 NumberOfNonLiveVariables, 1703 ConjunctsInSsa, 234 ConjunctsInUnsatCore, 23 InterpolantComputations, 7 PerfectInterpolantSequences, 2174/2477 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown [2023-12-21 07:34:27,134 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 137