./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive/McCarthy91-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive/McCarthy91-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 2a5dd5c1c64cd1875ba800cc2db6d1da955f2d2f519c1964ff87558bc42b9b4c --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-04 16:17:45,692 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-04 16:17:45,744 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2025-03-04 16:17:45,753 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-04 16:17:45,753 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-04 16:17:45,753 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-03-04 16:17:45,774 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-04 16:17:45,775 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-04 16:17:45,775 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-04 16:17:45,775 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-04 16:17:45,775 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-04 16:17:45,775 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-04 16:17:45,776 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-04 16:17:45,776 INFO L153 SettingsManager]: * Use SBE=true [2025-03-04 16:17:45,776 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-03-04 16:17:45,776 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-03-04 16:17:45,776 INFO L153 SettingsManager]: * Use old map elimination=false [2025-03-04 16:17:45,776 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-03-04 16:17:45,776 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-03-04 16:17:45,776 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-03-04 16:17:45,776 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-04 16:17:45,776 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-04 16:17:45,777 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-04 16:17:45,778 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-04 16:17:45,778 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-04 16:17:45,778 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-04 16:17:45,778 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-04 16:17:45,778 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-03-04 16:17:45,778 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 2a5dd5c1c64cd1875ba800cc2db6d1da955f2d2f519c1964ff87558bc42b9b4c [2025-03-04 16:17:45,997 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-04 16:17:46,005 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-04 16:17:46,007 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-04 16:17:46,008 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-04 16:17:46,008 INFO L274 PluginConnector]: CDTParser initialized [2025-03-04 16:17:46,009 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/McCarthy91-2.c [2025-03-04 16:17:47,228 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d790c3e26/881e023763b741d7913403df91faa43c/FLAG26ec36cbb [2025-03-04 16:17:47,436 INFO L384 CDTParser]: Found 1 translation units. [2025-03-04 16:17:47,437 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/McCarthy91-2.c [2025-03-04 16:17:47,443 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d790c3e26/881e023763b741d7913403df91faa43c/FLAG26ec36cbb [2025-03-04 16:17:47,784 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d790c3e26/881e023763b741d7913403df91faa43c [2025-03-04 16:17:47,786 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-04 16:17:47,787 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-04 16:17:47,788 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-04 16:17:47,788 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-04 16:17:47,791 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-04 16:17:47,791 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,792 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7f5a85fc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47, skipping insertion in model container [2025-03-04 16:17:47,792 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,801 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-04 16:17:47,901 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 16:17:47,909 INFO L200 MainTranslator]: Completed pre-run [2025-03-04 16:17:47,920 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-04 16:17:47,930 INFO L204 MainTranslator]: Completed translation [2025-03-04 16:17:47,931 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47 WrapperNode [2025-03-04 16:17:47,931 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-04 16:17:47,932 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-04 16:17:47,932 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-04 16:17:47,932 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-04 16:17:47,936 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,940 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,951 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 22 [2025-03-04 16:17:47,951 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-04 16:17:47,952 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-04 16:17:47,952 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-04 16:17:47,953 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-04 16:17:47,958 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,958 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,958 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,970 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]. [2025-03-04 16:17:47,971 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,971 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,973 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,975 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,978 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,978 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,979 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-04 16:17:47,982 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-04 16:17:47,982 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-04 16:17:47,982 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-04 16:17:47,983 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (1/1) ... [2025-03-04 16:17:47,986 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:47,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:48,007 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:48,009 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2025-03-04 16:17:48,025 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-04 16:17:48,026 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-04 16:17:48,026 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-04 16:17:48,026 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-04 16:17:48,026 INFO L130 BoogieDeclarations]: Found specification of procedure f91 [2025-03-04 16:17:48,026 INFO L138 BoogieDeclarations]: Found implementation of procedure f91 [2025-03-04 16:17:48,069 INFO L256 CfgBuilder]: Building ICFG [2025-03-04 16:17:48,071 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-04 16:17:48,132 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L21: havoc #t~ret4;havoc #t~ret5; [2025-03-04 16:17:48,137 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2025-03-04 16:17:48,137 INFO L307 CfgBuilder]: Performing block encoding [2025-03-04 16:17:48,143 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-04 16:17:48,143 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-04 16:17:48,143 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 04:17:48 BoogieIcfgContainer [2025-03-04 16:17:48,143 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-04 16:17:48,144 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-03-04 16:17:48,144 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-03-04 16:17:48,148 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-03-04 16:17:48,149 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-04 16:17:48,149 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 04.03 04:17:47" (1/3) ... [2025-03-04 16:17:48,150 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@707ecfa9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 04.03 04:17:48, skipping insertion in model container [2025-03-04 16:17:48,150 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-04 16:17:48,150 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.03 04:17:47" (2/3) ... [2025-03-04 16:17:48,151 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@707ecfa9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 04.03 04:17:48, skipping insertion in model container [2025-03-04 16:17:48,151 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-04 16:17:48,151 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 04:17:48" (3/3) ... [2025-03-04 16:17:48,152 INFO L363 chiAutomizerObserver]: Analyzing ICFG McCarthy91-2.c [2025-03-04 16:17:48,188 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-03-04 16:17:48,188 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-03-04 16:17:48,189 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-03-04 16:17:48,189 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-03-04 16:17:48,189 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-03-04 16:17:48,189 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-03-04 16:17:48,189 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-03-04 16:17:48,189 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-03-04 16:17:48,192 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 17 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-04 16:17:48,205 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-04 16:17:48,205 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:17:48,205 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:17:48,208 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-03-04 16:17:48,209 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-04 16:17:48,209 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-03-04 16:17:48,209 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 17 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-03-04 16:17:48,210 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-04 16:17:48,210 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:17:48,210 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:17:48,210 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2025-03-04 16:17:48,210 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-04 16:17:48,214 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< [2025-03-04 16:17:48,214 INFO L754 eck$LassoCheckResult]: Loop: "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< [2025-03-04 16:17:48,217 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:48,217 INFO L85 PathProgramCache]: Analyzing trace with hash 38707, now seen corresponding path program 1 times [2025-03-04 16:17:48,222 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:48,223 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [296593217] [2025-03-04 16:17:48,223 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:17:48,223 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:48,269 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:48,279 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:48,280 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:48,280 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:48,280 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:48,284 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:48,287 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:48,289 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:48,289 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:48,303 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:48,305 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:48,305 INFO L85 PathProgramCache]: Analyzing trace with hash 46647, now seen corresponding path program 1 times [2025-03-04 16:17:48,305 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:48,306 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [777165908] [2025-03-04 16:17:48,306 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:17:48,306 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:48,309 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:48,314 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:48,315 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:48,315 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:48,315 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:48,317 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:48,319 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:48,320 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:48,320 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:48,321 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:48,323 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:48,323 INFO L85 PathProgramCache]: Analyzing trace with hash 1153137093, now seen corresponding path program 1 times [2025-03-04 16:17:48,323 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:48,324 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1707760395] [2025-03-04 16:17:48,324 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:17:48,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:48,330 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 6 statements into 1 equivalence classes. [2025-03-04 16:17:48,334 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 6 of 6 statements. [2025-03-04 16:17:48,335 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:48,335 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:48,335 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:48,337 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 6 statements into 1 equivalence classes. [2025-03-04 16:17:48,343 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 6 of 6 statements. [2025-03-04 16:17:48,343 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:48,343 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:48,346 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:48,422 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:48,422 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:48,422 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:48,422 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:48,423 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-04 16:17:48,423 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:48,423 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:48,423 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:48,423 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration1_Loop [2025-03-04 16:17:48,423 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:48,423 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:48,431 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,436 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,444 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,447 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,449 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,481 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:48,481 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-04 16:17:48,483 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:48,483 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:48,485 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:48,486 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2025-03-04 16:17:48,488 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:17:48,488 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:48,502 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:17:48,502 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:17:48,509 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2025-03-04 16:17:48,509 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:48,509 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:48,511 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:48,512 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2025-03-04 16:17:48,513 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:17:48,513 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:48,530 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2025-03-04 16:17:48,530 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:48,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:48,532 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:48,533 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2025-03-04 16:17:48,534 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-04 16:17:48,534 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:48,663 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-04 16:17:48,670 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2025-03-04 16:17:48,671 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:48,671 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:48,671 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:48,671 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:48,671 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-04 16:17:48,671 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:48,671 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:48,671 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:48,671 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration1_Loop [2025-03-04 16:17:48,671 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:48,671 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:48,672 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,676 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,688 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,692 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,695 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:48,727 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:48,729 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-04 16:17:48,731 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:48,731 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:48,735 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:48,740 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2025-03-04 16:17:48,742 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-04 16:17:48,753 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:17:48,753 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:17:48,753 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:17:48,754 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:17:48,754 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:17:48,757 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:17:48,757 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:17:48,761 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:17:48,769 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2025-03-04 16:17:48,770 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:48,770 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:48,772 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:48,772 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2025-03-04 16:17:48,775 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-04 16:17:48,785 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:17:48,786 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:17:48,786 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:17:48,786 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:17:48,786 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:17:48,787 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:17:48,787 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:17:48,792 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-04 16:17:48,797 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-04 16:17:48,799 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-04 16:17:48,800 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:48,800 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:48,802 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:48,804 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2025-03-04 16:17:48,805 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-04 16:17:48,805 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-04 16:17:48,806 INFO L474 LassoAnalysis]: Proved termination. [2025-03-04 16:17:48,806 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -2*f91_#in~x + 211 Supporting invariants [] [2025-03-04 16:17:48,812 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2025-03-04 16:17:48,817 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-04 16:17:48,839 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:48,851 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:48,863 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:48,864 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:48,864 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:48,865 INFO L256 TraceCheckSpWp]: Trace formula consists of 54 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-04 16:17:48,866 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:48,879 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:48,884 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:48,884 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:48,884 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:48,885 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-04 16:17:48,886 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:48,925 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 16:17:48,942 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2025-03-04 16:17:48,944 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 17 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 3 states have internal predecessors, (4), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 16:17:49,017 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 17 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 12 states have internal predecessors, (14), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 3 states have internal predecessors, (4), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 35 states and 43 transitions. Complement of second has 16 states. [2025-03-04 16:17:49,019 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:49,023 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 1.3333333333333333) internal successors, (4), 3 states have internal predecessors, (4), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-04 16:17:49,025 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 8 transitions. [2025-03-04 16:17:49,030 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 3 letters. [2025-03-04 16:17:49,031 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:49,031 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 6 letters. Loop has 3 letters. [2025-03-04 16:17:49,031 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:49,031 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 8 transitions. Stem has 3 letters. Loop has 6 letters. [2025-03-04 16:17:49,031 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:49,032 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 35 states and 43 transitions. [2025-03-04 16:17:49,035 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-04 16:17:49,039 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 35 states to 19 states and 25 transitions. [2025-03-04 16:17:49,040 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 13 [2025-03-04 16:17:49,041 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 14 [2025-03-04 16:17:49,041 INFO L73 IsDeterministic]: Start isDeterministic. Operand 19 states and 25 transitions. [2025-03-04 16:17:49,042 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:17:49,042 INFO L218 hiAutomatonCegarLoop]: Abstraction has 19 states and 25 transitions. [2025-03-04 16:17:49,062 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states and 25 transitions. [2025-03-04 16:17:49,063 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2025-03-04 16:17:49,070 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 17. [2025-03-04 16:17:49,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 17 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 11 states have internal predecessors, (13), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2025-03-04 16:17:49,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 21 transitions. [2025-03-04 16:17:49,071 INFO L240 hiAutomatonCegarLoop]: Abstraction has 17 states and 21 transitions. [2025-03-04 16:17:49,071 INFO L432 stractBuchiCegarLoop]: Abstraction has 17 states and 21 transitions. [2025-03-04 16:17:49,072 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-03-04 16:17:49,072 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 17 states and 21 transitions. [2025-03-04 16:17:49,072 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-04 16:17:49,072 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:17:49,072 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:17:49,073 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 16:17:49,073 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-04 16:17:49,073 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#24#return;" [2025-03-04 16:17:49,073 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#24#return;" [2025-03-04 16:17:49,074 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:49,074 INFO L85 PathProgramCache]: Analyzing trace with hash 590804261, now seen corresponding path program 1 times [2025-03-04 16:17:49,074 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:49,074 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [783040809] [2025-03-04 16:17:49,074 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:17:49,074 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:49,077 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-04 16:17:49,081 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-04 16:17:49,081 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:49,081 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:49,081 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:49,083 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-04 16:17:49,088 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-04 16:17:49,088 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:49,088 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:49,090 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:49,090 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:49,090 INFO L85 PathProgramCache]: Analyzing trace with hash -1180657404, now seen corresponding path program 1 times [2025-03-04 16:17:49,090 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:49,090 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [760509508] [2025-03-04 16:17:49,090 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:17:49,090 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:49,092 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-04 16:17:49,094 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-04 16:17:49,095 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:49,095 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:49,095 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:49,096 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-04 16:17:49,097 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-04 16:17:49,098 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:49,098 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:49,099 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:49,099 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:49,099 INFO L85 PathProgramCache]: Analyzing trace with hash -1632490968, now seen corresponding path program 1 times [2025-03-04 16:17:49,099 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:49,099 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [146644540] [2025-03-04 16:17:49,099 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:17:49,099 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:49,102 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-04 16:17:49,112 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-04 16:17:49,112 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:49,112 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:49,112 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:49,118 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 18 statements into 1 equivalence classes. [2025-03-04 16:17:49,123 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 18 of 18 statements. [2025-03-04 16:17:49,126 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:49,126 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:49,128 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:49,259 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:49,259 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:49,259 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:49,259 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:49,259 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-04 16:17:49,259 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:49,259 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:49,259 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:49,259 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration2_Loop [2025-03-04 16:17:49,259 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:49,259 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:49,260 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:49,267 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:49,271 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:49,310 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:49,310 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-04 16:17:49,310 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:49,310 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:49,313 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:49,314 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2025-03-04 16:17:49,315 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:17:49,315 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:49,329 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:17:49,329 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#t~ret5=0} Honda state: {f91_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:17:49,335 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2025-03-04 16:17:49,335 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:49,335 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:49,337 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:49,337 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2025-03-04 16:17:49,338 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:17:49,338 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:49,349 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:17:49,349 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:17:49,354 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2025-03-04 16:17:49,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:49,354 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:49,356 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:49,357 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2025-03-04 16:17:49,358 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:17:49,358 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:49,391 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2025-03-04 16:17:49,391 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:49,391 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:49,393 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:49,394 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2025-03-04 16:17:49,395 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-04 16:17:49,395 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:49,981 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-04 16:17:49,996 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2025-03-04 16:17:49,996 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:49,997 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:49,997 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:49,997 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:49,997 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-04 16:17:49,997 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:49,997 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:49,997 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:49,997 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration2_Loop [2025-03-04 16:17:49,997 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:49,997 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:49,998 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:50,009 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:50,012 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:50,041 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:50,041 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-04 16:17:50,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:50,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:50,043 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:50,045 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2025-03-04 16:17:50,046 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-04 16:17:50,056 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:17:50,056 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:17:50,057 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:17:50,057 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:17:50,057 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:17:50,058 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:17:50,058 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:17:50,060 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-04 16:17:50,063 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-04 16:17:50,063 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-04 16:17:50,063 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:50,063 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:50,065 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:50,067 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2025-03-04 16:17:50,067 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-04 16:17:50,067 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-04 16:17:50,067 INFO L474 LassoAnalysis]: Proved termination. [2025-03-04 16:17:50,067 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#t~ret4) = -2*f91_#t~ret4 + 201 Supporting invariants [] [2025-03-04 16:17:50,074 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Forceful destruction successful, exit code 0 [2025-03-04 16:17:50,075 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-04 16:17:50,077 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2025-03-04 16:17:50,090 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:50,097 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-04 16:17:50,116 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-04 16:17:50,117 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:50,117 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:50,117 INFO L256 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-04 16:17:50,118 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:50,179 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-04 16:17:50,186 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-04 16:17:50,187 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:50,187 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:50,187 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-04 16:17:50,188 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:50,272 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 16:17:50,273 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2025-03-04 16:17:50,274 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 17 states and 21 transitions. cyclomatic complexity: 6 Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 16:17:50,416 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 17 states and 21 transitions. cyclomatic complexity: 6. Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 51 states and 73 transitions. Complement of second has 32 states. [2025-03-04 16:17:50,417 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:50,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 6 states have internal predecessors, (12), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2025-03-04 16:17:50,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2025-03-04 16:17:50,419 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 8 letters. [2025-03-04 16:17:50,419 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:50,419 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 18 letters. Loop has 8 letters. [2025-03-04 16:17:50,419 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:50,419 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 10 letters. Loop has 16 letters. [2025-03-04 16:17:50,419 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:50,420 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 73 transitions. [2025-03-04 16:17:50,422 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-04 16:17:50,427 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 42 states and 62 transitions. [2025-03-04 16:17:50,428 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2025-03-04 16:17:50,428 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2025-03-04 16:17:50,428 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 62 transitions. [2025-03-04 16:17:50,428 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:17:50,428 INFO L218 hiAutomatonCegarLoop]: Abstraction has 42 states and 62 transitions. [2025-03-04 16:17:50,428 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 62 transitions. [2025-03-04 16:17:50,433 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 36. [2025-03-04 16:17:50,434 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 10 states have call successors, (13), 7 states have call predecessors, (13), 4 states have return successors, (12), 5 states have call predecessors, (12), 7 states have call successors, (12) [2025-03-04 16:17:50,435 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 51 transitions. [2025-03-04 16:17:50,436 INFO L240 hiAutomatonCegarLoop]: Abstraction has 36 states and 51 transitions. [2025-03-04 16:17:50,436 INFO L432 stractBuchiCegarLoop]: Abstraction has 36 states and 51 transitions. [2025-03-04 16:17:50,436 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-03-04 16:17:50,436 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 36 states and 51 transitions. [2025-03-04 16:17:50,437 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-04 16:17:50,437 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:17:50,437 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:17:50,437 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-04 16:17:50,437 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-04 16:17:50,437 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#24#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume !(~x > 100);" [2025-03-04 16:17:50,437 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" [2025-03-04 16:17:50,438 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:50,438 INFO L85 PathProgramCache]: Analyzing trace with hash -126218833, now seen corresponding path program 2 times [2025-03-04 16:17:50,438 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:50,438 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [631953405] [2025-03-04 16:17:50,438 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 16:17:50,438 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:50,442 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 13 statements into 2 equivalence classes. [2025-03-04 16:17:50,453 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 13 of 13 statements. [2025-03-04 16:17:50,454 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 16:17:50,454 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:50,454 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:50,455 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-04 16:17:50,459 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-04 16:17:50,459 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:50,459 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:50,461 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:50,461 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:50,461 INFO L85 PathProgramCache]: Analyzing trace with hash 52437, now seen corresponding path program 2 times [2025-03-04 16:17:50,461 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:50,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2018886617] [2025-03-04 16:17:50,462 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 16:17:50,462 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:50,463 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:50,464 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:50,464 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-04 16:17:50,464 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:50,464 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:50,465 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:50,465 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:50,465 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:50,465 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:50,466 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:50,466 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:50,466 INFO L85 PathProgramCache]: Analyzing trace with hash -2088847257, now seen corresponding path program 3 times [2025-03-04 16:17:50,467 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:50,467 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1883038436] [2025-03-04 16:17:50,467 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-04 16:17:50,467 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:50,470 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 16 statements into 4 equivalence classes. [2025-03-04 16:17:50,476 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 16 of 16 statements. [2025-03-04 16:17:50,476 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-04 16:17:50,476 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:50,575 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2025-03-04 16:17:50,610 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2025-03-04 16:17:50,611 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:17:50,611 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1883038436] [2025-03-04 16:17:50,611 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1883038436] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 16:17:50,611 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-04 16:17:50,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-04 16:17:50,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2071692831] [2025-03-04 16:17:50,612 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 16:17:50,666 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:50,667 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:50,667 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:50,667 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:50,667 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-04 16:17:50,667 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:50,667 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:50,667 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:50,667 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration3_Loop [2025-03-04 16:17:50,667 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:50,667 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:50,668 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:50,674 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:50,676 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:50,677 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:50,700 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:50,700 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-04 16:17:50,700 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:50,700 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:50,702 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:50,703 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2025-03-04 16:17:50,705 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:17:50,705 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:50,734 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2025-03-04 16:17:50,734 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:50,734 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:50,736 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:50,738 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2025-03-04 16:17:50,741 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-04 16:17:50,741 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:51,090 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-04 16:17:51,101 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2025-03-04 16:17:51,101 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:51,101 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:51,101 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:51,101 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:51,101 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-04 16:17:51,101 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:51,101 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:51,101 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:51,101 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration3_Loop [2025-03-04 16:17:51,101 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:51,101 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:51,102 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:51,104 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:51,110 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:51,112 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:51,134 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:51,134 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-04 16:17:51,134 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:51,135 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:51,136 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:51,138 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2025-03-04 16:17:51,138 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-04 16:17:51,148 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:17:51,148 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:17:51,148 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:17:51,148 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:17:51,148 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:17:51,149 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:17:51,149 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:17:51,150 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:17:51,157 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2025-03-04 16:17:51,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:51,158 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:51,160 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:51,161 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2025-03-04 16:17:51,163 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-04 16:17:51,172 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:17:51,173 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:17:51,173 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:17:51,173 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:17:51,173 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:17:51,174 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:17:51,174 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:17:51,175 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-04 16:17:51,177 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-04 16:17:51,177 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-04 16:17:51,177 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:51,178 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:51,179 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:51,180 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2025-03-04 16:17:51,181 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-04 16:17:51,182 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-04 16:17:51,182 INFO L474 LassoAnalysis]: Proved termination. [2025-03-04 16:17:51,182 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_~x) = -2*f91_~x + 189 Supporting invariants [] [2025-03-04 16:17:51,187 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2025-03-04 16:17:51,188 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-04 16:17:51,204 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:51,209 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-04 16:17:51,220 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-04 16:17:51,220 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,220 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:51,222 INFO L256 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-04 16:17:51,223 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:51,278 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:51,282 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:51,282 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,282 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:51,283 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-04 16:17:51,283 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:51,307 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 16:17:51,307 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2025-03-04 16:17:51,307 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 16:17:51,373 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 43 states and 59 transitions. Complement of second has 13 states. [2025-03-04 16:17:51,374 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:51,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 16:17:51,375 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2025-03-04 16:17:51,375 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2025-03-04 16:17:51,376 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:51,376 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:17:51,383 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:51,393 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-04 16:17:51,402 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-04 16:17:51,402 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,402 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:51,403 INFO L256 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-04 16:17:51,404 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:51,468 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:51,471 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:51,471 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,471 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:51,472 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-04 16:17:51,472 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:51,490 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 16:17:51,491 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2025-03-04 16:17:51,491 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 16:17:51,533 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 43 states and 59 transitions. Complement of second has 13 states. [2025-03-04 16:17:51,534 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:51,534 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 16:17:51,535 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2025-03-04 16:17:51,536 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 13 letters. Loop has 3 letters. [2025-03-04 16:17:51,537 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:51,537 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:17:51,545 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:51,551 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-04 16:17:51,562 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-04 16:17:51,562 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,562 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:51,563 INFO L256 TraceCheckSpWp]: Trace formula consists of 132 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-04 16:17:51,564 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:51,617 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-04 16:17:51,620 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-04 16:17:51,621 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,621 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:51,621 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-04 16:17:51,622 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:51,643 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 16:17:51,643 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2025-03-04 16:17:51,643 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 16:17:51,708 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 51 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 71 states and 100 transitions. Complement of second has 16 states. [2025-03-04 16:17:51,710 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:51,710 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 16:17:51,711 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 19 transitions. [2025-03-04 16:17:51,711 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 3 letters. [2025-03-04 16:17:51,711 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:51,711 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 16 letters. Loop has 3 letters. [2025-03-04 16:17:51,711 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:51,711 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 13 letters. Loop has 6 letters. [2025-03-04 16:17:51,711 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:51,711 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 71 states and 100 transitions. [2025-03-04 16:17:51,713 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2025-03-04 16:17:51,716 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 71 states to 48 states and 74 transitions. [2025-03-04 16:17:51,716 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2025-03-04 16:17:51,716 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2025-03-04 16:17:51,716 INFO L73 IsDeterministic]: Start isDeterministic. Operand 48 states and 74 transitions. [2025-03-04 16:17:51,716 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:17:51,716 INFO L218 hiAutomatonCegarLoop]: Abstraction has 48 states and 74 transitions. [2025-03-04 16:17:51,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states and 74 transitions. [2025-03-04 16:17:51,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 42. [2025-03-04 16:17:51,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.0384615384615385) internal successors, (27), 26 states have internal predecessors, (27), 11 states have call successors, (18), 9 states have call predecessors, (18), 5 states have return successors, (15), 6 states have call predecessors, (15), 8 states have call successors, (15) [2025-03-04 16:17:51,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 60 transitions. [2025-03-04 16:17:51,721 INFO L240 hiAutomatonCegarLoop]: Abstraction has 42 states and 60 transitions. [2025-03-04 16:17:51,722 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 16:17:51,723 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-04 16:17:51,723 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-04 16:17:51,725 INFO L87 Difference]: Start difference. First operand 42 states and 60 transitions. Second operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 states have internal predecessors, (10), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-04 16:17:51,810 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 16:17:51,811 INFO L93 Difference]: Finished difference Result 63 states and 82 transitions. [2025-03-04 16:17:51,811 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 63 states and 82 transitions. [2025-03-04 16:17:51,812 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-04 16:17:51,813 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 63 states to 58 states and 75 transitions. [2025-03-04 16:17:51,813 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 42 [2025-03-04 16:17:51,813 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 42 [2025-03-04 16:17:51,813 INFO L73 IsDeterministic]: Start isDeterministic. Operand 58 states and 75 transitions. [2025-03-04 16:17:51,813 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:17:51,813 INFO L218 hiAutomatonCegarLoop]: Abstraction has 58 states and 75 transitions. [2025-03-04 16:17:51,813 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states and 75 transitions. [2025-03-04 16:17:51,816 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2025-03-04 16:17:51,824 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 35 states have (on average 1.0571428571428572) internal successors, (37), 37 states have internal predecessors, (37), 13 states have call successors, (18), 11 states have call predecessors, (18), 9 states have return successors, (19), 8 states have call predecessors, (19), 11 states have call successors, (19) [2025-03-04 16:17:51,824 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 74 transitions. [2025-03-04 16:17:51,824 INFO L240 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-03-04 16:17:51,828 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-04 16:17:51,828 INFO L432 stractBuchiCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-03-04 16:17:51,828 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-03-04 16:17:51,828 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 57 states and 74 transitions. [2025-03-04 16:17:51,829 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-04 16:17:51,829 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:17:51,829 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:17:51,830 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1] [2025-03-04 16:17:51,830 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2025-03-04 16:17:51,830 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2025-03-04 16:17:51,831 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#24#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#22#return;" "#res := #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#24#return;" "call #t~ret5 := f91(#t~ret4);"< [2025-03-04 16:17:51,831 INFO L754 eck$LassoCheckResult]: Loop: "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#24#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#22#return;" "#res := #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#24#return;" "call #t~ret5 := f91(#t~ret4);"< [2025-03-04 16:17:51,831 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:51,831 INFO L85 PathProgramCache]: Analyzing trace with hash -1368746910, now seen corresponding path program 1 times [2025-03-04 16:17:51,831 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:51,831 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [289794569] [2025-03-04 16:17:51,831 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:17:51,831 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:51,834 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 16:17:51,837 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:17:51,837 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,837 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:51,838 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:51,839 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 16:17:51,842 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:17:51,842 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,842 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:51,843 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:51,844 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:51,844 INFO L85 PathProgramCache]: Analyzing trace with hash -77812524, now seen corresponding path program 1 times [2025-03-04 16:17:51,844 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:51,844 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1366286677] [2025-03-04 16:17:51,844 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-04 16:17:51,844 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:51,846 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-04 16:17:51,851 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-04 16:17:51,851 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,851 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:51,851 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:51,852 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-04 16:17:51,855 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-04 16:17:51,855 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:51,855 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:51,856 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:51,856 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:51,856 INFO L85 PathProgramCache]: Analyzing trace with hash -1527524653, now seen corresponding path program 2 times [2025-03-04 16:17:51,856 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:51,856 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [519840015] [2025-03-04 16:17:51,856 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 16:17:51,856 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:51,859 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 41 statements into 2 equivalence classes. [2025-03-04 16:17:51,867 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 41 of 41 statements. [2025-03-04 16:17:51,867 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 16:17:51,867 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:51,983 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-04 16:17:51,984 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:17:51,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [519840015] [2025-03-04 16:17:51,984 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [519840015] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 16:17:51,984 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [949452950] [2025-03-04 16:17:51,984 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 16:17:51,984 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 16:17:51,984 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:51,986 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 16:17:51,987 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2025-03-04 16:17:52,009 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 41 statements into 2 equivalence classes. [2025-03-04 16:17:52,019 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 41 of 41 statements. [2025-03-04 16:17:52,019 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 16:17:52,019 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:52,020 INFO L256 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-04 16:17:52,021 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:52,048 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-04 16:17:52,048 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-04 16:17:52,227 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 31 proven. 23 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2025-03-04 16:17:52,228 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [949452950] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-04 16:17:52,228 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-04 16:17:52,228 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 15 [2025-03-04 16:17:52,228 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1282862298] [2025-03-04 16:17:52,228 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-04 16:17:52,371 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:52,371 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:52,371 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:52,371 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:52,371 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-04 16:17:52,371 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:52,371 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:52,371 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:52,372 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration4_Loop [2025-03-04 16:17:52,372 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:52,372 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:52,372 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,377 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,379 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,380 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,382 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,405 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:52,406 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-04 16:17:52,406 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:52,406 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:52,410 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:52,412 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2025-03-04 16:17:52,413 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:17:52,413 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:52,438 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2025-03-04 16:17:52,438 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:52,438 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:52,440 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:52,441 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2025-03-04 16:17:52,442 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-04 16:17:52,444 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:52,457 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-04 16:17:52,471 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2025-03-04 16:17:52,473 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:52,473 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:52,473 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:52,473 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:52,473 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-04 16:17:52,473 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:52,473 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:52,473 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:52,473 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration4_Loop [2025-03-04 16:17:52,473 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:52,473 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:52,474 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,487 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,489 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,491 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,493 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:52,516 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:52,516 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-04 16:17:52,516 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:52,516 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:52,521 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:52,527 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2025-03-04 16:17:52,527 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-04 16:17:52,540 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:17:52,540 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:17:52,540 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:17:52,540 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:17:52,540 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:17:52,541 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:17:52,542 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:17:52,545 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-04 16:17:52,547 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-04 16:17:52,547 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-04 16:17:52,547 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:52,547 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:52,551 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:52,554 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2025-03-04 16:17:52,555 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-04 16:17:52,555 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-04 16:17:52,555 INFO L474 LassoAnalysis]: Proved termination. [2025-03-04 16:17:52,555 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -1*f91_#in~x + 90 Supporting invariants [] [2025-03-04 16:17:52,561 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2025-03-04 16:17:52,562 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-04 16:17:52,592 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:52,600 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 16:17:52,618 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:17:52,619 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:52,619 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:52,619 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-04 16:17:52,620 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:52,675 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2025-03-04 16:17:52,748 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-04 16:17:52,762 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-04 16:17:52,762 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:52,762 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:52,763 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-04 16:17:52,764 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:52,889 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-04 16:17:52,890 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 9 loop predicates [2025-03-04 16:17:52,890 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-04 16:17:53,121 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Result 125 states and 150 transitions. Complement of second has 39 states. [2025-03-04 16:17:53,122 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 14 states 2 stem states 11 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:53,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-04 16:17:53,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 35 transitions. [2025-03-04 16:17:53,123 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 14 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2025-03-04 16:17:53,123 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:53,123 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:17:53,129 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:53,143 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 16:17:53,162 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:17:53,162 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:53,162 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:53,163 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-04 16:17:53,164 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:53,301 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-04 16:17:53,313 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-04 16:17:53,313 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:53,314 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:53,315 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 20 conjuncts are in the unsatisfiable core [2025-03-04 16:17:53,316 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:53,480 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-03-04 16:17:53,481 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 9 loop predicates [2025-03-04 16:17:53,481 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-04 16:17:53,728 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Result 125 states and 150 transitions. Complement of second has 39 states. [2025-03-04 16:17:53,730 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 14 states 2 stem states 11 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:53,730 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 11 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 5 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2025-03-04 16:17:53,731 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 35 transitions. [2025-03-04 16:17:53,731 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 14 states and 35 transitions. Stem has 22 letters. Loop has 19 letters. [2025-03-04 16:17:53,731 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:53,731 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:17:53,741 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:53,752 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 22 statements into 1 equivalence classes. [2025-03-04 16:17:53,765 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 22 of 22 statements. [2025-03-04 16:17:53,765 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:53,765 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:53,766 INFO L256 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-04 16:17:53,767 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:53,885 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-04 16:17:53,898 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-04 16:17:53,898 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:53,898 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:53,899 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-04 16:17:53,900 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:54,064 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 4 proven. 8 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2025-03-04 16:17:54,066 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 10 loop predicates [2025-03-04 16:17:54,066 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 16:17:54,577 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 57 states and 74 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) Result 431 states and 531 transitions. Complement of second has 224 states. [2025-03-04 16:17:54,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 21 states 2 stem states 18 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:54,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.8888888888888888) internal successors, (17), 7 states have internal predecessors, (17), 6 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (6), 5 states have call predecessors, (6), 5 states have call successors, (6) [2025-03-04 16:17:54,579 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 50 transitions. [2025-03-04 16:17:54,579 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 22 letters. Loop has 19 letters. [2025-03-04 16:17:54,579 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:54,579 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 41 letters. Loop has 19 letters. [2025-03-04 16:17:54,580 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:54,580 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 50 transitions. Stem has 22 letters. Loop has 38 letters. [2025-03-04 16:17:54,580 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:54,580 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 431 states and 531 transitions. [2025-03-04 16:17:54,586 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 29 [2025-03-04 16:17:54,590 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 431 states to 203 states and 269 transitions. [2025-03-04 16:17:54,590 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 95 [2025-03-04 16:17:54,591 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 106 [2025-03-04 16:17:54,591 INFO L73 IsDeterministic]: Start isDeterministic. Operand 203 states and 269 transitions. [2025-03-04 16:17:54,591 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:17:54,591 INFO L218 hiAutomatonCegarLoop]: Abstraction has 203 states and 269 transitions. [2025-03-04 16:17:54,591 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states and 269 transitions. [2025-03-04 16:17:54,599 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 157. [2025-03-04 16:17:54,600 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 157 states, 97 states have (on average 1.092783505154639) internal successors, (106), 99 states have internal predecessors, (106), 35 states have call successors, (45), 29 states have call predecessors, (45), 25 states have return successors, (47), 28 states have call predecessors, (47), 32 states have call successors, (47) [2025-03-04 16:17:54,602 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 198 transitions. [2025-03-04 16:17:54,602 INFO L240 hiAutomatonCegarLoop]: Abstraction has 157 states and 198 transitions. [2025-03-04 16:17:54,602 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 16:17:54,602 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-04 16:17:54,602 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2025-03-04 16:17:54,603 INFO L87 Difference]: Start difference. First operand 157 states and 198 transitions. Second operand has 15 states, 12 states have (on average 1.8333333333333333) internal successors, (22), 8 states have internal predecessors, (22), 7 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (9), 7 states have call predecessors, (9), 4 states have call successors, (9) [2025-03-04 16:17:54,750 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 16:17:54,751 INFO L93 Difference]: Finished difference Result 159 states and 188 transitions. [2025-03-04 16:17:54,751 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 159 states and 188 transitions. [2025-03-04 16:17:54,752 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2025-03-04 16:17:54,756 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 159 states to 104 states and 123 transitions. [2025-03-04 16:17:54,760 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2025-03-04 16:17:54,761 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2025-03-04 16:17:54,761 INFO L73 IsDeterministic]: Start isDeterministic. Operand 104 states and 123 transitions. [2025-03-04 16:17:54,761 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-04 16:17:54,761 INFO L218 hiAutomatonCegarLoop]: Abstraction has 104 states and 123 transitions. [2025-03-04 16:17:54,761 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states and 123 transitions. [2025-03-04 16:17:54,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 100. [2025-03-04 16:17:54,768 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 100 states, 63 states have (on average 1.0476190476190477) internal successors, (66), 64 states have internal predecessors, (66), 21 states have call successors, (28), 20 states have call predecessors, (28), 16 states have return successors, (25), 15 states have call predecessors, (25), 18 states have call successors, (25) [2025-03-04 16:17:54,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 100 states to 100 states and 119 transitions. [2025-03-04 16:17:54,768 INFO L240 hiAutomatonCegarLoop]: Abstraction has 100 states and 119 transitions. [2025-03-04 16:17:54,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-04 16:17:54,769 INFO L432 stractBuchiCegarLoop]: Abstraction has 100 states and 119 transitions. [2025-03-04 16:17:54,769 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-03-04 16:17:54,769 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 100 states and 119 transitions. [2025-03-04 16:17:54,770 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2025-03-04 16:17:54,770 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-04 16:17:54,770 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-04 16:17:54,774 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1] [2025-03-04 16:17:54,774 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-04 16:17:54,774 INFO L752 eck$LassoCheckResult]: Stem: "assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(15, 2);call #Ultimate.allocInit(12, 3);" "assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;havoc main_#t~nondet6#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1;" "call main_#t~ret7#1 := f91(main_~x~0#1);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#24#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#22#return;" "#res := #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#24#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#24#return;" [2025-03-04 16:17:54,774 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#24#return;" [2025-03-04 16:17:54,774 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:54,775 INFO L85 PathProgramCache]: Analyzing trace with hash -619448126, now seen corresponding path program 3 times [2025-03-04 16:17:54,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:54,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1837121405] [2025-03-04 16:17:54,775 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-04 16:17:54,775 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:54,777 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 32 statements into 7 equivalence classes. [2025-03-04 16:17:54,785 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 27 of 32 statements. [2025-03-04 16:17:54,785 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-04 16:17:54,785 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:54,872 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 28 proven. 8 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2025-03-04 16:17:54,872 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-04 16:17:54,872 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1837121405] [2025-03-04 16:17:54,872 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1837121405] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-04 16:17:54,872 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1613729990] [2025-03-04 16:17:54,872 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-04 16:17:54,872 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-04 16:17:54,872 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:54,874 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-04 16:17:54,875 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2025-03-04 16:17:54,900 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 32 statements into 7 equivalence classes. [2025-03-04 16:17:54,907 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 27 of 32 statements. [2025-03-04 16:17:54,907 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-04 16:17:54,907 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:54,908 INFO L256 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-04 16:17:54,909 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:54,927 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2025-03-04 16:17:54,928 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-04 16:17:54,929 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1613729990] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-04 16:17:54,929 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-04 16:17:54,929 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 9 [2025-03-04 16:17:54,929 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1778234519] [2025-03-04 16:17:54,929 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-04 16:17:54,929 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-04 16:17:54,929 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:54,930 INFO L85 PathProgramCache]: Analyzing trace with hash -1180657404, now seen corresponding path program 2 times [2025-03-04 16:17:54,930 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-04 16:17:54,930 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [713084487] [2025-03-04 16:17:54,930 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-04 16:17:54,930 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-04 16:17:54,932 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 8 statements into 2 equivalence classes. [2025-03-04 16:17:54,934 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 8 of 8 statements. [2025-03-04 16:17:54,937 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-04 16:17:54,937 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:54,937 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-04 16:17:54,938 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-04 16:17:54,939 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-04 16:17:54,939 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:54,939 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-04 16:17:54,940 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-04 16:17:55,024 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:55,025 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:55,025 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:55,025 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:55,025 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-04 16:17:55,025 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:55,025 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:55,025 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:55,025 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration5_Loop [2025-03-04 16:17:55,025 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:55,025 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:55,026 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:55,027 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:55,033 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:55,055 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:55,055 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-04 16:17:55,055 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:55,055 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:55,057 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:55,058 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2025-03-04 16:17:55,058 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:17:55,059 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:55,069 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-04 16:17:55,069 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-04 16:17:55,074 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2025-03-04 16:17:55,075 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:55,075 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:55,077 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:55,078 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2025-03-04 16:17:55,079 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-04 16:17:55,079 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:55,114 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2025-03-04 16:17:55,114 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:55,114 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:55,116 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:55,117 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2025-03-04 16:17:55,118 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-04 16:17:55,118 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-04 16:17:55,708 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-04 16:17:55,725 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2025-03-04 16:17:55,725 INFO L204 LassoAnalysis]: Preferences: [2025-03-04 16:17:55,725 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-04 16:17:55,725 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-04 16:17:55,725 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-04 16:17:55,725 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-04 16:17:55,725 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:55,725 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-04 16:17:55,725 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-04 16:17:55,725 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-2.c_Iteration5_Loop [2025-03-04 16:17:55,725 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-04 16:17:55,725 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-04 16:17:55,726 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:55,727 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:55,729 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-04 16:17:55,751 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-04 16:17:55,751 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-04 16:17:55,751 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:55,752 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:55,753 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:55,754 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2025-03-04 16:17:55,755 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-04 16:17:55,765 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:17:55,765 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:17:55,765 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:17:55,765 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:17:55,765 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:17:55,765 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:17:55,765 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:17:55,766 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:17:55,772 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2025-03-04 16:17:55,772 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:55,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:55,774 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:55,774 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2025-03-04 16:17:55,776 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-04 16:17:55,786 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:17:55,786 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:17:55,786 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:17:55,786 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:17:55,786 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:17:55,787 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:17:55,787 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:17:55,788 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-04 16:17:55,793 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2025-03-04 16:17:55,793 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:55,793 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:55,795 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:55,796 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2025-03-04 16:17:55,796 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2025-03-04 16:17:55,806 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-04 16:17:55,806 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-04 16:17:55,806 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-04 16:17:55,806 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-04 16:17:55,806 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-04 16:17:55,807 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-04 16:17:55,807 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-04 16:17:55,809 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-04 16:17:55,811 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-04 16:17:55,812 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-04 16:17:55,812 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-04 16:17:55,812 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-04 16:17:55,814 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2025-03-04 16:17:55,815 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2025-03-04 16:17:55,816 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-04 16:17:55,816 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-04 16:17:55,816 INFO L474 LassoAnalysis]: Proved termination. [2025-03-04 16:17:55,816 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#t~ret4) = -2*f91_#t~ret4 + 201 Supporting invariants [] [2025-03-04 16:17:55,821 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2025-03-04 16:17:55,822 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-04 16:17:55,823 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2025-03-04 16:17:55,829 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:55,837 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-04 16:17:55,856 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 16:17:55,856 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:55,856 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:55,857 INFO L256 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-04 16:17:55,858 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:55,981 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-04 16:17:55,987 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-04 16:17:55,987 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:55,987 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:55,988 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-04 16:17:55,988 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:56,051 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 16:17:56,052 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2025-03-04 16:17:56,052 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 100 states and 119 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-04 16:17:56,105 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2025-03-04 16:17:56,167 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 100 states and 119 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Result 139 states and 161 transitions. Complement of second has 24 states. [2025-03-04 16:17:56,167 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:56,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-04 16:17:56,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2025-03-04 16:17:56,168 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 32 letters. Loop has 8 letters. [2025-03-04 16:17:56,168 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:56,168 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:17:56,176 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:56,186 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-04 16:17:56,206 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 16:17:56,206 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:56,206 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:56,207 INFO L256 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-04 16:17:56,208 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:56,323 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-04 16:17:56,329 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-04 16:17:56,329 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:56,329 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:56,329 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-04 16:17:56,330 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:56,397 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 16:17:56,397 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2025-03-04 16:17:56,397 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 100 states and 119 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-04 16:17:56,508 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 100 states and 119 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Result 139 states and 161 transitions. Complement of second has 24 states. [2025-03-04 16:17:56,513 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:56,514 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-04 16:17:56,514 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 17 transitions. [2025-03-04 16:17:56,514 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 17 transitions. Stem has 32 letters. Loop has 8 letters. [2025-03-04 16:17:56,514 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:56,514 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-04 16:17:56,527 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-04 16:17:56,540 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-04 16:17:56,560 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-04 16:17:56,560 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:56,560 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:56,561 INFO L256 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-04 16:17:56,562 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:56,696 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-04 16:17:56,702 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-04 16:17:56,702 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-04 16:17:56,702 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-04 16:17:56,703 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-04 16:17:56,704 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-04 16:17:56,759 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-04 16:17:56,759 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2025-03-04 16:17:56,763 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 100 states and 119 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-04 16:17:56,853 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 100 states and 119 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Result 181 states and 211 transitions. Complement of second has 27 states. [2025-03-04 16:17:56,855 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2025-03-04 16:17:56,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 4 states have call successors, (8), 4 states have call predecessors, (8), 2 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2025-03-04 16:17:56,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 21 transitions. [2025-03-04 16:17:56,855 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 32 letters. Loop has 8 letters. [2025-03-04 16:17:56,855 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:56,856 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 40 letters. Loop has 8 letters. [2025-03-04 16:17:56,856 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:56,856 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 21 transitions. Stem has 32 letters. Loop has 16 letters. [2025-03-04 16:17:56,856 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-04 16:17:56,856 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 181 states and 211 transitions. [2025-03-04 16:17:56,858 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-04 16:17:56,858 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 181 states to 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-04 16:17:56,858 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-04 16:17:56,858 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-04 16:17:56,858 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-04 16:17:56,858 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-04 16:17:56,858 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-04 16:17:56,858 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 5 states have internal predecessors, (16), 4 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2025-03-04 16:17:56,858 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-04 16:17:56,858 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-04 16:17:56,858 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-04 16:17:56,858 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-04 16:17:56,858 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-04 16:17:56,858 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:17:56,858 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-04 16:17:56,861 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-04 16:17:56,861 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-03-04 16:17:56,861 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-03-04 16:17:56,861 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-04 16:17:56,861 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-03-04 16:17:56,868 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 04.03 04:17:56 BoogieIcfgContainer [2025-03-04 16:17:56,868 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-03-04 16:17:56,869 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-04 16:17:56,869 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-04 16:17:56,869 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-04 16:17:56,871 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 04.03 04:17:48" (3/4) ... [2025-03-04 16:17:56,872 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-04 16:17:56,873 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-04 16:17:56,874 INFO L158 Benchmark]: Toolchain (without parser) took 9086.53ms. Allocated memory is still 142.6MB. Free memory was 111.1MB in the beginning and 87.4MB in the end (delta: 23.7MB). Peak memory consumption was 28.6MB. Max. memory is 16.1GB. [2025-03-04 16:17:56,875 INFO L158 Benchmark]: CDTParser took 0.68ms. Allocated memory is still 201.3MB. Free memory is still 123.3MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-04 16:17:56,875 INFO L158 Benchmark]: CACSL2BoogieTranslator took 143.46ms. Allocated memory is still 142.6MB. Free memory was 110.6MB in the beginning and 100.4MB in the end (delta: 10.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-04 16:17:56,875 INFO L158 Benchmark]: Boogie Procedure Inliner took 19.85ms. Allocated memory is still 142.6MB. Free memory was 100.4MB in the beginning and 99.4MB in the end (delta: 979.7kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-04 16:17:56,875 INFO L158 Benchmark]: Boogie Preprocessor took 27.05ms. Allocated memory is still 142.6MB. Free memory was 99.4MB in the beginning and 98.3MB in the end (delta: 1.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-04 16:17:56,876 INFO L158 Benchmark]: IcfgBuilder took 161.59ms. Allocated memory is still 142.6MB. Free memory was 98.3MB in the beginning and 88.2MB in the end (delta: 10.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-04 16:17:56,876 INFO L158 Benchmark]: BuchiAutomizer took 8724.11ms. Allocated memory is still 142.6MB. Free memory was 88.2MB in the beginning and 87.4MB in the end (delta: 752.9kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-04 16:17:56,876 INFO L158 Benchmark]: Witness Printer took 4.28ms. Allocated memory is still 142.6MB. Free memory was 87.4MB in the beginning and 87.4MB in the end (delta: 27.1kB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-04 16:17:56,878 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.68ms. Allocated memory is still 201.3MB. Free memory is still 123.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 143.46ms. Allocated memory is still 142.6MB. Free memory was 110.6MB in the beginning and 100.4MB in the end (delta: 10.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 19.85ms. Allocated memory is still 142.6MB. Free memory was 100.4MB in the beginning and 99.4MB in the end (delta: 979.7kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 27.05ms. Allocated memory is still 142.6MB. Free memory was 99.4MB in the beginning and 98.3MB in the end (delta: 1.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * IcfgBuilder took 161.59ms. Allocated memory is still 142.6MB. Free memory was 98.3MB in the beginning and 88.2MB in the end (delta: 10.1MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 8724.11ms. Allocated memory is still 142.6MB. Free memory was 88.2MB in the beginning and 87.4MB in the end (delta: 752.9kB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 4.28ms. Allocated memory is still 142.6MB. Free memory was 87.4MB in the beginning and 87.4MB in the end (delta: 27.1kB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #t~ret4 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #t~ret4 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 8 terminating modules (3 trivial, 2 deterministic, 3 nondeterministic). One deterministic module has affine ranking function (211 + ((long long) -2 * \old(x))) and consists of 5 locations. One deterministic module has affine ranking function null and consists of 8 locations. One nondeterministic module has affine ranking function (((long long) -2 * x) + 189) and consists of 6 locations. One nondeterministic module has affine ranking function (((long long) -1 * \old(x)) + 90) and consists of 21 locations. One nondeterministic module has affine ranking function null and consists of 8 locations. 3 modules have a trivial ranking function, the largest among these consists of 15 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 8.6s and 6 iterations. TraceHistogramMax:7. Analysis of lassos took 4.1s. Construction of modules took 0.5s. Büchi inclusion checks took 3.8s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 6. Automata minimization 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 65 StatesRemovedByMinimization, 6 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 3, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 12/24 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 247 SdHoareTripleChecker+Valid, 0.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 234 mSDsluCounter, 411 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 239 mSDsCounter, 197 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 837 IncrementalHoareTripleChecker+Invalid, 1034 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 197 mSolverCounterUnsat, 172 mSDtfsCounter, 837 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT2 conc0 concLT2 SILN0 SILU0 SILI0 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital13 mio100 ax100 hnf100 lsp100 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq176 hnf90 smp100 dnf100 smp100 tf110 neg100 sie100 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 31ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.9s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-03-04 16:17:56,891 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Ended with exit code 0 [2025-03-04 16:17:57,088 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2025-03-04 16:17:57,289 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE