./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_7-1.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-1.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 17c70baee0bc6a4a26b6403fb6f46125ad9d7f8a7127109634f2327c61aaf5cb --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-023d838-m [2024-11-10 23:17:26,668 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-10 23:17:26,749 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:26,765 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-10 23:17:26,765 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-10 23:17:26,766 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2024-11-10 23:17:26,791 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-10 23:17:26,791 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-10 23:17:26,792 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-10 23:17:26,792 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-10 23:17:26,793 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-10 23:17:26,794 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-10 23:17:26,794 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-10 23:17:26,796 INFO L153 SettingsManager]: * Use SBE=true [2024-11-10 23:17:26,796 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-10 23:17:26,796 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-10 23:17:26,796 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-10 23:17:26,797 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-10 23:17:26,797 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-10 23:17:26,797 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-10 23:17:26,797 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-10 23:17:26,801 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-10 23:17:26,801 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-10 23:17:26,801 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-10 23:17:26,802 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-10 23:17:26,802 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-10 23:17:26,802 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-10 23:17:26,802 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-10 23:17:26,802 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-10 23:17:26,802 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-10 23:17:26,802 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-10 23:17:26,802 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-10 23:17:26,803 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-10 23:17:26,803 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-10 23:17:26,803 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-10 23:17:26,803 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-10 23:17:26,803 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-10 23:17:26,804 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-10 23:17:26,804 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-10 23:17:26,804 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-10 23:17:26,804 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 -> 17c70baee0bc6a4a26b6403fb6f46125ad9d7f8a7127109634f2327c61aaf5cb [2024-11-10 23:17:27,012 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-10 23:17:27,030 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-10 23:17:27,032 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-10 23:17:27,033 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-10 23:17:27,033 INFO L274 PluginConnector]: CDTParser initialized [2024-11-10 23:17:27,034 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_7-1.c [2024-11-10 23:17:28,309 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-10 23:17:28,461 INFO L384 CDTParser]: Found 1 translation units. [2024-11-10 23:17:28,462 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_7-1.c [2024-11-10 23:17:28,469 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5018f69a5/a1c6de2c65b1467392211ed3117b4899/FLAG08b2c5c0e [2024-11-10 23:17:28,480 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/5018f69a5/a1c6de2c65b1467392211ed3117b4899 [2024-11-10 23:17:28,482 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-10 23:17:28,483 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-10 23:17:28,484 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-10 23:17:28,484 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-10 23:17:28,489 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-10 23:17:28,489 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 11:17:28" (1/1) ... [2024-11-10 23:17:28,490 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7a1a13b6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:28, skipping insertion in model container [2024-11-10 23:17:28,490 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 10.11 11:17:28" (1/1) ... [2024-11-10 23:17:28,503 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-10 23:17:28,643 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 23:17:28,654 INFO L200 MainTranslator]: Completed pre-run [2024-11-10 23:17:28,664 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-10 23:17:28,677 INFO L204 MainTranslator]: Completed translation [2024-11-10 23:17:28,678 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:28 WrapperNode [2024-11-10 23:17:28,678 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-10 23:17:28,679 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-10 23:17:28,679 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-10 23:17:28,679 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-10 23:17:28,684 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:28" (1/1) ... [2024-11-10 23:17:28,689 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:28" (1/1) ... [2024-11-10 23:17:28,699 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-11-10 23:17:28,699 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-10 23:17:28,700 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-10 23:17:28,700 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-10 23:17:28,700 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-10 23:17:28,706 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:28" (1/1) ... [2024-11-10 23:17:28,707 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:28" (1/1) ... [2024-11-10 23:17:28,707 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:28" (1/1) ... [2024-11-10 23:17:28,715 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:28,715 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:28" (1/1) ... [2024-11-10 23:17:28,715 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:28" (1/1) ... [2024-11-10 23:17:28,717 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:28" (1/1) ... [2024-11-10 23:17:28,720 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:28" (1/1) ... [2024-11-10 23:17:28,720 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:28" (1/1) ... [2024-11-10 23:17:28,721 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:28" (1/1) ... [2024-11-10 23:17:28,721 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-10 23:17:28,722 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-10 23:17:28,722 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-10 23:17:28,722 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-10 23:17:28,723 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:28" (1/1) ... [2024-11-10 23:17:28,727 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:28,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:28,755 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:28,758 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:28,792 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-10 23:17:28,793 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-10 23:17:28,793 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-10 23:17:28,793 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-10 23:17:28,793 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-11-10 23:17:28,793 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-11-10 23:17:28,845 INFO L256 CfgBuilder]: Building ICFG [2024-11-10 23:17:28,846 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-10 23:17:28,925 INFO L1247 $ProcedureCfgBuilder]: dead code at ProgramPoint L13: havoc #t~ret4;havoc #t~ret5; [2024-11-10 23:17:28,932 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-10 23:17:28,932 INFO L307 CfgBuilder]: Performing block encoding [2024-11-10 23:17:28,941 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-10 23:17:28,941 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-10 23:17:28,942 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 11:17:28 BoogieIcfgContainer [2024-11-10 23:17:28,942 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-10 23:17:28,943 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-10 23:17:28,943 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-10 23:17:28,945 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-10 23:17:28,946 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:28,946 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 10.11 11:17:28" (1/3) ... [2024-11-10 23:17:28,947 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@c3bc026 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 10.11 11:17:28, skipping insertion in model container [2024-11-10 23:17:28,947 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:28,947 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 10.11 11:17:28" (2/3) ... [2024-11-10 23:17:28,947 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@c3bc026 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 10.11 11:17:28, skipping insertion in model container [2024-11-10 23:17:28,947 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-10 23:17:28,948 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 10.11 11:17:28" (3/3) ... [2024-11-10 23:17:28,948 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_7-1.c [2024-11-10 23:17:29,003 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-10 23:17:29,007 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-10 23:17:29,007 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-10 23:17:29,007 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-10 23:17:29,008 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-10 23:17:29,008 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-10 23:17:29,008 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-10 23:17:29,008 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-10 23:17:29,015 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:29,036 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:29,042 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:29,042 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:29,048 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-10 23:17:29,050 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:29,050 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-10 23:17:29,050 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:29,052 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:29,055 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:29,055 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:29,055 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-10 23:17:29,055 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:29,059 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:29,063 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:29,071 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:29,071 INFO L85 PathProgramCache]: Analyzing trace with hash 39702, now seen corresponding path program 1 times [2024-11-10 23:17:29,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:29,086 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1940209732] [2024-11-10 23:17:29,086 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:29,087 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:29,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:29,189 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:29,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:29,205 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:29,207 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:29,208 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 1 times [2024-11-10 23:17:29,208 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:29,208 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [962259810] [2024-11-10 23:17:29,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:29,208 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:29,213 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:29,213 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:29,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:29,216 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:29,217 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:29,217 INFO L85 PathProgramCache]: Analyzing trace with hash -1988460259, now seen corresponding path program 1 times [2024-11-10 23:17:29,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:29,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1164463639] [2024-11-10 23:17:29,218 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:29,218 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:29,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:29,225 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:29,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:29,233 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:29,331 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:29,331 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:29,331 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:29,331 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:29,331 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:29,332 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,332 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:29,332 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:29,332 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-1.c_Iteration1_Loop [2024-11-10 23:17:29,332 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:29,332 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:29,343 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,349 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,352 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,354 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,356 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,404 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:29,404 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:29,406 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,406 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,407 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:29,409 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:29,410 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:29,410 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:29,424 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:29,424 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:29,435 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:29,436 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,436 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,437 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:29,438 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:29,439 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:29,439 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:29,450 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:29,451 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:29,462 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-11-10 23:17:29,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,464 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:29,465 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:29,472 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:29,472 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:29,486 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:29,486 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:29,497 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-11-10 23:17:29,500 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,501 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,505 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:29,506 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:29,507 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:29,507 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:29,519 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:29,520 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:29,533 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-11-10 23:17:29,534 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,534 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,537 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:29,539 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:29,539 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:29,540 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:29,562 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-11-10 23:17:29,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,565 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:29,566 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:29,567 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:29,567 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:29,621 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:29,626 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-11-10 23:17:29,627 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:29,627 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:29,627 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:29,627 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:29,627 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:29,627 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,628 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:29,628 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:29,628 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-1.c_Iteration1_Loop [2024-11-10 23:17:29,628 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:29,628 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:29,630 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,636 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,638 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,643 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,645 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:29,700 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:29,703 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:29,704 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,704 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,707 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:29,710 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:29,711 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:29,722 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:29,722 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:29,722 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:29,722 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:29,722 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:29,724 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:29,724 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:29,726 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:29,738 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:29,738 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,738 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,740 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:29,741 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:29,742 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:29,751 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:29,752 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:29,752 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:29,752 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:29,752 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:29,753 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:29,753 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:29,755 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:29,766 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:29,766 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,768 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:29,769 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:29,770 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:29,780 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:29,780 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:29,780 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:29,780 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:29,780 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:29,781 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:29,781 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:29,784 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:29,794 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:29,795 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,795 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,796 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:29,798 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:29,799 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:29,809 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:29,809 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:29,809 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:29,809 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:29,809 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:29,810 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:29,810 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:29,811 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:29,821 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:29,822 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,822 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,824 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:29,825 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:29,829 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:29,841 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:29,841 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:29,841 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:29,841 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:29,841 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:29,843 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:29,843 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:29,847 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:29,857 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:29,857 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:29,858 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:29,859 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:29,860 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:29,861 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:29,862 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:29,862 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:29,862 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:29,863 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-10 23:17:29,874 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2024-11-10 23:17:29,880 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:29,929 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:29,942 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:29,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:29,947 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-10 23:17:29,948 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:29,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:29,989 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:29,989 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:30,022 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:30,046 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:30,047 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:30,114 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:30,117 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:30,120 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:30,121 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-11-10 23:17:30,122 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-11-10 23:17:30,122 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:30,122 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-11-10 23:17:30,123 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:30,123 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-11-10 23:17:30,123 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:30,123 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-11-10 23:17:30,125 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:30,129 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-11-10 23:17:30,130 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-11-10 23:17:30,130 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-11-10 23:17:30,130 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-11-10 23:17:30,131 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:30,131 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-11-10 23:17:30,143 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-11-10 23:17:30,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-11-10 23:17:30,151 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:30,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-11-10 23:17:30,152 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-10 23:17:30,152 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-11-10 23:17:30,152 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-10 23:17:30,152 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-11-10 23:17:30,153 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:30,153 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:30,153 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:30,154 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:30,154 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:30,154 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:30,154 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:30,154 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:30,155 INFO L85 PathProgramCache]: Analyzing trace with hash 1475604923, now seen corresponding path program 1 times [2024-11-10 23:17:30,155 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:30,155 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1932839668] [2024-11-10 23:17:30,155 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:30,155 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:30,163 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:30,252 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-10 23:17:30,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:30,279 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:30,280 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:30,280 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1932839668] [2024-11-10 23:17:30,281 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1932839668] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 23:17:30,281 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 23:17:30,281 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-10 23:17:30,281 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1476030655] [2024-11-10 23:17:30,282 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 23:17:30,283 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:30,284 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:30,284 INFO L85 PathProgramCache]: Analyzing trace with hash 93365724, now seen corresponding path program 1 times [2024-11-10 23:17:30,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:30,284 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [479793651] [2024-11-10 23:17:30,284 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:30,284 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:30,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:30,311 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 23:17:30,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:30,333 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:30,333 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:30,333 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [479793651] [2024-11-10 23:17:30,334 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [479793651] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-10 23:17:30,334 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-10 23:17:30,334 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-10 23:17:30,334 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1685840765] [2024-11-10 23:17:30,334 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-10 23:17:30,334 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-10 23:17:30,334 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:30,336 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-10 23:17:30,336 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-10 23:17:30,337 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:30,385 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:30,385 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-11-10 23:17:30,385 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-11-10 23:17:30,386 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:30,387 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-11-10 23:17:30,387 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-11-10 23:17:30,387 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-11-10 23:17:30,387 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-11-10 23:17:30,388 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:30,388 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:30,388 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-11-10 23:17:30,389 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-11-10 23:17:30,390 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:30,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-11-10 23:17:30,390 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:30,391 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-10 23:17:30,391 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-11-10 23:17:30,392 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-10 23:17:30,392 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-11-10 23:17:30,392 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:30,392 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:30,392 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:30,393 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-10 23:17:30,393 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-10 23:17:30,393 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:30,394 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:30,394 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:30,394 INFO L85 PathProgramCache]: Analyzing trace with hash -1500686953, now seen corresponding path program 1 times [2024-11-10 23:17:30,394 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:30,394 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [639477989] [2024-11-10 23:17:30,394 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:30,395 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:30,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:30,436 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-11-10 23:17:30,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:30,459 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:30,460 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:30,460 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [639477989] [2024-11-10 23:17:30,460 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [639477989] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:30,460 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1144980406] [2024-11-10 23:17:30,460 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:30,460 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:30,460 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:30,462 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:30,463 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:30,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:30,509 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:30,510 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:30,535 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:30,535 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:30,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:30,612 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1144980406] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:30,612 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:30,612 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-11-10 23:17:30,612 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1557638432] [2024-11-10 23:17:30,612 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:30,613 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:30,613 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:30,613 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 1 times [2024-11-10 23:17:30,613 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:30,613 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1972197937] [2024-11-10 23:17:30,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:30,613 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:30,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:30,620 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:30,623 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:30,625 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:30,829 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:30,830 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:30,830 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:30,830 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:30,830 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:30,830 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:30,830 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:30,830 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:30,830 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-1.c_Iteration3_Loop [2024-11-10 23:17:30,830 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:30,830 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:30,831 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:30,834 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:30,835 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:30,844 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:30,885 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:30,885 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:30,885 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:30,886 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:30,890 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:30,894 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:30,896 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:30,896 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:30,910 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:30,910 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:30,921 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:30,922 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:30,922 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:30,923 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:30,925 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:30,926 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:30,926 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:30,937 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:30,938 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:30,949 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:30,953 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:30,953 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:30,954 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:30,955 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:30,960 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:30,960 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:30,992 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:30,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:30,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:30,997 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:31,000 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:31,001 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:31,001 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:31,461 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:31,466 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2024-11-10 23:17:31,466 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:31,467 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:31,467 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:31,467 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:31,467 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:31,467 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,467 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:31,467 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:31,467 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-1.c_Iteration3_Loop [2024-11-10 23:17:31,467 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:31,467 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:31,468 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,481 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,483 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,485 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:31,525 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:31,526 INFO L451 LassoAnalysis]: Using template 'affine'. [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,526 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,529 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:31,530 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:31,531 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,541 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:31,541 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:31,541 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:31,541 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:31,541 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:31,543 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:31,543 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:31,569 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:31,572 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:31,573 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:31,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:31,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:31,575 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:31,581 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:31,581 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:31,582 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:31,582 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:31,582 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:31,597 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:31,598 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:31,606 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:31,623 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:31,624 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:31,625 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 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:31,695 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:31,795 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:31,796 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:31,796 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:31,975 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:31,976 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:31,976 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:31,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-11-10 23:17:31,977 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-11-10 23:17:31,978 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:31,978 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-11-10 23:17:31,978 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:31,978 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-11-10 23:17:31,979 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:31,979 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-11-10 23:17:31,983 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:31,987 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-11-10 23:17:31,987 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-10 23:17:31,987 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-10 23:17:31,987 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-11-10 23:17:31,987 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:31,987 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-11-10 23:17:31,988 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-11-10 23:17:31,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-11-10 23:17:31,996 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:31,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-11-10 23:17:31,998 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-11-10 23:17:31,998 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:31,998 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-10 23:17:31,998 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-11-10 23:17:31,999 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:32,092 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:32,092 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-11-10 23:17:32,093 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-11-10 23:17:32,096 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:32,100 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-11-10 23:17:32,100 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-11-10 23:17:32,100 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-11-10 23:17:32,100 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-11-10 23:17:32,100 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:32,100 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-11-10 23:17:32,101 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-11-10 23:17:32,107 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-11-10 23:17:32,107 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:32,108 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-11-10 23:17:32,108 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-10 23:17:32,109 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-10 23:17:32,109 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-11-10 23:17:32,109 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-10 23:17:32,110 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-11-10 23:17:32,111 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-11-10 23:17:32,111 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:32,111 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:32,112 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:32,112 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-11-10 23:17:32,112 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:32,112 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:32,113 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:32,113 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 1 times [2024-11-10 23:17:32,113 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:32,113 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [825979447] [2024-11-10 23:17:32,113 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:32,113 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:32,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,204 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-10 23:17:32,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,243 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:32,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,259 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:32,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,264 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:32,264 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:32,264 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [825979447] [2024-11-10 23:17:32,264 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [825979447] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:32,264 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [10905305] [2024-11-10 23:17:32,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:32,264 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:32,264 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:32,266 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:32,267 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:32,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,298 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-10 23:17:32,299 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:32,336 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:32,337 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:32,519 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:32,520 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [10905305] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:32,520 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:32,520 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 18 [2024-11-10 23:17:32,520 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [838682126] [2024-11-10 23:17:32,521 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:32,521 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:32,521 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:32,521 INFO L85 PathProgramCache]: Analyzing trace with hash -1547808212, now seen corresponding path program 1 times [2024-11-10 23:17:32,521 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:32,522 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1283695347] [2024-11-10 23:17:32,522 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:32,522 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:32,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,549 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-11-10 23:17:32,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,563 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:32,566 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,583 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:32,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,603 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:32,603 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:32,603 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1283695347] [2024-11-10 23:17:32,604 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1283695347] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:32,604 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1210585955] [2024-11-10 23:17:32,604 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:32,604 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:32,604 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:32,607 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:32,608 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:32,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,664 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-10 23:17:32,665 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:32,711 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:32,711 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:32,726 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:32,819 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:32,820 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1210585955] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:32,820 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:32,820 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-11-10 23:17:32,820 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2018377298] [2024-11-10 23:17:32,821 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:32,821 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-10 23:17:32,821 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:32,821 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-10 23:17:32,822 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-11-10 23:17:32,822 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:32,890 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:32,890 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-11-10 23:17:32,890 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-11-10 23:17:32,891 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:32,892 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-11-10 23:17:32,892 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-11-10 23:17:32,893 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-11-10 23:17:32,893 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-11-10 23:17:32,893 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:32,893 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:32,893 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-11-10 23:17:32,896 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-11-10 23:17:32,896 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:32,897 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-11-10 23:17:32,897 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:32,897 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-10 23:17:32,898 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-11-10 23:17:32,898 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-10 23:17:32,898 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-11-10 23:17:32,899 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-11-10 23:17:32,899 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:32,899 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:32,902 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:32,902 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-11-10 23:17:32,903 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:32,903 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:32,903 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:32,903 INFO L85 PathProgramCache]: Analyzing trace with hash 572026595, now seen corresponding path program 2 times [2024-11-10 23:17:32,903 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:32,903 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [163472315] [2024-11-10 23:17:32,903 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:32,903 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:32,910 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:32,971 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-10 23:17:32,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:33,007 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:33,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:33,022 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:33,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:33,026 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:33,026 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:33,026 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [163472315] [2024-11-10 23:17:33,026 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [163472315] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:33,027 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1839516397] [2024-11-10 23:17:33,027 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-10 23:17:33,027 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:33,027 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,028 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:33,032 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:33,065 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-10 23:17:33,066 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:33,066 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-10 23:17:33,067 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:33,109 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:33,109 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:33,287 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:33,288 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1839516397] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:33,288 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:33,288 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 18 [2024-11-10 23:17:33,288 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1248467979] [2024-11-10 23:17:33,288 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:33,289 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:33,290 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:33,290 INFO L85 PathProgramCache]: Analyzing trace with hash 865543216, now seen corresponding path program 2 times [2024-11-10 23:17:33,290 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:33,290 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1514288194] [2024-11-10 23:17:33,290 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:33,290 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:33,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:33,294 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:33,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:33,301 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:33,449 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:33,450 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:33,450 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:33,450 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:33,450 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:33,450 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,450 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:33,450 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:33,450 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-1.c_Iteration5_Loop [2024-11-10 23:17:33,450 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:33,451 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:33,451 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,453 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,457 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,459 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,461 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,489 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:33,489 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:33,489 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,490 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,495 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:33,496 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:33,497 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:33,497 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:33,511 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:33,511 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,521 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:33,521 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,521 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,524 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:33,526 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:33,527 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:33,527 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:33,547 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:33,548 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,548 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,551 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:33,552 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:33,552 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:33,552 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:33,567 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:33,577 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2024-11-10 23:17:33,578 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:33,578 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:33,578 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:33,578 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:33,578 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:33,578 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,578 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:33,578 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:33,578 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-1.c_Iteration5_Loop [2024-11-10 23:17:33,578 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:33,578 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:33,579 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,583 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,585 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,587 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,588 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:33,615 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:33,615 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:33,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,615 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,618 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:33,623 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:33,624 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,633 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:33,634 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:33,634 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:33,634 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:33,634 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:33,635 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:33,635 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:33,636 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:33,639 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:33,639 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:33,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:33,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:33,640 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:33,641 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:33,642 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:33,642 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:33,642 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:33,642 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-11-10 23:17:33,652 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:33,652 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:33,659 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:33,697 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:33,699 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:33,700 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:33,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:33,883 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:33,884 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:33,976 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:33,977 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:33,977 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:34,047 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:34,049 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:34,050 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:34,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-10 23:17:34,050 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:34,050 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:34,050 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:34,059 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:34,092 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:34,093 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:34,094 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:34,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:34,247 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:34,248 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:34,361 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:34,364 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,365 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:34,365 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:34,440 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:34,443 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:34,444 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:34,444 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-11-10 23:17:34,444 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:34,444 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:34,444 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:34,452 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:34,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:34,483 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-10 23:17:34,484 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:34,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:34,630 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-10 23:17:34,631 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:34,731 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-10 23:17:34,731 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:34,731 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2024-11-10 23:17:34,941 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:34,945 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,946 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:34,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-11-10 23:17:34,946 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 22 letters. [2024-11-10 23:17:34,947 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:34,947 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 54 letters. Loop has 22 letters. [2024-11-10 23:17:34,948 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:34,948 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 32 letters. Loop has 44 letters. [2024-11-10 23:17:34,949 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:34,949 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 526 transitions. [2024-11-10 23:17:34,954 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:34,958 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 259 states and 359 transitions. [2024-11-10 23:17:34,958 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 122 [2024-11-10 23:17:34,959 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 139 [2024-11-10 23:17:34,959 INFO L73 IsDeterministic]: Start isDeterministic. Operand 259 states and 359 transitions. [2024-11-10 23:17:34,959 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:34,959 INFO L218 hiAutomatonCegarLoop]: Abstraction has 259 states and 359 transitions. [2024-11-10 23:17:34,960 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states and 359 transitions. [2024-11-10 23:17:34,971 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 187. [2024-11-10 23:17:34,971 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:34,973 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 246 transitions. [2024-11-10 23:17:34,973 INFO L240 hiAutomatonCegarLoop]: Abstraction has 187 states and 246 transitions. [2024-11-10 23:17:34,973 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:34,973 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-10 23:17:34,974 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2024-11-10 23:17:34,974 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:35,156 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:35,156 INFO L93 Difference]: Finished difference Result 279 states and 369 transitions. [2024-11-10 23:17:35,156 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 279 states and 369 transitions. [2024-11-10 23:17:35,160 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:35,164 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 279 states to 269 states and 354 transitions. [2024-11-10 23:17:35,164 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 141 [2024-11-10 23:17:35,164 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 141 [2024-11-10 23:17:35,164 INFO L73 IsDeterministic]: Start isDeterministic. Operand 269 states and 354 transitions. [2024-11-10 23:17:35,165 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:35,165 INFO L218 hiAutomatonCegarLoop]: Abstraction has 269 states and 354 transitions. [2024-11-10 23:17:35,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 269 states and 354 transitions. [2024-11-10 23:17:35,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 269 to 242. [2024-11-10 23:17:35,175 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:35,177 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 242 states to 242 states and 318 transitions. [2024-11-10 23:17:35,177 INFO L240 hiAutomatonCegarLoop]: Abstraction has 242 states and 318 transitions. [2024-11-10 23:17:35,177 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2024-11-10 23:17:35,178 INFO L425 stractBuchiCegarLoop]: Abstraction has 242 states and 318 transitions. [2024-11-10 23:17:35,178 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-10 23:17:35,178 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 242 states and 318 transitions. [2024-11-10 23:17:35,179 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:35,179 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-10 23:17:35,180 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-10 23:17:35,180 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:35,180 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-10 23:17:35,181 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:35,181 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:35,181 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:35,181 INFO L85 PathProgramCache]: Analyzing trace with hash -1437432527, now seen corresponding path program 3 times [2024-11-10 23:17:35,181 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:35,181 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1917588948] [2024-11-10 23:17:35,181 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:35,181 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:35,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,322 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-10 23:17:35,324 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,326 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-10 23:17:35,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,328 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-11-10 23:17:35,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:35,329 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:35,330 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-10 23:17:35,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1917588948] [2024-11-10 23:17:35,330 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1917588948] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-10 23:17:35,330 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [976412077] [2024-11-10 23:17:35,330 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-10 23:17:35,330 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-10 23:17:35,330 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:35,332 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:35,340 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:35,381 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2024-11-10 23:17:35,381 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-10 23:17:35,382 INFO L255 TraceCheckSpWp]: Trace formula consists of 98 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-10 23:17:35,383 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:35,449 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:35,449 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-10 23:17:35,646 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:35,646 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [976412077] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-10 23:17:35,646 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-10 23:17:35,646 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 9, 10] total 22 [2024-11-10 23:17:35,646 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [935129739] [2024-11-10 23:17:35,646 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-10 23:17:35,647 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-11-10 23:17:35,647 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:35,647 INFO L85 PathProgramCache]: Analyzing trace with hash 1538184, now seen corresponding path program 2 times [2024-11-10 23:17:35,647 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-10 23:17:35,647 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [174811247] [2024-11-10 23:17:35,647 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-10 23:17:35,647 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-10 23:17:35,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:35,655 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-10 23:17:35,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-10 23:17:35,656 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-10 23:17:35,697 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:35,697 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:35,697 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:35,697 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:35,697 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-11-10 23:17:35,698 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:35,698 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:35,698 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:35,698 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-1.c_Iteration6_Loop [2024-11-10 23:17:35,698 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:35,698 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:35,698 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,700 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,706 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,708 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,709 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,736 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:35,736 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-11-10 23:17:35,736 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:35,736 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:35,742 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:35,743 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:35,743 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:35,743 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:35,766 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-11-10 23:17:35,766 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:35,787 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:35,788 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:35,788 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:35,789 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:35,794 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:35,795 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-11-10 23:17:35,795 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:35,819 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:35,819 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:35,820 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:35,821 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:35,821 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:35,822 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-11-10 23:17:35,822 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-11-10 23:17:35,873 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-11-10 23:17:35,877 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2024-11-10 23:17:35,878 INFO L204 LassoAnalysis]: Preferences: [2024-11-10 23:17:35,878 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-10 23:17:35,878 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-10 23:17:35,878 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-10 23:17:35,878 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-10 23:17:35,878 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:35,878 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-10 23:17:35,878 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-10 23:17:35,878 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_7-1.c_Iteration6_Loop [2024-11-10 23:17:35,878 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-10 23:17:35,878 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-10 23:17:35,879 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,880 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,885 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,887 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,888 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-10 23:17:35,909 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-10 23:17:35,910 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-10 23:17:35,910 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:35,910 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:35,913 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:35,920 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:35,921 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:35,931 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:35,931 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:35,931 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:35,931 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:35,931 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:35,931 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:35,932 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:35,933 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-10 23:17:35,942 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:35,943 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:35,943 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:35,944 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:35,945 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:35,945 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:35,956 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-10 23:17:35,956 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-10 23:17:35,956 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-10 23:17:35,956 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-10 23:17:35,956 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-10 23:17:35,957 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-10 23:17:35,957 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-10 23:17:35,959 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-10 23:17:35,965 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-10 23:17:35,965 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-10 23:17:35,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-10 23:17:35,965 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-10 23:17:35,967 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:35,969 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:35,969 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-10 23:17:35,969 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-10 23:17:35,969 INFO L474 LassoAnalysis]: Proved termination. [2024-11-10 23:17:35,969 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-11-10 23:17:35,979 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2024-11-10 23:17:35,980 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-10 23:17:35,988 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:36,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:36,049 INFO L255 TraceCheckSpWp]: Trace formula consists of 430 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-10 23:17:36,051 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:36,158 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2024-11-10 23:17:36,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:36,232 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:36,233 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:36,250 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:36,251 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:36,251 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:36,305 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:36,305 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:36,306 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:36,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-10 23:17:36,306 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 49 letters. Loop has 4 letters. [2024-11-10 23:17:36,306 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:36,306 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:36,316 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:36,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:36,364 INFO L255 TraceCheckSpWp]: Trace formula consists of 430 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-10 23:17:36,365 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:36,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:36,501 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:36,501 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:36,518 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:36,519 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:36,519 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:36,574 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:36,575 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:36,575 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:36,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-11-10 23:17:36,575 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 49 letters. Loop has 4 letters. [2024-11-10 23:17:36,575 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:36,575 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-10 23:17:36,582 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-10 23:17:36,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:36,634 INFO L255 TraceCheckSpWp]: Trace formula consists of 430 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-11-10 23:17:36,635 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:36,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-10 23:17:36,785 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-10 23:17:36,786 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-10 23:17:36,804 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:36,805 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:36,805 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:36,865 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:36,865 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:36,866 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:36,866 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-11-10 23:17:36,866 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2024-11-10 23:17:36,866 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:36,866 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 53 letters. Loop has 4 letters. [2024-11-10 23:17:36,866 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:36,866 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 8 letters. [2024-11-10 23:17:36,867 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-10 23:17:36,867 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 317 states and 394 transitions. [2024-11-10 23:17:36,870 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-11-10 23:17:36,876 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 317 states to 254 states and 330 transitions. [2024-11-10 23:17:36,876 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 109 [2024-11-10 23:17:36,877 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 112 [2024-11-10 23:17:36,877 INFO L73 IsDeterministic]: Start isDeterministic. Operand 254 states and 330 transitions. [2024-11-10 23:17:36,877 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-10 23:17:36,877 INFO L218 hiAutomatonCegarLoop]: Abstraction has 254 states and 330 transitions. [2024-11-10 23:17:36,877 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 254 states and 330 transitions. [2024-11-10 23:17:36,884 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 254 to 250. [2024-11-10 23:17:36,884 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:36,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 250 states to 250 states and 326 transitions. [2024-11-10 23:17:36,886 INFO L240 hiAutomatonCegarLoop]: Abstraction has 250 states and 326 transitions. [2024-11-10 23:17:36,886 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-10 23:17:36,887 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-10 23:17:36,887 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=359, Unknown=0, NotChecked=0, Total=462 [2024-11-10 23:17:36,887 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:37,144 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-10 23:17:37,144 INFO L93 Difference]: Finished difference Result 323 states and 430 transitions. [2024-11-10 23:17:37,145 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 323 states and 430 transitions. [2024-11-10 23:17:37,147 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-10 23:17:37,148 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 323 states to 0 states and 0 transitions. [2024-11-10 23:17:37,148 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-10 23:17:37,148 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-10 23:17:37,148 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-10 23:17:37,148 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-10 23:17:37,148 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:37,148 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:37,148 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-10 23:17:37,149 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-10 23:17:37,149 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-10 23:17:37,149 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-10 23:17:37,149 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-10 23:17:37,149 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-10 23:17:37,155 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 10.11 11:17:37 BoogieIcfgContainer [2024-11-10 23:17:37,155 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-10 23:17:37,156 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-10 23:17:37,156 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-10 23:17:37,156 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-10 23:17:37,157 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:28" (3/4) ... [2024-11-10 23:17:37,158 INFO L146 WitnessPrinter]: No result that supports witness generation found [2024-11-10 23:17:37,159 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-10 23:17:37,160 INFO L158 Benchmark]: Toolchain (without parser) took 8676.59ms. Allocated memory was 232.8MB in the beginning and 327.2MB in the end (delta: 94.4MB). Free memory was 164.3MB in the beginning and 160.8MB in the end (delta: 3.5MB). Peak memory consumption was 99.2MB. Max. memory is 16.1GB. [2024-11-10 23:17:37,160 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 121.6MB. Free memory is still 86.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:37,160 INFO L158 Benchmark]: CACSL2BoogieTranslator took 194.09ms. Allocated memory is still 232.8MB. Free memory was 164.3MB in the beginning and 152.4MB in the end (delta: 11.9MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-10 23:17:37,160 INFO L158 Benchmark]: Boogie Procedure Inliner took 20.60ms. Allocated memory is still 232.8MB. Free memory was 152.4MB in the beginning and 151.1MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:37,160 INFO L158 Benchmark]: Boogie Preprocessor took 21.64ms. Allocated memory is still 232.8MB. Free memory was 151.1MB in the beginning and 149.7MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-10 23:17:37,161 INFO L158 Benchmark]: IcfgBuilder took 220.12ms. Allocated memory is still 232.8MB. Free memory was 149.7MB in the beginning and 139.2MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-10 23:17:37,161 INFO L158 Benchmark]: BuchiAutomizer took 8212.88ms. Allocated memory was 232.8MB in the beginning and 327.2MB in the end (delta: 94.4MB). Free memory was 138.9MB in the beginning and 160.8MB in the end (delta: -22.0MB). Peak memory consumption was 74.0MB. Max. memory is 16.1GB. [2024-11-10 23:17:37,161 INFO L158 Benchmark]: Witness Printer took 3.28ms. Allocated memory is still 327.2MB. Free memory is still 160.8MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-10 23:17:37,162 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.13ms. Allocated memory is still 121.6MB. Free memory is still 86.4MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 194.09ms. Allocated memory is still 232.8MB. Free memory was 164.3MB in the beginning and 152.4MB in the end (delta: 11.9MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 20.60ms. Allocated memory is still 232.8MB. Free memory was 152.4MB in the beginning and 151.1MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 21.64ms. Allocated memory is still 232.8MB. Free memory was 151.1MB in the beginning and 149.7MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * IcfgBuilder took 220.12ms. Allocated memory is still 232.8MB. Free memory was 149.7MB in the beginning and 139.2MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 8212.88ms. Allocated memory was 232.8MB in the beginning and 327.2MB in the end (delta: 94.4MB). Free memory was 138.9MB in the beginning and 160.8MB in the end (delta: -22.0MB). Peak memory consumption was 74.0MB. Max. memory is 16.1GB. * Witness Printer took 3.28ms. Allocated memory is still 327.2MB. Free memory is still 160.8MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 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 8.1s and 7 iterations. TraceHistogramMax:10. Analysis of lassos took 4.4s. Construction of modules took 0.6s. Büchi inclusion checks took 2.8s. 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, 0.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 382 mSDsluCounter, 508 SdHoareTripleChecker+Invalid, 0.6s 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: 22ms 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:37,182 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:37,384 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2024-11-10 23:17:37,585 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:37,789 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:37,992 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:38,198 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE