./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive/McCarthy91-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 8fc3dc66 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-1.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 a7241ade69e14c61e98aa837796de568ecf31fbd07f5084e15c262d93cdb3376 --- Real Ultimate output --- This is Ultimate 0.3.0-?-8fc3dc6-m [2025-03-17 20:34:56,366 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-17 20:34:56,426 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2025-03-17 20:34:56,431 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-17 20:34:56,431 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-17 20:34:56,431 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2025-03-17 20:34:56,450 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-17 20:34:56,451 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-17 20:34:56,451 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-17 20:34:56,452 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-17 20:34:56,452 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-17 20:34:56,453 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-17 20:34:56,453 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-17 20:34:56,453 INFO L153 SettingsManager]: * Use SBE=true [2025-03-17 20:34:56,453 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2025-03-17 20:34:56,453 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2025-03-17 20:34:56,453 INFO L153 SettingsManager]: * Use old map elimination=false [2025-03-17 20:34:56,453 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2025-03-17 20:34:56,453 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2025-03-17 20:34:56,454 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2025-03-17 20:34:56,454 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2025-03-17 20:34:56,455 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-17 20:34:56,455 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-17 20:34:56,455 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2025-03-17 20:34:56,455 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-17 20:34:56,455 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-17 20:34:56,455 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-17 20:34:56,455 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-17 20:34:56,456 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-17 20:34:56,456 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-17 20:34:56,456 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2025-03-17 20:34:56,456 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 -> a7241ade69e14c61e98aa837796de568ecf31fbd07f5084e15c262d93cdb3376 [2025-03-17 20:34:56,701 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-17 20:34:56,711 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-17 20:34:56,714 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-17 20:34:56,715 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-17 20:34:56,715 INFO L274 PluginConnector]: CDTParser initialized [2025-03-17 20:34:56,716 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/McCarthy91-1.c [2025-03-17 20:34:57,883 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/66238264f/f88a8cedca4e475cb0733a7f66c663fe/FLAG56978fd7c [2025-03-17 20:34:58,129 INFO L384 CDTParser]: Found 1 translation units. [2025-03-17 20:34:58,131 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/McCarthy91-1.c [2025-03-17 20:34:58,141 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/66238264f/f88a8cedca4e475cb0733a7f66c663fe/FLAG56978fd7c [2025-03-17 20:34:58,460 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/66238264f/f88a8cedca4e475cb0733a7f66c663fe [2025-03-17 20:34:58,462 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-17 20:34:58,463 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-17 20:34:58,464 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-17 20:34:58,464 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-17 20:34:58,467 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-17 20:34:58,469 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,470 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@63c329a8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58, skipping insertion in model container [2025-03-17 20:34:58,470 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,479 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-17 20:34:58,583 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 20:34:58,591 INFO L200 MainTranslator]: Completed pre-run [2025-03-17 20:34:58,601 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-17 20:34:58,612 INFO L204 MainTranslator]: Completed translation [2025-03-17 20:34:58,613 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58 WrapperNode [2025-03-17 20:34:58,613 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-17 20:34:58,614 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-17 20:34:58,614 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-17 20:34:58,614 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-17 20:34:58,618 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,624 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,634 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 22 [2025-03-17 20:34:58,635 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-17 20:34:58,635 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-17 20:34:58,636 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-17 20:34:58,636 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-17 20:34:58,641 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,641 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,642 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,650 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-17 20:34:58,650 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,650 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,654 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,655 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,655 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,655 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,656 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-17 20:34:58,658 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-17 20:34:58,658 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-17 20:34:58,658 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-17 20:34:58,659 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (1/1) ... [2025-03-17 20:34:58,664 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:58,673 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:58,686 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-17 20:34:58,691 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-17 20:34:58,712 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-17 20:34:58,712 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-17 20:34:58,712 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-17 20:34:58,713 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-17 20:34:58,713 INFO L130 BoogieDeclarations]: Found specification of procedure f91 [2025-03-17 20:34:58,713 INFO L138 BoogieDeclarations]: Found implementation of procedure f91 [2025-03-17 20:34:58,756 INFO L256 CfgBuilder]: Building ICFG [2025-03-17 20:34:58,758 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-17 20:34:58,830 INFO L1322 $ProcedureCfgBuilder]: dead code at ProgramPoint L21: havoc #t~ret4;havoc #t~ret5; [2025-03-17 20:34:58,835 INFO L? ?]: Removed 5 outVars from TransFormulas that were not future-live. [2025-03-17 20:34:58,835 INFO L307 CfgBuilder]: Performing block encoding [2025-03-17 20:34:58,841 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-17 20:34:58,841 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-17 20:34:58,841 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 08:34:58 BoogieIcfgContainer [2025-03-17 20:34:58,841 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-17 20:34:58,842 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2025-03-17 20:34:58,842 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2025-03-17 20:34:58,846 INFO L274 PluginConnector]: BuchiAutomizer initialized [2025-03-17 20:34:58,846 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 20:34:58,847 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 17.03 08:34:58" (1/3) ... [2025-03-17 20:34:58,847 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@ec8ea4b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 08:34:58, skipping insertion in model container [2025-03-17 20:34:58,847 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 20:34:58,847 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 08:34:58" (2/3) ... [2025-03-17 20:34:58,847 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@ec8ea4b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.03 08:34:58, skipping insertion in model container [2025-03-17 20:34:58,848 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2025-03-17 20:34:58,848 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 08:34:58" (3/3) ... [2025-03-17 20:34:58,848 INFO L363 chiAutomizerObserver]: Analyzing ICFG McCarthy91-1.c [2025-03-17 20:34:58,883 INFO L306 stractBuchiCegarLoop]: Interprodecural is true [2025-03-17 20:34:58,884 INFO L307 stractBuchiCegarLoop]: Hoare is None [2025-03-17 20:34:58,885 INFO L308 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2025-03-17 20:34:58,885 INFO L309 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2025-03-17 20:34:58,885 INFO L310 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2025-03-17 20:34:58,886 INFO L311 stractBuchiCegarLoop]: Difference is false [2025-03-17 20:34:58,886 INFO L312 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2025-03-17 20:34:58,886 INFO L316 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2025-03-17 20:34:58,890 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 14 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 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-17 20:34:58,902 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 20:34:58,903 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:34:58,903 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:34:58,906 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 20:34:58,906 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 20:34:58,907 INFO L338 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2025-03-17 20:34:58,907 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 14 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 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-17 20:34:58,909 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 20:34:58,909 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:34:58,909 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:34:58,909 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2025-03-17 20:34:58,909 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 20:34:58,914 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-17 20:34:58,914 INFO L754 eck$LassoCheckResult]: Loop: "~x := #in~x;" "assume !(~x > 100);" "call #t~ret4 := f91(11 + ~x);"< [2025-03-17 20:34:58,919 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:58,922 INFO L85 PathProgramCache]: Analyzing trace with hash 1163, now seen corresponding path program 1 times [2025-03-17 20:34:58,927 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:58,927 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [60394113] [2025-03-17 20:34:58,928 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:58,928 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:58,971 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 20:34:58,985 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 20:34:58,985 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:58,985 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:58,986 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:58,988 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 20:34:58,992 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 20:34:58,993 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:58,995 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,010 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:59,013 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:59,013 INFO L85 PathProgramCache]: Analyzing trace with hash 43668, now seen corresponding path program 1 times [2025-03-17 20:34:59,013 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:59,013 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [480615456] [2025-03-17 20:34:59,013 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:59,014 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:59,018 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:34:59,023 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:34:59,024 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,024 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,024 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:59,027 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:34:59,029 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:34:59,030 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,030 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,031 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:59,032 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:59,033 INFO L85 PathProgramCache]: Analyzing trace with hash 34660810, now seen corresponding path program 1 times [2025-03-17 20:34:59,033 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:59,033 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1862097607] [2025-03-17 20:34:59,033 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:59,033 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:59,038 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 5 statements into 1 equivalence classes. [2025-03-17 20:34:59,044 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 5 of 5 statements. [2025-03-17 20:34:59,045 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,045 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,045 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:59,047 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 5 statements into 1 equivalence classes. [2025-03-17 20:34:59,054 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 5 of 5 statements. [2025-03-17 20:34:59,054 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,054 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,058 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:59,146 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:34:59,146 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:34:59,146 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:34:59,147 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:34:59,147 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:34:59,147 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,147 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:34:59,147 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:34:59,147 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration1_Loop [2025-03-17 20:34:59,147 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:34:59,147 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:34:59,159 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,168 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,182 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,186 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,189 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,235 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:34:59,235 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:34:59,237 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,237 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:59,239 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-17 20:34:59,240 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-17 20:34:59,240 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:34:59,240 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:59,256 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:34:59,257 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:34:59,263 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-17 20:34:59,263 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,263 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:59,265 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-17 20:34:59,266 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-17 20:34:59,267 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:34:59,267 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:59,284 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-17 20:34:59,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,286 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:59,289 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-17 20:34:59,290 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-17 20:34:59,291 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:34:59,291 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:34:59,415 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:34:59,422 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-17 20:34:59,422 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:34:59,422 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:34:59,422 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:34:59,422 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:34:59,422 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:34:59,422 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,422 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:34:59,422 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:34:59,422 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration1_Loop [2025-03-17 20:34:59,422 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:34:59,422 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:34:59,423 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,427 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,434 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,436 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,438 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:34:59,468 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:34:59,471 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:34:59,472 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,473 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:59,475 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-17 20:34:59,479 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-17 20:34:59,479 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-17 20:34:59,491 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:34:59,491 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:34:59,491 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:34:59,491 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:34:59,492 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:34:59,495 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:34:59,495 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:34:59,497 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:34:59,504 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-17 20:34:59,504 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,504 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:59,506 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-17 20:34:59,507 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-17 20:34:59,508 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-17 20:34:59,518 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:34:59,518 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:34:59,518 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:34:59,518 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:34:59,518 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:34:59,519 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:34:59,519 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:34:59,523 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:34:59,526 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:34:59,527 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:34:59,529 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:34:59,529 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:34:59,532 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-17 20:34:59,534 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-17 20:34:59,539 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:34:59,539 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:34:59,539 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:34:59,540 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -2*f91_#in~x + 211 Supporting invariants [] [2025-03-17 20:34:59,545 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2025-03-17 20:34:59,549 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:34:59,583 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:59,591 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 2 statements into 1 equivalence classes. [2025-03-17 20:34:59,598 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 2 of 2 statements. [2025-03-17 20:34:59,599 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,599 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:59,600 INFO L256 TraceCheckSpWp]: Trace formula consists of 53 conjuncts, 4 conjuncts are in the unsatisfiable core [2025-03-17 20:34:59,601 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:34:59,609 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:34:59,617 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:34:59,618 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,618 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:34:59,618 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:34:59,620 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:34:59,667 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-17 20:34:59,688 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-17 20:34:59,689 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 14 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 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.0) internal successors, (3), 3 states have internal predecessors, (3), 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-17 20:34:59,777 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 14 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 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.0) internal successors, (3), 3 states have internal predecessors, (3), 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 32 states and 40 transitions. Complement of second has 16 states. [2025-03-17 20:34:59,779 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-17 20:34:59,782 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 1.0) internal successors, (3), 3 states have internal predecessors, (3), 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-17 20:34:59,784 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 7 transitions. [2025-03-17 20:34:59,788 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 2 letters. Loop has 3 letters. [2025-03-17 20:34:59,790 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:34:59,790 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 5 letters. Loop has 3 letters. [2025-03-17 20:34:59,790 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:34:59,790 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 7 transitions. Stem has 2 letters. Loop has 6 letters. [2025-03-17 20:34:59,790 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:34:59,791 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 32 states and 40 transitions. [2025-03-17 20:34:59,794 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 20:34:59,798 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 32 states to 18 states and 24 transitions. [2025-03-17 20:34:59,798 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 12 [2025-03-17 20:34:59,799 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 13 [2025-03-17 20:34:59,799 INFO L73 IsDeterministic]: Start isDeterministic. Operand 18 states and 24 transitions. [2025-03-17 20:34:59,800 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:34:59,800 INFO L218 hiAutomatonCegarLoop]: Abstraction has 18 states and 24 transitions. [2025-03-17 20:34:59,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states and 24 transitions. [2025-03-17 20:34:59,816 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 16. [2025-03-17 20:34:59,817 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 16 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 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-17 20:34:59,817 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 20 transitions. [2025-03-17 20:34:59,818 INFO L240 hiAutomatonCegarLoop]: Abstraction has 16 states and 20 transitions. [2025-03-17 20:34:59,819 INFO L432 stractBuchiCegarLoop]: Abstraction has 16 states and 20 transitions. [2025-03-17 20:34:59,819 INFO L338 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2025-03-17 20:34:59,820 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 16 states and 20 transitions. [2025-03-17 20:34:59,820 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2025-03-17 20:34:59,820 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:34:59,820 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:34:59,821 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 20:34:59,822 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-17 20:34:59,822 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;" >"#21#return;" [2025-03-17 20:34:59,823 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;" >"#21#return;" [2025-03-17 20:34:59,823 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:59,823 INFO L85 PathProgramCache]: Analyzing trace with hash -404919830, now seen corresponding path program 1 times [2025-03-17 20:34:59,823 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:59,825 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [325143959] [2025-03-17 20:34:59,825 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:59,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:59,828 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 20:34:59,838 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 20:34:59,839 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,839 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,839 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:59,842 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 20:34:59,848 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 20:34:59,848 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,849 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,850 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:59,852 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:59,853 INFO L85 PathProgramCache]: Analyzing trace with hash -570415228, now seen corresponding path program 1 times [2025-03-17 20:34:59,854 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:59,854 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1291889286] [2025-03-17 20:34:59,854 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:59,854 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:59,856 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:34:59,861 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:34:59,863 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,863 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,863 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:59,864 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:34:59,868 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:34:59,870 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,870 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,871 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:34:59,872 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:34:59,872 INFO L85 PathProgramCache]: Analyzing trace with hash -1666344851, now seen corresponding path program 1 times [2025-03-17 20:34:59,874 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:34:59,874 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2040925449] [2025-03-17 20:34:59,874 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:34:59,874 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:34:59,890 ERROR L418 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Exception during sending of exit command (exit): Broken pipe [2025-03-17 20:34:59,894 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-17 20:34:59,893 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-03-17 20:34:59,899 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-03-17 20:34:59,899 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,899 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,899 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:34:59,901 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 17 statements into 1 equivalence classes. [2025-03-17 20:34:59,906 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 17 of 17 statements. [2025-03-17 20:34:59,906 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:34:59,906 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:34:59,911 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:00,038 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:00,038 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:00,038 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:00,038 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:00,038 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:00,038 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,038 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:00,038 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:00,038 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration2_Loop [2025-03-17 20:35:00,038 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:00,039 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:00,039 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,042 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,044 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,087 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:00,087 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:00,087 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,087 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,089 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-17 20:35:00,090 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-17 20:35:00,091 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,091 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,101 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:00,101 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-17 20:35:00,107 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:00,107 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,107 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,109 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-17 20:35:00,110 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-17 20:35:00,110 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,111 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,121 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:00,121 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:00,126 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-17 20:35:00,126 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,127 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,128 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-17 20:35:00,129 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-17 20:35:00,130 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:00,130 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,159 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:00,159 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,159 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,161 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-17 20:35:00,162 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-17 20:35:00,162 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:00,162 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:00,754 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:00,768 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-17 20:35:00,768 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:00,769 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:00,769 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:00,769 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:00,769 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:00,769 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,769 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:00,769 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:00,769 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration2_Loop [2025-03-17 20:35:00,769 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:00,769 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:00,770 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,780 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,782 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:00,811 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:00,811 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:00,811 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,811 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,813 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-17 20:35:00,814 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-17 20:35:00,815 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-17 20:35:00,825 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:00,826 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:00,826 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:00,826 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:00,826 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:00,827 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:00,827 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:00,829 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:00,832 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:00,832 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:00,832 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:00,832 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:00,834 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-17 20:35:00,835 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-17 20:35:00,836 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:00,836 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:00,836 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:00,836 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#t~ret4) = -2*f91_#t~ret4 + 201 Supporting invariants [] [2025-03-17 20:35:00,842 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-17 20:35:00,844 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:00,845 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2025-03-17 20:35:00,860 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:00,870 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 9 statements into 1 equivalence classes. [2025-03-17 20:35:00,882 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 9 of 9 statements. [2025-03-17 20:35:00,883 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,883 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:00,883 INFO L256 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-17 20:35:00,884 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:00,955 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:00,963 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:00,963 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:00,963 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:00,964 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 20:35:00,965 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:01,049 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-17 20:35:01,049 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-17 20:35:01,050 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 16 states and 20 transitions. cyclomatic complexity: 6 Second operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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-17 20:35:01,207 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 16 states and 20 transitions. cyclomatic complexity: 6. Second operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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 50 states and 72 transitions. Complement of second has 32 states. [2025-03-17 20:35:01,212 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-17 20:35:01,213 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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-17 20:35:01,214 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 16 transitions. [2025-03-17 20:35:01,214 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 9 letters. Loop has 8 letters. [2025-03-17 20:35:01,215 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,215 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 17 letters. Loop has 8 letters. [2025-03-17 20:35:01,215 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,215 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 9 letters. Loop has 16 letters. [2025-03-17 20:35:01,215 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:01,215 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 50 states and 72 transitions. [2025-03-17 20:35:01,219 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-17 20:35:01,221 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 50 states to 41 states and 61 transitions. [2025-03-17 20:35:01,221 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 25 [2025-03-17 20:35:01,223 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 26 [2025-03-17 20:35:01,223 INFO L73 IsDeterministic]: Start isDeterministic. Operand 41 states and 61 transitions. [2025-03-17 20:35:01,223 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:01,223 INFO L218 hiAutomatonCegarLoop]: Abstraction has 41 states and 61 transitions. [2025-03-17 20:35:01,223 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states and 61 transitions. [2025-03-17 20:35:01,227 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 35. [2025-03-17 20:35:01,228 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 22 states have internal predecessors, (25), 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-17 20:35:01,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 50 transitions. [2025-03-17 20:35:01,229 INFO L240 hiAutomatonCegarLoop]: Abstraction has 35 states and 50 transitions. [2025-03-17 20:35:01,229 INFO L432 stractBuchiCegarLoop]: Abstraction has 35 states and 50 transitions. [2025-03-17 20:35:01,229 INFO L338 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2025-03-17 20:35:01,229 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 35 states and 50 transitions. [2025-03-17 20:35:01,229 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 7 [2025-03-17 20:35:01,230 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:01,230 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:01,230 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 1, 1, 1, 1, 1, 1, 1] [2025-03-17 20:35:01,230 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2025-03-17 20:35:01,230 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;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume !(~x > 100);" [2025-03-17 20:35:01,230 INFO L754 eck$LassoCheckResult]: Loop: "call #t~ret4 := f91(11 + ~x);"< "~x := #in~x;" "assume !(~x > 100);" [2025-03-17 20:35:01,231 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:01,231 INFO L85 PathProgramCache]: Analyzing trace with hash 1596496679, now seen corresponding path program 2 times [2025-03-17 20:35:01,231 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:01,231 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1343413424] [2025-03-17 20:35:01,231 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:01,231 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:01,234 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 12 statements into 2 equivalence classes. [2025-03-17 20:35:01,239 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:01,239 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:01,239 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,239 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:01,241 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 20:35:01,247 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:01,247 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,247 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,249 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:01,249 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:01,249 INFO L85 PathProgramCache]: Analyzing trace with hash 49458, now seen corresponding path program 2 times [2025-03-17 20:35:01,249 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:01,249 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1295234626] [2025-03-17 20:35:01,249 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:01,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:01,257 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:01,262 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:01,262 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2025-03-17 20:35:01,262 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,262 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:01,263 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:01,264 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:01,264 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,264 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:01,264 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:01,268 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:01,268 INFO L85 PathProgramCache]: Analyzing trace with hash -1235252148, now seen corresponding path program 3 times [2025-03-17 20:35:01,268 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:01,268 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1821866700] [2025-03-17 20:35:01,268 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 20:35:01,268 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:01,271 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 15 statements into 4 equivalence classes. [2025-03-17 20:35:01,278 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) and asserted 15 of 15 statements. [2025-03-17 20:35:01,278 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2025-03-17 20:35:01,278 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:01,386 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-17 20:35:01,386 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:35:01,386 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1821866700] [2025-03-17 20:35:01,386 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1821866700] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 20:35:01,387 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-17 20:35:01,387 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2025-03-17 20:35:01,387 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2096530363] [2025-03-17 20:35:01,387 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 20:35:01,434 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:01,434 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:01,434 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:01,434 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:01,434 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:01,434 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,434 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:01,434 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:01,434 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration3_Loop [2025-03-17 20:35:01,434 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:01,434 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:01,435 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,446 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,451 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,452 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,472 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:01,490 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:01,490 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:01,490 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,491 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:01,492 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-17 20:35:01,494 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-17 20:35:01,495 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:01,495 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:01,519 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:01,519 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:01,521 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-17 20:35:01,522 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-17 20:35:01,523 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:01,523 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:01,854 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:01,865 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-17 20:35:01,865 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:01,865 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:01,865 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:01,865 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:01,865 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:01,865 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,865 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:01,865 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:01,865 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration3_Loop [2025-03-17 20:35:01,865 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:01,865 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:01,866 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,869 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,874 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,876 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:01,903 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:01,903 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:01,903 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,903 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:01,905 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-17 20:35:01,907 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-17 20:35:01,908 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-17 20:35:01,917 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:01,918 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:01,918 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:01,918 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:01,918 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:01,918 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:01,918 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:01,919 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:01,925 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-17 20:35:01,925 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:01,927 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-17 20:35:01,929 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-17 20:35:01,930 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-17 20:35:01,940 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:01,940 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:01,940 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:01,940 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:01,940 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:01,941 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:01,941 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:01,943 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:01,945 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:01,945 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:01,946 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:01,946 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:01,947 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-17 20:35:01,948 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-17 20:35:01,949 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:01,949 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:01,949 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:01,949 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_~x) = -2*f91_~x + 189 Supporting invariants [] [2025-03-17 20:35:01,954 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:01,955 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:01,967 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:01,973 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 20:35:01,983 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:01,983 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:01,983 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:01,984 INFO L256 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 20:35:01,984 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,040 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:02,042 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:02,043 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,043 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,043 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,043 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,062 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-17 20:35:02,062 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-17 20:35:02,063 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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-17 20:35:02,115 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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 42 states and 58 transitions. Complement of second has 13 states. [2025-03-17 20:35:02,117 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-17 20:35:02,117 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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-17 20:35:02,118 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-03-17 20:35:02,118 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 12 letters. Loop has 3 letters. [2025-03-17 20:35:02,118 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:02,118 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:02,129 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,134 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 20:35:02,147 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:02,147 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,147 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,148 INFO L256 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,149 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,196 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:02,200 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:02,201 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,201 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,201 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,202 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,223 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-17 20:35:02,224 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-17 20:35:02,224 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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-17 20:35:02,270 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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 42 states and 58 transitions. Complement of second has 13 states. [2025-03-17 20:35:02,271 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-17 20:35:02,272 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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-17 20:35:02,272 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 10 transitions. [2025-03-17 20:35:02,272 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 10 transitions. Stem has 12 letters. Loop has 3 letters. [2025-03-17 20:35:02,272 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:02,272 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:02,279 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,292 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-17 20:35:02,302 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-17 20:35:02,302 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,302 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,303 INFO L256 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 8 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,303 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,348 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 3 statements into 1 equivalence classes. [2025-03-17 20:35:02,352 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 3 of 3 statements. [2025-03-17 20:35:02,352 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,352 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,352 INFO L256 TraceCheckSpWp]: Trace formula consists of 37 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,352 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,371 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-17 20:35:02,371 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-17 20:35:02,371 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19 Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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-17 20:35:02,426 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 35 states and 50 transitions. cyclomatic complexity: 19. Second operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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 70 states and 99 transitions. Complement of second has 16 states. [2025-03-17 20:35:02,427 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-17 20:35:02,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 2.25) internal successors, (9), 4 states have internal predecessors, (9), 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-17 20:35:02,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2025-03-17 20:35:02,427 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 12 letters. Loop has 3 letters. [2025-03-17 20:35:02,427 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:02,427 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 15 letters. Loop has 3 letters. [2025-03-17 20:35:02,428 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:02,428 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 12 letters. Loop has 6 letters. [2025-03-17 20:35:02,428 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:02,428 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 70 states and 99 transitions. [2025-03-17 20:35:02,430 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 9 [2025-03-17 20:35:02,431 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 70 states to 47 states and 73 transitions. [2025-03-17 20:35:02,431 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 25 [2025-03-17 20:35:02,431 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 27 [2025-03-17 20:35:02,431 INFO L73 IsDeterministic]: Start isDeterministic. Operand 47 states and 73 transitions. [2025-03-17 20:35:02,431 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:02,431 INFO L218 hiAutomatonCegarLoop]: Abstraction has 47 states and 73 transitions. [2025-03-17 20:35:02,431 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states and 73 transitions. [2025-03-17 20:35:02,434 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 41. [2025-03-17 20:35:02,434 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 25 states have (on average 1.04) internal successors, (26), 25 states have internal predecessors, (26), 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-17 20:35:02,434 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 59 transitions. [2025-03-17 20:35:02,434 INFO L240 hiAutomatonCegarLoop]: Abstraction has 41 states and 59 transitions. [2025-03-17 20:35:02,434 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:35:02,435 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2025-03-17 20:35:02,436 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2025-03-17 20:35:02,436 INFO L87 Difference]: Start difference. First operand 41 states and 59 transitions. Second operand has 8 states, 6 states have (on average 1.5) internal successors, (9), 5 states have internal predecessors, (9), 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-17 20:35:02,505 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:35:02,506 INFO L93 Difference]: Finished difference Result 62 states and 81 transitions. [2025-03-17 20:35:02,506 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 62 states and 81 transitions. [2025-03-17 20:35:02,507 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-17 20:35:02,508 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 62 states to 57 states and 74 transitions. [2025-03-17 20:35:02,508 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 41 [2025-03-17 20:35:02,508 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 41 [2025-03-17 20:35:02,508 INFO L73 IsDeterministic]: Start isDeterministic. Operand 57 states and 74 transitions. [2025-03-17 20:35:02,508 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:02,508 INFO L218 hiAutomatonCegarLoop]: Abstraction has 57 states and 74 transitions. [2025-03-17 20:35:02,510 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 57 states and 74 transitions. [2025-03-17 20:35:02,513 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 57 to 56. [2025-03-17 20:35:02,514 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 34 states have (on average 1.0588235294117647) internal successors, (36), 36 states have internal predecessors, (36), 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-17 20:35:02,515 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 73 transitions. [2025-03-17 20:35:02,516 INFO L240 hiAutomatonCegarLoop]: Abstraction has 56 states and 73 transitions. [2025-03-17 20:35:02,516 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2025-03-17 20:35:02,517 INFO L432 stractBuchiCegarLoop]: Abstraction has 56 states and 73 transitions. [2025-03-17 20:35:02,517 INFO L338 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2025-03-17 20:35:02,517 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 56 states and 73 transitions. [2025-03-17 20:35:02,518 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 11 [2025-03-17 20:35:02,520 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:02,520 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:02,520 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2025-03-17 20:35:02,521 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 2, 2, 2, 2, 2, 1, 1] [2025-03-17 20:35:02,521 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;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#19#return;" "#res := #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< [2025-03-17 20:35:02,521 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;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#19#return;" "#res := #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< [2025-03-17 20:35:02,521 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,521 INFO L85 PathProgramCache]: Analyzing trace with hash 1221193575, now seen corresponding path program 1 times [2025-03-17 20:35:02,521 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:02,521 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [888416630] [2025-03-17 20:35:02,521 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:02,521 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:02,524 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:02,527 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:02,527 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,527 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,527 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:02,528 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:02,532 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:02,532 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,532 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,534 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:02,534 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,535 INFO L85 PathProgramCache]: Analyzing trace with hash -466426831, now seen corresponding path program 1 times [2025-03-17 20:35:02,535 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:02,535 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [885172599] [2025-03-17 20:35:02,535 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-17 20:35:02,535 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:02,536 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:02,539 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:02,539 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,539 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,539 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:02,540 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:02,542 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:02,542 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:02,542 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:02,543 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:02,544 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:02,544 INFO L85 PathProgramCache]: Analyzing trace with hash 1315438347, now seen corresponding path program 2 times [2025-03-17 20:35:02,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:02,544 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1908358236] [2025-03-17 20:35:02,544 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:02,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:02,547 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-03-17 20:35:02,558 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-03-17 20:35:02,558 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:02,559 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,577 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-17 20:35:02,690 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-17 20:35:02,691 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:35:02,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1908358236] [2025-03-17 20:35:02,691 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1908358236] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 20:35:02,691 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1517878185] [2025-03-17 20:35:02,691 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:02,691 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 20:35:02,691 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:02,693 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-17 20:35:02,695 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-17 20:35:02,718 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 40 statements into 2 equivalence classes. [2025-03-17 20:35:02,727 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 40 of 40 statements. [2025-03-17 20:35:02,727 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:02,727 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:02,728 INFO L256 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-17 20:35:02,729 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:02,757 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-17 20:35:02,759 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-17 20:35:02,934 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-17 20:35:02,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1517878185] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-17 20:35:02,935 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-17 20:35:02,935 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 15 [2025-03-17 20:35:02,935 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1133609816] [2025-03-17 20:35:02,935 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-17 20:35:03,055 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:03,055 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:03,056 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:03,056 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:03,056 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:03,056 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,056 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:03,056 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:03,056 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration4_Loop [2025-03-17 20:35:03,056 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:03,056 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:03,056 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,059 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,064 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,065 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,066 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,085 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:03,085 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:03,085 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,085 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:03,087 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-17 20:35:03,088 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-17 20:35:03,089 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:03,089 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:03,113 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:03,113 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:03,115 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-17 20:35:03,117 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-17 20:35:03,118 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:03,118 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:03,130 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:03,136 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-17 20:35:03,137 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:03,137 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:03,137 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:03,137 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:03,137 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:03,137 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,137 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:03,137 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:03,137 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration4_Loop [2025-03-17 20:35:03,137 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:03,137 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:03,137 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,143 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,145 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,147 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,148 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:03,172 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:03,172 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:03,172 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,172 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:03,176 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-17 20:35:03,177 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-17 20:35:03,177 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-17 20:35:03,187 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:03,187 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:03,187 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:03,187 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:03,187 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:03,188 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:03,188 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:03,190 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:03,192 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:03,192 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:03,192 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:03,192 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:03,195 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-17 20:35:03,195 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-17 20:35:03,196 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:03,196 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:03,196 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:03,196 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#in~x) = -1*f91_#in~x + 90 Supporting invariants [] [2025-03-17 20:35:03,202 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2025-03-17 20:35:03,203 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:03,212 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,219 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:03,235 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:03,235 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,235 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,236 INFO L256 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,237 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,339 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2025-03-17 20:35:03,372 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:03,385 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:03,385 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,385 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,386 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,387 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:03,549 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-17 20:35:03,549 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 10 loop predicates [2025-03-17 20:35:03,549 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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-17 20:35:03,836 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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 124 states and 149 transitions. Complement of second has 49 states. [2025-03-17 20:35:03,837 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 15 states 2 stem states 12 non-accepting loop states 1 accepting loop states [2025-03-17 20:35:03,838 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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-17 20:35:03,838 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 34 transitions. [2025-03-17 20:35:03,839 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 34 transitions. Stem has 21 letters. Loop has 19 letters. [2025-03-17 20:35:03,839 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:03,839 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:03,847 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:03,856 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:03,877 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:03,877 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:03,877 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:03,878 INFO L256 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 20:35:03,879 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,000 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:04,021 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:04,021 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,021 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,022 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,025 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,183 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-17 20:35:04,183 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 10 loop predicates [2025-03-17 20:35:04,184 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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-17 20:35:04,436 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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 124 states and 149 transitions. Complement of second has 49 states. [2025-03-17 20:35:04,437 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 15 states 2 stem states 12 non-accepting loop states 1 accepting loop states [2025-03-17 20:35:04,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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-17 20:35:04,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 34 transitions. [2025-03-17 20:35:04,438 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 15 states and 34 transitions. Stem has 21 letters. Loop has 19 letters. [2025-03-17 20:35:04,438 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:04,438 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:04,449 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:04,457 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 21 statements into 1 equivalence classes. [2025-03-17 20:35:04,472 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 21 of 21 statements. [2025-03-17 20:35:04,473 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,473 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,474 INFO L256 TraceCheckSpWp]: Trace formula consists of 208 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,475 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,576 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 19 statements into 1 equivalence classes. [2025-03-17 20:35:04,588 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 19 of 19 statements. [2025-03-17 20:35:04,588 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:04,588 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:04,589 INFO L256 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 25 conjuncts are in the unsatisfiable core [2025-03-17 20:35:04,590 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:04,742 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-17 20:35:04,742 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-17 20:35:04,742 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21 Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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-17 20:35:05,257 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 56 states and 73 transitions. cyclomatic complexity: 21. Second operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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 430 states and 530 transitions. Complement of second has 224 states. [2025-03-17 20:35:05,258 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-17 20:35:05,258 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 9 states have (on average 1.7777777777777777) internal successors, (16), 7 states have internal predecessors, (16), 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-17 20:35:05,258 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 49 transitions. [2025-03-17 20:35:05,259 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 49 transitions. Stem has 21 letters. Loop has 19 letters. [2025-03-17 20:35:05,259 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:05,259 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 49 transitions. Stem has 40 letters. Loop has 19 letters. [2025-03-17 20:35:05,259 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:05,260 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 21 states and 49 transitions. Stem has 21 letters. Loop has 38 letters. [2025-03-17 20:35:05,260 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:05,260 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 430 states and 530 transitions. [2025-03-17 20:35:05,266 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 29 [2025-03-17 20:35:05,269 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 430 states to 202 states and 268 transitions. [2025-03-17 20:35:05,269 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 94 [2025-03-17 20:35:05,270 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 105 [2025-03-17 20:35:05,270 INFO L73 IsDeterministic]: Start isDeterministic. Operand 202 states and 268 transitions. [2025-03-17 20:35:05,270 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:05,270 INFO L218 hiAutomatonCegarLoop]: Abstraction has 202 states and 268 transitions. [2025-03-17 20:35:05,270 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 202 states and 268 transitions. [2025-03-17 20:35:05,282 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 202 to 156. [2025-03-17 20:35:05,286 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 156 states, 96 states have (on average 1.09375) internal successors, (105), 98 states have internal predecessors, (105), 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-17 20:35:05,287 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 197 transitions. [2025-03-17 20:35:05,288 INFO L240 hiAutomatonCegarLoop]: Abstraction has 156 states and 197 transitions. [2025-03-17 20:35:05,288 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:35:05,288 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2025-03-17 20:35:05,289 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2025-03-17 20:35:05,289 INFO L87 Difference]: Start difference. First operand 156 states and 197 transitions. Second operand has 15 states, 12 states have (on average 1.75) internal successors, (21), 8 states have internal predecessors, (21), 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-17 20:35:05,441 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:35:05,441 INFO L93 Difference]: Finished difference Result 158 states and 187 transitions. [2025-03-17 20:35:05,441 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 158 states and 187 transitions. [2025-03-17 20:35:05,443 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2025-03-17 20:35:05,444 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 158 states to 103 states and 122 transitions. [2025-03-17 20:35:05,444 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 75 [2025-03-17 20:35:05,445 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 75 [2025-03-17 20:35:05,445 INFO L73 IsDeterministic]: Start isDeterministic. Operand 103 states and 122 transitions. [2025-03-17 20:35:05,445 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2025-03-17 20:35:05,445 INFO L218 hiAutomatonCegarLoop]: Abstraction has 103 states and 122 transitions. [2025-03-17 20:35:05,445 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states and 122 transitions. [2025-03-17 20:35:05,448 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 99. [2025-03-17 20:35:05,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 62 states have (on average 1.0483870967741935) internal successors, (65), 63 states have internal predecessors, (65), 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-17 20:35:05,449 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 118 transitions. [2025-03-17 20:35:05,449 INFO L240 hiAutomatonCegarLoop]: Abstraction has 99 states and 118 transitions. [2025-03-17 20:35:05,455 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-17 20:35:05,455 INFO L432 stractBuchiCegarLoop]: Abstraction has 99 states and 118 transitions. [2025-03-17 20:35:05,455 INFO L338 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2025-03-17 20:35:05,455 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 99 states and 118 transitions. [2025-03-17 20:35:05,456 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2025-03-17 20:35:05,456 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2025-03-17 20:35:05,456 INFO L119 BuchiIsEmpty]: Starting construction of run [2025-03-17 20:35:05,457 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1] [2025-03-17 20:35:05,457 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1] [2025-03-17 20:35:05,457 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;" >"#21#return;" "call #t~ret5 := f91(#t~ret4);"< "~x := #in~x;" "assume ~x > 100;#res := ~x - 10;" "assume true;" >"#19#return;" "#res := #t~ret5;havoc #t~ret4;havoc #t~ret5;" "assume true;" >"#21#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;" >"#21#return;" [2025-03-17 20:35:05,457 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;" >"#21#return;" [2025-03-17 20:35:05,458 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:05,458 INFO L85 PathProgramCache]: Analyzing trace with hash 158007207, now seen corresponding path program 3 times [2025-03-17 20:35:05,458 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:05,458 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [618216977] [2025-03-17 20:35:05,458 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 20:35:05,458 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:05,460 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 31 statements into 7 equivalence classes. [2025-03-17 20:35:05,464 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 26 of 31 statements. [2025-03-17 20:35:05,465 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-17 20:35:05,465 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:05,536 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-17 20:35:05,536 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-17 20:35:05,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [618216977] [2025-03-17 20:35:05,537 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [618216977] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-17 20:35:05,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1439913534] [2025-03-17 20:35:05,537 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2025-03-17 20:35:05,537 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-17 20:35:05,537 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:05,539 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-17 20:35:05,540 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-17 20:35:05,561 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 partitioned 31 statements into 7 equivalence classes. [2025-03-17 20:35:05,570 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) and asserted 26 of 31 statements. [2025-03-17 20:35:05,570 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2025-03-17 20:35:05,570 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:05,571 INFO L256 TraceCheckSpWp]: Trace formula consists of 78 conjuncts, 10 conjuncts are in the unsatisfiable core [2025-03-17 20:35:05,572 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:05,588 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-17 20:35:05,589 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-17 20:35:05,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1439913534] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-17 20:35:05,589 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-03-17 20:35:05,589 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 9 [2025-03-17 20:35:05,589 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2044278923] [2025-03-17 20:35:05,589 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-17 20:35:05,589 INFO L757 eck$LassoCheckResult]: stem already infeasible [2025-03-17 20:35:05,589 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:05,590 INFO L85 PathProgramCache]: Analyzing trace with hash -570415228, now seen corresponding path program 2 times [2025-03-17 20:35:05,590 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-17 20:35:05,590 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [271086614] [2025-03-17 20:35:05,590 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-17 20:35:05,590 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-17 20:35:05,592 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 8 statements into 2 equivalence classes. [2025-03-17 20:35:05,593 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:05,593 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-17 20:35:05,593 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:05,593 INFO L348 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2025-03-17 20:35:05,594 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:05,598 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:05,598 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:05,598 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is sat [2025-03-17 20:35:05,599 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2025-03-17 20:35:05,687 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:05,687 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:05,687 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:05,687 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:05,687 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2025-03-17 20:35:05,687 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:05,687 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:05,687 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:05,687 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration5_Loop [2025-03-17 20:35:05,687 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:05,687 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:05,688 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:05,690 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:05,698 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:05,720 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:05,720 INFO L365 LassoAnalysis]: Checking for nontermination... [2025-03-17 20:35:05,720 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:05,720 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:05,722 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-17 20:35:05,723 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-17 20:35:05,723 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:05,723 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:05,734 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2025-03-17 20:35:05,734 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {f91_#res=0} Honda state: {f91_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2025-03-17 20:35:05,740 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-17 20:35:05,740 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:05,740 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:05,742 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-17 20:35:05,742 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-17 20:35:05,743 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2025-03-17 20:35:05,743 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:05,772 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-17 20:35:05,773 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:05,773 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:05,775 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-17 20:35:05,776 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-17 20:35:05,776 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2025-03-17 20:35:05,776 INFO L160 nArgumentSynthesizer]: Using integer mode. [2025-03-17 20:35:06,326 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2025-03-17 20:35:06,342 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-17 20:35:06,342 INFO L204 LassoAnalysis]: Preferences: [2025-03-17 20:35:06,342 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2025-03-17 20:35:06,342 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2025-03-17 20:35:06,342 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2025-03-17 20:35:06,342 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2025-03-17 20:35:06,342 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:06,342 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2025-03-17 20:35:06,342 INFO L131 ssoRankerPreferences]: Path of dumped script: [2025-03-17 20:35:06,342 INFO L132 ssoRankerPreferences]: Filename of dumped script: McCarthy91-1.c_Iteration5_Loop [2025-03-17 20:35:06,342 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2025-03-17 20:35:06,342 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2025-03-17 20:35:06,343 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:06,345 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:06,346 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2025-03-17 20:35:06,372 INFO L259 LassoAnalysis]: Preprocessing complete. [2025-03-17 20:35:06,372 INFO L451 LassoAnalysis]: Using template 'affine'. [2025-03-17 20:35:06,372 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:06,372 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:06,374 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-17 20:35:06,375 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-17 20:35:06,376 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-17 20:35:06,385 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:06,385 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:06,385 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:06,385 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:06,385 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:06,386 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:06,386 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:06,387 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:06,392 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-17 20:35:06,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:06,392 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:06,394 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-17 20:35:06,394 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-17 20:35:06,395 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-17 20:35:06,404 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:06,405 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:06,405 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:06,405 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:06,405 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:06,405 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:06,405 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:06,406 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2025-03-17 20:35:06,411 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-17 20:35:06,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:06,411 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:06,413 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-17 20:35:06,413 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-17 20:35:06,414 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-17 20:35:06,424 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2025-03-17 20:35:06,424 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2025-03-17 20:35:06,424 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2025-03-17 20:35:06,424 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2025-03-17 20:35:06,424 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2025-03-17 20:35:06,425 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2025-03-17 20:35:06,425 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2025-03-17 20:35:06,427 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2025-03-17 20:35:06,429 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2025-03-17 20:35:06,429 INFO L444 ModelExtractionUtils]: 2 out of 5 variables were initially zero. Simplification set additionally 0 variables to zero. [2025-03-17 20:35:06,429 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2025-03-17 20:35:06,429 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-17 20:35:06,432 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-17 20:35:06,433 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-17 20:35:06,434 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2025-03-17 20:35:06,434 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2025-03-17 20:35:06,434 INFO L474 LassoAnalysis]: Proved termination. [2025-03-17 20:35:06,434 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(f91_#t~ret4) = -2*f91_#t~ret4 + 201 Supporting invariants [] [2025-03-17 20:35:06,439 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-17 20:35:06,440 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2025-03-17 20:35:06,441 WARN L970 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret4 [2025-03-17 20:35:06,448 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:06,460 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:35:06,480 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:35:06,480 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:06,480 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:06,481 INFO L256 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 20:35:06,482 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:06,613 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:06,619 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:06,619 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:06,619 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:06,620 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 20:35:06,620 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:06,676 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-17 20:35:06,676 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-17 20:35:06,676 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-17 20:35:06,773 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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 138 states and 160 transitions. Complement of second has 24 states. [2025-03-17 20:35:06,776 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-17 20:35:06,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-17 20:35:06,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 16 transitions. [2025-03-17 20:35:06,777 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 31 letters. Loop has 8 letters. [2025-03-17 20:35:06,777 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:06,777 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:06,790 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:06,804 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:35:06,828 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:35:06,828 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:06,828 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:06,829 INFO L256 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 20:35:06,830 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:06,965 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:06,973 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:06,973 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:06,973 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:06,974 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 20:35:06,974 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:07,043 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-17 20:35:07,045 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-17 20:35:07,045 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-17 20:35:07,165 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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 138 states and 160 transitions. Complement of second has 24 states. [2025-03-17 20:35:07,166 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-17 20:35:07,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-17 20:35:07,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 16 transitions. [2025-03-17 20:35:07,167 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 31 letters. Loop has 8 letters. [2025-03-17 20:35:07,167 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:07,167 INFO L689 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2025-03-17 20:35:07,176 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-17 20:35:07,191 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-17 20:35:07,212 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-17 20:35:07,212 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:07,212 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:07,213 INFO L256 TraceCheckSpWp]: Trace formula consists of 286 conjuncts, 16 conjuncts are in the unsatisfiable core [2025-03-17 20:35:07,214 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:07,294 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2025-03-17 20:35:07,353 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-03-17 20:35:07,361 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-03-17 20:35:07,361 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-17 20:35:07,361 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-17 20:35:07,361 INFO L256 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 13 conjuncts are in the unsatisfiable core [2025-03-17 20:35:07,361 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-17 20:35:07,416 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-17 20:35:07,416 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-17 20:35:07,416 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24 Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-17 20:35:07,517 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 24. Second operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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 180 states and 210 transitions. Complement of second has 27 states. [2025-03-17 20:35:07,518 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-17 20:35:07,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-17 20:35:07,518 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 20 transitions. [2025-03-17 20:35:07,518 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 20 transitions. Stem has 31 letters. Loop has 8 letters. [2025-03-17 20:35:07,519 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:07,519 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 20 transitions. Stem has 39 letters. Loop has 8 letters. [2025-03-17 20:35:07,519 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:07,519 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 20 transitions. Stem has 31 letters. Loop has 16 letters. [2025-03-17 20:35:07,519 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2025-03-17 20:35:07,519 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 180 states and 210 transitions. [2025-03-17 20:35:07,521 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 20:35:07,521 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 180 states to 0 states and 0 transitions. [2025-03-17 20:35:07,521 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-17 20:35:07,521 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-17 20:35:07,521 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-17 20:35:07,521 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-17 20:35:07,521 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:07,521 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:07,521 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-17 20:35:07,522 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2025-03-17 20:35:07,522 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2025-03-17 20:35:07,522 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 9 states, 8 states have (on average 1.875) internal successors, (15), 5 states have internal predecessors, (15), 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-17 20:35:07,522 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-17 20:35:07,522 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2025-03-17 20:35:07,522 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2025-03-17 20:35:07,522 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 20:35:07,523 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2025-03-17 20:35:07,523 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2025-03-17 20:35:07,523 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2025-03-17 20:35:07,523 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2025-03-17 20:35:07,523 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2025-03-17 20:35:07,523 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:07,523 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:07,523 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-03-17 20:35:07,523 INFO L432 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-03-17 20:35:07,523 INFO L338 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2025-03-17 20:35:07,523 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2025-03-17 20:35:07,523 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2025-03-17 20:35:07,523 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2025-03-17 20:35:07,530 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 17.03 08:35:07 BoogieIcfgContainer [2025-03-17 20:35:07,531 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2025-03-17 20:35:07,531 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-03-17 20:35:07,531 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-03-17 20:35:07,532 INFO L274 PluginConnector]: Witness Printer initialized [2025-03-17 20:35:07,532 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.03 08:34:58" (3/4) ... [2025-03-17 20:35:07,533 INFO L149 WitnessPrinter]: No result that supports witness generation found [2025-03-17 20:35:07,534 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-03-17 20:35:07,535 INFO L158 Benchmark]: Toolchain (without parser) took 9071.52ms. Allocated memory was 142.6MB in the beginning and 285.2MB in the end (delta: 142.6MB). Free memory was 110.4MB in the beginning and 216.8MB in the end (delta: -106.4MB). Peak memory consumption was 37.0MB. Max. memory is 16.1GB. [2025-03-17 20:35:07,535 INFO L158 Benchmark]: CDTParser took 0.21ms. Allocated memory is still 201.3MB. Free memory is still 127.7MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:07,535 INFO L158 Benchmark]: CACSL2BoogieTranslator took 149.44ms. Allocated memory is still 142.6MB. Free memory was 110.4MB in the beginning and 100.3MB in the end (delta: 10.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-17 20:35:07,535 INFO L158 Benchmark]: Boogie Procedure Inliner took 21.02ms. Allocated memory is still 142.6MB. Free memory was 100.3MB in the beginning and 99.3MB in the end (delta: 998.0kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:07,536 INFO L158 Benchmark]: Boogie Preprocessor took 20.73ms. Allocated memory is still 142.6MB. Free memory was 98.4MB in the beginning and 97.4MB in the end (delta: 961.6kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:07,536 INFO L158 Benchmark]: IcfgBuilder took 183.25ms. Allocated memory is still 142.6MB. Free memory was 97.4MB in the beginning and 87.2MB in the end (delta: 10.2MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-17 20:35:07,536 INFO L158 Benchmark]: BuchiAutomizer took 8688.71ms. Allocated memory was 142.6MB in the beginning and 285.2MB in the end (delta: 142.6MB). Free memory was 87.2MB in the beginning and 216.9MB in the end (delta: -129.6MB). Peak memory consumption was 11.8MB. Max. memory is 16.1GB. [2025-03-17 20:35:07,537 INFO L158 Benchmark]: Witness Printer took 2.80ms. Allocated memory is still 285.2MB. Free memory was 216.9MB in the beginning and 216.8MB in the end (delta: 87.7kB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-17 20:35:07,538 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.21ms. Allocated memory is still 201.3MB. Free memory is still 127.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 149.44ms. Allocated memory is still 142.6MB. Free memory was 110.4MB in the beginning and 100.3MB in the end (delta: 10.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 21.02ms. Allocated memory is still 142.6MB. Free memory was 100.3MB in the beginning and 99.3MB in the end (delta: 998.0kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 20.73ms. Allocated memory is still 142.6MB. Free memory was 98.4MB in the beginning and 97.4MB in the end (delta: 961.6kB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 183.25ms. Allocated memory is still 142.6MB. Free memory was 97.4MB in the beginning and 87.2MB in the end (delta: 10.2MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * BuchiAutomizer took 8688.71ms. Allocated memory was 142.6MB in the beginning and 285.2MB in the end (delta: 142.6MB). Free memory was 87.2MB in the beginning and 216.9MB in the end (delta: -129.6MB). Peak memory consumption was 11.8MB. Max. memory is 16.1GB. * Witness Printer took 2.80ms. Allocated memory is still 285.2MB. Free memory was 216.9MB in the beginning and 216.8MB in the end (delta: 87.7kB). There was no memory consumed. 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.0s. Construction of modules took 0.5s. Büchi inclusion checks took 3.9s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 6. Automata minimization 0.0s 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, 251 SdHoareTripleChecker+Valid, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 238 mSDsluCounter, 371 SdHoareTripleChecker+Invalid, 0.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 212 mSDsCounter, 202 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 808 IncrementalHoareTripleChecker+Invalid, 1010 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 202 mSolverCounterUnsat, 159 mSDtfsCounter, 808 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: 25ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 4 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.8s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2025-03-17 20:35:07,550 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-17 20:35:07,750 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2025-03-17 20:35:07,952 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