./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_7-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 023d838f 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_7-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 40add90db9f8d501baba3978de407d6383e788a1a5fafc7225d7676b58d18c84 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-10 23:17:27,904 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-10 23:17:27,981 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-10 23:17:27,988 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-10 23:17:27,989 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-10 23:17:27,990 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2024-11-10 23:17:28,015 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-10 23:17:28,017 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-10 23:17:28,018 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-10 23:17:28,019 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-10 23:17:28,020 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-10 23:17:28,021 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-10 23:17:28,021 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-10 23:17:28,022 INFO L153 SettingsManager]: * Use SBE=true [2024-11-10 23:17:28,025 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-10 23:17:28,025 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-10 23:17:28,025 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-10 23:17:28,026 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-10 23:17:28,026 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-10 23:17:28,026 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-10 23:17:28,026 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-10 23:17:28,027 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-10 23:17:28,027 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-10 23:17:28,027 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-10 23:17:28,028 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-10 23:17:28,028 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-10 23:17:28,028 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-10 23:17:28,028 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-10 23:17:28,029 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-10 23:17:28,029 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-10 23:17:28,029 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-10 23:17:28,029 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-10 23:17:28,030 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-10 23:17:28,030 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-10 23:17:28,030 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-10 23:17:28,031 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-10 23:17:28,032 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-10 23:17:28,032 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-10 23:17:28,032 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-10 23:17:28,033 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-10 23:17:28,033 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 -> 40add90db9f8d501baba3978de407d6383e788a1a5fafc7225d7676b58d18c84 [2024-11-10 23:17:28,286 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-10 23:17:28,314 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-10 23:17:28,317 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-10 23:17:28,318 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-10 23:17:28,319 INFO L274 PluginConnector]: CDTParser initialized [2024-11-10 23:17:28,320 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_7-2.c [2024-11-10 23:17:29,746 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-10 23:17:29,933 INFO L384 CDTParser]: Found 1 translation units. [2024-11-10 23:17:29,933 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_7-2.c [2024-11-10 23:17:29,943 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/020f51cb2/8e98ea52fd7a4a239fc29f51e86b7c66/FLAG0b98e4949 [2024-11-10 23:17:29,959 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/020f51cb2/8e98ea52fd7a4a239fc29f51e86b7c66 [2024-11-10 23:17:29,964 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-10 23:17:29,965 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-10 23:17:29,967 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-10 23:17:29,967 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-10 23:17:29,972 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-10 23:17:29,973 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 11:17:29" (1/1) ... [2024-11-10 23:17:29,974 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@48b86e73 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:29, skipping insertion in model container [2024-11-10 23:17:29,974 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 11:17:29" (1/1) ... [2024-11-10 23:17:29,993 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-10 23:17:30,186 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 23:17:30,200 INFO L200 MainTranslator]: Completed pre-run [2024-11-10 23:17:30,215 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 23:17:30,233 INFO L204 MainTranslator]: Completed translation [2024-11-10 23:17:30,234 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30 WrapperNode [2024-11-10 23:17:30,234 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-10 23:17:30,235 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-10 23:17:30,235 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-10 23:17:30,235 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-10 23:17:30,242 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,249 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,264 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-10 23:17:30,265 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-10 23:17:30,266 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-10 23:17:30,266 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-10 23:17:30,266 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-10 23:17:30,275 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,276 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,277 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,288 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-10 23:17:30,289 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,289 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,292 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,293 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,294 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,295 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,296 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-10 23:17:30,297 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-10 23:17:30,297 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-10 23:17:30,297 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-10 23:17:30,298 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (1/1) ... [2024-11-10 23:17:30,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:30,318 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:30,333 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-10 23:17:30,336 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-10 23:17:30,380 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-10 23:17:30,380 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-10 23:17:30,380 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-10 23:17:30,380 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-10 23:17:30,380 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-10 23:17:30,380 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-10 23:17:30,445 INFO L256 CfgBuilder]: Building ICFG [2024-11-10 23:17:30,447 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-10 23:17:30,527 INFO L1247 $ProcedureCfgBuilder]: dead code at ProgramPoint L13: havoc #t~ret4;havoc #t~ret5; [2024-11-10 23:17:30,536 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-10 23:17:30,536 INFO L307 CfgBuilder]: Performing block encoding [2024-11-10 23:17:30,548 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-10 23:17:30,548 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-10 23:17:30,549 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 11:17:30 BoogieIcfgContainer [2024-11-10 23:17:30,549 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-10 23:17:30,551 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-10 23:17:30,552 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-10 23:17:30,555 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-10 23:17:30,556 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:30,557 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 10.11 11:17:29" (1/3) ... [2024-11-10 23:17:30,558 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@76f7f3a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 10.11 11:17:30, skipping insertion in model container [2024-11-10 23:17:30,558 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:30,558 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:30" (2/3) ... [2024-11-10 23:17:30,560 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@76f7f3a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 10.11 11:17:30, skipping insertion in model container [2024-11-10 23:17:30,560 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:30,560 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 11:17:30" (3/3) ... [2024-11-10 23:17:30,561 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_7-2.c [2024-11-10 23:17:30,630 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-10 23:17:30,630 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-10 23:17:30,631 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-10 23:17:30,631 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-10 23:17:30,631 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-10 23:17:30,632 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-10 23:17:30,634 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-10 23:17:30,634 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-10 23:17:30,638 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-10 23:17:30,658 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:30,658 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:30,658 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:30,664 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-10 23:17:30,664 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:30,664 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-10 23:17:30,665 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-10 23:17:30,668 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:30,668 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:30,669 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:30,669 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-10 23:17:30,669 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:30,674 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(11, 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 := 7; 18#L27-1true call main_#t~ret6#1 := fibo(main_~x~0#1);< 7#fiboENTRYtrue [2024-11-10 23:17:30,674 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-10 23:17:30,679 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:30,680 INFO L85 PathProgramCache]: Analyzing trace with hash 39702, now seen corresponding path program 1 times [2024-11-10 23:17:30,688 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:30,689 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [720348799] [2024-11-10 23:17:30,689 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:30,690 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:30,803 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:30,803 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:30,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:30,832 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:30,834 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:30,835 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 1 times [2024-11-10 23:17:30,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:30,835 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [4554021] [2024-11-10 23:17:30,836 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:30,836 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:30,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:30,855 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:30,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:30,861 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:30,862 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:30,862 INFO L85 PathProgramCache]: Analyzing trace with hash -1988460259, now seen corresponding path program 1 times [2024-11-10 23:17:30,863 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:30,863 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1365676352] [2024-11-10 23:17:30,863 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:30,863 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:30,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:30,874 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:30,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:30,885 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:31,010 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:31,011 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:31,011 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:31,011 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:31,011 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:31,012 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,012 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:31,012 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:31,012 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration1_Loop [2024-11-10 23:17:31,012 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:31,013 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:31,028 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,037 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,039 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,042 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,045 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,133 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:31,134 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:31,136 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,136 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,137 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-10 23:17:31,138 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-10 23:17:31,140 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:31,140 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:31,159 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:31,159 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-10 23:17:31,171 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-10 23:17:31,172 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,173 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,174 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-10 23:17:31,175 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-10 23:17:31,176 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:31,176 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:31,189 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:31,189 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-10 23:17:31,200 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:31,201 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,201 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,202 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-10 23:17:31,203 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-10 23:17:31,204 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:31,204 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:31,215 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:31,216 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-10 23:17:31,227 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:31,227 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,228 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,229 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-10 23:17:31,230 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-10 23:17:31,230 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:31,230 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:31,242 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:31,242 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-10 23:17:31,253 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-10 23:17:31,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,255 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-10 23:17:31,256 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-10 23:17:31,256 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:31,256 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:31,282 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:31,282 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,283 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,284 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-10 23:17:31,285 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-10 23:17:31,285 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:31,286 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:31,341 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:31,346 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:31,347 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:31,347 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:31,347 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:31,347 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:31,347 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:31,347 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,347 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:31,348 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:31,348 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration1_Loop [2024-11-10 23:17:31,348 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:31,348 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:31,349 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,353 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,357 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,360 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,362 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,421 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:31,426 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:31,427 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,428 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,429 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-10 23:17:31,431 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-10 23:17:31,432 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-10 23:17:31,446 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:31,446 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:31,447 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:31,447 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:31,447 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:31,449 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:31,450 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:31,453 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:31,463 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-11-10 23:17:31,463 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,465 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-10 23:17:31,465 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-10 23:17:31,466 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-10 23:17:31,476 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:31,477 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:31,477 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:31,477 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:31,477 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:31,478 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:31,478 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:31,480 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:31,492 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-10 23:17:31,493 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,493 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,494 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-10 23:17:31,495 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-10 23:17:31,496 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-10 23:17:31,506 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:31,506 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:31,507 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:31,507 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:31,507 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:31,507 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:31,507 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:31,511 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:31,526 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-10 23:17:31,526 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,528 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-10 23:17:31,529 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-10 23:17:31,530 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-10 23:17:31,540 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:31,540 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:31,540 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:31,540 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:31,540 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:31,541 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:31,541 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:31,543 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:31,554 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-10 23:17:31,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,555 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,556 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-10 23:17:31,557 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-10 23:17:31,557 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-10 23:17:31,567 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:31,568 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:31,568 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:31,568 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:31,568 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:31,569 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:31,569 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:31,572 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:31,575 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:31,576 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:31,577 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,577 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,595 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-10 23:17:31,597 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-10 23:17:31,598 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:31,598 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:31,598 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:31,599 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-10 23:17:31,611 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-10 23:17:31,614 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:31,639 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:31,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:31,664 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-10 23:17:31,666 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:31,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:31,693 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:31,694 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:31,750 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-10 23:17:31,786 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-10 23:17:31,789 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-10 23:17:31,890 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-10 23:17:31,892 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-10 23:17:31,896 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-10 23:17:31,897 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-10 23:17:31,899 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-10 23:17:31,899 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:31,900 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-10 23:17:31,900 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:31,900 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-10 23:17:31,900 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:31,901 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-10 23:17:31,904 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:31,909 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-10 23:17:31,912 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-10 23:17:31,912 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-10 23:17:31,913 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-10 23:17:31,914 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:31,914 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-10 23:17:31,927 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-10 23:17:31,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-10 23:17:31,936 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-10 23:17:31,937 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-10 23:17:31,938 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-10 23:17:31,938 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-10 23:17:31,939 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-10 23:17:31,939 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-10 23:17:31,940 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:31,940 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:31,940 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:31,941 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:31,941 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:31,942 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(11, 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 := 7; 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-10 23:17:31,942 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-10 23:17:31,942 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:31,942 INFO L85 PathProgramCache]: Analyzing trace with hash 1475604923, now seen corresponding path program 1 times [2024-11-10 23:17:31,943 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:31,943 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [892563166] [2024-11-10 23:17:31,943 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:31,943 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:31,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,058 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-10 23:17:32,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,096 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-10 23:17:32,097 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:32,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [892563166] [2024-11-10 23:17:32,097 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [892563166] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 23:17:32,098 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 23:17:32,098 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-10 23:17:32,098 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2020557360] [2024-11-10 23:17:32,099 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 23:17:32,101 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:32,101 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:32,101 INFO L85 PathProgramCache]: Analyzing trace with hash 93365724, now seen corresponding path program 1 times [2024-11-10 23:17:32,102 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:32,102 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1143733192] [2024-11-10 23:17:32,102 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:32,102 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:32,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,156 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 23:17:32,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,209 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-10 23:17:32,209 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:32,209 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1143733192] [2024-11-10 23:17:32,209 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1143733192] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 23:17:32,210 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 23:17:32,210 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-10 23:17:32,210 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1988732473] [2024-11-10 23:17:32,210 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 23:17:32,211 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-10 23:17:32,211 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:32,213 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-10 23:17:32,214 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-10 23:17:32,215 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-10 23:17:32,276 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:32,276 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-10 23:17:32,277 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-10 23:17:32,278 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:32,279 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-10 23:17:32,279 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-10 23:17:32,280 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-10 23:17:32,280 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-10 23:17:32,280 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:32,280 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:32,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-10 23:17:32,283 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-10 23:17:32,283 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-10 23:17:32,284 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-10 23:17:32,284 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:32,285 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-10 23:17:32,286 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:32,286 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-10 23:17:32,286 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-10 23:17:32,288 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:32,290 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:32,290 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:32,291 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:32,291 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-10 23:17:32,291 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(11, 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 := 7; 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-10 23:17:32,292 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-10 23:17:32,292 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:32,292 INFO L85 PathProgramCache]: Analyzing trace with hash -1500686953, now seen corresponding path program 1 times [2024-11-10 23:17:32,293 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:32,293 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1031068407] [2024-11-10 23:17:32,293 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:32,294 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:32,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,374 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-10 23:17:32,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,414 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-10 23:17:32,415 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:32,415 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1031068407] [2024-11-10 23:17:32,416 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1031068407] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:32,416 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1297768362] [2024-11-10 23:17:32,416 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:32,416 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:32,416 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:32,418 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-10 23:17:32,420 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-10 23:17:32,449 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,450 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:32,451 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:32,484 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-10 23:17:32,485 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:32,611 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-10 23:17:32,612 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1297768362] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:32,612 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:32,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-10 23:17:32,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [92452423] [2024-11-10 23:17:32,612 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:32,613 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:32,613 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:32,613 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 1 times [2024-11-10 23:17:32,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:32,613 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2025578213] [2024-11-10 23:17:32,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:32,614 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:32,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:32,627 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:32,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:32,639 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:32,966 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:32,967 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:32,967 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:32,967 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:32,967 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:32,967 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:32,967 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:32,968 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:32,968 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration3_Loop [2024-11-10 23:17:32,968 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:32,968 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:32,969 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:32,972 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:32,974 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:32,984 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,037 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:33,038 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:33,038 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,041 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-10 23:17:33,044 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-10 23:17:33,045 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:33,045 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:33,059 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:33,059 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-10 23:17:33,069 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:33,070 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,070 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,071 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-10 23:17:33,072 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-10 23:17:33,072 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:33,072 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:33,083 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:33,083 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-10 23:17:33,093 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-11-10 23:17:33,093 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,093 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,094 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-10 23:17:33,096 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-10 23:17:33,097 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:33,097 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:33,131 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-10 23:17:33,132 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,134 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-10 23:17:33,135 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-10 23:17:33,136 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:33,136 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:33,603 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:33,608 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-10 23:17:33,609 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:33,609 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:33,609 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:33,609 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:33,609 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:33,609 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,609 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:33,609 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:33,609 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration3_Loop [2024-11-10 23:17:33,609 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:33,609 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:33,610 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,619 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,620 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,624 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,680 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:33,680 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:33,681 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,681 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,682 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-10 23:17:33,683 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-10 23:17:33,684 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-10 23:17:33,693 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:33,694 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:33,694 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:33,694 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:33,694 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:33,695 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:33,695 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:33,698 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:33,701 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:33,701 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:33,702 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,704 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-10 23:17:33,709 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-10 23:17:33,709 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:33,709 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:33,709 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:33,710 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:33,724 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-11-10 23:17:33,726 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:33,744 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:33,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:33,766 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:33,767 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:33,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:33,886 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:33,889 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:33,992 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-10 23:17:34,024 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-10 23:17:34,169 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-10 23:17:34,170 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-10 23:17:34,171 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-10 23:17:34,406 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-10 23:17:34,407 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-10 23:17:34,408 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-10 23:17:34,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-11-10 23:17:34,409 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-11-10 23:17:34,410 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:34,410 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-11-10 23:17:34,410 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:34,410 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-11-10 23:17:34,411 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:34,411 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-11-10 23:17:34,418 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:34,425 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-11-10 23:17:34,426 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-10 23:17:34,426 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-10 23:17:34,426 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-11-10 23:17:34,427 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:34,427 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-11-10 23:17:34,427 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-11-10 23:17:34,438 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-11-10 23:17:34,438 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-10 23:17:34,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-11-10 23:17:34,441 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-11-10 23:17:34,441 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:34,441 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-10 23:17:34,442 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-10 23:17:34,442 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-10 23:17:34,566 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:34,566 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-11-10 23:17:34,566 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-11-10 23:17:34,570 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:34,574 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-11-10 23:17:34,574 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-11-10 23:17:34,574 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-11-10 23:17:34,575 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-11-10 23:17:34,575 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:34,575 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-11-10 23:17:34,575 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-11-10 23:17:34,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-11-10 23:17:34,586 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-10 23:17:34,588 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-11-10 23:17:34,588 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-10 23:17:34,588 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-10 23:17:34,589 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-10 23:17:34,589 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-10 23:17:34,589 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-11-10 23:17:34,591 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:34,592 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:34,592 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:34,593 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:34,593 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-10 23:17:34,593 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(11, 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 := 7; 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-10 23:17:34,594 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-10 23:17:34,594 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:34,594 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 1 times [2024-11-10 23:17:34,594 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:34,595 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [180895504] [2024-11-10 23:17:34,595 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:34,595 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:34,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:34,723 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-10 23:17:34,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:34,786 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:34,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:34,821 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:34,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:34,830 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-10 23:17:34,832 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:34,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [180895504] [2024-11-10 23:17:34,832 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [180895504] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:34,832 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [948190406] [2024-11-10 23:17:34,833 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:34,833 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:34,833 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:34,835 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-10 23:17:34,837 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-10 23:17:34,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:34,879 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-10 23:17:34,880 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:34,947 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-10 23:17:34,947 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:35,203 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-10 23:17:35,204 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [948190406] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:35,204 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:35,204 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 18 [2024-11-10 23:17:35,204 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [542763029] [2024-11-10 23:17:35,204 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:35,205 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:35,205 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:35,205 INFO L85 PathProgramCache]: Analyzing trace with hash -1547808212, now seen corresponding path program 1 times [2024-11-10 23:17:35,205 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:35,205 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1491737945] [2024-11-10 23:17:35,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:35,206 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:35,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,224 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 23:17:35,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,242 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:35,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,262 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:35,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,289 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-10 23:17:35,290 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:35,290 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1491737945] [2024-11-10 23:17:35,290 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1491737945] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:35,290 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1895536506] [2024-11-10 23:17:35,291 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:35,291 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:35,291 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:35,293 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-10 23:17:35,294 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-10 23:17:35,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,328 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:35,329 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:35,359 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-10 23:17:35,360 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:35,496 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-10 23:17:35,496 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1895536506] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:35,496 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:35,496 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-10 23:17:35,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [605685115] [2024-11-10 23:17:35,496 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:35,497 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-10 23:17:35,498 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:35,498 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-10 23:17:35,499 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-11-10 23:17:35,499 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-10 23:17:35,589 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:35,589 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-11-10 23:17:35,589 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-11-10 23:17:35,591 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:35,592 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-11-10 23:17:35,592 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-11-10 23:17:35,592 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-10 23:17:35,592 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-11-10 23:17:35,592 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:35,592 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:35,592 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-11-10 23:17:35,596 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-11-10 23:17:35,596 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-10 23:17:35,597 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-11-10 23:17:35,597 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:35,601 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-10 23:17:35,602 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:35,603 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-10 23:17:35,603 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-11-10 23:17:35,604 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:35,607 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:35,607 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:35,608 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:35,608 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-10 23:17:35,609 INFO L745 eck$LassoCheckResult]: Stem: 1468#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(11, 2);call #Ultimate.allocInit(12, 3); 1469#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 := 7; 1476#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1495#fiboENTRY ~n := #in~n; 1504#L8 assume !(~n < 1); 1506#L10 assume !(1 == ~n); 1481#L13-3 call #t~ret4 := fibo(~n - 1);< 1480#fiboENTRY ~n := #in~n; 1482#L8 assume !(~n < 1); 1494#L10 assume !(1 == ~n); 1489#L13-3 call #t~ret4 := fibo(~n - 1);< 1498#fiboENTRY ~n := #in~n; 1488#L8 assume !(~n < 1); 1491#L10 assume !(1 == ~n); 1490#L13-3 call #t~ret4 := fibo(~n - 1);< 1498#fiboENTRY ~n := #in~n; 1488#L8 assume !(~n < 1); 1491#L10 assume !(1 == ~n); 1490#L13-3 call #t~ret4 := fibo(~n - 1);< 1498#fiboENTRY ~n := #in~n; 1505#L8 assume !(~n < 1); 1492#L10 assume 1 == ~n;#res := 1; 1493#fiboFINAL assume true; 1511#fiboEXIT >#27#return; 1478#L13-2 call #t~ret5 := fibo(~n - 2);< 1477#fiboENTRY ~n := #in~n; 1479#L8 assume ~n < 1;#res := 0; 1487#fiboFINAL assume true; 1485#fiboEXIT >#25#return; 1486#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1520#fiboFINAL assume true; 1517#fiboEXIT >#27#return; 1473#L13-2 [2024-11-10 23:17:35,609 INFO L747 eck$LassoCheckResult]: Loop: 1473#L13-2 call #t~ret5 := fibo(~n - 2);< 1497#fiboENTRY ~n := #in~n; 1502#L8 assume !(~n < 1); 1500#L10 assume !(1 == ~n); 1471#L13-3 call #t~ret4 := fibo(~n - 1);< 1497#fiboENTRY ~n := #in~n; 1502#L8 assume !(~n < 1); 1500#L10 assume !(1 == ~n); 1471#L13-3 call #t~ret4 := fibo(~n - 1);< 1497#fiboENTRY ~n := #in~n; 1502#L8 assume !(~n < 1); 1500#L10 assume 1 == ~n;#res := 1; 1501#fiboFINAL assume true; 1508#fiboEXIT >#27#return; 1470#L13-2 call #t~ret5 := fibo(~n - 2);< 1475#fiboENTRY ~n := #in~n; 1521#L8 assume ~n < 1;#res := 0; 1503#fiboFINAL assume true; 1516#fiboEXIT >#25#return; 1499#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1483#fiboFINAL assume true; 1484#fiboEXIT >#27#return; 1473#L13-2 [2024-11-10 23:17:35,609 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:35,609 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 2 times [2024-11-10 23:17:35,609 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:35,610 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1098261132] [2024-11-10 23:17:35,610 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:35,610 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:35,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,696 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-10 23:17:35,699 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,744 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:35,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,768 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:35,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,773 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-10 23:17:35,774 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:35,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1098261132] [2024-11-10 23:17:35,774 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1098261132] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:35,774 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [40872437] [2024-11-10 23:17:35,774 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-10 23:17:35,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:35,775 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:35,777 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-10 23:17:35,781 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-10 23:17:35,858 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-10 23:17:35,858 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:35,859 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-10 23:17:35,861 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:35,920 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-10 23:17:35,920 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:36,161 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-10 23:17:36,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [40872437] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:36,162 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:36,162 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 18 [2024-11-10 23:17:36,163 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [549161038] [2024-11-10 23:17:36,163 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:36,163 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:36,164 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:36,164 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 2 times [2024-11-10 23:17:36,164 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:36,164 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1764965653] [2024-11-10 23:17:36,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:36,164 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:36,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:36,174 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:36,176 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:36,178 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:36,382 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:36,382 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:36,382 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:36,382 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:36,382 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:36,382 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:36,382 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:36,383 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:36,383 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration5_Loop [2024-11-10 23:17:36,383 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:36,383 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:36,384 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,386 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,390 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,393 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,395 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,428 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:36,428 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:36,428 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:36,429 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:36,431 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-10 23:17:36,432 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-10 23:17:36,434 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:36,434 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:36,448 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:36,448 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-10 23:17:36,463 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-10 23:17:36,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:36,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:36,465 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-10 23:17:36,466 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-10 23:17:36,467 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:36,467 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:36,492 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-10 23:17:36,493 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:36,493 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:36,494 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-10 23:17:36,495 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-10 23:17:36,496 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:36,496 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:36,510 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:36,523 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-10 23:17:36,523 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:36,523 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:36,523 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:36,523 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:36,523 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:36,524 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:36,524 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:36,524 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:36,524 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration5_Loop [2024-11-10 23:17:36,524 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:36,524 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:36,525 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,529 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,531 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,535 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,537 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:36,573 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:36,573 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:36,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:36,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:36,575 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-10 23:17:36,578 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-10 23:17:36,579 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-10 23:17:36,593 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:36,593 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:36,593 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:36,593 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:36,594 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:36,595 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:36,595 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:36,599 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:36,605 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:36,605 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:36,605 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:36,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:36,607 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-10 23:17:36,609 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-10 23:17:36,610 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:36,610 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:36,610 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:36,610 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:36,625 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-10 23:17:36,626 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:36,642 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:36,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:36,691 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:36,692 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:36,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:36,911 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:36,913 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:37,049 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-10 23:17:37,050 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-10 23:17:37,050 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-10 23:17:37,130 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-10 23:17:37,130 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-10 23:17:37,131 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-10 23:17:37,131 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-10 23:17:37,132 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:37,132 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:37,132 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:37,140 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:37,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:37,184 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:37,187 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:37,381 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:37,383 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:37,384 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:37,497 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-10 23:17:37,498 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-10 23:17:37,498 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-10 23:17:37,605 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2024-11-10 23:17:37,608 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-10 23:17:37,611 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-10 23:17:37,612 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-10 23:17:37,612 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-10 23:17:37,612 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:37,612 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:37,612 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:37,626 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:37,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:37,665 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:37,670 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:37,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:37,844 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:37,845 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:37,963 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-10 23:17:37,964 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-10 23:17:37,964 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-10 23:17:38,217 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-10 23:17:38,218 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-10 23:17:38,219 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-10 23:17:38,220 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-11-10 23:17:38,220 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:38,221 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:38,221 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 54 letters. Loop has 22 letters. [2024-11-10 23:17:38,222 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:38,222 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 44 letters. [2024-11-10 23:17:38,223 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:38,224 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 526 transitions. [2024-11-10 23:17:38,230 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:38,235 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 259 states and 359 transitions. [2024-11-10 23:17:38,236 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 122 [2024-11-10 23:17:38,236 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 139 [2024-11-10 23:17:38,236 INFO L73 IsDeterministic]: Start isDeterministic. Operand 259 states and 359 transitions. [2024-11-10 23:17:38,236 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:38,237 INFO L218 hiAutomatonCegarLoop]: Abstraction has 259 states and 359 transitions. [2024-11-10 23:17:38,237 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states and 359 transitions. [2024-11-10 23:17:38,251 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 187. [2024-11-10 23:17:38,252 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-10 23:17:38,253 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 246 transitions. [2024-11-10 23:17:38,254 INFO L240 hiAutomatonCegarLoop]: Abstraction has 187 states and 246 transitions. [2024-11-10 23:17:38,254 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:38,254 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-10 23:17:38,255 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2024-11-10 23:17:38,255 INFO L87 Difference]: Start difference. First operand 187 states and 246 transitions. Second operand has 19 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 11 states have call successors, (12), 5 states have call predecessors, (12), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-10 23:17:38,476 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:38,476 INFO L93 Difference]: Finished difference Result 279 states and 369 transitions. [2024-11-10 23:17:38,476 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 279 states and 369 transitions. [2024-11-10 23:17:38,481 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:38,486 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 279 states to 269 states and 354 transitions. [2024-11-10 23:17:38,487 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 141 [2024-11-10 23:17:38,487 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 141 [2024-11-10 23:17:38,487 INFO L73 IsDeterministic]: Start isDeterministic. Operand 269 states and 354 transitions. [2024-11-10 23:17:38,488 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:38,488 INFO L218 hiAutomatonCegarLoop]: Abstraction has 269 states and 354 transitions. [2024-11-10 23:17:38,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 269 states and 354 transitions. [2024-11-10 23:17:38,500 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 269 to 242. [2024-11-10 23:17:38,501 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 242 states, 148 states have (on average 1.114864864864865) internal successors, (165), 158 states have internal predecessors, (165), 55 states have call successors, (59), 30 states have call predecessors, (59), 39 states have return successors, (94), 53 states have call predecessors, (94), 49 states have call successors, (94) [2024-11-10 23:17:38,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 242 states to 242 states and 318 transitions. [2024-11-10 23:17:38,503 INFO L240 hiAutomatonCegarLoop]: Abstraction has 242 states and 318 transitions. [2024-11-10 23:17:38,504 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-10 23:17:38,504 INFO L425 stractBuchiCegarLoop]: Abstraction has 242 states and 318 transitions. [2024-11-10 23:17:38,504 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-10 23:17:38,504 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 242 states and 318 transitions. [2024-11-10 23:17:38,506 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:38,506 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:38,506 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:38,507 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 9, 8, 8, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:38,508 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:38,508 INFO L745 eck$LassoCheckResult]: Stem: 3457#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(11, 2);call #Ultimate.allocInit(12, 3); 3458#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 := 7; 3459#L27-1 call main_#t~ret6#1 := fibo(main_~x~0#1);< 3500#fiboENTRY ~n := #in~n; 3528#L8 assume !(~n < 1); 3527#L10 assume !(1 == ~n); 3523#L13-3 call #t~ret4 := fibo(~n - 1);< 3526#fiboENTRY ~n := #in~n; 3525#L8 assume !(~n < 1); 3524#L10 assume !(1 == ~n); 3519#L13-3 call #t~ret4 := fibo(~n - 1);< 3522#fiboENTRY ~n := #in~n; 3521#L8 assume !(~n < 1); 3520#L10 assume !(1 == ~n); 3514#L13-3 call #t~ret4 := fibo(~n - 1);< 3518#fiboENTRY ~n := #in~n; 3516#L8 assume !(~n < 1); 3517#L10 assume !(1 == ~n); 3511#L13-3 call #t~ret4 := fibo(~n - 1);< 3509#fiboENTRY ~n := #in~n; 3512#L8 assume !(~n < 1); 3515#L10 assume !(1 == ~n); 3510#L13-3 call #t~ret4 := fibo(~n - 1);< 3509#fiboENTRY ~n := #in~n; 3512#L8 assume !(~n < 1); 3515#L10 assume !(1 == ~n); 3510#L13-3 call #t~ret4 := fibo(~n - 1);< 3509#fiboENTRY ~n := #in~n; 3513#L8 assume !(~n < 1); 3636#L10 assume 1 == ~n;#res := 1; 3635#fiboFINAL assume true; 3633#fiboEXIT >#27#return; 3630#L13-2 call #t~ret5 := fibo(~n - 2);< 3631#fiboENTRY ~n := #in~n; 3634#L8 assume ~n < 1;#res := 0; 3632#fiboFINAL assume true; 3629#fiboEXIT >#25#return; 3627#L13-1 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3607#fiboFINAL assume true; 3582#fiboEXIT >#27#return; 3569#L13-2 call #t~ret5 := fibo(~n - 2);< 3578#fiboENTRY ~n := #in~n; 3647#L8 assume !(~n < 1); 3648#L10 assume !(1 == ~n); 3652#L13-3 call #t~ret4 := fibo(~n - 1);< 3503#fiboENTRY ~n := #in~n; 3677#L8 assume !(~n < 1); 3675#L10 assume !(1 == ~n); 3532#L13-3 call #t~ret4 := fibo(~n - 1);< 3535#fiboENTRY [2024-11-10 23:17:38,508 INFO L747 eck$LassoCheckResult]: Loop: 3535#fiboENTRY ~n := #in~n; 3550#L8 assume !(~n < 1); 3546#L10 assume !(1 == ~n); 3533#L13-3 call #t~ret4 := fibo(~n - 1);< 3535#fiboENTRY [2024-11-10 23:17:38,508 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:38,508 INFO L85 PathProgramCache]: Analyzing trace with hash -1437432527, now seen corresponding path program 3 times [2024-11-10 23:17:38,509 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:38,509 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1685329519] [2024-11-10 23:17:38,509 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:38,509 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:38,516 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:38,689 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-10 23:17:38,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:38,695 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:38,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:38,698 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:38,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:38,700 INFO L134 CoverageAnalysis]: Checked inductivity of 161 backedges. 102 proven. 45 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-10 23:17:38,700 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:38,700 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1685329519] [2024-11-10 23:17:38,700 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1685329519] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:38,700 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [50657681] [2024-11-10 23:17:38,700 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-10 23:17:38,701 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:38,701 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:38,713 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-10 23:17:38,746 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-10 23:17:38,795 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-10 23:17:38,795 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:38,796 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-10 23:17:38,797 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:38,881 INFO L134 CoverageAnalysis]: Checked inductivity of 161 backedges. 82 proven. 14 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-10 23:17:38,881 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:39,053 INFO L134 CoverageAnalysis]: Checked inductivity of 161 backedges. 82 proven. 16 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2024-11-10 23:17:39,053 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [50657681] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:39,053 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:39,053 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 9, 10] total 22 [2024-11-10 23:17:39,053 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [200571450] [2024-11-10 23:17:39,053 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:39,054 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:39,054 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:39,054 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 2 times [2024-11-10 23:17:39,055 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:39,055 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1636984505] [2024-11-10 23:17:39,055 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:39,055 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:39,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:39,058 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:39,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:39,060 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:39,107 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:39,107 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:39,107 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:39,108 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:39,108 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:39,108 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:39,108 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:39,108 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:39,108 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration6_Loop [2024-11-10 23:17:39,108 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:39,108 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:39,109 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,111 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,117 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,119 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,121 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,148 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:39,149 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:39,149 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:39,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:39,151 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-10 23:17:39,152 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-10 23:17:39,153 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:39,153 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:39,169 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:39,169 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-11-10 23:17:39,184 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2024-11-10 23:17:39,184 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:39,184 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:39,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-10 23:17:39,188 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-10 23:17:39,189 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:39,189 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:39,212 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-10 23:17:39,212 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:39,212 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:39,213 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-10 23:17:39,214 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-10 23:17:39,215 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:39,215 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:39,270 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:39,274 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-10 23:17:39,274 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:39,275 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:39,275 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:39,275 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:39,275 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:39,275 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:39,275 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:39,275 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:39,275 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-2.c_Iteration6_Loop [2024-11-10 23:17:39,275 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:39,275 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:39,276 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,279 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,285 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,287 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,289 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:39,318 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:39,318 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:39,319 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:39,319 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:39,321 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-10 23:17:39,322 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-10 23:17:39,323 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-10 23:17:39,335 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:39,335 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:39,335 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:39,335 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:39,335 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:39,336 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:39,336 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:39,338 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:39,352 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-10 23:17:39,353 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:39,353 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:39,354 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-10 23:17:39,356 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-10 23:17:39,357 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-10 23:17:39,368 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:39,368 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:39,369 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:39,369 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:39,369 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:39,369 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:39,369 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:39,371 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:39,375 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:39,375 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:39,375 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:39,375 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:39,376 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-10 23:17:39,378 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-10 23:17:39,378 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:39,378 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:39,379 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:39,379 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-10 23:17:39,391 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-10 23:17:39,392 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:39,403 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:39,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:39,473 INFO L255 TraceCheckSpWp]: Trace formula consists of 430 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-10 23:17:39,475 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:39,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:39,663 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:39,664 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:39,688 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-10 23:17:39,689 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-10 23:17:39,690 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 242 states and 318 transitions. cyclomatic complexity: 80 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-10 23:17:39,752 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 242 states and 318 transitions. cyclomatic complexity: 80. 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 258 states and 334 transitions. Complement of second has 15 states. [2024-11-10 23:17:39,752 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-10 23:17:39,753 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-10 23:17:39,753 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-10 23:17:39,753 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 49 letters. Loop has 4 letters. [2024-11-10 23:17:39,754 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:39,754 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:39,765 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:39,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:39,819 INFO L255 TraceCheckSpWp]: Trace formula consists of 430 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-10 23:17:39,820 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:39,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:39,997 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:39,997 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:40,024 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-10 23:17:40,025 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-10 23:17:40,025 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 242 states and 318 transitions. cyclomatic complexity: 80 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-10 23:17:40,082 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 242 states and 318 transitions. cyclomatic complexity: 80. 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 258 states and 334 transitions. Complement of second has 15 states. [2024-11-10 23:17:40,083 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-10 23:17:40,084 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-10 23:17:40,084 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-10 23:17:40,084 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 49 letters. Loop has 4 letters. [2024-11-10 23:17:40,084 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:40,084 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:40,095 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:40,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:40,163 INFO L255 TraceCheckSpWp]: Trace formula consists of 430 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-10 23:17:40,165 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:40,358 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:40,359 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:40,360 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:40,382 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-10 23:17:40,383 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-10 23:17:40,383 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 242 states and 318 transitions. cyclomatic complexity: 80 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-10 23:17:40,456 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 242 states and 318 transitions. cyclomatic complexity: 80. 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 317 states and 394 transitions. Complement of second has 19 states. [2024-11-10 23:17:40,457 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-10 23:17:40,457 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-10 23:17:40,458 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-10 23:17:40,458 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2024-11-10 23:17:40,458 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:40,458 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 53 letters. Loop has 4 letters. [2024-11-10 23:17:40,459 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:40,459 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 8 letters. [2024-11-10 23:17:40,459 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:40,459 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 317 states and 394 transitions. [2024-11-10 23:17:40,464 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:40,467 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 317 states to 254 states and 330 transitions. [2024-11-10 23:17:40,467 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 109 [2024-11-10 23:17:40,467 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 112 [2024-11-10 23:17:40,467 INFO L73 IsDeterministic]: Start isDeterministic. Operand 254 states and 330 transitions. [2024-11-10 23:17:40,468 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:40,468 INFO L218 hiAutomatonCegarLoop]: Abstraction has 254 states and 330 transitions. [2024-11-10 23:17:40,468 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 254 states and 330 transitions. [2024-11-10 23:17:40,484 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 254 to 250. [2024-11-10 23:17:40,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 250 states, 156 states have (on average 1.108974358974359) internal successors, (173), 166 states have internal predecessors, (173), 55 states have call successors, (59), 30 states have call predecessors, (59), 39 states have return successors, (94), 53 states have call predecessors, (94), 49 states have call successors, (94) [2024-11-10 23:17:40,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 250 states to 250 states and 326 transitions. [2024-11-10 23:17:40,491 INFO L240 hiAutomatonCegarLoop]: Abstraction has 250 states and 326 transitions. [2024-11-10 23:17:40,491 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:40,491 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-10 23:17:40,491 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=359, Unknown=0, NotChecked=0, Total=462 [2024-11-10 23:17:40,491 INFO L87 Difference]: Start difference. First operand 250 states and 326 transitions. Second operand has 22 states, 21 states have (on average 2.2857142857142856) internal successors, (48), 16 states have internal predecessors, (48), 12 states have call successors, (15), 9 states have call predecessors, (15), 3 states have return successors, (7), 3 states have call predecessors, (7), 5 states have call successors, (7) [2024-11-10 23:17:40,668 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-10 23:17:40,834 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:40,835 INFO L93 Difference]: Finished difference Result 323 states and 430 transitions. [2024-11-10 23:17:40,835 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 323 states and 430 transitions. [2024-11-10 23:17:40,839 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-10 23:17:40,839 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 323 states to 0 states and 0 transitions. [2024-11-10 23:17:40,839 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-10 23:17:40,839 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-10 23:17:40,839 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-10 23:17:40,839 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-10 23:17:40,839 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:40,840 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:40,840 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-10 23:17:40,841 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:40,841 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-10 23:17:40,841 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-10 23:17:40,841 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-10 23:17:40,841 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-10 23:17:40,853 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 10.11 11:17:40 BoogieIcfgContainer [2024-11-10 23:17:40,853 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-10 23:17:40,854 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-10 23:17:40,854 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-10 23:17:40,854 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-10 23:17:40,855 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 11:17:30" (3/4) ... [2024-11-10 23:17:40,857 INFO L146 WitnessPrinter]: No result that supports witness generation found [2024-11-10 23:17:40,858 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-10 23:17:40,859 INFO L158 Benchmark]: Toolchain (without parser) took 10893.62ms. Allocated memory was 184.5MB in the beginning and 260.0MB in the end (delta: 75.5MB). Free memory was 128.1MB in the beginning and 210.1MB in the end (delta: -82.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:40,859 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 184.5MB. Free memory is still 143.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:40,859 INFO L158 Benchmark]: CACSL2BoogieTranslator took 267.66ms. Allocated memory is still 184.5MB. Free memory was 127.7MB in the beginning and 116.2MB in the end (delta: 11.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-10 23:17:40,859 INFO L158 Benchmark]: Boogie Procedure Inliner took 30.26ms. Allocated memory is still 184.5MB. Free memory was 116.2MB in the beginning and 114.7MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-10 23:17:40,860 INFO L158 Benchmark]: Boogie Preprocessor took 30.22ms. Allocated memory is still 184.5MB. Free memory was 114.7MB in the beginning and 113.0MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-10 23:17:40,860 INFO L158 Benchmark]: IcfgBuilder took 252.43ms. Allocated memory is still 184.5MB. Free memory was 113.0MB in the beginning and 103.4MB in the end (delta: 9.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-10 23:17:40,860 INFO L158 Benchmark]: BuchiAutomizer took 10301.83ms. Allocated memory was 184.5MB in the beginning and 260.0MB in the end (delta: 75.5MB). Free memory was 103.4MB in the beginning and 210.1MB in the end (delta: -106.7MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:40,860 INFO L158 Benchmark]: Witness Printer took 4.26ms. Allocated memory is still 260.0MB. Free memory is still 210.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:40,862 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.18ms. Allocated memory is still 184.5MB. Free memory is still 143.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 267.66ms. Allocated memory is still 184.5MB. Free memory was 127.7MB in the beginning and 116.2MB in the end (delta: 11.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 30.26ms. Allocated memory is still 184.5MB. Free memory was 116.2MB in the beginning and 114.7MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 30.22ms. Allocated memory is still 184.5MB. Free memory was 114.7MB in the beginning and 113.0MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * IcfgBuilder took 252.43ms. Allocated memory is still 184.5MB. Free memory was 113.0MB in the beginning and 103.4MB in the end (delta: 9.6MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 10301.83ms. Allocated memory was 184.5MB in the beginning and 260.0MB in the end (delta: 75.5MB). Free memory was 103.4MB in the beginning and 210.1MB in the end (delta: -106.7MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 4.26ms. Allocated memory is still 260.0MB. Free memory is still 210.1MB. 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 9 terminating modules (5 trivial, 2 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 11 locations. One 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. 5 modules have a trivial ranking function, the largest among these consists of 22 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 10.2s and 7 iterations. TraceHistogramMax:10. Analysis of lassos took 5.4s. Construction of modules took 0.8s. Büchi inclusion checks took 3.7s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 8. Automata minimization 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 137 StatesRemovedByMinimization, 6 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 16/46 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 407 SdHoareTripleChecker+Valid, 1.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 382 mSDsluCounter, 508 SdHoareTripleChecker+Invalid, 0.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 332 mSDsCounter, 289 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1079 IncrementalHoareTripleChecker+Invalid, 1368 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 289 mSolverCounterUnsat, 176 mSDtfsCounter, 1079 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI2 SILT3 lasso0 LassoPreprocessingBenchmarks: Lassos: inital16 mio100 ax100 hnf100 lsp86 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq178 hnf93 smp76 dnf100 smp100 tf112 neg100 sie107 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 25ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 8 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.8s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-10 23:17:40,888 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-10 23:17:41,083 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-10 23:17:41,284 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-10 23:17:41,484 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:41,684 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:41,886 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE