./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_10-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 3289d67d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive-simple/fibo_10-1.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash acde98dd01af02b5a508b32116f1b2c3612f1f84e6ba2fe02fc76c333a1d32d3 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-17 08:49:24,097 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-17 08:49:24,163 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-17 08:49:24,166 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-17 08:49:24,168 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-17 08:49:24,168 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2024-11-17 08:49:24,191 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-17 08:49:24,192 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-17 08:49:24,192 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-17 08:49:24,193 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-17 08:49:24,194 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-17 08:49:24,194 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-17 08:49:24,195 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-17 08:49:24,195 INFO L153 SettingsManager]: * Use SBE=true [2024-11-17 08:49:24,197 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-17 08:49:24,197 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-17 08:49:24,197 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-17 08:49:24,197 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-17 08:49:24,197 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-17 08:49:24,198 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-17 08:49:24,198 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-17 08:49:24,198 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-17 08:49:24,198 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-17 08:49:24,199 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-17 08:49:24,201 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-17 08:49:24,201 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-17 08:49:24,201 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-17 08:49:24,202 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-17 08:49:24,202 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-17 08:49:24,202 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-17 08:49:24,202 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-17 08:49:24,202 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-17 08:49:24,202 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-17 08:49:24,202 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-17 08:49:24,202 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-17 08:49:24,203 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-17 08:49:24,203 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-17 08:49:24,203 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-17 08:49:24,203 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-17 08:49:24,203 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-17 08:49:24,204 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> acde98dd01af02b5a508b32116f1b2c3612f1f84e6ba2fe02fc76c333a1d32d3 [2024-11-17 08:49:24,382 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-17 08:49:24,403 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-17 08:49:24,405 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-17 08:49:24,406 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-17 08:49:24,406 INFO L274 PluginConnector]: CDTParser initialized [2024-11-17 08:49:24,407 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_10-1.c [2024-11-17 08:49:25,566 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-17 08:49:25,768 INFO L384 CDTParser]: Found 1 translation units. [2024-11-17 08:49:25,769 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_10-1.c [2024-11-17 08:49:25,777 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f65e8b167/b14d1bd8e0754e9cb880de61e82d5a9f/FLAGcee87ea07 [2024-11-17 08:49:25,791 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f65e8b167/b14d1bd8e0754e9cb880de61e82d5a9f [2024-11-17 08:49:25,794 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-17 08:49:25,795 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-17 08:49:25,796 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-17 08:49:25,798 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-17 08:49:25,802 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-17 08:49:25,803 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:25,804 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1ade334c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25, skipping insertion in model container [2024-11-17 08:49:25,804 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:25,818 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-17 08:49:25,961 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-17 08:49:25,973 INFO L200 MainTranslator]: Completed pre-run [2024-11-17 08:49:25,985 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-17 08:49:25,998 INFO L204 MainTranslator]: Completed translation [2024-11-17 08:49:25,999 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25 WrapperNode [2024-11-17 08:49:25,999 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-17 08:49:26,000 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-17 08:49:26,000 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-17 08:49:26,000 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-17 08:49:26,006 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,012 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,023 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-17 08:49:26,023 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-17 08:49:26,024 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-17 08:49:26,024 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-17 08:49:26,024 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-17 08:49:26,031 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,032 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,033 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,040 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-11-17 08:49:26,040 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,041 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,043 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,046 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,046 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,047 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,048 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-17 08:49:26,050 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-17 08:49:26,050 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-17 08:49:26,050 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-17 08:49:26,051 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (1/1) ... [2024-11-17 08:49:26,055 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,066 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,079 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,081 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-11-17 08:49:26,116 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-17 08:49:26,116 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-17 08:49:26,116 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-17 08:49:26,116 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-17 08:49:26,116 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-17 08:49:26,116 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-17 08:49:26,166 INFO L256 CfgBuilder]: Building ICFG [2024-11-17 08:49:26,168 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-17 08:49:26,241 INFO L1250 $ProcedureCfgBuilder]: dead code at ProgramPoint L13: havoc #t~ret4;havoc #t~ret5; [2024-11-17 08:49:26,249 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-17 08:49:26,251 INFO L307 CfgBuilder]: Performing block encoding [2024-11-17 08:49:26,261 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-17 08:49:26,261 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-17 08:49:26,263 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 08:49:26 BoogieIcfgContainer [2024-11-17 08:49:26,263 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-17 08:49:26,264 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-17 08:49:26,264 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-17 08:49:26,267 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-17 08:49:26,267 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-17 08:49:26,268 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 17.11 08:49:25" (1/3) ... [2024-11-17 08:49:26,268 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@13b6d2e6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.11 08:49:26, skipping insertion in model container [2024-11-17 08:49:26,268 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-17 08:49:26,269 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:49:25" (2/3) ... [2024-11-17 08:49:26,269 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@13b6d2e6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.11 08:49:26, skipping insertion in model container [2024-11-17 08:49:26,270 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-17 08:49:26,270 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 08:49:26" (3/3) ... [2024-11-17 08:49:26,271 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_10-1.c [2024-11-17 08:49:26,315 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-17 08:49:26,315 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-17 08:49:26,316 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-17 08:49:26,316 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-17 08:49:26,316 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-17 08:49:26,316 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-17 08:49:26,317 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-17 08:49:26,317 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-17 08:49:26,320 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-17 08:49:26,334 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-17 08:49:26,335 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:49:26,335 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:49:26,339 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-17 08:49:26,339 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-17 08:49:26,340 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-17 08:49:26,340 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-17 08:49:26,342 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-17 08:49:26,342 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:49:26,342 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:49:26,343 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-17 08:49:26,343 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-17 08:49:26,347 INFO L745 eck$LassoCheckResult]: Stem: 3#ULTIMATE.startENTRYtrue 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(12, 2);call #Ultimate.allocInit(12, 3); 12#ULTIMATE.init_returnLabel#1true assume true;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 := 10; 18#L27-1true call main_#t~ret6#1 := fibo(main_~x~0#1);< 7#fiboENTRYtrue [2024-11-17 08:49:26,347 INFO L747 eck$LassoCheckResult]: Loop: 7#fiboENTRYtrue ~n := #in~n; 8#L8true assume !(~n < 1); 9#L10true assume !(1 == ~n); 19#L13-3true call #t~ret4 := fibo(~n - 1);< 7#fiboENTRYtrue [2024-11-17 08:49:26,352 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:26,352 INFO L85 PathProgramCache]: Analyzing trace with hash 39702, now seen corresponding path program 1 times [2024-11-17 08:49:26,361 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:26,362 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [792153769] [2024-11-17 08:49:26,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:26,362 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:26,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:26,426 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:49:26,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:26,442 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:49:26,444 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:26,445 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 1 times [2024-11-17 08:49:26,445 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:26,445 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [437393581] [2024-11-17 08:49:26,445 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:26,445 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:26,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:26,449 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:49:26,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:26,452 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:49:26,454 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:26,454 INFO L85 PathProgramCache]: Analyzing trace with hash -1988460259, now seen corresponding path program 1 times [2024-11-17 08:49:26,454 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:26,454 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [329613147] [2024-11-17 08:49:26,454 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:26,454 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:26,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:26,462 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:49:26,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:26,475 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:49:26,561 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:26,561 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:26,561 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:26,561 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:26,562 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-17 08:49:26,562 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,562 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:26,562 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:26,562 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration1_Loop [2024-11-17 08:49:26,562 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:26,562 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:26,572 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,578 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,581 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,584 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,588 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,645 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:26,646 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-17 08:49:26,647 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,647 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,649 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,650 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-11-17 08:49:26,651 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:26,651 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:26,665 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-17 08:49:26,665 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=0} Honda state: {fibo_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-17 08:49:26,678 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-11-17 08:49:26,679 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,679 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,681 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,682 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-11-17 08:49:26,683 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:26,683 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:26,703 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-17 08:49:26,703 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-17 08:49:26,717 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-11-17 08:49:26,717 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,719 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,720 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-11-17 08:49:26,721 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:26,722 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:26,733 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-17 08:49:26,733 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-17 08:49:26,744 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-11-17 08:49:26,744 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,744 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,745 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,746 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-11-17 08:49:26,747 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:26,747 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:26,758 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-17 08:49:26,758 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-17 08:49:26,768 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:26,769 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,769 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,770 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,771 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-11-17 08:49:26,771 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:26,771 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:26,792 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-11-17 08:49:26,793 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,793 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,794 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,795 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-11-17 08:49:26,796 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-17 08:49:26,796 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:26,848 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-17 08:49:26,852 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-11-17 08:49:26,853 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:26,853 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:26,853 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:26,853 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:26,853 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:49:26,854 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,854 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:26,854 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:26,854 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration1_Loop [2024-11-17 08:49:26,854 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:26,854 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:26,857 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,863 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,865 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,867 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,869 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:26,909 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:26,913 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:49:26,913 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,914 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,914 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,915 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-17 08:49:26,916 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:26,926 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:26,926 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:26,927 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:26,927 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:26,927 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:26,928 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:26,928 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:26,930 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:49:26,941 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:26,941 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,942 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,942 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,943 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-11-17 08:49:26,946 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:26,956 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:26,956 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:26,956 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:26,957 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:26,957 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:26,957 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:26,957 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:26,958 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:49:26,968 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-11-17 08:49:26,968 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,969 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,970 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,970 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-17 08:49:26,971 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:26,980 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:26,981 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:26,981 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:26,981 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:26,981 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:26,981 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:26,981 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:26,982 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:49:26,993 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:26,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:26,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:26,994 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:26,995 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-11-17 08:49:26,996 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:27,006 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:27,006 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:27,006 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:27,006 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:27,006 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:27,006 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:27,006 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:27,008 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:49:27,018 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:27,018 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:27,018 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:27,019 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:27,020 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2024-11-17 08:49:27,020 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:27,030 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:27,030 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:27,030 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:27,030 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:27,030 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:27,031 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:27,031 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:27,033 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:49:27,037 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-17 08:49:27,037 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-17 08:49:27,038 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:27,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:27,040 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:27,041 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-17 08:49:27,042 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:49:27,042 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-17 08:49:27,042 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:49:27,042 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-17 08:49:27,054 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:27,060 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-17 08:49:27,083 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:27,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:27,108 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-17 08:49:27,109 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:27,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:27,124 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-17 08:49:27,124 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:27,160 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:27,205 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-11-17 08:49:27,210 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 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-11-17 08:49:27,224 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-17 08:49:27,311 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 19 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 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 41 states and 54 transitions. Complement of second has 16 states. [2024-11-17 08:49:27,315 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-17 08:49:27,319 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-11-17 08:49:27,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-17 08:49:27,320 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-17 08:49:27,321 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:27,321 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-17 08:49:27,321 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:27,321 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-17 08:49:27,322 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:27,322 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-17 08:49:27,324 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-17 08:49:27,328 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-17 08:49:27,330 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-17 08:49:27,330 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-17 08:49:27,331 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-17 08:49:27,331 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:27,331 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-17 08:49:27,342 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-17 08:49:27,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-17 08:49:27,349 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-11-17 08:49:27,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-17 08:49:27,350 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-17 08:49:27,350 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-17 08:49:27,350 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-17 08:49:27,350 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-17 08:49:27,351 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-17 08:49:27,351 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:49:27,351 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:49:27,351 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:49:27,351 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:49:27,352 INFO L745 eck$LassoCheckResult]: Stem: 120#ULTIMATE.startENTRY 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(12, 2);call #Ultimate.allocInit(12, 3); 121#ULTIMATE.init_returnLabel#1 assume true;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 := 10; 124#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 129#fiboENTRY ~n := #in~n; 130#L8 assume !(~n < 1); 134#L10 assume !(1 == ~n); 123#L13-3 call #t~ret4 := fibo(~n - 1);< 131#fiboENTRY ~n := #in~n; 132#L8 assume ~n < 1;#res := 0; 127#fiboFINAL assume true; 128#fiboEXIT >#27#return; 122#L13-2 [2024-11-17 08:49:27,352 INFO L747 eck$LassoCheckResult]: Loop: 122#L13-2 call #t~ret5 := fibo(~n - 2);< 126#fiboENTRY ~n := #in~n; 139#L8 assume !(~n < 1); 138#L10 assume !(1 == ~n); 125#L13-3 call #t~ret4 := fibo(~n - 1);< 126#fiboENTRY ~n := #in~n; 139#L8 assume ~n < 1;#res := 0; 136#fiboFINAL assume true; 137#fiboEXIT >#27#return; 122#L13-2 [2024-11-17 08:49:27,352 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:27,352 INFO L85 PathProgramCache]: Analyzing trace with hash 1475604923, now seen corresponding path program 1 times [2024-11-17 08:49:27,352 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:27,352 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [342098909] [2024-11-17 08:49:27,352 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:27,353 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:27,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:27,441 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-17 08:49:27,444 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:27,476 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-17 08:49:27,476 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 08:49:27,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [342098909] [2024-11-17 08:49:27,477 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [342098909] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 08:49:27,477 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 08:49:27,477 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-17 08:49:27,477 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2132785010] [2024-11-17 08:49:27,478 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 08:49:27,479 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-17 08:49:27,479 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:27,480 INFO L85 PathProgramCache]: Analyzing trace with hash 93365724, now seen corresponding path program 1 times [2024-11-17 08:49:27,480 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:27,480 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1083356657] [2024-11-17 08:49:27,480 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:27,480 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:27,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:27,521 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-17 08:49:27,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:27,560 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-17 08:49:27,560 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 08:49:27,560 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1083356657] [2024-11-17 08:49:27,561 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1083356657] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-17 08:49:27,561 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-17 08:49:27,561 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-17 08:49:27,561 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1515825581] [2024-11-17 08:49:27,561 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-17 08:49:27,561 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-17 08:49:27,561 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 08:49:27,563 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-17 08:49:27,564 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-17 08:49:27,565 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-11-17 08:49:27,622 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 08:49:27,622 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-17 08:49:27,622 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-17 08:49:27,623 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-17 08:49:27,624 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-17 08:49:27,624 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-17 08:49:27,624 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-17 08:49:27,624 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-17 08:49:27,624 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:27,624 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-17 08:49:27,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-17 08:49:27,626 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-17 08:49:27,626 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-11-17 08:49:27,627 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-17 08:49:27,627 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-17 08:49:27,627 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-17 08:49:27,628 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-17 08:49:27,628 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-17 08:49:27,628 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-17 08:49:27,629 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-17 08:49:27,629 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:49:27,629 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:49:27,630 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:49:27,630 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-17 08:49:27,630 INFO L745 eck$LassoCheckResult]: Stem: 191#ULTIMATE.startENTRY 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(12, 2);call #Ultimate.allocInit(12, 3); 192#ULTIMATE.init_returnLabel#1 assume true;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 := 10; 193#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 208#fiboENTRY ~n := #in~n; 200#L8 assume !(~n < 1); 206#L10 assume !(1 == ~n); 196#L13-3 call #t~ret4 := fibo(~n - 1);< 199#fiboENTRY ~n := #in~n; 201#L8 assume !(~n < 1); 205#L10 assume 1 == ~n;#res := 1; 207#fiboFINAL assume true; 204#fiboEXIT >#27#return; 194#L13-2 [2024-11-17 08:49:27,630 INFO L747 eck$LassoCheckResult]: Loop: 194#L13-2 call #t~ret5 := fibo(~n - 2);< 197#fiboENTRY ~n := #in~n; 198#L8 assume !(~n < 1); 212#L10 assume !(1 == ~n); 195#L13-3 call #t~ret4 := fibo(~n - 1);< 197#fiboENTRY ~n := #in~n; 198#L8 assume !(~n < 1); 212#L10 assume !(1 == ~n); 195#L13-3 call #t~ret4 := fibo(~n - 1);< 197#fiboENTRY ~n := #in~n; 198#L8 assume !(~n < 1); 212#L10 assume 1 == ~n;#res := 1; 202#fiboFINAL assume true; 203#fiboEXIT >#27#return; 194#L13-2 call #t~ret5 := fibo(~n - 2);< 197#fiboENTRY ~n := #in~n; 198#L8 assume ~n < 1;#res := 0; 213#fiboFINAL assume true; 211#fiboEXIT >#25#return; 209#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 210#fiboFINAL assume true; 214#fiboEXIT >#27#return; 194#L13-2 [2024-11-17 08:49:27,630 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:27,630 INFO L85 PathProgramCache]: Analyzing trace with hash -1500686953, now seen corresponding path program 1 times [2024-11-17 08:49:27,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:27,631 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [237190964] [2024-11-17 08:49:27,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:27,631 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:27,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:27,684 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-17 08:49:27,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:27,720 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:27,720 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 08:49:27,720 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [237190964] [2024-11-17 08:49:27,720 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [237190964] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 08:49:27,720 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [480556014] [2024-11-17 08:49:27,720 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:27,720 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 08:49:27,720 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:27,721 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 08:49:27,722 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2024-11-17 08:49:27,748 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:27,748 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-17 08:49:27,749 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:27,782 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:27,782 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 08:49:27,872 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:27,873 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [480556014] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 08:49:27,873 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 08:49:27,873 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-17 08:49:27,873 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1875453304] [2024-11-17 08:49:27,873 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 08:49:27,873 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-17 08:49:27,874 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:27,874 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 1 times [2024-11-17 08:49:27,874 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:27,874 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [581494873] [2024-11-17 08:49:27,874 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:27,874 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:27,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:27,883 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:49:27,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:27,888 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:49:28,106 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:28,106 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:28,106 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:28,107 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:28,107 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-17 08:49:28,107 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:28,107 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:28,107 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:28,107 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration3_Loop [2024-11-17 08:49:28,107 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:28,107 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:28,107 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:28,112 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:28,115 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:28,122 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:28,175 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:28,176 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-17 08:49:28,176 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:28,176 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:28,178 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:28,179 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-11-17 08:49:28,180 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:28,180 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:28,191 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-17 08:49:28,191 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=1} Honda state: {fibo_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-17 08:49:28,202 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-11-17 08:49:28,202 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:28,202 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:28,204 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:28,204 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-11-17 08:49:28,206 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:28,206 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:28,218 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-17 08:49:28,218 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-17 08:49:28,228 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:28,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:28,229 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:28,230 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:28,231 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-11-17 08:49:28,232 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:28,232 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:28,260 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-11-17 08:49:28,261 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:28,261 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:28,262 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:28,263 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2024-11-17 08:49:28,264 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-17 08:49:28,264 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:28,702 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-17 08:49:28,707 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:28,707 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:28,707 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:28,707 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:28,707 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:28,707 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:49:28,707 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:28,707 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:28,707 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:28,707 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration3_Loop [2024-11-17 08:49:28,707 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:28,707 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:28,708 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:28,719 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:28,720 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:28,721 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:28,760 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:28,760 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:49:28,760 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:28,760 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:28,762 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:28,774 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-17 08:49:28,779 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:28,793 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:28,810 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:28,811 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:28,811 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:28,811 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:28,812 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:28,812 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:28,814 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:49:28,817 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-17 08:49:28,817 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-17 08:49:28,818 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:28,818 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:28,819 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:28,820 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-11-17 08:49:28,828 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:49:28,828 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-17 08:49:28,828 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:49:28,828 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-17 08:49:28,845 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:28,848 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-17 08:49:28,862 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:28,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:28,882 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-17 08:49:28,882 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:28,969 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:28,970 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-17 08:49:28,974 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:29,091 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-17 08:49:29,091 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-11-17 08:49:29,092 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-11-17 08:49:29,289 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-11-17 08:49:29,291 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-11-17 08:49:29,292 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-11-17 08:49:29,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-11-17 08:49:29,293 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-11-17 08:49:29,293 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:29,293 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-11-17 08:49:29,293 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:29,293 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-11-17 08:49:29,294 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:29,294 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-11-17 08:49:29,302 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-17 08:49:29,309 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-11-17 08:49:29,310 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-17 08:49:29,311 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-17 08:49:29,311 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-11-17 08:49:29,311 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:29,312 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-11-17 08:49:29,312 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-11-17 08:49:29,323 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-11-17 08:49:29,323 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-11-17 08:49:29,324 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-11-17 08:49:29,325 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-11-17 08:49:29,325 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 08:49:29,325 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-17 08:49:29,325 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-17 08:49:29,325 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-11-17 08:49:29,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 08:49:29,434 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-11-17 08:49:29,435 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-11-17 08:49:29,437 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-17 08:49:29,442 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-11-17 08:49:29,442 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-11-17 08:49:29,442 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-11-17 08:49:29,442 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-11-17 08:49:29,442 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:29,442 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-11-17 08:49:29,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-11-17 08:49:29,448 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-11-17 08:49:29,448 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-11-17 08:49:29,449 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-11-17 08:49:29,449 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-17 08:49:29,449 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-17 08:49:29,450 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-17 08:49:29,450 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-17 08:49:29,450 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-11-17 08:49:29,451 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-17 08:49:29,451 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:49:29,451 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:49:29,452 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:49:29,452 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-17 08:49:29,452 INFO L745 eck$LassoCheckResult]: Stem: 881#ULTIMATE.startENTRY 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(12, 2);call #Ultimate.allocInit(12, 3); 882#ULTIMATE.init_returnLabel#1 assume true;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 := 10; 884#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 916#fiboENTRY ~n := #in~n; 950#L8 assume !(~n < 1); 949#L10 assume !(1 == ~n); 894#L13-3 call #t~ret4 := fibo(~n - 1);< 893#fiboENTRY ~n := #in~n; 895#L8 assume !(~n < 1); 908#L10 assume !(1 == ~n); 915#L13-3 call #t~ret4 := fibo(~n - 1);< 943#fiboENTRY ~n := #in~n; 947#L8 assume !(~n < 1); 945#L10 assume !(1 == ~n); 940#L13-3 call #t~ret4 := fibo(~n - 1);< 943#fiboENTRY ~n := #in~n; 947#L8 assume !(~n < 1); 945#L10 assume !(1 == ~n); 940#L13-3 call #t~ret4 := fibo(~n - 1);< 943#fiboENTRY ~n := #in~n; 948#L8 assume !(~n < 1); 946#L10 assume 1 == ~n;#res := 1; 944#fiboFINAL assume true; 942#fiboEXIT >#27#return; 887#L13-2 call #t~ret5 := fibo(~n - 2);< 941#fiboENTRY ~n := #in~n; 996#L8 assume ~n < 1;#res := 0; 995#fiboFINAL assume true; 994#fiboEXIT >#25#return; 992#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 989#fiboFINAL assume true; 979#fiboEXIT >#27#return; 912#L13-2 [2024-11-17 08:49:29,453 INFO L747 eck$LassoCheckResult]: Loop: 912#L13-2 call #t~ret5 := fibo(~n - 2);< 917#fiboENTRY ~n := #in~n; 987#L8 assume !(~n < 1); 909#L10 assume !(1 == ~n); 911#L13-3 call #t~ret4 := fibo(~n - 1);< 917#fiboENTRY ~n := #in~n; 987#L8 assume !(~n < 1); 909#L10 assume !(1 == ~n); 911#L13-3 call #t~ret4 := fibo(~n - 1);< 917#fiboENTRY ~n := #in~n; 987#L8 assume !(~n < 1); 909#L10 assume 1 == ~n;#res := 1; 914#fiboFINAL assume true; 983#fiboEXIT >#27#return; 912#L13-2 call #t~ret5 := fibo(~n - 2);< 917#fiboENTRY ~n := #in~n; 987#L8 assume !(~n < 1); 909#L10 assume 1 == ~n;#res := 1; 914#fiboFINAL assume true; 983#fiboEXIT >#25#return; 981#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 988#fiboFINAL assume true; 980#fiboEXIT >#27#return; 912#L13-2 [2024-11-17 08:49:29,453 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:29,453 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 1 times [2024-11-17 08:49:29,453 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:29,453 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [207167278] [2024-11-17 08:49:29,453 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:29,453 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:29,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:29,549 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-17 08:49:29,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:29,599 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-17 08:49:29,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:29,616 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-17 08:49:29,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:29,620 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-17 08:49:29,621 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 08:49:29,621 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [207167278] [2024-11-17 08:49:29,621 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [207167278] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 08:49:29,621 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1690226355] [2024-11-17 08:49:29,621 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:29,621 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 08:49:29,621 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:29,623 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 08:49:29,624 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2024-11-17 08:49:29,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:29,654 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-17 08:49:29,656 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:29,704 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-17 08:49:29,704 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 08:49:29,787 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:29,967 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-17 08:49:29,968 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1690226355] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 08:49:29,968 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 08:49:29,968 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-17 08:49:29,968 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1555811679] [2024-11-17 08:49:29,968 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 08:49:29,968 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-17 08:49:29,969 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:29,969 INFO L85 PathProgramCache]: Analyzing trace with hash -1547808212, now seen corresponding path program 1 times [2024-11-17 08:49:29,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:29,969 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1820361387] [2024-11-17 08:49:29,969 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:29,969 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:29,976 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:29,998 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-17 08:49:30,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:30,031 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-17 08:49:30,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:30,050 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-17 08:49:30,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:30,071 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-11-17 08:49:30,071 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 08:49:30,071 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1820361387] [2024-11-17 08:49:30,072 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1820361387] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 08:49:30,072 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [723904869] [2024-11-17 08:49:30,072 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:30,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 08:49:30,072 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:30,073 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 08:49:30,075 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2024-11-17 08:49:30,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:30,102 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-17 08:49:30,103 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:30,126 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-17 08:49:30,127 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 08:49:30,236 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-17 08:49:30,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [723904869] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 08:49:30,236 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 08:49:30,236 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-17 08:49:30,236 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1586111891] [2024-11-17 08:49:30,237 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 08:49:30,237 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-17 08:49:30,237 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 08:49:30,237 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-17 08:49:30,237 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-11-17 08:49:30,237 INFO L87 Difference]: Start difference. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 11 states, 10 states have (on average 2.3) internal successors, (23), 10 states have internal predecessors, (23), 2 states have call successors, (3), 1 states have call predecessors, (3), 3 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:30,311 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 08:49:30,311 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-11-17 08:49:30,311 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-11-17 08:49:30,312 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-17 08:49:30,312 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-11-17 08:49:30,313 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-11-17 08:49:30,313 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-17 08:49:30,313 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-11-17 08:49:30,313 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:30,313 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-17 08:49:30,313 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-11-17 08:49:30,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-11-17 08:49:30,318 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 37 states have internal predecessors, (38), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (21), 9 states have call predecessors, (21), 9 states have call successors, (21) [2024-11-17 08:49:30,319 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-11-17 08:49:30,319 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-17 08:49:30,321 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-17 08:49:30,322 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-17 08:49:30,322 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-17 08:49:30,322 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-11-17 08:49:30,323 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-17 08:49:30,323 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:49:30,323 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:49:30,323 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:49:30,323 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-17 08:49:30,324 INFO L745 eck$LassoCheckResult]: Stem: 1472#ULTIMATE.startENTRY 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(12, 2);call #Ultimate.allocInit(12, 3); 1473#ULTIMATE.init_returnLabel#1 assume true;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 := 10; 1480#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1499#fiboENTRY ~n := #in~n; 1508#L8 assume !(~n < 1); 1510#L10 assume !(1 == ~n); 1485#L13-3 call #t~ret4 := fibo(~n - 1);< 1484#fiboENTRY ~n := #in~n; 1486#L8 assume !(~n < 1); 1498#L10 assume !(1 == ~n); 1493#L13-3 call #t~ret4 := fibo(~n - 1);< 1502#fiboENTRY ~n := #in~n; 1492#L8 assume !(~n < 1); 1495#L10 assume !(1 == ~n); 1494#L13-3 call #t~ret4 := fibo(~n - 1);< 1502#fiboENTRY ~n := #in~n; 1492#L8 assume !(~n < 1); 1495#L10 assume !(1 == ~n); 1494#L13-3 call #t~ret4 := fibo(~n - 1);< 1502#fiboENTRY ~n := #in~n; 1509#L8 assume !(~n < 1); 1496#L10 assume 1 == ~n;#res := 1; 1497#fiboFINAL assume true; 1515#fiboEXIT >#27#return; 1482#L13-2 call #t~ret5 := fibo(~n - 2);< 1481#fiboENTRY ~n := #in~n; 1483#L8 assume ~n < 1;#res := 0; 1491#fiboFINAL assume true; 1489#fiboEXIT >#25#return; 1490#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1523#fiboFINAL assume true; 1522#fiboEXIT >#27#return; 1478#L13-2 [2024-11-17 08:49:30,324 INFO L747 eck$LassoCheckResult]: Loop: 1478#L13-2 call #t~ret5 := fibo(~n - 2);< 1501#fiboENTRY ~n := #in~n; 1506#L8 assume !(~n < 1); 1504#L10 assume !(1 == ~n); 1476#L13-3 call #t~ret4 := fibo(~n - 1);< 1501#fiboENTRY ~n := #in~n; 1506#L8 assume !(~n < 1); 1504#L10 assume !(1 == ~n); 1476#L13-3 call #t~ret4 := fibo(~n - 1);< 1501#fiboENTRY ~n := #in~n; 1506#L8 assume !(~n < 1); 1504#L10 assume 1 == ~n;#res := 1; 1505#fiboFINAL assume true; 1512#fiboEXIT >#27#return; 1474#L13-2 call #t~ret5 := fibo(~n - 2);< 1479#fiboENTRY ~n := #in~n; 1525#L8 assume ~n < 1;#res := 0; 1507#fiboFINAL assume true; 1520#fiboEXIT >#25#return; 1503#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1487#fiboFINAL assume true; 1488#fiboEXIT >#27#return; 1478#L13-2 [2024-11-17 08:49:30,324 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:30,324 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 2 times [2024-11-17 08:49:30,324 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:30,324 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [796993417] [2024-11-17 08:49:30,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:30,324 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:30,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:30,402 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-17 08:49:30,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:30,436 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-17 08:49:30,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:30,450 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-17 08:49:30,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:30,453 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-17 08:49:30,453 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 08:49:30,453 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [796993417] [2024-11-17 08:49:30,454 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [796993417] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 08:49:30,454 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1807922013] [2024-11-17 08:49:30,454 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-17 08:49:30,454 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 08:49:30,454 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:30,455 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 08:49:30,457 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2024-11-17 08:49:30,491 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-17 08:49:30,491 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 08:49:30,491 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-17 08:49:30,492 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:30,529 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-17 08:49:30,529 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 08:49:30,732 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-17 08:49:30,732 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1807922013] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 08:49:30,732 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 08:49:30,732 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-11-17 08:49:30,732 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1229900847] [2024-11-17 08:49:30,733 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 08:49:30,733 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-17 08:49:30,733 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:30,733 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 2 times [2024-11-17 08:49:30,733 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:30,733 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [932059479] [2024-11-17 08:49:30,733 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:30,733 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:30,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:30,736 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:49:30,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:30,739 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:49:30,898 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:30,898 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:30,898 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:30,898 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:30,899 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-17 08:49:30,899 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:30,899 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:30,899 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:30,899 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration5_Loop [2024-11-17 08:49:30,899 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:30,899 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:30,899 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:30,902 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:30,907 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:30,909 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:30,910 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:30,934 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:30,934 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-17 08:49:30,934 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:30,934 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:30,935 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:30,936 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-11-17 08:49:30,937 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:30,937 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:30,948 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-17 08:49:30,948 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=1} Honda state: {fibo_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-17 08:49:30,958 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:30,959 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:30,959 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:30,960 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:30,960 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2024-11-17 08:49:30,961 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:30,961 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:30,983 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:30,984 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:30,984 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:30,985 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:30,986 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-11-17 08:49:30,987 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-17 08:49:30,987 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:31,002 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-17 08:49:31,012 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:31,012 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:31,012 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:31,012 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:31,012 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:31,012 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:49:31,012 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:31,012 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:31,012 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:31,012 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration5_Loop [2024-11-17 08:49:31,013 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:31,013 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:31,013 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:31,016 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:31,018 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:31,019 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:31,021 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:31,041 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:31,041 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:49:31,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:31,041 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:31,042 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:31,042 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-11-17 08:49:31,043 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:31,053 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:31,053 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:31,053 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:31,053 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:31,053 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:31,054 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:31,054 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:31,056 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:49:31,058 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-17 08:49:31,058 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-17 08:49:31,058 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:31,058 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:31,060 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:31,061 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-11-17 08:49:31,061 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:49:31,061 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-17 08:49:31,061 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:49:31,062 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-17 08:49:31,071 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2024-11-17 08:49:31,072 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-17 08:49:31,081 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:31,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:31,113 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-17 08:49:31,114 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:31,273 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:31,277 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-17 08:49:31,278 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:31,367 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-17 08:49:31,368 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-11-17 08:49:31,368 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-17 08:49:31,438 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 77 transitions. Complement of second has 11 states. [2024-11-17 08:49:31,438 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-11-17 08:49:31,438 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-17 08:49:31,439 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-17 08:49:31,439 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-17 08:49:31,439 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:31,439 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:49:31,445 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:31,473 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:31,474 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-17 08:49:31,475 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:31,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:31,616 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-17 08:49:31,617 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:31,720 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:31,731 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-17 08:49:31,731 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-17 08:49:31,731 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-17 08:49:31,808 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 77 transitions. Complement of second has 11 states. [2024-11-17 08:49:31,811 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-11-17 08:49:31,811 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-17 08:49:31,811 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-17 08:49:31,811 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-17 08:49:31,811 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:31,812 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:49:31,819 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:31,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:31,848 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-17 08:49:31,848 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:31,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:31,982 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-17 08:49:31,983 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:32,073 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-17 08:49:32,073 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-11-17 08:49:32,074 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-17 08:49:32,240 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 408 states and 526 transitions. Complement of second has 132 states. [2024-11-17 08:49:32,241 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-11-17 08:49:32,241 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-17 08:49:32,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-11-17 08:49:32,241 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-17 08:49:32,242 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:32,242 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 54 letters. Loop has 22 letters. [2024-11-17 08:49:32,243 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:32,243 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 44 letters. [2024-11-17 08:49:32,244 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:32,244 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 526 transitions. [2024-11-17 08:49:32,248 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-17 08:49:32,252 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 259 states and 359 transitions. [2024-11-17 08:49:32,252 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 122 [2024-11-17 08:49:32,252 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 139 [2024-11-17 08:49:32,252 INFO L73 IsDeterministic]: Start isDeterministic. Operand 259 states and 359 transitions. [2024-11-17 08:49:32,252 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:32,252 INFO L218 hiAutomatonCegarLoop]: Abstraction has 259 states and 359 transitions. [2024-11-17 08:49:32,253 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states and 359 transitions. [2024-11-17 08:49:32,264 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 187. [2024-11-17 08:49:32,265 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 187 states, 115 states have (on average 1.1391304347826088) internal successors, (131), 122 states have internal predecessors, (131), 43 states have call successors, (48), 25 states have call predecessors, (48), 29 states have return successors, (67), 39 states have call predecessors, (67), 39 states have call successors, (67) [2024-11-17 08:49:32,266 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 246 transitions. [2024-11-17 08:49:32,266 INFO L240 hiAutomatonCegarLoop]: Abstraction has 187 states and 246 transitions. [2024-11-17 08:49:32,266 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 08:49:32,267 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-11-17 08:49:32,267 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-11-17 08:49:32,267 INFO L87 Difference]: Start difference. First operand 187 states and 246 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-11-17 08:49:32,492 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 08:49:32,492 INFO L93 Difference]: Finished difference Result 380 states and 491 transitions. [2024-11-17 08:49:32,492 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 380 states and 491 transitions. [2024-11-17 08:49:32,496 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-17 08:49:32,499 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 380 states to 356 states and 457 transitions. [2024-11-17 08:49:32,500 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 177 [2024-11-17 08:49:32,500 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 177 [2024-11-17 08:49:32,500 INFO L73 IsDeterministic]: Start isDeterministic. Operand 356 states and 457 transitions. [2024-11-17 08:49:32,500 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:32,500 INFO L218 hiAutomatonCegarLoop]: Abstraction has 356 states and 457 transitions. [2024-11-17 08:49:32,501 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 356 states and 457 transitions. [2024-11-17 08:49:32,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 356 to 332. [2024-11-17 08:49:32,511 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 332 states, 203 states have (on average 1.0886699507389161) internal successors, (221), 216 states have internal predecessors, (221), 78 states have call successors, (82), 41 states have call predecessors, (82), 51 states have return successors, (125), 74 states have call predecessors, (125), 69 states have call successors, (125) [2024-11-17 08:49:32,517 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 332 states to 332 states and 428 transitions. [2024-11-17 08:49:32,517 INFO L240 hiAutomatonCegarLoop]: Abstraction has 332 states and 428 transitions. [2024-11-17 08:49:32,518 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-17 08:49:32,518 INFO L425 stractBuchiCegarLoop]: Abstraction has 332 states and 428 transitions. [2024-11-17 08:49:32,518 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-17 08:49:32,518 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 332 states and 428 transitions. [2024-11-17 08:49:32,520 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-17 08:49:32,520 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:49:32,520 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:49:32,521 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 11, 10, 10, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:49:32,521 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-17 08:49:32,521 INFO L745 eck$LassoCheckResult]: Stem: 3572#ULTIMATE.startENTRY 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(12, 2);call #Ultimate.allocInit(12, 3); 3573#ULTIMATE.init_returnLabel#1 assume true;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 := 10; 3574#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 3615#fiboENTRY ~n := #in~n; 3652#L8 assume !(~n < 1); 3651#L10 assume !(1 == ~n); 3647#L13-3 call #t~ret4 := fibo(~n - 1);< 3650#fiboENTRY ~n := #in~n; 3649#L8 assume !(~n < 1); 3648#L10 assume !(1 == ~n); 3643#L13-3 call #t~ret4 := fibo(~n - 1);< 3646#fiboENTRY ~n := #in~n; 3645#L8 assume !(~n < 1); 3644#L10 assume !(1 == ~n); 3639#L13-3 call #t~ret4 := fibo(~n - 1);< 3642#fiboENTRY ~n := #in~n; 3641#L8 assume !(~n < 1); 3640#L10 assume !(1 == ~n); 3635#L13-3 call #t~ret4 := fibo(~n - 1);< 3638#fiboENTRY ~n := #in~n; 3637#L8 assume !(~n < 1); 3636#L10 assume !(1 == ~n); 3630#L13-3 call #t~ret4 := fibo(~n - 1);< 3633#fiboENTRY ~n := #in~n; 3634#L8 assume !(~n < 1); 3631#L10 assume !(1 == ~n); 3626#L13-3 call #t~ret4 := fibo(~n - 1);< 3625#fiboENTRY ~n := #in~n; 3628#L8 assume !(~n < 1); 3632#L10 assume !(1 == ~n); 3627#L13-3 call #t~ret4 := fibo(~n - 1);< 3625#fiboENTRY ~n := #in~n; 3628#L8 assume !(~n < 1); 3632#L10 assume !(1 == ~n); 3627#L13-3 call #t~ret4 := fibo(~n - 1);< 3625#fiboENTRY ~n := #in~n; 3629#L8 assume !(~n < 1); 3888#L10 assume 1 == ~n;#res := 1; 3886#fiboFINAL assume true; 3879#fiboEXIT >#27#return; 3876#L13-2 call #t~ret5 := fibo(~n - 2);< 3877#fiboENTRY ~n := #in~n; 3897#L8 assume ~n < 1;#res := 0; 3896#fiboFINAL assume true; 3875#fiboEXIT >#25#return; 3853#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3852#fiboFINAL assume true; 3828#fiboEXIT >#27#return; 3751#L13-2 call #t~ret5 := fibo(~n - 2);< 3754#fiboENTRY ~n := #in~n; 3868#L8 assume !(~n < 1); 3866#L10 assume !(1 == ~n); 3601#L13-3 call #t~ret4 := fibo(~n - 1);< 3864#fiboENTRY ~n := #in~n; 3872#L8 assume !(~n < 1); 3870#L10 assume !(1 == ~n); 3671#L13-3 call #t~ret4 := fibo(~n - 1);< 3675#fiboENTRY [2024-11-17 08:49:32,521 INFO L747 eck$LassoCheckResult]: Loop: 3675#fiboENTRY ~n := #in~n; 3679#L8 assume !(~n < 1); 3677#L10 assume !(1 == ~n); 3668#L13-3 call #t~ret4 := fibo(~n - 1);< 3675#fiboENTRY [2024-11-17 08:49:32,523 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:32,523 INFO L85 PathProgramCache]: Analyzing trace with hash -1417466561, now seen corresponding path program 3 times [2024-11-17 08:49:32,523 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:32,523 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [484038291] [2024-11-17 08:49:32,523 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:32,523 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:32,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:32,732 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-11-17 08:49:32,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:32,778 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-17 08:49:32,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:32,798 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-17 08:49:32,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:32,803 INFO L134 CoverageAnalysis]: Checked inductivity of 239 backedges. 77 proven. 153 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-11-17 08:49:32,803 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 08:49:32,803 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [484038291] [2024-11-17 08:49:32,803 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [484038291] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 08:49:32,803 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1483824704] [2024-11-17 08:49:32,803 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-17 08:49:32,803 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 08:49:32,803 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:32,805 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 08:49:32,806 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (29)] Waiting until timeout for monitored process [2024-11-17 08:49:32,842 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-17 08:49:32,842 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 08:49:32,842 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-17 08:49:32,843 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:32,909 INFO L134 CoverageAnalysis]: Checked inductivity of 239 backedges. 108 proven. 14 refuted. 0 times theorem prover too weak. 117 trivial. 0 not checked. [2024-11-17 08:49:32,909 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 08:49:33,090 INFO L134 CoverageAnalysis]: Checked inductivity of 239 backedges. 108 proven. 16 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2024-11-17 08:49:33,090 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1483824704] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 08:49:33,090 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 08:49:33,090 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 9, 10] total 28 [2024-11-17 08:49:33,090 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [154056136] [2024-11-17 08:49:33,091 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 08:49:33,091 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-17 08:49:33,091 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:33,091 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 2 times [2024-11-17 08:49:33,091 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:33,091 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [803530469] [2024-11-17 08:49:33,091 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:33,093 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:33,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:33,095 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:49:33,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:33,096 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:49:33,124 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:33,125 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:33,125 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:33,125 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:33,125 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-17 08:49:33,125 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:33,125 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:33,125 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:33,125 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration6_Loop [2024-11-17 08:49:33,125 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:33,125 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:33,127 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,129 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,136 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,137 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,139 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,160 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:33,160 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-17 08:49:33,161 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:33,161 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:33,162 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:33,163 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-11-17 08:49:33,164 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:33,164 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:33,174 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-17 08:49:33,175 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-17 08:49:33,185 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:33,185 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:33,185 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:33,186 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:33,187 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-11-17 08:49:33,188 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:33,188 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:33,209 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:33,209 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:33,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:33,211 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:33,211 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-17 08:49:33,213 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-17 08:49:33,213 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:33,265 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-17 08:49:33,269 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:33,269 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:33,269 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:33,269 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:33,269 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:33,269 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:49:33,269 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:33,269 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:33,269 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:33,269 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration6_Loop [2024-11-17 08:49:33,269 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:33,269 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:33,270 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,272 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,280 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,281 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,283 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:33,306 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:33,306 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:49:33,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:33,306 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:33,307 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:33,308 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-11-17 08:49:33,310 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:33,320 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:33,320 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:33,321 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:33,321 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:33,321 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:33,323 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:33,323 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:33,325 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:49:33,335 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:33,335 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:33,336 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:33,336 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:33,337 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2024-11-17 08:49:33,338 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:33,347 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:33,347 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:33,347 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:33,347 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:33,348 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:33,348 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:33,348 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:33,350 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:49:33,352 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-17 08:49:33,352 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-17 08:49:33,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:33,352 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:33,353 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:33,354 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-11-17 08:49:33,354 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:49:33,354 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-17 08:49:33,355 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:49:33,355 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-17 08:49:33,365 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:33,365 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-17 08:49:33,373 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:33,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:33,428 INFO L255 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-17 08:49:33,430 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:33,515 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:33,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:33,606 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-17 08:49:33,606 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:33,621 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:33,621 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-11-17 08:49:33,621 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:33,669 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 354 states and 450 transitions. Complement of second has 15 states. [2024-11-17 08:49:33,671 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-11-17 08:49:33,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:33,671 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-17 08:49:33,671 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 57 letters. Loop has 4 letters. [2024-11-17 08:49:33,671 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:33,671 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:49:33,681 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:33,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:33,736 INFO L255 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-17 08:49:33,738 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:33,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:33,885 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-17 08:49:33,886 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:33,903 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:33,904 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-11-17 08:49:33,904 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:33,952 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 354 states and 450 transitions. Complement of second has 15 states. [2024-11-17 08:49:33,953 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-11-17 08:49:33,953 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:33,954 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-17 08:49:33,954 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 57 letters. Loop has 4 letters. [2024-11-17 08:49:33,954 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:33,954 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:49:33,963 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:34,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:34,012 INFO L255 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-17 08:49:34,014 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:34,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:34,155 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-17 08:49:34,155 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:34,172 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:34,172 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-11-17 08:49:34,172 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100 Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:34,226 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 332 states and 428 transitions. cyclomatic complexity: 100. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 441 states and 538 transitions. Complement of second has 19 states. [2024-11-17 08:49:34,229 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-11-17 08:49:34,230 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:34,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-17 08:49:34,230 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 57 letters. Loop has 4 letters. [2024-11-17 08:49:34,230 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:34,230 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 61 letters. Loop has 4 letters. [2024-11-17 08:49:34,231 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:34,231 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 57 letters. Loop has 8 letters. [2024-11-17 08:49:34,231 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:34,231 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 441 states and 538 transitions. [2024-11-17 08:49:34,236 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-17 08:49:34,241 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 441 states to 342 states and 438 transitions. [2024-11-17 08:49:34,241 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 138 [2024-11-17 08:49:34,242 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 141 [2024-11-17 08:49:34,242 INFO L73 IsDeterministic]: Start isDeterministic. Operand 342 states and 438 transitions. [2024-11-17 08:49:34,242 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:34,242 INFO L218 hiAutomatonCegarLoop]: Abstraction has 342 states and 438 transitions. [2024-11-17 08:49:34,243 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 342 states and 438 transitions. [2024-11-17 08:49:34,256 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 342 to 340. [2024-11-17 08:49:34,256 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 340 states, 211 states have (on average 1.085308056872038) internal successors, (229), 224 states have internal predecessors, (229), 78 states have call successors, (82), 41 states have call predecessors, (82), 51 states have return successors, (125), 74 states have call predecessors, (125), 69 states have call successors, (125) [2024-11-17 08:49:34,258 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 340 states to 340 states and 436 transitions. [2024-11-17 08:49:34,258 INFO L240 hiAutomatonCegarLoop]: Abstraction has 340 states and 436 transitions. [2024-11-17 08:49:34,258 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 08:49:34,261 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2024-11-17 08:49:34,262 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=625, Unknown=0, NotChecked=0, Total=756 [2024-11-17 08:49:34,262 INFO L87 Difference]: Start difference. First operand 340 states and 436 transitions. Second operand has 28 states, 25 states have (on average 2.16) internal successors, (54), 18 states have internal predecessors, (54), 17 states have call successors, (19), 11 states have call predecessors, (19), 3 states have return successors, (7), 4 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-17 08:49:34,622 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 08:49:34,622 INFO L93 Difference]: Finished difference Result 552 states and 741 transitions. [2024-11-17 08:49:34,622 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 552 states and 741 transitions. [2024-11-17 08:49:34,629 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-17 08:49:34,637 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 552 states to 517 states and 697 transitions. [2024-11-17 08:49:34,637 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 199 [2024-11-17 08:49:34,637 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 212 [2024-11-17 08:49:34,637 INFO L73 IsDeterministic]: Start isDeterministic. Operand 517 states and 697 transitions. [2024-11-17 08:49:34,637 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:34,637 INFO L218 hiAutomatonCegarLoop]: Abstraction has 517 states and 697 transitions. [2024-11-17 08:49:34,639 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 517 states and 697 transitions. [2024-11-17 08:49:34,653 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 517 to 421. [2024-11-17 08:49:34,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 421 states, 262 states have (on average 1.083969465648855) internal successors, (284), 269 states have internal predecessors, (284), 105 states have call successors, (113), 57 states have call predecessors, (113), 54 states have return successors, (149), 94 states have call predecessors, (149), 94 states have call successors, (149) [2024-11-17 08:49:34,658 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 421 states to 421 states and 546 transitions. [2024-11-17 08:49:34,658 INFO L240 hiAutomatonCegarLoop]: Abstraction has 421 states and 546 transitions. [2024-11-17 08:49:34,658 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-17 08:49:34,659 INFO L425 stractBuchiCegarLoop]: Abstraction has 421 states and 546 transitions. [2024-11-17 08:49:34,659 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-17 08:49:34,659 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 421 states and 546 transitions. [2024-11-17 08:49:34,660 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-17 08:49:34,660 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:49:34,660 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:49:34,661 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [16, 15, 13, 12, 5, 3, 3, 2, 2, 2, 1, 1, 1, 1] [2024-11-17 08:49:34,662 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-17 08:49:34,662 INFO L745 eck$LassoCheckResult]: Stem: 6996#ULTIMATE.startENTRY 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(12, 2);call #Ultimate.allocInit(12, 3); 6997#ULTIMATE.init_returnLabel#1 assume true;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 := 10; 6998#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 7038#fiboENTRY ~n := #in~n; 7204#L8 assume !(~n < 1); 7203#L10 assume !(1 == ~n); 7195#L13-3 call #t~ret4 := fibo(~n - 1);< 7200#fiboENTRY ~n := #in~n; 7198#L8 assume !(~n < 1); 7197#L10 assume !(1 == ~n); 7184#L13-3 call #t~ret4 := fibo(~n - 1);< 7193#fiboENTRY ~n := #in~n; 7192#L8 assume !(~n < 1); 7191#L10 assume !(1 == ~n); 7188#L13-3 call #t~ret4 := fibo(~n - 1);< 7190#fiboENTRY ~n := #in~n; 7254#L8 assume !(~n < 1); 7242#L10 assume !(1 == ~n); 7235#L13-3 call #t~ret4 := fibo(~n - 1);< 7238#fiboENTRY ~n := #in~n; 7250#L8 assume !(~n < 1); 7240#L10 assume !(1 == ~n); 7212#L13-3 call #t~ret4 := fibo(~n - 1);< 7236#fiboENTRY ~n := #in~n; 7262#L8 assume !(~n < 1); 7261#L10 assume !(1 == ~n); 7256#L13-3 call #t~ret4 := fibo(~n - 1);< 7260#fiboENTRY ~n := #in~n; 7281#L8 assume !(~n < 1); 7279#L10 assume !(1 == ~n); 7247#L13-3 call #t~ret4 := fibo(~n - 1);< 7277#fiboENTRY ~n := #in~n; 7315#L8 assume !(~n < 1); 7314#L10 assume !(1 == ~n); 7245#L13-3 call #t~ret4 := fibo(~n - 1);< 7277#fiboENTRY ~n := #in~n; 7315#L8 assume !(~n < 1); 7314#L10 assume !(1 == ~n); 7245#L13-3 call #t~ret4 := fibo(~n - 1);< 7277#fiboENTRY ~n := #in~n; 7315#L8 assume !(~n < 1); 7314#L10 assume !(1 == ~n); 7245#L13-3 call #t~ret4 := fibo(~n - 1);< 7277#fiboENTRY ~n := #in~n; 7316#L8 assume !(~n < 1); 7371#L10 assume 1 == ~n;#res := 1; 7370#fiboFINAL assume true; 7369#fiboEXIT >#27#return; 7362#L13-2 call #t~ret5 := fibo(~n - 2);< 7364#fiboENTRY ~n := #in~n; 7367#L8 assume ~n < 1;#res := 0; 7365#fiboFINAL assume true; 7361#fiboEXIT >#25#return; 7360#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 7359#fiboFINAL assume true; 7355#fiboEXIT >#27#return; 7319#L13-2 call #t~ret5 := fibo(~n - 2);< 7321#fiboENTRY ~n := #in~n; 7326#L8 assume !(~n < 1); 7322#L10 assume 1 == ~n;#res := 1; 7272#fiboFINAL assume true; 7318#fiboEXIT >#25#return; 7228#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 7312#fiboFINAL assume true; 7243#fiboEXIT >#27#return; 7246#L13-2 call #t~ret5 := fibo(~n - 2);< 7249#fiboENTRY ~n := #in~n; 7324#L8 assume !(~n < 1); 7325#L10 assume !(1 == ~n); 7024#L13-3 call #t~ret4 := fibo(~n - 1);< 7067#fiboENTRY ~n := #in~n; 7392#L8 assume !(~n < 1); 7387#L10 assume !(1 == ~n); 7056#L13-3 call #t~ret4 := fibo(~n - 1);< 7055#fiboENTRY ~n := #in~n; 7062#L8 assume !(~n < 1); 7385#L10 assume !(1 == ~n); 7059#L13-3 [2024-11-17 08:49:34,662 INFO L747 eck$LassoCheckResult]: Loop: 7059#L13-3 call #t~ret4 := fibo(~n - 1);< 7055#fiboENTRY ~n := #in~n; 7062#L8 assume !(~n < 1); 7385#L10 assume !(1 == ~n); 7059#L13-3 [2024-11-17 08:49:34,662 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:34,664 INFO L85 PathProgramCache]: Analyzing trace with hash -1215864849, now seen corresponding path program 4 times [2024-11-17 08:49:34,664 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:34,665 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [292548304] [2024-11-17 08:49:34,665 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:34,665 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:34,673 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:34,910 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-11-17 08:49:34,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:34,918 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-17 08:49:34,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:34,921 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-17 08:49:34,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:34,922 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-17 08:49:34,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:34,923 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-11-17 08:49:34,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:34,925 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 254 proven. 128 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2024-11-17 08:49:34,925 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-17 08:49:34,925 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [292548304] [2024-11-17 08:49:34,925 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [292548304] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-17 08:49:34,925 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [942990634] [2024-11-17 08:49:34,925 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-17 08:49:34,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-17 08:49:34,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:34,928 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-17 08:49:34,929 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (36)] Waiting until timeout for monitored process [2024-11-17 08:49:34,966 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-17 08:49:34,966 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-17 08:49:34,967 INFO L255 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-17 08:49:34,968 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:35,063 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 262 proven. 145 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-11-17 08:49:35,063 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-17 08:49:35,427 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 262 proven. 150 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2024-11-17 08:49:35,428 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [942990634] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-17 08:49:35,428 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-17 08:49:35,428 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 23, 25] total 29 [2024-11-17 08:49:35,428 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1548015221] [2024-11-17 08:49:35,428 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-17 08:49:35,428 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-17 08:49:35,429 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:35,429 INFO L85 PathProgramCache]: Analyzing trace with hash 1717914, now seen corresponding path program 3 times [2024-11-17 08:49:35,429 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:49:35,429 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1421641726] [2024-11-17 08:49:35,429 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:49:35,429 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:49:35,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:35,431 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:49:35,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:49:35,432 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:49:35,472 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:35,472 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:35,472 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:35,472 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:35,472 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-17 08:49:35,472 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:35,472 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:35,472 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:35,472 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration7_Loop [2024-11-17 08:49:35,472 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:35,472 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:35,473 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:35,474 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:35,480 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:35,481 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:35,509 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:35,510 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-17 08:49:35,510 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:35,510 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:35,511 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:35,512 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-11-17 08:49:35,513 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:35,513 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:35,524 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-17 08:49:35,524 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-17 08:49:35,534 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:35,534 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:35,534 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:35,535 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:35,536 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-11-17 08:49:35,536 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-17 08:49:35,536 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:35,564 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:35,564 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:35,564 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:35,565 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:35,566 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-11-17 08:49:35,566 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-17 08:49:35,566 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-17 08:49:36,188 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-17 08:49:36,193 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:36,193 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:49:36,193 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:49:36,193 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:49:36,193 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:49:36,193 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:49:36,193 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:36,193 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:49:36,193 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:49:36,193 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration7_Loop [2024-11-17 08:49:36,193 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:49:36,193 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:49:36,194 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:36,195 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:36,200 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:36,201 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:49:36,222 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:49:36,222 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:49:36,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:36,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:36,223 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:36,224 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-11-17 08:49:36,225 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:36,234 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:36,234 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:36,234 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:36,234 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:36,234 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:36,235 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:36,235 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:36,236 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:49:36,246 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:36,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:36,246 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:36,247 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:36,248 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-11-17 08:49:36,248 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:49:36,257 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:49:36,257 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:49:36,257 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:49:36,258 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:49:36,258 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:49:36,258 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:49:36,258 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:49:36,260 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:49:36,262 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-17 08:49:36,262 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-17 08:49:36,262 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:49:36,262 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:49:36,263 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:49:36,264 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-11-17 08:49:36,264 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:49:36,264 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-17 08:49:36,264 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:49:36,265 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-17 08:49:36,274 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Ended with exit code 0 [2024-11-17 08:49:36,274 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-17 08:49:36,281 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:36,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:36,346 INFO L255 TraceCheckSpWp]: Trace formula consists of 625 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-17 08:49:36,347 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:36,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:36,559 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-17 08:49:36,559 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:36,582 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:36,583 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-11-17 08:49:36,583 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:36,622 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 443 states and 569 transitions. Complement of second has 18 states. [2024-11-17 08:49:36,622 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-11-17 08:49:36,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:36,623 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-11-17 08:49:36,623 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 77 letters. Loop has 4 letters. [2024-11-17 08:49:36,623 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:36,623 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:49:36,631 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:36,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:36,693 INFO L255 TraceCheckSpWp]: Trace formula consists of 625 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-17 08:49:36,695 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:36,837 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:36,919 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:36,919 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-17 08:49:36,920 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:36,939 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:36,939 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-11-17 08:49:36,940 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:36,995 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 451 states and 577 transitions. Complement of second has 17 states. [2024-11-17 08:49:36,995 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-11-17 08:49:36,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:36,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-11-17 08:49:36,996 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 77 letters. Loop has 4 letters. [2024-11-17 08:49:36,996 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:36,996 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:49:37,003 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:49:37,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:37,067 INFO L255 TraceCheckSpWp]: Trace formula consists of 625 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-17 08:49:37,068 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:37,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:49:37,263 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-17 08:49:37,263 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:49:37,285 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:49:37,285 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 4 loop predicates [2024-11-17 08:49:37,285 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:37,330 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 421 states and 546 transitions. cyclomatic complexity: 129. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 558 states and 718 transitions. Complement of second has 21 states. [2024-11-17 08:49:37,330 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-11-17 08:49:37,331 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-17 08:49:37,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 20 transitions. [2024-11-17 08:49:37,331 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 77 letters. Loop has 4 letters. [2024-11-17 08:49:37,331 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:37,332 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 81 letters. Loop has 4 letters. [2024-11-17 08:49:37,332 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:37,332 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 20 transitions. Stem has 77 letters. Loop has 8 letters. [2024-11-17 08:49:37,336 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:49:37,336 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 558 states and 718 transitions. [2024-11-17 08:49:37,340 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-17 08:49:37,344 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 558 states to 429 states and 555 transitions. [2024-11-17 08:49:37,344 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 130 [2024-11-17 08:49:37,344 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 141 [2024-11-17 08:49:37,344 INFO L73 IsDeterministic]: Start isDeterministic. Operand 429 states and 555 transitions. [2024-11-17 08:49:37,344 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:49:37,344 INFO L218 hiAutomatonCegarLoop]: Abstraction has 429 states and 555 transitions. [2024-11-17 08:49:37,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 429 states and 555 transitions. [2024-11-17 08:49:37,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 429 to 419. [2024-11-17 08:49:37,350 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 419 states, 260 states have (on average 1.0846153846153845) internal successors, (282), 269 states have internal predecessors, (282), 105 states have call successors, (113), 55 states have call predecessors, (113), 54 states have return successors, (149), 94 states have call predecessors, (149), 94 states have call successors, (149) [2024-11-17 08:49:37,353 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 419 states to 419 states and 544 transitions. [2024-11-17 08:49:37,353 INFO L240 hiAutomatonCegarLoop]: Abstraction has 419 states and 544 transitions. [2024-11-17 08:49:37,353 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-17 08:49:37,354 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2024-11-17 08:49:37,354 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=152, Invalid=660, Unknown=0, NotChecked=0, Total=812 [2024-11-17 08:49:37,354 INFO L87 Difference]: Start difference. First operand 419 states and 544 transitions. Second operand has 29 states, 28 states have (on average 2.0357142857142856) internal successors, (57), 20 states have internal predecessors, (57), 16 states have call successors, (19), 11 states have call predecessors, (19), 4 states have return successors, (10), 5 states have call predecessors, (10), 7 states have call successors, (10) [2024-11-17 08:49:37,841 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-17 08:49:37,841 INFO L93 Difference]: Finished difference Result 456 states and 518 transitions. [2024-11-17 08:49:37,841 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 456 states and 518 transitions. [2024-11-17 08:49:37,845 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-17 08:49:37,845 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 456 states to 0 states and 0 transitions. [2024-11-17 08:49:37,845 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-17 08:49:37,845 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-17 08:49:37,845 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-17 08:49:37,845 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-17 08:49:37,845 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-17 08:49:37,845 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-17 08:49:37,846 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2024-11-17 08:49:37,846 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-17 08:49:37,846 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-11-17 08:49:37,846 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-17 08:49:37,847 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-17 08:49:37,847 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-17 08:49:37,852 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 17.11 08:49:37 BoogieIcfgContainer [2024-11-17 08:49:37,852 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-17 08:49:37,853 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-17 08:49:37,853 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-17 08:49:37,853 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-17 08:49:37,854 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 08:49:26" (3/4) ... [2024-11-17 08:49:37,855 INFO L146 WitnessPrinter]: No result that supports witness generation found [2024-11-17 08:49:37,856 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-17 08:49:37,856 INFO L158 Benchmark]: Toolchain (without parser) took 12061.41ms. Allocated memory was 161.5MB in the beginning and 285.2MB in the end (delta: 123.7MB). Free memory was 128.8MB in the beginning and 231.3MB in the end (delta: -102.5MB). Peak memory consumption was 21.2MB. Max. memory is 16.1GB. [2024-11-17 08:49:37,857 INFO L158 Benchmark]: CDTParser took 0.37ms. Allocated memory is still 121.6MB. Free memory was 84.3MB in the beginning and 84.1MB in the end (delta: 118.9kB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-17 08:49:37,857 INFO L158 Benchmark]: CACSL2BoogieTranslator took 203.28ms. Allocated memory is still 161.5MB. Free memory was 128.8MB in the beginning and 117.3MB in the end (delta: 11.5MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-17 08:49:37,857 INFO L158 Benchmark]: Boogie Procedure Inliner took 23.79ms. Allocated memory is still 161.5MB. Free memory was 117.3MB in the beginning and 116.3MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-17 08:49:37,857 INFO L158 Benchmark]: Boogie Preprocessor took 24.50ms. Allocated memory is still 161.5MB. Free memory was 116.2MB in the beginning and 114.2MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-17 08:49:37,857 INFO L158 Benchmark]: IcfgBuilder took 213.34ms. Allocated memory is still 161.5MB. Free memory was 114.2MB in the beginning and 103.7MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-17 08:49:37,858 INFO L158 Benchmark]: BuchiAutomizer took 11588.72ms. Allocated memory was 161.5MB in the beginning and 285.2MB in the end (delta: 123.7MB). Free memory was 103.7MB in the beginning and 232.4MB in the end (delta: -128.7MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-17 08:49:37,858 INFO L158 Benchmark]: Witness Printer took 3.11ms. Allocated memory is still 285.2MB. Free memory was 232.4MB in the beginning and 231.3MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-17 08:49:37,859 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.37ms. Allocated memory is still 121.6MB. Free memory was 84.3MB in the beginning and 84.1MB in the end (delta: 118.9kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 203.28ms. Allocated memory is still 161.5MB. Free memory was 128.8MB in the beginning and 117.3MB in the end (delta: 11.5MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 23.79ms. Allocated memory is still 161.5MB. Free memory was 117.3MB in the beginning and 116.3MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 24.50ms. Allocated memory is still 161.5MB. Free memory was 116.2MB in the beginning and 114.2MB in the end (delta: 2.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * IcfgBuilder took 213.34ms. Allocated memory is still 161.5MB. Free memory was 114.2MB in the beginning and 103.7MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 11588.72ms. Allocated memory was 161.5MB in the beginning and 285.2MB in the end (delta: 123.7MB). Free memory was 103.7MB in the beginning and 232.4MB in the end (delta: -128.7MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 3.11ms. Allocated memory is still 285.2MB. Free memory was 232.4MB in the beginning and 231.3MB in the end (delta: 1.0MB). 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 11 terminating modules (6 trivial, 2 deterministic, 3 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 nondeterministic module has affine ranking function n and consists of 11 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. One nondeterministic module has affine ranking function n and consists of 6 locations. 6 modules have a trivial ranking function, the largest among these consists of 29 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 11.5s and 8 iterations. TraceHistogramMax:16. Analysis of lassos took 6.1s. Construction of modules took 0.9s. Büchi inclusion checks took 4.2s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 10. Automata minimization 0.1s AutomataMinimizationTime, 10 MinimizatonAttempts, 238 StatesRemovedByMinimization, 8 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 3, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 16/46 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 602 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 564 mSDsluCounter, 829 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 583 mSDsCounter, 415 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1674 IncrementalHoareTripleChecker+Invalid, 2089 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 415 mSolverCounterUnsat, 246 mSDtfsCounter, 1674 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI2 SILT4 lasso0 LassoPreprocessingBenchmarks: Lassos: inital16 mio100 ax100 hnf100 lsp88 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq179 hnf93 smp75 dnf100 smp100 tf111 neg100 sie107 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 17ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.4s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-17 08:49:37,877 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (36)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:38,081 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (29)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:38,281 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Ended with exit code 0 [2024-11-17 08:49:38,481 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2024-11-17 08:49:38,683 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2024-11-17 08:49:38,883 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Ended with exit code 0 [2024-11-17 08:49:39,084 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE