./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 84cfde4a Calling Ultimate with: /root/.sdkman/candidates/java/current/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c -s /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-84cfde4 [2024-10-12 00:59:14,451 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-12 00:59:14,524 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-10-12 00:59:14,531 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-12 00:59:14,532 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-12 00:59:14,557 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-12 00:59:14,558 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-12 00:59:14,558 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-12 00:59:14,559 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-12 00:59:14,560 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-12 00:59:14,560 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-12 00:59:14,560 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-12 00:59:14,561 INFO L153 SettingsManager]: * Use SBE=true [2024-10-12 00:59:14,561 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-12 00:59:14,561 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-12 00:59:14,562 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-12 00:59:14,563 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-12 00:59:14,564 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-12 00:59:14,565 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-12 00:59:14,565 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-12 00:59:14,565 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-12 00:59:14,565 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-12 00:59:14,565 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-12 00:59:14,566 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-12 00:59:14,566 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-12 00:59:14,566 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-12 00:59:14,566 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-12 00:59:14,566 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-12 00:59:14,566 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-12 00:59:14,566 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-12 00:59:14,567 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-12 00:59:14,567 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-12 00:59:14,567 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-12 00:59:14,567 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-12 00:59:14,567 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-12 00:59:14,567 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-12 00:59:14,569 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-12 00:59:14,569 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-12 00:59:14,569 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-12 00:59:14,570 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-clean/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-clean/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 [2024-10-12 00:59:14,744 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-12 00:59:14,775 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-12 00:59:14,780 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-12 00:59:14,782 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-12 00:59:14,782 INFO L274 PluginConnector]: CDTParser initialized [2024-10-12 00:59:14,783 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2024-10-12 00:59:16,293 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-12 00:59:16,467 INFO L384 CDTParser]: Found 1 translation units. [2024-10-12 00:59:16,467 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2024-10-12 00:59:16,476 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/1e49c80ef/474a87cebe4945419ed877822a9f702c/FLAG66ced2020 [2024-10-12 00:59:16,491 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/data/1e49c80ef/474a87cebe4945419ed877822a9f702c [2024-10-12 00:59:16,493 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-12 00:59:16,495 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-12 00:59:16,496 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-12 00:59:16,497 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-12 00:59:16,501 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-12 00:59:16,502 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,503 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5c9684e9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16, skipping insertion in model container [2024-10-12 00:59:16,503 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,518 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-12 00:59:16,677 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 00:59:16,691 INFO L200 MainTranslator]: Completed pre-run [2024-10-12 00:59:16,703 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-12 00:59:16,723 INFO L204 MainTranslator]: Completed translation [2024-10-12 00:59:16,723 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16 WrapperNode [2024-10-12 00:59:16,724 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-12 00:59:16,724 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-12 00:59:16,725 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-12 00:59:16,725 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-12 00:59:16,734 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,739 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,764 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-10-12 00:59:16,767 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-12 00:59:16,771 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-12 00:59:16,772 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-12 00:59:16,772 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-12 00:59:16,781 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,782 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,783 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,796 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-12 00:59:16,796 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,796 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,798 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,802 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,803 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,803 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,804 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-12 00:59:16,809 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-12 00:59:16,809 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-12 00:59:16,809 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-12 00:59:16,810 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (1/1) ... [2024-10-12 00:59:16,823 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:16,836 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:16,851 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:16,859 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-10-12 00:59:16,909 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2024-10-12 00:59:16,909 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2024-10-12 00:59:16,909 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-12 00:59:16,909 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-12 00:59:16,909 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-12 00:59:16,910 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-12 00:59:16,970 INFO L238 CfgBuilder]: Building ICFG [2024-10-12 00:59:16,972 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-12 00:59:17,071 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-12 00:59:17,071 INFO L287 CfgBuilder]: Performing block encoding [2024-10-12 00:59:17,089 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-12 00:59:17,090 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-12 00:59:17,094 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 12:59:17 BoogieIcfgContainer [2024-10-12 00:59:17,094 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-12 00:59:17,096 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-12 00:59:17,097 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-12 00:59:17,103 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-12 00:59:17,104 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-12 00:59:17,104 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 12.10 12:59:16" (1/3) ... [2024-10-12 00:59:17,105 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1c97633a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 12.10 12:59:17, skipping insertion in model container [2024-10-12 00:59:17,105 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-12 00:59:17,105 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.10 12:59:16" (2/3) ... [2024-10-12 00:59:17,106 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1c97633a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 12.10 12:59:17, skipping insertion in model container [2024-10-12 00:59:17,106 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-12 00:59:17,106 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 12:59:17" (3/3) ... [2024-10-12 00:59:17,107 INFO L332 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2024-10-12 00:59:17,207 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-12 00:59:17,207 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-12 00:59:17,207 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-12 00:59:17,207 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-12 00:59:17,208 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-12 00:59:17,208 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-12 00:59:17,208 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-12 00:59:17,209 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-12 00:59:17,214 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 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-10-12 00:59:17,248 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-12 00:59:17,248 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:59:17,248 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:59:17,261 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-12 00:59:17,261 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-12 00:59:17,261 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-12 00:59:17,261 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 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-10-12 00:59:17,262 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-12 00:59:17,263 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:59:17,263 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:59:17,263 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-12 00:59:17,263 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-12 00:59:17,276 INFO L745 eck$LassoCheckResult]: Stem: 17#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 12#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 8#L29true call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 14#$Ultimate##0true [2024-10-12 00:59:17,277 INFO L747 eck$LassoCheckResult]: Loop: 14#$Ultimate##0true ~n := #in~n; 4#L17true assume !(~n < 1); 18#L19true assume !(1 == ~n); 16#L22true call #t~ret4 := fibonacci(~n - 1);< 14#$Ultimate##0true [2024-10-12 00:59:17,289 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:17,289 INFO L85 PathProgramCache]: Analyzing trace with hash 42783, now seen corresponding path program 1 times [2024-10-12 00:59:17,303 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:17,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1098295165] [2024-10-12 00:59:17,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:17,304 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:17,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:17,435 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:59:17,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:17,474 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:59:17,476 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:17,476 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 1 times [2024-10-12 00:59:17,476 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:17,476 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1229981028] [2024-10-12 00:59:17,477 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:17,477 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:17,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:17,492 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:59:17,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:17,503 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:59:17,508 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:17,508 INFO L85 PathProgramCache]: Analyzing trace with hash 856297401, now seen corresponding path program 1 times [2024-10-12 00:59:17,509 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:17,509 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2094421784] [2024-10-12 00:59:17,509 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:17,509 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:17,535 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:17,535 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:59:17,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:17,550 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:59:17,720 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:17,720 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:17,720 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:17,720 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:17,721 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:59:17,721 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:17,721 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:17,721 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:17,721 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-10-12 00:59:17,721 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:17,721 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:17,748 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:17,780 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:17,783 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:17,791 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:17,813 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:17,921 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:17,922 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:59:17,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:17,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:17,930 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:17,932 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-10-12 00:59:17,933 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:17,933 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:17,947 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:59:17,948 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:59:17,958 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:17,959 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:17,959 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:17,960 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:17,961 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-10-12 00:59:17,963 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:17,963 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:17,975 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:59:17,975 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:59:17,986 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-10-12 00:59:17,987 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:17,987 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:17,988 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:17,989 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-10-12 00:59:17,990 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:17,990 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:18,001 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:59:18,001 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:59:18,011 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-10-12 00:59:18,012 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:18,012 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:18,013 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:18,014 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-10-12 00:59:18,017 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:18,018 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:18,038 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:18,039 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:18,039 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:18,040 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:18,041 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-10-12 00:59:18,042 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:59:18,042 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:18,095 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-12 00:59:18,105 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:18,105 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:18,105 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:18,105 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:18,105 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:18,105 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:59:18,105 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:18,106 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:18,106 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:18,106 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-10-12 00:59:18,106 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:18,106 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:18,107 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:18,110 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:18,115 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:18,117 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:18,125 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:18,160 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:18,163 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:59:18,164 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:18,165 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:18,166 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:18,167 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-10-12 00:59:18,168 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-10-12 00:59:18,179 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:18,179 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:18,179 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:18,179 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:18,180 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:18,181 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:18,181 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:18,183 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-12 00:59:18,194 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-10-12 00:59:18,194 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:18,195 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:18,196 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:18,197 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-10-12 00:59:18,198 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-10-12 00:59:18,208 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:18,208 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:18,208 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:18,208 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:18,208 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:18,209 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:18,209 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:18,211 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-12 00:59:18,222 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-10-12 00:59:18,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:18,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:18,223 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:18,224 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-10-12 00:59:18,226 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-10-12 00:59:18,236 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:18,236 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:18,237 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:18,237 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:18,237 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:18,239 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:18,239 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:18,240 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-12 00:59:18,253 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-10-12 00:59:18,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:18,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:18,255 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:18,256 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-10-12 00:59:18,257 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-10-12 00:59:18,267 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:18,267 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:18,267 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:18,267 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:18,267 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:18,268 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:18,268 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:18,274 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:59:18,278 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-12 00:59:18,278 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-12 00:59:18,279 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:18,279 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:18,281 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:18,282 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-10-12 00:59:18,283 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:59:18,283 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:59:18,283 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:59:18,283 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-12 00:59:18,294 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2024-10-12 00:59:18,297 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:59:18,317 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:18,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:18,341 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-12 00:59:18,342 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:18,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:18,363 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:59:18,364 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:18,405 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:18,433 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-10-12 00:59:18,435 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 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, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 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-10-12 00:59:18,502 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 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, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 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 40 states and 53 transitions. Complement of second has 16 states. [2024-10-12 00:59:18,504 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-10-12 00:59:18,507 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 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-10-12 00:59:18,508 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-10-12 00:59:18,509 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-10-12 00:59:18,509 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:18,510 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-10-12 00:59:18,510 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:18,510 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-10-12 00:59:18,510 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:18,511 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2024-10-12 00:59:18,515 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-12 00:59:18,519 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2024-10-12 00:59:18,520 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-10-12 00:59:18,520 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-10-12 00:59:18,520 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-10-12 00:59:18,521 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:59:18,521 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-10-12 00:59:18,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-10-12 00:59:18,541 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-10-12 00:59:18,541 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-12 00:59:18,542 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-10-12 00:59:18,544 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-12 00:59:18,544 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-12 00:59:18,544 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-12 00:59:18,544 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-10-12 00:59:18,545 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-12 00:59:18,545 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:59:18,545 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:59:18,545 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 00:59:18,546 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 00:59:18,547 INFO L745 eck$LassoCheckResult]: Stem: 130#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 131#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 120#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 132#$Ultimate##0 ~n := #in~n; 126#L17 assume !(~n < 1); 127#L19 assume !(1 == ~n); 119#L22 call #t~ret4 := fibonacci(~n - 1);< 128#$Ultimate##0 ~n := #in~n; 123#L17 assume ~n < 1;#res := 0; 124#fibonacciFINAL assume true; 129#fibonacciEXIT >#31#return; 118#L22-1 [2024-10-12 00:59:18,547 INFO L747 eck$LassoCheckResult]: Loop: 118#L22-1 call #t~ret5 := fibonacci(~n - 2);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume !(~n < 1); 136#L19 assume !(1 == ~n); 121#L22 call #t~ret4 := fibonacci(~n - 1);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume ~n < 1;#res := 0; 134#fibonacciFINAL assume true; 135#fibonacciEXIT >#31#return; 118#L22-1 [2024-10-12 00:59:18,547 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:18,547 INFO L85 PathProgramCache]: Analyzing trace with hash 2073663503, now seen corresponding path program 1 times [2024-10-12 00:59:18,548 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:18,549 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1842318805] [2024-10-12 00:59:18,549 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:18,549 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:18,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:18,641 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 00:59:18,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:18,665 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-12 00:59:18,665 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 00:59:18,665 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1842318805] [2024-10-12 00:59:18,666 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1842318805] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 00:59:18,666 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 00:59:18,666 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 00:59:18,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [6571858] [2024-10-12 00:59:18,667 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 00:59:18,668 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-12 00:59:18,669 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:18,669 INFO L85 PathProgramCache]: Analyzing trace with hash 1606275375, now seen corresponding path program 1 times [2024-10-12 00:59:18,669 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:18,669 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [714395745] [2024-10-12 00:59:18,669 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:18,669 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:18,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:18,695 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-12 00:59:18,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:18,716 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-12 00:59:18,716 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 00:59:18,716 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [714395745] [2024-10-12 00:59:18,717 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [714395745] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-12 00:59:18,717 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-12 00:59:18,717 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-12 00:59:18,717 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1794417972] [2024-10-12 00:59:18,717 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-12 00:59:18,717 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-12 00:59:18,717 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 00:59:18,719 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-12 00:59:18,719 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-10-12 00:59:18,720 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:18,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 00:59:18,763 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-10-12 00:59:18,763 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-10-12 00:59:18,764 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-12 00:59:18,765 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-10-12 00:59:18,765 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-10-12 00:59:18,765 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-10-12 00:59:18,765 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-10-12 00:59:18,766 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:59:18,766 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-12 00:59:18,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-10-12 00:59:18,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-10-12 00:59:18,767 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-10-12 00:59:18,768 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-10-12 00:59:18,768 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-12 00:59:18,768 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-12 00:59:18,769 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-12 00:59:18,769 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-12 00:59:18,769 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-10-12 00:59:18,770 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-12 00:59:18,770 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:59:18,770 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:59:18,770 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 00:59:18,770 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-10-12 00:59:18,771 INFO L745 eck$LassoCheckResult]: Stem: 202#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 203#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 191#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 201#$Ultimate##0 ~n := #in~n; 196#L17 assume !(~n < 1); 197#L19 assume !(1 == ~n); 192#L22 call #t~ret4 := fibonacci(~n - 1);< 198#$Ultimate##0 ~n := #in~n; 194#L17 assume !(~n < 1); 195#L19 assume 1 == ~n;#res := 1; 205#fibonacciFINAL assume true; 208#fibonacciEXIT >#31#return; 189#L22-1 [2024-10-12 00:59:18,771 INFO L747 eck$LassoCheckResult]: Loop: 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume 1 == ~n;#res := 1; 210#fibonacciFINAL assume true; 207#fibonacciEXIT >#31#return; 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume ~n < 1;#res := 0; 212#fibonacciFINAL assume true; 199#fibonacciEXIT >#33#return; 200#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 204#fibonacciFINAL assume true; 206#fibonacciEXIT >#31#return; 189#L22-1 [2024-10-12 00:59:18,771 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:18,771 INFO L85 PathProgramCache]: Analyzing trace with hash -140916419, now seen corresponding path program 1 times [2024-10-12 00:59:18,771 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:18,771 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1933261336] [2024-10-12 00:59:18,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:18,772 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:18,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:18,808 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-12 00:59:18,810 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:18,830 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:18,830 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 00:59:18,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1933261336] [2024-10-12 00:59:18,830 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1933261336] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 00:59:18,830 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2073828148] [2024-10-12 00:59:18,830 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:18,830 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 00:59:18,830 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:18,832 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 00:59:18,833 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-10-12 00:59:18,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:18,861 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-12 00:59:18,862 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:18,884 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:18,884 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 00:59:18,952 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:18,953 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2073828148] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 00:59:18,953 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 00:59:18,953 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-10-12 00:59:18,953 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2020009088] [2024-10-12 00:59:18,953 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 00:59:18,953 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-12 00:59:18,954 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:18,954 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 1 times [2024-10-12 00:59:18,954 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:18,954 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [440152950] [2024-10-12 00:59:18,954 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:18,954 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:18,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:18,960 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:59:18,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:18,965 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:59:19,123 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:19,124 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:19,124 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:19,124 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:19,124 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:59:19,124 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:19,124 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:19,124 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:19,124 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-10-12 00:59:19,124 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:19,124 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:19,125 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,127 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,131 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,133 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,135 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,163 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:19,163 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:59:19,163 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:19,164 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:19,165 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:19,166 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-10-12 00:59:19,167 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:19,167 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:19,178 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:59:19,179 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=3} Honda state: {fibonacci_#in~n=3} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:59:19,193 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-10-12 00:59:19,193 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:19,193 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:19,194 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:19,197 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-10-12 00:59:19,198 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:19,199 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:19,220 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-10-12 00:59:19,221 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:19,221 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:19,222 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:19,223 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-10-12 00:59:19,224 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:59:19,224 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:19,236 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-12 00:59:19,247 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-10-12 00:59:19,247 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:19,247 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:19,248 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:19,248 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:19,248 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:59:19,248 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:19,248 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:19,248 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:19,248 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-10-12 00:59:19,248 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:19,248 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:19,249 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,254 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,256 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,258 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,259 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:19,299 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:19,299 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:59:19,299 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:19,299 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:19,300 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:19,301 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-10-12 00:59:19,303 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-10-12 00:59:19,313 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:19,313 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:19,313 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:19,313 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:19,313 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:19,315 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:19,315 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:19,317 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:59:19,319 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-12 00:59:19,319 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-12 00:59:19,335 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:19,335 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:19,343 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:19,346 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-10-12 00:59:19,350 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:19,353 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:59:19,354 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:59:19,354 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:59:19,354 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-12 00:59:19,364 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-10-12 00:59:19,365 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:59:19,378 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:19,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:19,396 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-12 00:59:19,397 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:19,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:19,537 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-12 00:59:19,538 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:19,649 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 00:59:19,650 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-10-12 00:59:19,650 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-12 00:59:19,902 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Result 152 states and 210 transitions. Complement of second has 54 states. [2024-10-12 00:59:19,903 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-10-12 00:59:19,904 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-12 00:59:19,905 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-10-12 00:59:19,905 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-10-12 00:59:19,905 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:19,905 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-10-12 00:59:19,905 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:19,905 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-10-12 00:59:19,906 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:19,906 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-10-12 00:59:19,913 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-12 00:59:19,918 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-10-12 00:59:19,921 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-10-12 00:59:19,922 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-10-12 00:59:19,922 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-10-12 00:59:19,922 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:59:19,922 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-10-12 00:59:19,922 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-10-12 00:59:19,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-10-12 00:59:19,936 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.2272727272727273) internal successors, (81), 70 states have internal predecessors, (81), 25 states have call successors, (26), 13 states have call predecessors, (26), 15 states have return successors, (35), 22 states have call predecessors, (35), 23 states have call successors, (35) [2024-10-12 00:59:19,937 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-10-12 00:59:19,938 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-10-12 00:59:19,938 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 00:59:19,939 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-12 00:59:19,939 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-10-12 00:59:19,939 INFO L87 Difference]: Start difference. First operand 106 states and 142 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-12 00:59:20,040 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 00:59:20,041 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-10-12 00:59:20,041 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-10-12 00:59:20,044 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-12 00:59:20,046 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-10-12 00:59:20,046 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-10-12 00:59:20,046 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-10-12 00:59:20,046 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-10-12 00:59:20,046 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:59:20,046 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-10-12 00:59:20,047 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-10-12 00:59:20,052 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-10-12 00:59:20,053 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 74 states have (on average 1.2027027027027026) internal successors, (89), 78 states have internal predecessors, (89), 28 states have call successors, (29), 15 states have call predecessors, (29), 16 states have return successors, (39), 24 states have call predecessors, (39), 26 states have call successors, (39) [2024-10-12 00:59:20,054 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-10-12 00:59:20,054 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-10-12 00:59:20,054 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-12 00:59:20,055 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-10-12 00:59:20,055 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-12 00:59:20,055 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-10-12 00:59:20,056 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-12 00:59:20,056 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:59:20,056 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:59:20,057 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 00:59:20,057 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-10-12 00:59:20,057 INFO L745 eck$LassoCheckResult]: Stem: 905#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 906#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 880#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 907#$Ultimate##0 ~n := #in~n; 887#L17 assume !(~n < 1); 888#L19 assume !(1 == ~n); 891#L22 call #t~ret4 := fibonacci(~n - 1);< 892#$Ultimate##0 ~n := #in~n; 949#L17 assume !(~n < 1); 948#L19 assume !(1 == ~n); 937#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 946#L17 assume !(~n < 1); 944#L19 assume !(1 == ~n); 938#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 946#L17 assume !(~n < 1); 944#L19 assume !(1 == ~n); 938#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 947#L17 assume !(~n < 1); 945#L19 assume 1 == ~n;#res := 1; 943#fibonacciFINAL assume true; 941#fibonacciEXIT >#31#return; 883#L22-1 call #t~ret5 := fibonacci(~n - 2);< 940#$Ultimate##0 ~n := #in~n; 885#L17 assume ~n < 1;#res := 0; 886#fibonacciFINAL assume true; 992#fibonacciEXIT >#33#return; 990#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 987#fibonacciFINAL assume true; 980#fibonacciEXIT >#31#return; 913#L22-1 [2024-10-12 00:59:20,057 INFO L747 eck$LassoCheckResult]: Loop: 913#L22-1 call #t~ret5 := fibonacci(~n - 2);< 890#$Ultimate##0 ~n := #in~n; 986#L17 assume !(~n < 1); 911#L19 assume !(1 == ~n); 914#L22 call #t~ret4 := fibonacci(~n - 1);< 890#$Ultimate##0 ~n := #in~n; 986#L17 assume !(~n < 1); 911#L19 assume 1 == ~n;#res := 1; 915#fibonacciFINAL assume true; 916#fibonacciEXIT >#31#return; 913#L22-1 [2024-10-12 00:59:20,058 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:20,058 INFO L85 PathProgramCache]: Analyzing trace with hash 3324437, now seen corresponding path program 1 times [2024-10-12 00:59:20,058 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:20,058 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [496291215] [2024-10-12 00:59:20,058 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:20,058 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:20,067 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:20,158 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-12 00:59:20,162 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:20,212 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-12 00:59:20,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:20,233 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-12 00:59:20,235 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:20,239 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-12 00:59:20,239 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 00:59:20,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [496291215] [2024-10-12 00:59:20,239 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [496291215] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 00:59:20,239 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [783267168] [2024-10-12 00:59:20,239 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:20,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 00:59:20,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:20,241 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 00:59:20,246 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-10-12 00:59:20,278 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:20,278 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-12 00:59:20,280 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:20,324 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-12 00:59:20,325 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 00:59:20,520 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-10-12 00:59:20,520 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [783267168] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 00:59:20,521 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 00:59:20,521 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-10-12 00:59:20,521 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [380053242] [2024-10-12 00:59:20,521 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 00:59:20,521 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-12 00:59:20,522 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:20,522 INFO L85 PathProgramCache]: Analyzing trace with hash -1745046499, now seen corresponding path program 1 times [2024-10-12 00:59:20,522 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:20,522 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [739013450] [2024-10-12 00:59:20,522 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:20,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:20,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:20,526 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:59:20,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:20,528 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:59:20,596 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:20,596 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:20,596 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:20,596 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:20,596 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:59:20,596 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:20,596 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:20,596 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:20,596 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-10-12 00:59:20,596 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:20,596 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:20,597 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,599 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,602 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,604 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,605 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,633 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:20,633 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:59:20,633 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:20,633 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:20,635 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:20,636 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-10-12 00:59:20,637 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:20,637 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:20,649 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:59:20,650 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=2} Honda state: {fibonacci_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:59:20,661 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-10-12 00:59:20,661 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:20,661 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:20,662 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:20,664 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-10-12 00:59:20,665 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:20,665 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:20,686 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:20,686 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:20,687 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:20,688 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:20,707 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-10-12 00:59:20,708 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:59:20,708 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:20,723 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-10-12 00:59:20,726 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-12 00:59:20,737 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:20,737 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:20,737 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:20,737 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:20,737 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:20,737 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:59:20,737 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:20,737 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:20,737 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:20,738 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-10-12 00:59:20,738 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:20,738 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:20,738 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,742 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,745 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,747 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,748 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:20,783 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:20,783 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:59:20,783 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:20,783 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:20,785 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:20,786 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-10-12 00:59:20,786 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-10-12 00:59:20,796 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:20,796 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:20,796 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:20,796 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:20,796 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:20,797 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:20,797 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:20,799 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-12 00:59:20,809 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:20,810 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:20,810 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:20,811 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:20,812 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-10-12 00:59:20,812 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-10-12 00:59:20,822 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:20,823 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:20,823 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:20,823 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:20,823 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:20,824 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:20,824 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:20,825 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:59:20,827 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-12 00:59:20,828 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-12 00:59:20,828 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:20,828 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:20,829 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:20,830 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-10-12 00:59:20,831 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:59:20,831 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:59:20,831 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:59:20,831 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-12 00:59:20,842 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:20,843 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:59:20,851 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:20,879 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:20,880 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-12 00:59:20,881 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:21,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:21,023 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-12 00:59:21,024 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:21,078 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:21,078 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-12 00:59:21,079 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-12 00:59:21,229 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 230 states and 321 transitions. Complement of second has 37 states. [2024-10-12 00:59:21,229 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-10-12 00:59:21,230 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-12 00:59:21,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-10-12 00:59:21,230 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-12 00:59:21,230 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:21,230 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:59:21,238 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:21,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:21,268 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-12 00:59:21,269 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:21,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:21,397 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-12 00:59:21,397 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:21,452 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:21,452 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-12 00:59:21,452 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-12 00:59:21,579 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 300 states and 408 transitions. Complement of second has 29 states. [2024-10-12 00:59:21,579 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-10-12 00:59:21,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-12 00:59:21,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2024-10-12 00:59:21,580 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-12 00:59:21,580 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:21,580 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:59:21,589 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:21,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:21,618 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-12 00:59:21,619 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:21,723 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:21,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:21,771 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-12 00:59:21,771 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:21,825 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:21,825 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-12 00:59:21,826 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-12 00:59:21,985 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 808 states and 1112 transitions. Complement of second has 135 states. [2024-10-12 00:59:21,985 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-10-12 00:59:21,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-12 00:59:21,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2024-10-12 00:59:21,986 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-12 00:59:21,987 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:21,987 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2024-10-12 00:59:21,987 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:21,987 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2024-10-12 00:59:21,988 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:21,988 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 808 states and 1112 transitions. [2024-10-12 00:59:21,996 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2024-10-12 00:59:22,003 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 808 states to 427 states and 634 transitions. [2024-10-12 00:59:22,003 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 166 [2024-10-12 00:59:22,003 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 186 [2024-10-12 00:59:22,003 INFO L73 IsDeterministic]: Start isDeterministic. Operand 427 states and 634 transitions. [2024-10-12 00:59:22,003 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:59:22,004 INFO L218 hiAutomatonCegarLoop]: Abstraction has 427 states and 634 transitions. [2024-10-12 00:59:22,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 427 states and 634 transitions. [2024-10-12 00:59:22,022 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 427 to 352. [2024-10-12 00:59:22,023 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 352 states, 221 states have (on average 1.1990950226244343) internal successors, (265), 235 states have internal predecessors, (265), 75 states have call successors, (84), 46 states have call predecessors, (84), 56 states have return successors, (130), 70 states have call predecessors, (130), 71 states have call successors, (130) [2024-10-12 00:59:22,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 352 states to 352 states and 479 transitions. [2024-10-12 00:59:22,025 INFO L240 hiAutomatonCegarLoop]: Abstraction has 352 states and 479 transitions. [2024-10-12 00:59:22,025 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 00:59:22,025 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-12 00:59:22,025 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-10-12 00:59:22,025 INFO L87 Difference]: Start difference. First operand 352 states and 479 transitions. Second operand has 23 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 15 states have internal predecessors, (41), 13 states have call successors, (13), 7 states have call predecessors, (13), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-12 00:59:22,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 00:59:22,258 INFO L93 Difference]: Finished difference Result 707 states and 1054 transitions. [2024-10-12 00:59:22,258 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 707 states and 1054 transitions. [2024-10-12 00:59:22,265 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-12 00:59:22,274 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 707 states to 676 states and 1009 transitions. [2024-10-12 00:59:22,274 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 296 [2024-10-12 00:59:22,275 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 299 [2024-10-12 00:59:22,275 INFO L73 IsDeterministic]: Start isDeterministic. Operand 676 states and 1009 transitions. [2024-10-12 00:59:22,275 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:59:22,275 INFO L218 hiAutomatonCegarLoop]: Abstraction has 676 states and 1009 transitions. [2024-10-12 00:59:22,276 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 676 states and 1009 transitions. [2024-10-12 00:59:22,299 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 676 to 628. [2024-10-12 00:59:22,300 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 628 states, 383 states have (on average 1.1618798955613576) internal successors, (445), 406 states have internal predecessors, (445), 151 states have call successors, (165), 76 states have call predecessors, (165), 94 states have return successors, (326), 145 states have call predecessors, (326), 141 states have call successors, (326) [2024-10-12 00:59:22,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 628 states to 628 states and 936 transitions. [2024-10-12 00:59:22,304 INFO L240 hiAutomatonCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-10-12 00:59:22,304 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-12 00:59:22,305 INFO L425 stractBuchiCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-10-12 00:59:22,305 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-12 00:59:22,305 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 628 states and 936 transitions. [2024-10-12 00:59:22,308 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-12 00:59:22,308 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:59:22,308 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:59:22,309 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 00:59:22,309 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-12 00:59:22,310 INFO L745 eck$LassoCheckResult]: Stem: 4310#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 4311#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 4312#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 4313#$Ultimate##0 ~n := #in~n; 4329#L17 assume !(~n < 1); 4398#L19 assume !(1 == ~n); 4394#L22 call #t~ret4 := fibonacci(~n - 1);< 4395#$Ultimate##0 ~n := #in~n; 4427#L17 assume !(~n < 1); 4414#L19 assume !(1 == ~n); 4407#L22 call #t~ret4 := fibonacci(~n - 1);< 4410#$Ultimate##0 ~n := #in~n; 4421#L17 assume !(~n < 1); 4412#L19 assume !(1 == ~n); 4402#L22 call #t~ret4 := fibonacci(~n - 1);< 4408#$Ultimate##0 ~n := #in~n; 4431#L17 assume !(~n < 1); 4430#L19 assume !(1 == ~n); 4424#L22 call #t~ret4 := fibonacci(~n - 1);< 4429#$Ultimate##0 ~n := #in~n; 4448#L17 assume !(~n < 1); 4447#L19 assume !(1 == ~n); 4416#L22 call #t~ret4 := fibonacci(~n - 1);< 4446#$Ultimate##0 ~n := #in~n; 4461#L17 assume !(~n < 1); 4460#L19 assume !(1 == ~n); 4344#L22 call #t~ret4 := fibonacci(~n - 1);< 4342#$Ultimate##0 ~n := #in~n; 4345#L17 assume !(~n < 1); 4464#L19 assume !(1 == ~n); 4343#L22 call #t~ret4 := fibonacci(~n - 1);< 4342#$Ultimate##0 ~n := #in~n; 4346#L17 assume !(~n < 1); 4536#L19 assume 1 == ~n;#res := 1; 4535#fibonacciFINAL assume true; 4530#fibonacciEXIT >#31#return; 4514#L22-1 call #t~ret5 := fibonacci(~n - 2);< 4528#$Ultimate##0 ~n := #in~n; 4777#L17 assume !(~n < 1); 4655#L19 assume !(1 == ~n); 4656#L22 call #t~ret4 := fibonacci(~n - 1);< 4707#$Ultimate##0 ~n := #in~n; 4821#L17 assume !(~n < 1); 4818#L19 assume !(1 == ~n); 4819#L22 call #t~ret4 := fibonacci(~n - 1);< 4828#$Ultimate##0 [2024-10-12 00:59:22,310 INFO L747 eck$LassoCheckResult]: Loop: 4828#$Ultimate##0 ~n := #in~n; 4850#L17 assume !(~n < 1); 4847#L19 assume !(1 == ~n); 4827#L22 call #t~ret4 := fibonacci(~n - 1);< 4828#$Ultimate##0 [2024-10-12 00:59:22,310 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:22,310 INFO L85 PathProgramCache]: Analyzing trace with hash 1729544275, now seen corresponding path program 1 times [2024-10-12 00:59:22,310 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:22,310 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1374699816] [2024-10-12 00:59:22,310 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:22,310 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:22,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:22,476 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-12 00:59:22,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:22,501 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 00:59:22,501 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 00:59:22,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1374699816] [2024-10-12 00:59:22,501 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1374699816] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 00:59:22,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [997513035] [2024-10-12 00:59:22,502 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:22,502 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 00:59:22,502 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:22,503 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 00:59:22,515 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Waiting until timeout for monitored process [2024-10-12 00:59:22,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:22,552 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-10-12 00:59:22,554 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:22,605 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 00:59:22,606 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 00:59:22,776 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-12 00:59:22,777 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [997513035] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 00:59:22,777 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 00:59:22,777 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 21 [2024-10-12 00:59:22,777 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1754055747] [2024-10-12 00:59:22,777 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 00:59:22,778 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-12 00:59:22,778 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:22,778 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 2 times [2024-10-12 00:59:22,778 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:22,779 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1687544747] [2024-10-12 00:59:22,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:22,779 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:22,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:22,781 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:59:22,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:22,783 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:59:22,814 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:22,814 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:22,814 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:22,814 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:22,815 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:59:22,815 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:22,815 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:22,815 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:22,815 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-10-12 00:59:22,815 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:22,815 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:22,816 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:22,818 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:22,820 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:22,825 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:22,827 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:22,855 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:22,856 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:59:22,856 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:22,856 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:22,857 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:22,858 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-10-12 00:59:22,859 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:22,859 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:22,871 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:59:22,871 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:59:22,882 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2024-10-12 00:59:22,882 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:22,882 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:22,884 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:22,885 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-10-12 00:59:22,886 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:22,886 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:22,897 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:59:22,897 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:59:22,907 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:22,908 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:22,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:22,909 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:22,910 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-10-12 00:59:22,911 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:22,911 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:22,931 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:22,932 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:22,932 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:22,933 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:22,934 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-10-12 00:59:22,935 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:59:22,935 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:22,961 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-12 00:59:22,965 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:22,965 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:22,965 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:22,965 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:22,965 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:22,965 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:59:22,966 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:22,966 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:22,966 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:22,966 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-10-12 00:59:22,966 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:22,966 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:22,966 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:22,972 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:22,974 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:22,979 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:22,980 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:23,000 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:23,001 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:59:23,001 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:23,001 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:23,002 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:23,005 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-10-12 00:59:23,005 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-10-12 00:59:23,015 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:23,015 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:23,015 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:23,015 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:23,015 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:23,016 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:23,016 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:23,017 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-12 00:59:23,028 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:23,028 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:23,028 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:23,029 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:23,030 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-10-12 00:59:23,031 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-10-12 00:59:23,041 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:23,041 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:23,041 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:23,041 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:23,041 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:23,042 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:23,042 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:23,045 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-12 00:59:23,055 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:23,056 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:23,056 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:23,057 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:23,058 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-10-12 00:59:23,059 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-10-12 00:59:23,068 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:23,068 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:23,068 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:23,069 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:23,069 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:23,069 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:23,069 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:23,071 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:59:23,073 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-12 00:59:23,073 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-12 00:59:23,073 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:23,073 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:23,075 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:23,078 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-10-12 00:59:23,078 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:59:23,078 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:59:23,078 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:59:23,078 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-12 00:59:23,089 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2024-10-12 00:59:23,089 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:59:23,096 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:23,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:23,151 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-12 00:59:23,153 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:23,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:23,256 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:59:23,257 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:23,280 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:23,280 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-12 00:59:23,280 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:23,342 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 650 states and 958 transitions. Complement of second has 15 states. [2024-10-12 00:59:23,346 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-12 00:59:23,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:23,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-12 00:59:23,347 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-12 00:59:23,347 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:23,347 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:59:23,358 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:23,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:23,418 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-12 00:59:23,419 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:23,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:23,526 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:59:23,526 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:23,548 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:23,549 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-12 00:59:23,549 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:23,607 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 650 states and 958 transitions. Complement of second has 15 states. [2024-10-12 00:59:23,608 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-12 00:59:23,608 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:23,608 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-12 00:59:23,608 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-12 00:59:23,609 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:23,609 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:59:23,616 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:23,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:23,668 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-12 00:59:23,670 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:23,753 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:23,754 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:59:23,754 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:23,775 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:23,776 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-12 00:59:23,776 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:23,840 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 839 states and 1163 transitions. Complement of second has 19 states. [2024-10-12 00:59:23,840 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-12 00:59:23,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:23,841 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-10-12 00:59:23,841 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-12 00:59:23,841 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:23,841 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2024-10-12 00:59:23,842 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:23,842 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2024-10-12 00:59:23,842 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:23,842 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 839 states and 1163 transitions. [2024-10-12 00:59:23,849 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-12 00:59:23,856 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 839 states to 684 states and 996 transitions. [2024-10-12 00:59:23,857 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 241 [2024-10-12 00:59:23,857 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 250 [2024-10-12 00:59:23,857 INFO L73 IsDeterministic]: Start isDeterministic. Operand 684 states and 996 transitions. [2024-10-12 00:59:23,857 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:59:23,858 INFO L218 hiAutomatonCegarLoop]: Abstraction has 684 states and 996 transitions. [2024-10-12 00:59:23,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 684 states and 996 transitions. [2024-10-12 00:59:23,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 684 to 654. [2024-10-12 00:59:23,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 654 states, 407 states have (on average 1.1523341523341524) internal successors, (469), 432 states have internal predecessors, (469), 151 states have call successors, (165), 76 states have call predecessors, (165), 96 states have return successors, (326), 145 states have call predecessors, (326), 141 states have call successors, (326) [2024-10-12 00:59:23,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 654 states to 654 states and 960 transitions. [2024-10-12 00:59:23,883 INFO L240 hiAutomatonCegarLoop]: Abstraction has 654 states and 960 transitions. [2024-10-12 00:59:23,884 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 00:59:23,884 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-12 00:59:23,884 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2024-10-12 00:59:23,884 INFO L87 Difference]: Start difference. First operand 654 states and 960 transitions. Second operand has 21 states, 20 states have (on average 1.8) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (10), 9 states have call predecessors, (10), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:23,924 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:24,156 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 00:59:24,157 INFO L93 Difference]: Finished difference Result 781 states and 1180 transitions. [2024-10-12 00:59:24,157 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 781 states and 1180 transitions. [2024-10-12 00:59:24,163 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-12 00:59:24,170 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 781 states to 760 states and 1148 transitions. [2024-10-12 00:59:24,171 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 279 [2024-10-12 00:59:24,171 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 282 [2024-10-12 00:59:24,171 INFO L73 IsDeterministic]: Start isDeterministic. Operand 760 states and 1148 transitions. [2024-10-12 00:59:24,171 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:59:24,172 INFO L218 hiAutomatonCegarLoop]: Abstraction has 760 states and 1148 transitions. [2024-10-12 00:59:24,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 760 states and 1148 transitions. [2024-10-12 00:59:24,184 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 760 to 702. [2024-10-12 00:59:24,185 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 702 states, 437 states have (on average 1.1464530892448512) internal successors, (501), 462 states have internal predecessors, (501), 169 states have call successors, (185), 86 states have call predecessors, (185), 96 states have return successors, (336), 153 states have call predecessors, (336), 159 states have call successors, (336) [2024-10-12 00:59:24,188 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 702 states to 702 states and 1022 transitions. [2024-10-12 00:59:24,188 INFO L240 hiAutomatonCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-10-12 00:59:24,189 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-12 00:59:24,190 INFO L425 stractBuchiCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-10-12 00:59:24,190 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-12 00:59:24,190 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 702 states and 1022 transitions. [2024-10-12 00:59:24,193 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-12 00:59:24,193 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-12 00:59:24,193 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-12 00:59:24,194 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1, 1] [2024-10-12 00:59:24,194 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-12 00:59:24,194 INFO L745 eck$LassoCheckResult]: Stem: 9342#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 9343#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 9344#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 9345#$Ultimate##0 ~n := #in~n; 9513#L17 assume !(~n < 1); 9512#L19 assume !(1 == ~n); 9490#L22 call #t~ret4 := fibonacci(~n - 1);< 9491#$Ultimate##0 ~n := #in~n; 9555#L17 assume !(~n < 1); 9553#L19 assume !(1 == ~n); 9545#L22 call #t~ret4 := fibonacci(~n - 1);< 9551#$Ultimate##0 ~n := #in~n; 9550#L17 assume !(~n < 1); 9547#L19 assume !(1 == ~n); 9509#L22 call #t~ret4 := fibonacci(~n - 1);< 9546#$Ultimate##0 ~n := #in~n; 9661#L17 assume !(~n < 1); 9657#L19 assume !(1 == ~n); 9653#L22 call #t~ret4 := fibonacci(~n - 1);< 9655#$Ultimate##0 ~n := #in~n; 9680#L17 assume !(~n < 1); 9679#L19 assume !(1 == ~n); 9319#L22 call #t~ret4 := fibonacci(~n - 1);< 9678#$Ultimate##0 ~n := #in~n; 9723#L17 assume !(~n < 1); 9721#L19 assume !(1 == ~n); 9674#L22 call #t~ret4 := fibonacci(~n - 1);< 9698#$Ultimate##0 ~n := #in~n; 9792#L17 assume !(~n < 1); 9777#L19 assume !(1 == ~n); 9694#L22 call #t~ret4 := fibonacci(~n - 1);< 9761#$Ultimate##0 ~n := #in~n; 9819#L17 assume !(~n < 1); 9815#L19 assume !(1 == ~n); 9693#L22 call #t~ret4 := fibonacci(~n - 1);< 9761#$Ultimate##0 ~n := #in~n; 9822#L17 assume !(~n < 1); 9820#L19 assume 1 == ~n;#res := 1; 9816#fibonacciFINAL assume true; 9808#fibonacciEXIT >#31#return; 9715#L22-1 call #t~ret5 := fibonacci(~n - 2);< 9726#$Ultimate##0 ~n := #in~n; 9846#L17 assume !(~n < 1); 9909#L19 assume !(1 == ~n); 9368#L22 call #t~ret4 := fibonacci(~n - 1);< 9374#$Ultimate##0 ~n := #in~n; 9375#L17 assume !(~n < 1); 9973#L19 assume !(1 == ~n); 9354#L22 call #t~ret4 := fibonacci(~n - 1);< 9376#$Ultimate##0 ~n := #in~n; 9377#L17 assume !(~n < 1); 9972#L19 assume !(1 == ~n); 9355#L22 [2024-10-12 00:59:24,195 INFO L747 eck$LassoCheckResult]: Loop: 9355#L22 call #t~ret4 := fibonacci(~n - 1);< 9376#$Ultimate##0 ~n := #in~n; 9377#L17 assume !(~n < 1); 9972#L19 assume !(1 == ~n); 9355#L22 [2024-10-12 00:59:24,195 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:24,195 INFO L85 PathProgramCache]: Analyzing trace with hash 1537328375, now seen corresponding path program 2 times [2024-10-12 00:59:24,195 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:24,195 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1406071287] [2024-10-12 00:59:24,195 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:24,196 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:24,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:24,481 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-12 00:59:24,486 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:24,488 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-12 00:59:24,488 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-12 00:59:24,489 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1406071287] [2024-10-12 00:59:24,492 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1406071287] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-12 00:59:24,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1470052174] [2024-10-12 00:59:24,492 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-12 00:59:24,492 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-12 00:59:24,492 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:24,497 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-12 00:59:24,501 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Waiting until timeout for monitored process [2024-10-12 00:59:24,534 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-12 00:59:24,534 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-12 00:59:24,535 INFO L255 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-10-12 00:59:24,536 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:24,577 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-12 00:59:24,577 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-12 00:59:24,840 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-12 00:59:24,840 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1470052174] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-12 00:59:24,840 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-12 00:59:24,840 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2024-10-12 00:59:24,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1367330906] [2024-10-12 00:59:24,841 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-12 00:59:24,841 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-12 00:59:24,841 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:24,841 INFO L85 PathProgramCache]: Analyzing trace with hash 1817383, now seen corresponding path program 3 times [2024-10-12 00:59:24,841 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-12 00:59:24,842 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1787116957] [2024-10-12 00:59:24,842 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-12 00:59:24,842 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-12 00:59:24,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:24,843 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-12 00:59:24,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-12 00:59:24,845 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-12 00:59:24,913 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:24,913 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:24,913 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:24,913 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:24,913 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-12 00:59:24,913 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:24,913 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:24,913 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:24,913 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-10-12 00:59:24,913 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:24,914 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:24,914 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:24,916 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:24,917 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:24,923 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:24,957 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:24,957 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-12 00:59:24,957 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:24,957 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:24,959 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:24,960 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-10-12 00:59:24,960 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:24,960 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:24,971 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:59:24,972 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:59:24,983 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:24,983 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:24,983 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:24,984 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:24,985 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-10-12 00:59:24,986 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:24,986 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:24,997 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-12 00:59:24,997 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-12 00:59:25,009 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:25,010 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:25,010 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:25,011 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:25,012 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-10-12 00:59:25,012 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-12 00:59:25,012 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:25,041 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:25,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:25,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:25,042 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:25,043 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-10-12 00:59:25,047 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-12 00:59:25,047 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-12 00:59:26,292 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-12 00:59:26,298 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:26,298 INFO L204 LassoAnalysis]: Preferences: [2024-10-12 00:59:26,298 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-12 00:59:26,298 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-12 00:59:26,298 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-12 00:59:26,298 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-12 00:59:26,298 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:26,298 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-12 00:59:26,298 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-12 00:59:26,298 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-10-12 00:59:26,298 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-12 00:59:26,298 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-12 00:59:26,299 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:26,302 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:26,307 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:26,319 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-12 00:59:26,363 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-12 00:59:26,363 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-12 00:59:26,363 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:26,363 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:26,365 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:26,370 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-10-12 00:59:26,374 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-10-12 00:59:26,386 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:26,386 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:26,386 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:26,386 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:26,386 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:26,390 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:26,390 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:26,391 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-12 00:59:26,405 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:26,406 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:26,406 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:26,408 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:26,413 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-10-12 00:59:26,414 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-12 00:59:26,435 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:26,435 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:26,435 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:26,435 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:26,435 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:26,436 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:26,436 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:26,437 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-12 00:59:26,452 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:26,452 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:26,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:26,453 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:26,454 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-10-12 00:59:26,455 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-10-12 00:59:26,465 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-12 00:59:26,465 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-12 00:59:26,465 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-12 00:59:26,465 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-12 00:59:26,465 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-12 00:59:26,467 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-12 00:59:26,467 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-12 00:59:26,478 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-12 00:59:26,484 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-12 00:59:26,484 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-12 00:59:26,484 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-12 00:59:26,484 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 [2024-10-12 00:59:26,485 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-12 00:59:26,487 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-10-12 00:59:26,488 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-12 00:59:26,488 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-12 00:59:26,492 INFO L474 LassoAnalysis]: Proved termination. [2024-10-12 00:59:26,492 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-12 00:59:26,515 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2024-10-12 00:59:26,516 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-12 00:59:26,552 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:26,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:26,644 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-10-12 00:59:26,646 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:26,680 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:26,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:26,839 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:59:26,840 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:26,874 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:26,875 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2024-10-12 00:59:26,875 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:26,924 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 724 states and 1045 transitions. Complement of second has 18 states. [2024-10-12 00:59:26,925 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-12 00:59:26,925 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:26,926 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-12 00:59:26,926 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 52 letters. Loop has 4 letters. [2024-10-12 00:59:26,926 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:26,926 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-12 00:59:26,934 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-12 00:59:26,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:26,986 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-10-12 00:59:26,987 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:27,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-12 00:59:27,102 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-12 00:59:27,102 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-12 00:59:27,130 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-12 00:59:27,130 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2024-10-12 00:59:27,131 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:27,218 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 944 states and 1356 transitions. Complement of second has 22 states. [2024-10-12 00:59:27,223 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-10-12 00:59:27,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:27,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-10-12 00:59:27,224 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 4 letters. [2024-10-12 00:59:27,224 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:27,224 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 4 letters. [2024-10-12 00:59:27,224 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:27,224 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 8 letters. [2024-10-12 00:59:27,224 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-12 00:59:27,225 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 944 states and 1356 transitions. [2024-10-12 00:59:27,243 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-12 00:59:27,260 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 944 states to 874 states and 1278 transitions. [2024-10-12 00:59:27,261 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 282 [2024-10-12 00:59:27,261 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 310 [2024-10-12 00:59:27,261 INFO L73 IsDeterministic]: Start isDeterministic. Operand 874 states and 1278 transitions. [2024-10-12 00:59:27,261 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-12 00:59:27,261 INFO L218 hiAutomatonCegarLoop]: Abstraction has 874 states and 1278 transitions. [2024-10-12 00:59:27,262 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 874 states and 1278 transitions. [2024-10-12 00:59:27,273 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 874 to 854. [2024-10-12 00:59:27,274 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 854 states, 537 states have (on average 1.1340782122905029) internal successors, (609), 569 states have internal predecessors, (609), 202 states have call successors, (236), 111 states have call predecessors, (236), 115 states have return successors, (409), 173 states have call predecessors, (409), 192 states have call successors, (409) [2024-10-12 00:59:27,277 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 854 states to 854 states and 1254 transitions. [2024-10-12 00:59:27,277 INFO L240 hiAutomatonCegarLoop]: Abstraction has 854 states and 1254 transitions. [2024-10-12 00:59:27,277 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-12 00:59:27,278 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-12 00:59:27,278 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2024-10-12 00:59:27,278 INFO L87 Difference]: Start difference. First operand 854 states and 1254 transitions. Second operand has 21 states, 20 states have (on average 1.75) internal successors, (35), 12 states have internal predecessors, (35), 10 states have call successors, (11), 11 states have call predecessors, (11), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-12 00:59:27,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-12 00:59:27,532 INFO L93 Difference]: Finished difference Result 471 states and 558 transitions. [2024-10-12 00:59:27,532 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 471 states and 558 transitions. [2024-10-12 00:59:27,535 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-12 00:59:27,535 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 471 states to 0 states and 0 transitions. [2024-10-12 00:59:27,535 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-12 00:59:27,535 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-12 00:59:27,535 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-12 00:59:27,535 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-12 00:59:27,535 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-12 00:59:27,535 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-12 00:59:27,535 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-12 00:59:27,536 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-12 00:59:27,536 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-10-12 00:59:27,536 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-12 00:59:27,536 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-12 00:59:27,536 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-12 00:59:27,542 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 12.10 12:59:27 BoogieIcfgContainer [2024-10-12 00:59:27,543 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-12 00:59:27,543 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-12 00:59:27,543 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-12 00:59:27,543 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-12 00:59:27,544 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 12:59:17" (3/4) ... [2024-10-12 00:59:27,545 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-12 00:59:27,546 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-12 00:59:27,546 INFO L158 Benchmark]: Toolchain (without parser) took 11051.49ms. Allocated memory was 153.1MB in the beginning and 251.7MB in the end (delta: 98.6MB). Free memory was 96.9MB in the beginning and 128.8MB in the end (delta: -31.9MB). Peak memory consumption was 69.5MB. Max. memory is 16.1GB. [2024-10-12 00:59:27,546 INFO L158 Benchmark]: CDTParser took 0.15ms. Allocated memory is still 153.1MB. Free memory is still 113.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-12 00:59:27,546 INFO L158 Benchmark]: CACSL2BoogieTranslator took 227.86ms. Allocated memory is still 153.1MB. Free memory was 96.6MB in the beginning and 85.0MB in the end (delta: 11.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-10-12 00:59:27,547 INFO L158 Benchmark]: Boogie Procedure Inliner took 46.41ms. Allocated memory is still 153.1MB. Free memory was 85.0MB in the beginning and 83.7MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-12 00:59:27,547 INFO L158 Benchmark]: Boogie Preprocessor took 36.61ms. Allocated memory is still 153.1MB. Free memory was 83.7MB in the beginning and 82.2MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-12 00:59:27,547 INFO L158 Benchmark]: RCFGBuilder took 285.91ms. Allocated memory is still 153.1MB. Free memory was 82.2MB in the beginning and 72.5MB in the end (delta: 9.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-12 00:59:27,547 INFO L158 Benchmark]: BuchiAutomizer took 10446.07ms. Allocated memory was 153.1MB in the beginning and 251.7MB in the end (delta: 98.6MB). Free memory was 72.5MB in the beginning and 128.8MB in the end (delta: -56.3MB). Peak memory consumption was 44.4MB. Max. memory is 16.1GB. [2024-10-12 00:59:27,547 INFO L158 Benchmark]: Witness Printer took 2.77ms. Allocated memory is still 251.7MB. Free memory is still 128.8MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-12 00:59:27,549 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.15ms. Allocated memory is still 153.1MB. Free memory is still 113.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 227.86ms. Allocated memory is still 153.1MB. Free memory was 96.6MB in the beginning and 85.0MB in the end (delta: 11.6MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 46.41ms. Allocated memory is still 153.1MB. Free memory was 85.0MB in the beginning and 83.7MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 36.61ms. Allocated memory is still 153.1MB. Free memory was 83.7MB in the beginning and 82.2MB in the end (delta: 1.5MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 285.91ms. Allocated memory is still 153.1MB. Free memory was 82.2MB in the beginning and 72.5MB in the end (delta: 9.7MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 10446.07ms. Allocated memory was 153.1MB in the beginning and 251.7MB in the end (delta: 98.6MB). Free memory was 72.5MB in the beginning and 128.8MB in the end (delta: -56.3MB). Peak memory consumption was 44.4MB. Max. memory is 16.1GB. * Witness Printer took 2.77ms. Allocated memory is still 251.7MB. Free memory is still 128.8MB. 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 10 terminating modules (5 trivial, 3 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 11 locations. One deterministic module has affine ranking function n and consists of 7 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 23 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 10.3s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 5.6s. Construction of modules took 0.8s. Büchi inclusion checks took 3.4s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 265 StatesRemovedByMinimization, 8 NontrivialMinimizations. Non-live state removal took 0.1s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 1, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 596 SdHoareTripleChecker+Valid, 1.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 571 mSDsluCounter, 658 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 425 mSDsCounter, 357 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1357 IncrementalHoareTripleChecker+Invalid, 1714 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 357 mSolverCounterUnsat, 233 mSDtfsCounter, 1357 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI1 SILT4 lasso0 LassoPreprocessingBenchmarks: Lassos: inital14 mio100 ax100 hnf100 lsp82 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq185 hnf92 smp80 dnf100 smp100 tf112 neg100 sie106 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 19ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.6s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-10-12 00:59:27,572 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:27,775 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Ended with exit code 0 [2024-10-12 00:59:27,976 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-10-12 00:59:28,180 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-12 00:59:28,381 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-clean/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