./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/termination-crafted/RecursiveMultiplication-1.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version c7c6ca5d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/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.5.800.v20200727-1323.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/termination-crafted/RecursiveMultiplication-1.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-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 64bit --witnessprinter.graph.data.programhash 759adb73d7cf84e38b053793a18c9790a1be4e7fcbaa9f1ea135fb0a39711b48 --- Real Ultimate output --- This is Ultimate 0.2.5-?-c7c6ca5-m [2024-11-09 15:18:49,761 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 15:18:49,831 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-11-09 15:18:49,836 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 15:18:49,839 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 15:18:49,862 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 15:18:49,862 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 15:18:49,863 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 15:18:49,863 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 15:18:49,864 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 15:18:49,864 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 15:18:49,864 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 15:18:49,865 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 15:18:49,865 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-09 15:18:49,865 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-09 15:18:49,866 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-09 15:18:49,866 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-09 15:18:49,866 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-09 15:18:49,867 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-09 15:18:49,867 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 15:18:49,867 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-09 15:18:49,871 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 15:18:49,871 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 15:18:49,871 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-09 15:18:49,872 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-09 15:18:49,872 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-09 15:18:49,872 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 15:18:49,872 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 15:18:49,873 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 15:18:49,873 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-09 15:18:49,873 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 15:18:49,873 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 15:18:49,874 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 15:18:49,874 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 15:18:49,874 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 15:18:49,875 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-09 15:18:49,877 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: 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 -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 759adb73d7cf84e38b053793a18c9790a1be4e7fcbaa9f1ea135fb0a39711b48 [2024-11-09 15:18:50,139 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 15:18:50,163 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 15:18:50,168 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 15:18:50,169 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 15:18:50,170 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 15:18:50,171 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-crafted/RecursiveMultiplication-1.c [2024-11-09 15:18:51,600 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 15:18:51,752 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 15:18:51,753 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-crafted/RecursiveMultiplication-1.c [2024-11-09 15:18:51,759 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b42eb7ab5/fd9c99b8b70541e1bacbebc6435dd96b/FLAG146454729 [2024-11-09 15:18:52,165 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/b42eb7ab5/fd9c99b8b70541e1bacbebc6435dd96b [2024-11-09 15:18:52,168 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 15:18:52,169 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 15:18:52,171 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 15:18:52,171 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 15:18:52,176 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 15:18:52,176 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,177 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5f9ca901 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52, skipping insertion in model container [2024-11-09 15:18:52,177 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,194 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 15:18:52,414 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 15:18:52,426 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 15:18:52,442 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 15:18:52,459 INFO L204 MainTranslator]: Completed translation [2024-11-09 15:18:52,459 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52 WrapperNode [2024-11-09 15:18:52,460 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 15:18:52,461 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 15:18:52,461 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 15:18:52,461 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 15:18:52,469 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,473 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,489 INFO L138 Inliner]: procedures = 5, calls = 5, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 19 [2024-11-09 15:18:52,490 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 15:18:52,491 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 15:18:52,491 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 15:18:52,492 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 15:18:52,500 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,501 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,502 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,508 INFO L175 MemorySlicer]: No memory access in input program. [2024-11-09 15:18:52,509 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,509 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,511 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,512 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,514 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,514 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,518 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 15:18:52,519 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 15:18:52,520 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 15:18:52,520 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 15:18:52,520 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (1/1) ... [2024-11-09 15:18:52,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:52,543 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:52,559 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) [2024-11-09 15:18:52,562 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 [2024-11-09 15:18:52,609 INFO L130 BoogieDeclarations]: Found specification of procedure mult [2024-11-09 15:18:52,610 INFO L138 BoogieDeclarations]: Found implementation of procedure mult [2024-11-09 15:18:52,611 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 15:18:52,611 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 15:18:52,659 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 15:18:52,661 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 15:18:52,747 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2024-11-09 15:18:52,748 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 15:18:52,765 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 15:18:52,767 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-09 15:18:52,768 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 03:18:52 BoogieIcfgContainer [2024-11-09 15:18:52,768 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 15:18:52,769 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-09 15:18:52,769 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-09 15:18:52,773 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-09 15:18:52,774 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 15:18:52,774 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.11 03:18:52" (1/3) ... [2024-11-09 15:18:52,775 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@3e95a20f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 03:18:52, skipping insertion in model container [2024-11-09 15:18:52,775 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 15:18:52,775 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:18:52" (2/3) ... [2024-11-09 15:18:52,777 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@3e95a20f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 03:18:52, skipping insertion in model container [2024-11-09 15:18:52,777 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 15:18:52,777 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 03:18:52" (3/3) ... [2024-11-09 15:18:52,778 INFO L332 chiAutomizerObserver]: Analyzing ICFG RecursiveMultiplication-1.c [2024-11-09 15:18:52,826 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-09 15:18:52,826 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-09 15:18:52,826 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-09 15:18:52,827 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-09 15:18:52,827 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-09 15:18:52,827 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-09 15:18:52,827 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-09 15:18:52,827 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-09 15:18:52,831 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 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) [2024-11-09 15:18:52,848 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 15:18:52,848 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:52,848 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:52,857 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1] [2024-11-09 15:18:52,857 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 15:18:52,857 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-09 15:18:52,858 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 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) [2024-11-09 15:18:52,860 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 15:18:52,860 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:52,860 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:52,860 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1] [2024-11-09 15:18:52,861 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 15:18:52,867 INFO L745 eck$LassoCheckResult]: Stem: 15#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true; 11#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet2#1, main_#t~nondet3#1, main_#t~ret4#1, main_~m~0#1, main_~n~0#1, main_~res~0#1;havoc main_#t~nondet2#1;main_~m~0#1 := main_#t~nondet2#1;havoc main_#t~nondet2#1;havoc main_#t~nondet3#1;main_~n~0#1 := main_#t~nondet3#1;havoc main_#t~nondet3#1; 9#L26true assume !!(-65535 <= main_~m~0#1 && main_~m~0#1 <= 65535); 5#L27true assume !!(-65535 <= main_~n~0#1 && main_~n~0#1 <= 65535); 14#L28true call main_#t~ret4#1 := mult(main_~m~0#1, main_~n~0#1);< 3#$Ultimate##0true [2024-11-09 15:18:52,868 INFO L747 eck$LassoCheckResult]: Loop: 3#$Ultimate##0true ~n := #in~n;~m := #in~m; 4#L13true assume ~m < 0; 17#L14true call #t~ret0 := mult(~n, -~m);< 3#$Ultimate##0true [2024-11-09 15:18:52,872 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:52,872 INFO L85 PathProgramCache]: Analyzing trace with hash 42056124, now seen corresponding path program 1 times [2024-11-09 15:18:52,881 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:52,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1413916155] [2024-11-09 15:18:52,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:52,882 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:52,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:52,955 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:52,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:52,975 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:52,977 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:52,978 INFO L85 PathProgramCache]: Analyzing trace with hash 29916, now seen corresponding path program 1 times [2024-11-09 15:18:52,978 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:52,978 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [760937547] [2024-11-09 15:18:52,978 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:52,979 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:52,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:52,986 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:52,990 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:52,992 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:52,993 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:52,993 INFO L85 PathProgramCache]: Analyzing trace with hash -1236460223, now seen corresponding path program 1 times [2024-11-09 15:18:52,994 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:52,994 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [400061943] [2024-11-09 15:18:52,994 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:52,994 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:53,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:53,004 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:53,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:53,012 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:53,129 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:53,129 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:53,130 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:53,130 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:53,130 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 15:18:53,130 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,131 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:53,131 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:53,131 INFO L132 ssoRankerPreferences]: Filename of dumped script: RecursiveMultiplication-1.c_Iteration1_Loop [2024-11-09 15:18:53,131 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:53,131 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:53,149 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,159 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,163 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,171 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,180 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,183 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,189 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,271 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:53,272 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 15:18:53,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,275 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,277 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) [2024-11-09 15:18:53,278 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 [2024-11-09 15:18:53,281 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:53,281 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:53,298 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:53,299 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_#t~ret1=0} Honda state: {mult_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:53,310 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:53,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,311 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,313 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) [2024-11-09 15:18:53,314 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 [2024-11-09 15:18:53,315 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:53,315 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:53,331 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:53,331 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_#res=0} Honda state: {mult_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:53,347 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 [2024-11-09 15:18:53,348 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,348 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,350 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) [2024-11-09 15:18:53,351 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 [2024-11-09 15:18:53,352 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:53,352 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:53,366 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:53,366 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_~n=0} Honda state: {mult_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:53,382 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:53,383 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,383 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,385 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) [2024-11-09 15:18:53,387 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 [2024-11-09 15:18:53,389 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:53,389 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:53,407 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:53,407 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_#in~n=0} Honda state: {mult_#in~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:53,421 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 [2024-11-09 15:18:53,421 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,422 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,423 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) [2024-11-09 15:18:53,424 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 [2024-11-09 15:18:53,425 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:53,425 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:53,436 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:53,436 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_#t~ret0=0} Honda state: {mult_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:53,447 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 [2024-11-09 15:18:53,447 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,448 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,449 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) [2024-11-09 15:18:53,451 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 [2024-11-09 15:18:53,452 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:53,452 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:53,467 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:53,467 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_~m=0} Honda state: {mult_~m=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:53,478 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 [2024-11-09 15:18:53,479 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,479 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,480 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) [2024-11-09 15:18:53,482 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 [2024-11-09 15:18:53,484 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:53,484 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:53,507 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 [2024-11-09 15:18:53,508 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,508 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,509 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) [2024-11-09 15:18:53,510 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 [2024-11-09 15:18:53,511 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 15:18:53,511 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:53,546 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 15:18:53,550 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 [2024-11-09 15:18:53,551 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:53,551 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:53,551 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:53,551 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:53,551 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:18:53,552 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,552 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:53,552 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:53,552 INFO L132 ssoRankerPreferences]: Filename of dumped script: RecursiveMultiplication-1.c_Iteration1_Loop [2024-11-09 15:18:53,552 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:53,552 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:53,553 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,556 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,558 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,561 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,563 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,566 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,569 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:53,624 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:53,628 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:18:53,630 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,630 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,632 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) [2024-11-09 15:18:53,633 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 [2024-11-09 15:18:53,634 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 [2024-11-09 15:18:53,648 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:53,648 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:53,649 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:53,649 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:53,649 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:53,651 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:53,651 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:53,655 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:53,666 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 [2024-11-09 15:18:53,666 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,667 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,668 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) [2024-11-09 15:18:53,670 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 [2024-11-09 15:18:53,672 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 [2024-11-09 15:18:53,685 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:53,685 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:53,685 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:53,685 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:53,685 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:53,687 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:53,687 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:53,689 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:53,705 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 [2024-11-09 15:18:53,705 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,705 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,708 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) [2024-11-09 15:18:53,709 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 [2024-11-09 15:18:53,710 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 [2024-11-09 15:18:53,724 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:53,724 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:53,725 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:53,725 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:53,725 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:53,725 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:53,726 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:53,729 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:53,744 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2024-11-09 15:18:53,744 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,746 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) [2024-11-09 15:18:53,747 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 [2024-11-09 15:18:53,748 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 [2024-11-09 15:18:53,758 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:53,758 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:53,758 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:53,758 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:53,758 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:53,759 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:53,759 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:53,761 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:53,773 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 [2024-11-09 15:18:53,773 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,773 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,774 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) [2024-11-09 15:18:53,775 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 [2024-11-09 15:18:53,776 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-09 15:18:53,786 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:53,786 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:53,786 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:53,786 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:53,786 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:53,787 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:53,787 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:53,789 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:53,801 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-11-09 15:18:53,801 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,802 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,803 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) [2024-11-09 15:18:53,804 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 [2024-11-09 15:18:53,805 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 [2024-11-09 15:18:53,815 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:53,815 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:53,815 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:53,815 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:53,816 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:53,816 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:53,816 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:53,818 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:53,857 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 [2024-11-09 15:18:53,858 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,858 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,864 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) [2024-11-09 15:18:53,865 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 [2024-11-09 15:18:53,866 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 [2024-11-09 15:18:53,875 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:53,876 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:53,876 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:53,876 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:53,876 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:53,877 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:53,877 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:53,891 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:18:53,893 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-09 15:18:53,894 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 15:18:53,895 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:53,895 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:53,897 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) [2024-11-09 15:18:53,898 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 [2024-11-09 15:18:53,899 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:18:53,899 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 15:18:53,899 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:18:53,900 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mult_#in~m) = -1*mult_#in~m Supporting invariants [] [2024-11-09 15:18:53,911 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:53,914 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 15:18:53,950 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:53,970 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:53,973 INFO L255 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-09 15:18:53,974 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:54,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:54,004 INFO L255 TraceCheckSpWp]: Trace formula consists of 41 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:54,005 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:54,054 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 15:18:54,081 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 [2024-11-09 15:18:54,083 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 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 2.0) internal successors, (6), 3 states have internal predecessors, (6), 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) [2024-11-09 15:18:54,193 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-11-09 15:18:54,219 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 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 2.0) internal successors, (6), 3 states have internal predecessors, (6), 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 47 states and 60 transitions. Complement of second has 16 states. [2024-11-09 15:18:54,224 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 [2024-11-09 15:18:54,231 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 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) [2024-11-09 15:18:54,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 16 transitions. [2024-11-09 15:18:54,234 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 5 letters. Loop has 3 letters. [2024-11-09 15:18:54,235 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:54,235 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 8 letters. Loop has 3 letters. [2024-11-09 15:18:54,235 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:54,235 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 16 transitions. Stem has 5 letters. Loop has 6 letters. [2024-11-09 15:18:54,235 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:54,236 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 47 states and 60 transitions. [2024-11-09 15:18:54,239 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 15:18:54,243 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 47 states to 22 states and 25 transitions. [2024-11-09 15:18:54,243 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-09 15:18:54,244 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 17 [2024-11-09 15:18:54,244 INFO L73 IsDeterministic]: Start isDeterministic. Operand 22 states and 25 transitions. [2024-11-09 15:18:54,244 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:54,245 INFO L218 hiAutomatonCegarLoop]: Abstraction has 22 states and 25 transitions. [2024-11-09 15:18:54,258 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states and 25 transitions. [2024-11-09 15:18:54,266 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 15. [2024-11-09 15:18:54,267 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 11 states have internal predecessors, (14), 4 states have call successors, (4), 3 states have call predecessors, (4), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 15:18:54,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 18 transitions. [2024-11-09 15:18:54,269 INFO L240 hiAutomatonCegarLoop]: Abstraction has 15 states and 18 transitions. [2024-11-09 15:18:54,269 INFO L425 stractBuchiCegarLoop]: Abstraction has 15 states and 18 transitions. [2024-11-09 15:18:54,270 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-09 15:18:54,270 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 15 states and 18 transitions. [2024-11-09 15:18:54,270 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 15:18:54,270 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:54,271 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:54,272 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:18:54,272 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-09 15:18:54,272 INFO L745 eck$LassoCheckResult]: Stem: 136#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 137#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet2#1, main_#t~nondet3#1, main_#t~ret4#1, main_~m~0#1, main_~n~0#1, main_~res~0#1;havoc main_#t~nondet2#1;main_~m~0#1 := main_#t~nondet2#1;havoc main_#t~nondet2#1;havoc main_#t~nondet3#1;main_~n~0#1 := main_#t~nondet3#1;havoc main_#t~nondet3#1; 141#L26 assume !!(-65535 <= main_~m~0#1 && main_~m~0#1 <= 65535); 135#L27 assume !!(-65535 <= main_~n~0#1 && main_~n~0#1 <= 65535); 131#L28 call main_#t~ret4#1 := mult(main_~m~0#1, main_~n~0#1);< 133#$Ultimate##0 ~n := #in~n;~m := #in~m; 128#L13 assume !(~m < 0); 130#L16 [2024-11-09 15:18:54,273 INFO L747 eck$LassoCheckResult]: Loop: 130#L16 assume !(0 == ~m); 138#L19 call #t~ret1 := mult(~n, ~m - 1);< 139#$Ultimate##0 ~n := #in~n;~m := #in~m; 142#L13 assume !(~m < 0); 130#L16 [2024-11-09 15:18:54,273 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:54,273 INFO L85 PathProgramCache]: Analyzing trace with hash 1761229506, now seen corresponding path program 1 times [2024-11-09 15:18:54,274 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:54,274 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [390239868] [2024-11-09 15:18:54,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:54,274 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:54,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:54,282 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:54,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:54,287 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:54,288 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:54,288 INFO L85 PathProgramCache]: Analyzing trace with hash 1254111, now seen corresponding path program 1 times [2024-11-09 15:18:54,288 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:54,288 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [336399676] [2024-11-09 15:18:54,288 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:54,289 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:54,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:54,293 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:54,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:54,297 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:54,297 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:54,298 INFO L85 PathProgramCache]: Analyzing trace with hash -1744825056, now seen corresponding path program 1 times [2024-11-09 15:18:54,298 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:54,298 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [838154739] [2024-11-09 15:18:54,298 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:54,298 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:54,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:54,307 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:54,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:54,323 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:54,419 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:54,419 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:54,419 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:54,419 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:54,419 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 15:18:54,419 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:54,420 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:54,420 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:54,420 INFO L132 ssoRankerPreferences]: Filename of dumped script: RecursiveMultiplication-1.c_Iteration2_Loop [2024-11-09 15:18:54,420 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:54,420 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:54,421 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:54,423 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:54,425 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:54,427 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:54,435 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:54,481 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:54,481 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 15:18:54,482 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:54,482 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:54,483 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) [2024-11-09 15:18:54,485 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 [2024-11-09 15:18:54,486 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:54,486 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:54,497 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:54,497 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_#t~ret0=0} Honda state: {mult_#t~ret0=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:54,508 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:54,509 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:54,509 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:54,510 INFO L229 MonitoredProcess]: Starting monitored process 19 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) [2024-11-09 15:18:54,511 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-09 15:18:54,512 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:54,512 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:54,523 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:54,523 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_#t~ret1=0} Honda state: {mult_#t~ret1=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:54,535 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:54,535 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:54,536 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:54,537 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) [2024-11-09 15:18:54,538 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 [2024-11-09 15:18:54,539 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:54,539 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:54,551 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:54,551 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_#res=0} Honda state: {mult_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:54,562 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-11-09 15:18:54,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:54,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:54,564 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) [2024-11-09 15:18:54,565 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 [2024-11-09 15:18:54,566 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:54,566 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:54,595 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:54,596 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:54,596 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:54,598 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) [2024-11-09 15:18:54,599 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 [2024-11-09 15:18:54,599 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 15:18:54,599 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:56,768 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 15:18:56,773 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 [2024-11-09 15:18:56,774 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:56,774 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:56,774 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:56,774 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:56,774 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:18:56,774 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:56,774 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:56,774 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:56,774 INFO L132 ssoRankerPreferences]: Filename of dumped script: RecursiveMultiplication-1.c_Iteration2_Loop [2024-11-09 15:18:56,774 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:56,774 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:56,775 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:56,779 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:56,786 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:56,788 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:56,798 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:56,854 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:56,855 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:18:56,855 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:56,855 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:56,857 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) [2024-11-09 15:18:56,859 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 [2024-11-09 15:18:56,859 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 [2024-11-09 15:18:56,872 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:56,872 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:56,872 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:56,872 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:56,872 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:56,873 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:56,873 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:56,875 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:56,889 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 [2024-11-09 15:18:56,890 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:56,890 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:56,891 INFO L229 MonitoredProcess]: Starting monitored process 24 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) [2024-11-09 15:18:56,893 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-11-09 15:18:56,894 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 [2024-11-09 15:18:56,906 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:56,906 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:56,907 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:56,907 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:56,907 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:56,908 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:56,908 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:56,912 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:56,926 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:56,927 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:56,927 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:56,929 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) [2024-11-09 15:18:56,929 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 [2024-11-09 15:18:56,931 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 [2024-11-09 15:18:56,943 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:56,943 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:56,944 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:56,944 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:56,944 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:56,944 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:56,945 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:56,950 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:56,963 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:56,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:56,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:56,966 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) [2024-11-09 15:18:56,968 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 [2024-11-09 15:18:56,969 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 [2024-11-09 15:18:56,982 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:56,983 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:56,983 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:56,983 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:56,983 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:56,986 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:56,986 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:56,988 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:18:56,993 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 15:18:56,997 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 15:18:56,997 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:56,997 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:56,999 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) [2024-11-09 15:18:57,000 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 [2024-11-09 15:18:57,001 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:18:57,001 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 15:18:57,002 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:18:57,002 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mult_~m) = 1*mult_~m Supporting invariants [] [2024-11-09 15:18:57,016 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 [2024-11-09 15:18:57,017 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 15:18:57,030 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:57,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:57,047 INFO L255 TraceCheckSpWp]: Trace formula consists of 47 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-09 15:18:57,048 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:57,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:57,082 INFO L255 TraceCheckSpWp]: Trace formula consists of 42 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 15:18:57,083 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:57,201 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 15:18:57,202 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 4 loop predicates [2024-11-09 15:18:57,202 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 15 states and 18 transitions. cyclomatic complexity: 5 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, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 15:18:57,373 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 15 states and 18 transitions. cyclomatic complexity: 5. 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, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 27 states and 32 transitions. Complement of second has 15 states. [2024-11-09 15:18:57,375 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 1 stem states 4 non-accepting loop states 1 accepting loop states [2024-11-09 15:18:57,376 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, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 15:18:57,377 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 14 transitions. [2024-11-09 15:18:57,377 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 14 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-09 15:18:57,377 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:57,378 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 14 transitions. Stem has 11 letters. Loop has 4 letters. [2024-11-09 15:18:57,378 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:57,378 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 14 transitions. Stem has 7 letters. Loop has 8 letters. [2024-11-09 15:18:57,378 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:57,378 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 27 states and 32 transitions. [2024-11-09 15:18:57,380 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 15:18:57,383 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 27 states to 26 states and 31 transitions. [2024-11-09 15:18:57,383 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 16 [2024-11-09 15:18:57,383 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 18 [2024-11-09 15:18:57,383 INFO L73 IsDeterministic]: Start isDeterministic. Operand 26 states and 31 transitions. [2024-11-09 15:18:57,383 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:57,383 INFO L218 hiAutomatonCegarLoop]: Abstraction has 26 states and 31 transitions. [2024-11-09 15:18:57,383 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states and 31 transitions. [2024-11-09 15:18:57,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 23. [2024-11-09 15:18:57,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 17 states have internal predecessors, (22), 6 states have call successors, (6), 5 states have call predecessors, (6), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 15:18:57,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 28 transitions. [2024-11-09 15:18:57,386 INFO L240 hiAutomatonCegarLoop]: Abstraction has 23 states and 28 transitions. [2024-11-09 15:18:57,386 INFO L425 stractBuchiCegarLoop]: Abstraction has 23 states and 28 transitions. [2024-11-09 15:18:57,386 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-09 15:18:57,388 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 23 states and 28 transitions. [2024-11-09 15:18:57,389 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 15:18:57,390 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:18:57,390 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:18:57,390 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:18:57,391 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 15:18:57,391 INFO L745 eck$LassoCheckResult]: Stem: 251#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true; 252#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet2#1, main_#t~nondet3#1, main_#t~ret4#1, main_~m~0#1, main_~n~0#1, main_~res~0#1;havoc main_#t~nondet2#1;main_~m~0#1 := main_#t~nondet2#1;havoc main_#t~nondet2#1;havoc main_#t~nondet3#1;main_~n~0#1 := main_#t~nondet3#1;havoc main_#t~nondet3#1; 253#L26 assume !!(-65535 <= main_~m~0#1 && main_~m~0#1 <= 65535); 249#L27 assume !!(-65535 <= main_~n~0#1 && main_~n~0#1 <= 65535); 248#L28 call main_#t~ret4#1 := mult(main_~m~0#1, main_~n~0#1);< 250#$Ultimate##0 ~n := #in~n;~m := #in~m; 245#L13 assume !(~m < 0); 262#L16 assume !(0 == ~m); 241#L19 call #t~ret1 := mult(~n, ~m - 1);< 240#$Ultimate##0 ~n := #in~n;~m := #in~m; 242#L13 assume ~m < 0; 247#L14 [2024-11-09 15:18:57,391 INFO L747 eck$LassoCheckResult]: Loop: 247#L14 call #t~ret0 := mult(~n, -~m);< 255#$Ultimate##0 ~n := #in~n;~m := #in~m; 261#L13 assume ~m < 0; 247#L14 [2024-11-09 15:18:57,391 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:57,392 INFO L85 PathProgramCache]: Analyzing trace with hash -1744825059, now seen corresponding path program 1 times [2024-11-09 15:18:57,392 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:57,392 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [987120947] [2024-11-09 15:18:57,393 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:57,393 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:57,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:57,537 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 15:18:57,537 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-09 15:18:57,537 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [987120947] [2024-11-09 15:18:57,538 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [987120947] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 15:18:57,538 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 15:18:57,538 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-09 15:18:57,539 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [756064562] [2024-11-09 15:18:57,539 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 15:18:57,541 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-09 15:18:57,541 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:57,541 INFO L85 PathProgramCache]: Analyzing trace with hash 60546, now seen corresponding path program 2 times [2024-11-09 15:18:57,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:18:57,542 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [36747280] [2024-11-09 15:18:57,542 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:18:57,542 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:18:57,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:57,546 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:18:57,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:18:57,552 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:18:57,625 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:57,626 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:57,626 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:57,626 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:57,626 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-09 15:18:57,626 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:57,626 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:57,626 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:57,627 INFO L132 ssoRankerPreferences]: Filename of dumped script: RecursiveMultiplication-1.c_Iteration3_Loop [2024-11-09 15:18:57,627 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:57,627 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:57,628 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:57,633 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:57,641 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:57,643 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:57,645 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:57,695 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:57,698 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-09 15:18:57,698 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:57,698 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:57,700 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) [2024-11-09 15:18:57,701 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 [2024-11-09 15:18:57,702 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:57,703 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:57,727 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-09 15:18:57,728 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {mult_~n=-6, mult_#in~n=-6} Honda state: {mult_~n=-6, mult_#in~n=-6} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-09 15:18:57,742 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 [2024-11-09 15:18:57,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:57,742 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:57,743 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) [2024-11-09 15:18:57,744 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 [2024-11-09 15:18:57,745 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-09 15:18:57,745 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:57,775 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:57,776 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:57,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:57,777 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) [2024-11-09 15:18:57,778 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 [2024-11-09 15:18:57,779 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-09 15:18:57,779 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-09 15:18:58,406 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-09 15:18:58,411 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:58,411 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:18:58,411 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:18:58,411 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:18:58,411 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:18:58,411 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:18:58,411 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:58,411 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:18:58,411 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:18:58,412 INFO L132 ssoRankerPreferences]: Filename of dumped script: RecursiveMultiplication-1.c_Iteration3_Loop [2024-11-09 15:18:58,412 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:18:58,412 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:18:58,413 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:58,422 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:58,429 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:58,431 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:58,433 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:18:58,481 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 [2024-11-09 15:18:58,498 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:18:58,498 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:18:58,498 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:58,498 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:58,499 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) [2024-11-09 15:18:58,500 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 [2024-11-09 15:18:58,501 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 [2024-11-09 15:18:58,511 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:58,511 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:58,511 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:58,512 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:58,512 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:58,514 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:58,514 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:58,518 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:18:58,531 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 [2024-11-09 15:18:58,532 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:58,532 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:58,533 INFO L229 MonitoredProcess]: Starting monitored process 32 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) [2024-11-09 15:18:58,534 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-09 15:18:58,534 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 [2024-11-09 15:18:58,547 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:18:58,547 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:18:58,547 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:18:58,547 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:18:58,547 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:18:58,548 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:18:58,548 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:18:58,551 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:18:58,553 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-09 15:18:58,553 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-09 15:18:58,553 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:18:58,553 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:18:58,555 INFO L229 MonitoredProcess]: Starting monitored process 33 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) [2024-11-09 15:18:58,556 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-11-09 15:18:58,557 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:18:58,557 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 15:18:58,557 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:18:58,557 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(mult_~m) = 1*mult_~m Supporting invariants [] [2024-11-09 15:18:58,571 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:58,572 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 15:18:58,586 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:18:58,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:58,604 INFO L255 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 15:18:58,605 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:58,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:18:58,637 INFO L255 TraceCheckSpWp]: Trace formula consists of 41 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 15:18:58,637 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:18:58,660 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-09 15:18:58,661 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 [2024-11-09 15:18:58,661 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 23 states and 28 transitions. cyclomatic complexity: 8 Second operand has 4 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 15:18:58,700 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 23 states and 28 transitions. cyclomatic complexity: 8. Second operand has 4 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 52 states and 62 transitions. Complement of second has 9 states. [2024-11-09 15:18:58,701 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 4 states 1 stem states 2 non-accepting loop states 1 accepting loop states [2024-11-09 15:18:58,702 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 3 states have (on average 3.3333333333333335) internal successors, (10), 3 states have internal predecessors, (10), 2 states have call successors, (3), 2 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 15:18:58,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 15 transitions. [2024-11-09 15:18:58,703 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 11 letters. Loop has 3 letters. [2024-11-09 15:18:58,703 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:58,703 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 14 letters. Loop has 3 letters. [2024-11-09 15:18:58,704 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:58,704 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 11 letters. Loop has 6 letters. [2024-11-09 15:18:58,704 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:18:58,704 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 52 states and 62 transitions. [2024-11-09 15:18:58,706 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-09 15:18:58,707 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 52 states to 45 states and 55 transitions. [2024-11-09 15:18:58,707 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 26 [2024-11-09 15:18:58,707 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2024-11-09 15:18:58,707 INFO L73 IsDeterministic]: Start isDeterministic. Operand 45 states and 55 transitions. [2024-11-09 15:18:58,708 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:18:58,708 INFO L218 hiAutomatonCegarLoop]: Abstraction has 45 states and 55 transitions. [2024-11-09 15:18:58,708 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states and 55 transitions. [2024-11-09 15:18:58,711 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 39. [2024-11-09 15:18:58,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 29 states have (on average 1.206896551724138) internal successors, (35), 28 states have internal predecessors, (35), 10 states have call successors, (13), 10 states have call predecessors, (13), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 15:18:58,712 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 48 transitions. [2024-11-09 15:18:58,712 INFO L240 hiAutomatonCegarLoop]: Abstraction has 39 states and 48 transitions. [2024-11-09 15:18:58,712 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-09 15:18:58,714 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 15:18:58,714 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-09 15:18:58,715 INFO L87 Difference]: Start difference. First operand 39 states and 48 transitions. Second operand has 5 states, 3 states have (on average 3.0) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (2), 2 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-09 15:18:58,751 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 15:18:58,752 INFO L93 Difference]: Finished difference Result 32 states and 36 transitions. [2024-11-09 15:18:58,752 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 32 states and 36 transitions. [2024-11-09 15:18:58,752 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 15:18:58,753 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 32 states to 0 states and 0 transitions. [2024-11-09 15:18:58,753 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 15:18:58,753 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 15:18:58,753 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 15:18:58,753 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 15:18:58,753 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:18:58,753 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:18:58,754 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-09 15:18:58,754 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:18:58,754 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-09 15:18:58,755 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-09 15:18:58,755 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 15:18:58,755 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-09 15:18:58,762 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.11 03:18:58 BoogieIcfgContainer [2024-11-09 15:18:58,762 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-09 15:18:58,763 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 15:18:58,763 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 15:18:58,763 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 15:18:58,764 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 03:18:52" (3/4) ... [2024-11-09 15:18:58,766 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-09 15:18:58,767 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 15:18:58,767 INFO L158 Benchmark]: Toolchain (without parser) took 6598.23ms. Allocated memory is still 161.5MB. Free memory was 94.5MB in the beginning and 108.9MB in the end (delta: -14.4MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 15:18:58,768 INFO L158 Benchmark]: CDTParser took 0.67ms. Allocated memory is still 109.1MB. Free memory is still 69.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 15:18:58,768 INFO L158 Benchmark]: CACSL2BoogieTranslator took 288.85ms. Allocated memory is still 161.5MB. Free memory was 94.2MB in the beginning and 126.7MB in the end (delta: -32.5MB). Peak memory consumption was 6.3MB. Max. memory is 16.1GB. [2024-11-09 15:18:58,768 INFO L158 Benchmark]: Boogie Procedure Inliner took 29.99ms. Allocated memory is still 161.5MB. Free memory was 126.7MB in the beginning and 125.4MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 15:18:58,769 INFO L158 Benchmark]: Boogie Preprocessor took 27.27ms. Allocated memory is still 161.5MB. Free memory was 125.4MB in the beginning and 124.0MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 15:18:58,769 INFO L158 Benchmark]: RCFGBuilder took 248.61ms. Allocated memory is still 161.5MB. Free memory was 124.0MB in the beginning and 113.5MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-09 15:18:58,769 INFO L158 Benchmark]: BuchiAutomizer took 5993.41ms. Allocated memory is still 161.5MB. Free memory was 113.5MB in the beginning and 109.9MB in the end (delta: 3.6MB). Peak memory consumption was 5.3MB. Max. memory is 16.1GB. [2024-11-09 15:18:58,769 INFO L158 Benchmark]: Witness Printer took 3.90ms. Allocated memory is still 161.5MB. Free memory is still 108.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 15:18:58,771 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.67ms. Allocated memory is still 109.1MB. Free memory is still 69.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 288.85ms. Allocated memory is still 161.5MB. Free memory was 94.2MB in the beginning and 126.7MB in the end (delta: -32.5MB). Peak memory consumption was 6.3MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 29.99ms. Allocated memory is still 161.5MB. Free memory was 126.7MB in the beginning and 125.4MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 27.27ms. Allocated memory is still 161.5MB. Free memory was 125.4MB in the beginning and 124.0MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 248.61ms. Allocated memory is still 161.5MB. Free memory was 124.0MB in the beginning and 113.5MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 5993.41ms. Allocated memory is still 161.5MB. Free memory was 113.5MB in the beginning and 109.9MB in the end (delta: 3.6MB). Peak memory consumption was 5.3MB. Max. memory is 16.1GB. * Witness Printer took 3.90ms. Allocated memory is still 161.5MB. Free memory is still 108.9MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 4 terminating modules (1 trivial, 3 deterministic, 0 nondeterministic). One deterministic module has affine ranking function ((long) -1 * \old(m)) and consists of 5 locations. One deterministic module has affine ranking function m and consists of 6 locations. One deterministic module has affine ranking function m and consists of 4 locations. 1 modules have a trivial ranking function, the largest among these consists of 5 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 5.9s and 4 iterations. TraceHistogramMax:2. Analysis of lassos took 4.9s. Construction of modules took 0.0s. Büchi inclusion checks took 0.7s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 3. Automata minimization 0.0s AutomataMinimizationTime, 3 MinimizatonAttempts, 16 StatesRemovedByMinimization, 3 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 [3, 0, 0, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 0/0 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 48 SdHoareTripleChecker+Valid, 0.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 45 mSDsluCounter, 62 SdHoareTripleChecker+Invalid, 0.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 16 mSDsCounter, 12 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 77 IncrementalHoareTripleChecker+Invalid, 89 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 12 mSolverCounterUnsat, 46 mSDtfsCounter, 77 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT2 conc0 concLT0 SILN0 SILU0 SILI0 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital18 mio100 ax100 hnf100 lsp73 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq164 hnf92 smp100 dnf100 smp100 tf109 neg100 sie100 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 25ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 10 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 3 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 3.1s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-09 15:18:58,794 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-09 15:18:59,000 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