./Ultimate.py --spec /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/properties/termination.prp --file /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_10-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version a046e57d Calling Ultimate with: /root/.sdkman/candidates/java/current/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 /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_10-1.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash acde98dd01af02b5a508b32116f1b2c3612f1f84e6ba2fe02fc76c333a1d32d3 --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-mul-div-a046e57-m [2024-10-13 17:41:44,905 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-13 17:41:44,955 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-10-13 17:41:44,959 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-13 17:41:44,962 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-13 17:41:44,984 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-13 17:41:44,984 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-13 17:41:44,985 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-13 17:41:44,985 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-13 17:41:44,988 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-13 17:41:44,988 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-13 17:41:44,988 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-13 17:41:44,988 INFO L153 SettingsManager]: * Use SBE=true [2024-10-13 17:41:44,989 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-13 17:41:44,989 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-13 17:41:44,989 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-13 17:41:44,989 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-13 17:41:44,989 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-13 17:41:44,989 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-13 17:41:44,990 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-13 17:41:44,990 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-13 17:41:44,991 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-13 17:41:44,991 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-13 17:41:44,991 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-13 17:41:44,992 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-13 17:41:44,992 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-13 17:41:44,992 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-13 17:41:44,992 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-13 17:41:44,992 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-13 17:41:44,992 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-13 17:41:44,993 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-13 17:41:44,993 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-13 17:41:44,993 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-13 17:41:44,993 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-13 17:41:44,994 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-13 17:41:44,994 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-13 17:41:44,995 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-13 17:41:44,995 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-13 17:41:44,995 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-13 17:41:44,995 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> acde98dd01af02b5a508b32116f1b2c3612f1f84e6ba2fe02fc76c333a1d32d3 [2024-10-13 17:41:45,192 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-13 17:41:45,209 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-13 17:41:45,211 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-13 17:41:45,212 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-13 17:41:45,212 INFO L274 PluginConnector]: CDTParser initialized [2024-10-13 17:41:45,213 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_10-1.c [2024-10-13 17:41:46,411 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-13 17:41:46,551 INFO L384 CDTParser]: Found 1 translation units. [2024-10-13 17:41:46,551 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_10-1.c [2024-10-13 17:41:46,557 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/857d6bd8c/db0d59e3609641a3a6270cd2777fb0e8/FLAGe6c32510c [2024-10-13 17:41:46,578 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/857d6bd8c/db0d59e3609641a3a6270cd2777fb0e8 [2024-10-13 17:41:46,585 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-13 17:41:46,587 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-13 17:41:46,588 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-13 17:41:46,588 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-13 17:41:46,594 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-13 17:41:46,594 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,595 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@531f43f0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46, skipping insertion in model container [2024-10-13 17:41:46,595 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,634 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-13 17:41:46,748 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:41:46,757 INFO L200 MainTranslator]: Completed pre-run [2024-10-13 17:41:46,765 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-13 17:41:46,776 INFO L204 MainTranslator]: Completed translation [2024-10-13 17:41:46,776 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46 WrapperNode [2024-10-13 17:41:46,776 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-13 17:41:46,777 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-13 17:41:46,777 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-13 17:41:46,777 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-13 17:41:46,782 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,787 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,797 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-10-13 17:41:46,798 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-13 17:41:46,798 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-13 17:41:46,798 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-13 17:41:46,798 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-13 17:41:46,805 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,806 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,806 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,813 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2024-10-13 17:41:46,814 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,814 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,815 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,816 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,817 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,817 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,819 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-13 17:41:46,820 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-13 17:41:46,820 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-13 17:41:46,820 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-13 17:41:46,821 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (1/1) ... [2024-10-13 17:41:46,825 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:46,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:46,849 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-10-13 17:41:46,851 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-10-13 17:41:46,886 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-13 17:41:46,886 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-13 17:41:46,886 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-13 17:41:46,887 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-13 17:41:46,887 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2024-10-13 17:41:46,887 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2024-10-13 17:41:46,937 INFO L238 CfgBuilder]: Building ICFG [2024-10-13 17:41:46,939 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-13 17:41:47,003 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-13 17:41:47,004 INFO L287 CfgBuilder]: Performing block encoding [2024-10-13 17:41:47,012 INFO L309 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-13 17:41:47,013 INFO L314 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-13 17:41:47,013 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:47 BoogieIcfgContainer [2024-10-13 17:41:47,013 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-13 17:41:47,014 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-13 17:41:47,014 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-13 17:41:47,016 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-13 17:41:47,019 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:47,019 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 13.10 05:41:46" (1/3) ... [2024-10-13 17:41:47,020 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@55df0be2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:41:47, skipping insertion in model container [2024-10-13 17:41:47,020 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:47,020 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.10 05:41:46" (2/3) ... [2024-10-13 17:41:47,020 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@55df0be2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.10 05:41:47, skipping insertion in model container [2024-10-13 17:41:47,021 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-13 17:41:47,021 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:47" (3/3) ... [2024-10-13 17:41:47,022 INFO L332 chiAutomizerObserver]: Analyzing ICFG fibo_10-1.c [2024-10-13 17:41:47,062 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-13 17:41:47,062 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-13 17:41:47,062 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-13 17:41:47,062 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-13 17:41:47,062 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-13 17:41:47,063 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-13 17:41:47,063 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-13 17:41:47,063 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-13 17:41:47,069 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-10-13 17:41:47,084 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:47,085 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:47,085 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:47,090 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:41:47,090 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:47,090 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-13 17:41:47,090 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-10-13 17:41:47,092 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:47,092 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:47,093 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:47,093 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-13 17:41:47,093 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:47,099 INFO L745 eck$LassoCheckResult]: Stem: 17#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 9#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 4#L27true call main_#t~ret6#1 := fibo(main_~x~0#1);< 11#$Ultimate##0true [2024-10-13 17:41:47,099 INFO L747 eck$LassoCheckResult]: Loop: 11#$Ultimate##0true ~n := #in~n; 5#L8true assume !(~n < 1); 7#L10true assume !(1 == ~n); 13#L13true call #t~ret4 := fibo(~n - 1);< 11#$Ultimate##0true [2024-10-13 17:41:47,106 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:47,106 INFO L85 PathProgramCache]: Analyzing trace with hash 29885, now seen corresponding path program 1 times [2024-10-13 17:41:47,112 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:47,112 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [340743937] [2024-10-13 17:41:47,113 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:47,113 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:47,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:47,187 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:47,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:47,205 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:47,208 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:47,208 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 1 times [2024-10-13 17:41:47,208 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:47,209 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1089578575] [2024-10-13 17:41:47,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:47,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:47,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:47,218 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:47,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:47,223 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:47,225 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:47,226 INFO L85 PathProgramCache]: Analyzing trace with hash 1830210312, now seen corresponding path program 1 times [2024-10-13 17:41:47,226 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:47,226 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [487559333] [2024-10-13 17:41:47,227 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:47,227 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:47,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:47,240 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:47,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:47,251 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:47,335 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:47,336 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:47,336 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:47,336 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:47,336 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:47,336 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,336 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:47,337 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:47,337 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration1_Loop [2024-10-13 17:41:47,337 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:47,337 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:47,347 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,359 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,361 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,363 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,375 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,430 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:47,431 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:47,433 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,433 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,435 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-10-13 17:41:47,436 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-10-13 17:41:47,437 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:47,437 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:47,452 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:47,453 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-10-13 17:41:47,463 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:47,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,465 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-10-13 17:41:47,466 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-10-13 17:41:47,467 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:47,467 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:47,478 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:47,478 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:47,489 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-10-13 17:41:47,489 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,489 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,490 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-10-13 17:41:47,491 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-10-13 17:41:47,493 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:47,493 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:47,504 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:47,504 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:47,515 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:47,516 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,516 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,517 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-10-13 17:41:47,518 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-10-13 17:41:47,519 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:47,519 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:47,540 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-10-13 17:41:47,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,541 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,542 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-10-13 17:41:47,543 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-10-13 17:41:47,543 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:47,544 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:47,596 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:47,601 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:47,601 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:47,601 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:47,601 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:47,601 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:47,601 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:47,601 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,601 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:47,601 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:47,601 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration1_Loop [2024-10-13 17:41:47,602 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:47,602 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:47,603 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,606 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,608 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,613 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,620 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:47,662 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:47,666 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:47,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,667 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,669 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-10-13 17:41:47,670 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-10-13 17:41:47,672 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:47,683 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:47,683 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:47,683 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:47,683 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:47,683 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:47,685 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:47,685 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:47,687 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:47,698 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:47,698 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,698 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,699 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-10-13 17:41:47,700 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-10-13 17:41:47,701 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:47,710 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:47,710 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:47,710 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:47,711 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:47,711 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:47,711 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:47,711 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:47,713 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:47,723 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:47,724 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,724 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,725 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-10-13 17:41:47,725 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-10-13 17:41:47,726 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:47,736 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:47,736 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:47,736 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:47,736 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:47,737 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:47,737 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:47,737 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:47,738 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:47,749 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-10-13 17:41:47,750 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,750 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,751 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-10-13 17:41:47,751 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-10-13 17:41:47,752 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:47,761 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:47,762 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:47,762 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:47,762 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:47,762 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:47,764 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:47,765 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:47,767 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:47,770 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:47,770 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:47,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:47,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:47,786 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-10-13 17:41:47,787 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-10-13 17:41:47,788 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:47,788 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:47,788 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:47,789 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-10-13 17:41:47,799 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-10-13 17:41:47,801 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:47,820 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:47,842 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:47,845 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-13 17:41:47,846 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:47,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:47,864 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:47,865 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:47,908 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:47,936 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2024-10-13 17:41:47,938 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-10-13 17:41:48,016 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-10-13 17:41:48,018 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 1 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:48,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-13 17:41:48,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-10-13 17:41:48,023 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-10-13 17:41:48,027 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:48,027 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-10-13 17:41:48,027 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:48,027 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-10-13 17:41:48,028 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:48,028 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 41 states and 54 transitions. [2024-10-13 17:41:48,030 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:48,034 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 41 states to 23 states and 31 transitions. [2024-10-13 17:41:48,035 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-10-13 17:41:48,035 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-10-13 17:41:48,035 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-10-13 17:41:48,036 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:48,036 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-10-13 17:41:48,047 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-10-13 17:41:48,053 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-10-13 17:41:48,054 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-13 17:41:48,054 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-10-13 17:41:48,055 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-13 17:41:48,055 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-13 17:41:48,055 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-13 17:41:48,055 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-10-13 17:41:48,056 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:48,056 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:48,056 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:48,057 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:48,057 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:48,057 INFO L745 eck$LassoCheckResult]: Stem: 135#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 136#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 121#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 120#$Ultimate##0 ~n := #in~n; 122#L8 assume !(~n < 1); 134#L10 assume !(1 == ~n); 124#L13 call #t~ret4 := fibo(~n - 1);< 123#$Ultimate##0 ~n := #in~n; 125#L8 assume ~n < 1;#res := 0; 131#fiboFINAL assume true; 132#fiboEXIT >#35#return; 127#L13-1 [2024-10-13 17:41:48,057 INFO L747 eck$LassoCheckResult]: Loop: 127#L13-1 call #t~ret5 := fibo(~n - 2);< 128#$Ultimate##0 ~n := #in~n; 138#L8 assume !(~n < 1); 139#L10 assume !(1 == ~n); 126#L13 call #t~ret4 := fibo(~n - 1);< 128#$Ultimate##0 ~n := #in~n; 138#L8 assume ~n < 1;#res := 0; 130#fiboFINAL assume true; 137#fiboEXIT >#35#return; 127#L13-1 [2024-10-13 17:41:48,057 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:48,058 INFO L85 PathProgramCache]: Analyzing trace with hash 523436175, now seen corresponding path program 1 times [2024-10-13 17:41:48,058 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:48,058 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [48581038] [2024-10-13 17:41:48,058 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:48,058 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:48,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:48,152 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2024-10-13 17:41:48,157 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:41:48,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:48,213 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-13 17:41:48,213 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:48,213 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [48581038] [2024-10-13 17:41:48,214 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [48581038] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:41:48,215 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-13 17:41:48,215 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-13 17:41:48,217 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1487489390] [2024-10-13 17:41:48,217 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:41:48,219 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:48,219 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:48,219 INFO L85 PathProgramCache]: Analyzing trace with hash 1950983701, now seen corresponding path program 1 times [2024-10-13 17:41:48,220 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:48,220 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1559072217] [2024-10-13 17:41:48,220 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:48,221 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:48,228 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:48,267 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-13 17:41:48,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:48,303 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-10-13 17:41:48,303 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:48,303 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1559072217] [2024-10-13 17:41:48,304 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1559072217] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-13 17:41:48,304 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-13 17:41:48,304 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-13 17:41:48,304 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1907390823] [2024-10-13 17:41:48,304 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-13 17:41:48,304 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-13 17:41:48,305 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:48,306 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-13 17:41:48,307 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-10-13 17:41:48,308 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-13 17:41:48,360 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:48,360 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-10-13 17:41:48,360 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-10-13 17:41:48,361 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:48,362 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-10-13 17:41:48,362 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-10-13 17:41:48,362 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-10-13 17:41:48,362 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-10-13 17:41:48,362 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:48,362 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:41:48,362 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-10-13 17:41:48,364 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-10-13 17:41:48,365 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2024-10-13 17:41:48,365 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-10-13 17:41:48,365 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:41:48,366 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-13 17:41:48,366 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-13 17:41:48,367 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-13 17:41:48,367 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-10-13 17:41:48,367 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:48,367 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:48,367 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:48,368 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:48,368 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:48,368 INFO L745 eck$LassoCheckResult]: Stem: 205#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 206#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 199#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 202#$Ultimate##0 ~n := #in~n; 197#L8 assume !(~n < 1); 208#L10 assume !(1 == ~n); 196#L13 call #t~ret4 := fibo(~n - 1);< 195#$Ultimate##0 ~n := #in~n; 198#L8 assume !(~n < 1); 214#L10 assume 1 == ~n;#res := 1; 213#fiboFINAL assume true; 211#fiboEXIT >#35#return; 192#L13-1 [2024-10-13 17:41:48,368 INFO L747 eck$LassoCheckResult]: Loop: 192#L13-1 call #t~ret5 := fibo(~n - 2);< 191#$Ultimate##0 ~n := #in~n; 194#L8 assume !(~n < 1); 207#L10 assume !(1 == ~n); 193#L13 call #t~ret4 := fibo(~n - 1);< 191#$Ultimate##0 ~n := #in~n; 194#L8 assume !(~n < 1); 207#L10 assume 1 == ~n;#res := 1; 209#fiboFINAL assume true; 210#fiboEXIT >#35#return; 192#L13-1 [2024-10-13 17:41:48,368 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:48,368 INFO L85 PathProgramCache]: Analyzing trace with hash -953322862, now seen corresponding path program 1 times [2024-10-13 17:41:48,369 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:48,369 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [701947814] [2024-10-13 17:41:48,369 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:48,369 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:48,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:48,421 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-13 17:41:48,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:48,444 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:48,445 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:48,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [701947814] [2024-10-13 17:41:48,445 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [701947814] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:48,445 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [835864891] [2024-10-13 17:41:48,445 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:48,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:48,446 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:48,447 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:41:48,448 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-10-13 17:41:48,483 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:48,484 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:41:48,485 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:48,511 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:48,511 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:48,616 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:48,616 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [835864891] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:48,617 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:48,617 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-10-13 17:41:48,617 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1271711413] [2024-10-13 17:41:48,617 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:48,617 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:48,617 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:48,618 INFO L85 PathProgramCache]: Analyzing trace with hash 350977484, now seen corresponding path program 1 times [2024-10-13 17:41:48,618 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:48,618 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1707823212] [2024-10-13 17:41:48,618 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:48,618 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:48,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:48,625 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:48,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:48,636 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:48,723 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:48,723 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:48,724 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:48,724 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:48,724 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:48,724 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:48,724 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:48,724 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:48,724 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration3_Loop [2024-10-13 17:41:48,724 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:48,724 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:48,725 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,728 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,729 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,732 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,736 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,770 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:48,771 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:48,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:48,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:48,772 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-10-13 17:41:48,773 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-10-13 17:41:48,773 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:48,774 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:48,785 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:48,785 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#in~n=2} Honda state: {fibo_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:48,795 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:48,795 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:48,796 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:48,797 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:48,797 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-10-13 17:41:48,798 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:48,798 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:48,808 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:48,810 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:48,820 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-10-13 17:41:48,821 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:48,821 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:48,822 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-10-13 17:41:48,823 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-10-13 17:41:48,824 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:48,825 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:48,838 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:48,839 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-10-13 17:41:48,849 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-10-13 17:41:48,850 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:48,850 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:48,852 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-10-13 17:41:48,853 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-10-13 17:41:48,853 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:48,854 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:48,875 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-10-13 17:41:48,875 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:48,876 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:48,877 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-10-13 17:41:48,878 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-10-13 17:41:48,879 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:48,879 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:48,891 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:48,901 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-10-13 17:41:48,902 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:48,902 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:48,902 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:48,902 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:48,902 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:48,902 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:48,902 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:48,902 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:48,902 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration3_Loop [2024-10-13 17:41:48,902 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:48,902 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:48,905 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,911 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,913 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,915 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,918 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:48,952 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:48,953 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:48,953 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:48,953 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:48,954 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-10-13 17:41:48,955 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-10-13 17:41:48,956 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:48,966 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:48,966 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:48,966 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:48,966 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:48,966 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:48,967 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:48,967 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:48,969 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:48,980 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:48,980 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:48,980 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:48,982 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-10-13 17:41:48,983 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-10-13 17:41:48,983 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:48,993 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:48,993 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:48,994 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:48,994 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:48,994 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:48,994 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:48,994 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:48,996 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:49,006 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-10-13 17:41:49,007 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:49,007 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:49,009 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-10-13 17:41:49,010 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-10-13 17:41:49,011 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:49,020 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:49,020 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:49,021 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:49,021 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:49,021 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:49,021 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:49,021 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:49,022 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:49,032 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-10-13 17:41:49,032 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:49,033 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:49,034 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:49,035 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-10-13 17:41:49,035 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:49,045 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:49,045 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:49,045 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:49,045 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:49,045 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:49,046 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:49,046 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:49,047 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:49,057 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:49,057 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:49,058 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:49,059 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:49,060 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-10-13 17:41:49,061 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:49,070 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:49,071 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:49,071 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:49,071 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:49,071 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:49,072 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:49,072 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:49,073 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:49,075 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:49,076 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:49,076 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:49,076 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:49,077 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:49,078 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-10-13 17:41:49,079 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:49,079 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:49,080 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:49,080 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-10-13 17:41:49,090 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:49,091 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:49,099 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:49,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:49,123 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:41:49,124 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:49,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:49,212 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-13 17:41:49,213 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:49,276 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:49,277 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-13 17:41:49,277 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-13 17:41:49,444 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 128 states and 178 transitions. Complement of second has 40 states. [2024-10-13 17:41:49,447 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:49,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-13 17:41:49,448 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-10-13 17:41:49,448 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 10 letters. [2024-10-13 17:41:49,449 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:49,449 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 22 letters. Loop has 10 letters. [2024-10-13 17:41:49,449 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:49,449 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 12 letters. Loop has 20 letters. [2024-10-13 17:41:49,449 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:49,449 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 128 states and 178 transitions. [2024-10-13 17:41:49,454 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-10-13 17:41:49,456 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 128 states to 105 states and 151 transitions. [2024-10-13 17:41:49,456 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 62 [2024-10-13 17:41:49,457 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 66 [2024-10-13 17:41:49,457 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 151 transitions. [2024-10-13 17:41:49,457 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:49,457 INFO L218 hiAutomatonCegarLoop]: Abstraction has 105 states and 151 transitions. [2024-10-13 17:41:49,457 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 151 transitions. [2024-10-13 17:41:49,464 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 94. [2024-10-13 17:41:49,464 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 64 states have internal predecessors, (71), 21 states have call successors, (22), 11 states have call predecessors, (22), 15 states have return successors, (35), 18 states have call predecessors, (35), 19 states have call successors, (35) [2024-10-13 17:41:49,465 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 128 transitions. [2024-10-13 17:41:49,465 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 128 transitions. [2024-10-13 17:41:49,465 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:49,466 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-13 17:41:49,466 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-10-13 17:41:49,466 INFO L87 Difference]: Start difference. First operand 94 states and 128 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-13 17:41:49,561 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:49,561 INFO L93 Difference]: Finished difference Result 119 states and 163 transitions. [2024-10-13 17:41:49,562 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 119 states and 163 transitions. [2024-10-13 17:41:49,564 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-10-13 17:41:49,566 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 119 states to 114 states and 158 transitions. [2024-10-13 17:41:49,566 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 73 [2024-10-13 17:41:49,566 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 73 [2024-10-13 17:41:49,567 INFO L73 IsDeterministic]: Start isDeterministic. Operand 114 states and 158 transitions. [2024-10-13 17:41:49,567 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:49,567 INFO L218 hiAutomatonCegarLoop]: Abstraction has 114 states and 158 transitions. [2024-10-13 17:41:49,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states and 158 transitions. [2024-10-13 17:41:49,576 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 106. [2024-10-13 17:41:49,576 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.196969696969697) internal successors, (79), 72 states have internal predecessors, (79), 24 states have call successors, (25), 13 states have call predecessors, (25), 16 states have return successors, (39), 20 states have call predecessors, (39), 22 states have call successors, (39) [2024-10-13 17:41:49,577 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 143 transitions. [2024-10-13 17:41:49,578 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-10-13 17:41:49,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-13 17:41:49,579 INFO L425 stractBuchiCegarLoop]: Abstraction has 106 states and 143 transitions. [2024-10-13 17:41:49,579 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-13 17:41:49,579 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 143 transitions. [2024-10-13 17:41:49,580 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2024-10-13 17:41:49,580 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:49,580 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:49,581 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:49,581 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 4, 3, 2, 2, 2, 2, 2, 1, 1] [2024-10-13 17:41:49,581 INFO L745 eck$LassoCheckResult]: Stem: 806#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 807#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 792#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 793#$Ultimate##0 ~n := #in~n; 809#L8 assume !(~n < 1); 810#L10 assume !(1 == ~n); 780#L13 call #t~ret4 := fibo(~n - 1);< 779#$Ultimate##0 ~n := #in~n; 781#L8 assume !(~n < 1); 816#L10 assume !(1 == ~n); 790#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 838#L8 assume !(~n < 1); 836#L10 assume !(1 == ~n); 832#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 838#L8 assume !(~n < 1); 836#L10 assume !(1 == ~n); 832#L13 call #t~ret4 := fibo(~n - 1);< 791#$Ultimate##0 ~n := #in~n; 839#L8 assume !(~n < 1); 837#L10 assume 1 == ~n;#res := 1; 835#fiboFINAL assume true; 834#fiboEXIT >#35#return; 817#L13-1 call #t~ret5 := fibo(~n - 2);< 833#$Ultimate##0 ~n := #in~n; 879#L8 assume ~n < 1;#res := 0; 878#fiboFINAL assume true; 877#fiboEXIT >#37#return; 875#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 872#fiboFINAL assume true; 864#fiboEXIT >#35#return; 813#L13-1 [2024-10-13 17:41:49,582 INFO L747 eck$LassoCheckResult]: Loop: 813#L13-1 call #t~ret5 := fibo(~n - 2);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume !(1 == ~n); 814#L13 call #t~ret4 := fibo(~n - 1);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume !(1 == ~n); 814#L13 call #t~ret4 := fibo(~n - 1);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume 1 == ~n;#res := 1; 815#fiboFINAL assume true; 861#fiboEXIT >#35#return; 813#L13-1 call #t~ret5 := fibo(~n - 2);< 789#$Ultimate##0 ~n := #in~n; 869#L8 assume !(~n < 1); 811#L10 assume 1 == ~n;#res := 1; 815#fiboFINAL assume true; 861#fiboEXIT >#37#return; 862#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 871#fiboFINAL assume true; 865#fiboEXIT >#35#return; 813#L13-1 [2024-10-13 17:41:49,582 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:49,582 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 1 times [2024-10-13 17:41:49,582 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:49,582 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [824469897] [2024-10-13 17:41:49,582 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:49,582 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:49,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:49,647 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2024-10-13 17:41:49,710 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-13 17:41:49,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:49,766 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:49,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:49,783 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:49,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:49,788 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-13 17:41:49,788 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:49,789 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [824469897] [2024-10-13 17:41:49,789 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [824469897] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:49,789 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1412867408] [2024-10-13 17:41:49,789 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:49,789 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:49,789 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:49,790 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:41:49,792 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Waiting until timeout for monitored process [2024-10-13 17:41:49,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:49,822 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-13 17:41:49,823 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:49,862 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-13 17:41:49,862 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:50,057 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-10-13 17:41:50,058 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1412867408] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:50,058 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:50,058 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-10-13 17:41:50,058 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [149160144] [2024-10-13 17:41:50,058 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:50,059 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:50,059 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:50,059 INFO L85 PathProgramCache]: Analyzing trace with hash -1138642743, now seen corresponding path program 1 times [2024-10-13 17:41:50,059 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:50,059 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [509101525] [2024-10-13 17:41:50,059 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:50,059 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:50,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,072 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-13 17:41:50,075 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,089 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:50,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,105 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:50,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,127 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2024-10-13 17:41:50,128 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:50,128 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [509101525] [2024-10-13 17:41:50,128 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [509101525] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:50,128 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1049295766] [2024-10-13 17:41:50,128 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:50,128 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:50,128 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:50,130 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:41:50,130 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Waiting until timeout for monitored process [2024-10-13 17:41:50,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,157 INFO L255 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-13 17:41:50,157 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:50,182 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-10-13 17:41:50,182 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:50,294 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 13 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2024-10-13 17:41:50,294 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1049295766] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:50,295 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:50,295 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2024-10-13 17:41:50,295 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1199159486] [2024-10-13 17:41:50,295 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:50,295 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-13 17:41:50,295 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:50,295 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-10-13 17:41:50,295 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2024-10-13 17:41:50,295 INFO L87 Difference]: Start difference. First operand 106 states and 143 transitions. cyclomatic complexity: 42 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-10-13 17:41:50,373 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:50,373 INFO L93 Difference]: Finished difference Result 58 states and 76 transitions. [2024-10-13 17:41:50,373 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 76 transitions. [2024-10-13 17:41:50,374 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:50,375 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 54 states and 70 transitions. [2024-10-13 17:41:50,375 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2024-10-13 17:41:50,375 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2024-10-13 17:41:50,375 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2024-10-13 17:41:50,375 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:50,375 INFO L218 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-10-13 17:41:50,375 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2024-10-13 17:41:50,382 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2024-10-13 17:41:50,382 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-10-13 17:41:50,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2024-10-13 17:41:50,385 INFO L240 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-10-13 17:41:50,385 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-13 17:41:50,385 INFO L425 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2024-10-13 17:41:50,386 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-13 17:41:50,386 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2024-10-13 17:41:50,388 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:50,388 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:50,388 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:50,389 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:50,389 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 1] [2024-10-13 17:41:50,389 INFO L745 eck$LassoCheckResult]: Stem: 1377#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 1378#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 1371#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1372#$Ultimate##0 ~n := #in~n; 1387#L8 assume !(~n < 1); 1386#L10 assume !(1 == ~n); 1359#L13 call #t~ret4 := fibo(~n - 1);< 1358#$Ultimate##0 ~n := #in~n; 1360#L8 assume !(~n < 1); 1380#L10 assume !(1 == ~n); 1364#L13 call #t~ret4 := fibo(~n - 1);< 1365#$Ultimate##0 ~n := #in~n; 1385#L8 assume !(~n < 1); 1403#L10 assume !(1 == ~n); 1375#L13 call #t~ret4 := fibo(~n - 1);< 1365#$Ultimate##0 ~n := #in~n; 1385#L8 assume !(~n < 1); 1403#L10 assume !(1 == ~n); 1375#L13 call #t~ret4 := fibo(~n - 1);< 1365#$Ultimate##0 ~n := #in~n; 1384#L8 assume !(~n < 1); 1381#L10 assume 1 == ~n;#res := 1; 1382#fiboFINAL assume true; 1374#fiboEXIT >#35#return; 1376#L13-1 call #t~ret5 := fibo(~n - 2);< 1402#$Ultimate##0 ~n := #in~n; 1408#L8 assume ~n < 1;#res := 0; 1407#fiboFINAL assume true; 1401#fiboEXIT >#37#return; 1399#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1397#fiboFINAL assume true; 1394#fiboEXIT >#35#return; 1368#L13-1 [2024-10-13 17:41:50,389 INFO L747 eck$LassoCheckResult]: Loop: 1368#L13-1 call #t~ret5 := fibo(~n - 2);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume !(~n < 1); 1389#L10 assume !(1 == ~n); 1367#L13 call #t~ret4 := fibo(~n - 1);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume !(~n < 1); 1389#L10 assume !(1 == ~n); 1367#L13 call #t~ret4 := fibo(~n - 1);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume !(~n < 1); 1389#L10 assume !(1 == ~n); 1367#L13 call #t~ret4 := fibo(~n - 1);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume !(~n < 1); 1389#L10 assume 1 == ~n;#res := 1; 1404#fiboFINAL assume true; 1405#fiboEXIT >#35#return; 1356#L13-1 call #t~ret5 := fibo(~n - 2);< 1355#$Ultimate##0 ~n := #in~n; 1357#L8 assume ~n < 1;#res := 0; 1379#fiboFINAL assume true; 1400#fiboEXIT >#37#return; 1366#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1370#fiboFINAL assume true; 1373#fiboEXIT >#35#return; 1368#L13-1 call #t~ret5 := fibo(~n - 2);< 1363#$Ultimate##0 ~n := #in~n; 1388#L8 assume ~n < 1;#res := 0; 1379#fiboFINAL assume true; 1400#fiboEXIT >#37#return; 1391#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1398#fiboFINAL assume true; 1395#fiboEXIT >#35#return; 1368#L13-1 [2024-10-13 17:41:50,389 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:50,389 INFO L85 PathProgramCache]: Analyzing trace with hash 870102534, now seen corresponding path program 2 times [2024-10-13 17:41:50,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:50,390 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [817597564] [2024-10-13 17:41:50,390 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:50,390 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:50,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,468 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-13 17:41:50,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,505 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:50,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,518 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:50,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,522 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-13 17:41:50,522 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:50,522 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [817597564] [2024-10-13 17:41:50,522 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [817597564] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:50,522 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1168046323] [2024-10-13 17:41:50,523 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-13 17:41:50,523 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:50,523 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:50,524 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:41:50,525 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (26)] Waiting until timeout for monitored process [2024-10-13 17:41:50,555 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-13 17:41:50,556 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-13 17:41:50,556 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-13 17:41:50,558 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:50,594 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-13 17:41:50,595 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:50,794 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-10-13 17:41:50,795 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1168046323] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:50,795 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:50,795 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-10-13 17:41:50,795 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [65170413] [2024-10-13 17:41:50,795 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:50,795 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:50,796 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:50,796 INFO L85 PathProgramCache]: Analyzing trace with hash 1083596768, now seen corresponding path program 1 times [2024-10-13 17:41:50,796 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:50,796 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1031341922] [2024-10-13 17:41:50,796 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:50,796 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:50,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,823 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-13 17:41:50,825 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,848 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:50,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,886 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:50,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,889 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:50,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,894 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2024-10-13 17:41:50,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,908 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 29 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2024-10-13 17:41:50,909 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:50,909 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1031341922] [2024-10-13 17:41:50,909 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1031341922] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:50,909 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2102207578] [2024-10-13 17:41:50,909 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:50,909 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:50,909 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:50,911 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:41:50,912 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (27)] Waiting until timeout for monitored process [2024-10-13 17:41:50,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:50,942 INFO L255 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-10-13 17:41:50,942 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:50,973 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 12 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-10-13 17:41:50,973 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:51,160 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 13 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2024-10-13 17:41:51,161 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2102207578] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:51,161 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:51,161 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 14 [2024-10-13 17:41:51,161 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1304566153] [2024-10-13 17:41:51,161 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:51,162 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-13 17:41:51,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:51,162 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-13 17:41:51,162 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-10-13 17:41:51,162 INFO L87 Difference]: Start difference. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 23 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 15 states have internal predecessors, (41), 13 states have call successors, (13), 7 states have call predecessors, (13), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-13 17:41:51,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:51,432 INFO L93 Difference]: Finished difference Result 110 states and 129 transitions. [2024-10-13 17:41:51,432 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 110 states and 129 transitions. [2024-10-13 17:41:51,434 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:51,435 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 110 states to 99 states and 118 transitions. [2024-10-13 17:41:51,435 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-10-13 17:41:51,435 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 72 [2024-10-13 17:41:51,436 INFO L73 IsDeterministic]: Start isDeterministic. Operand 99 states and 118 transitions. [2024-10-13 17:41:51,436 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:51,436 INFO L218 hiAutomatonCegarLoop]: Abstraction has 99 states and 118 transitions. [2024-10-13 17:41:51,436 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 99 states and 118 transitions. [2024-10-13 17:41:51,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 99 to 99. [2024-10-13 17:41:51,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 64 states have (on average 1.046875) internal successors, (67), 66 states have internal predecessors, (67), 23 states have call successors, (23), 14 states have call predecessors, (23), 12 states have return successors, (28), 18 states have call predecessors, (28), 20 states have call successors, (28) [2024-10-13 17:41:51,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 118 transitions. [2024-10-13 17:41:51,445 INFO L240 hiAutomatonCegarLoop]: Abstraction has 99 states and 118 transitions. [2024-10-13 17:41:51,445 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-13 17:41:51,446 INFO L425 stractBuchiCegarLoop]: Abstraction has 99 states and 118 transitions. [2024-10-13 17:41:51,446 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-13 17:41:51,446 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 99 states and 118 transitions. [2024-10-13 17:41:51,447 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-13 17:41:51,447 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:51,447 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:51,448 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 9, 8, 8, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:51,448 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-10-13 17:41:51,448 INFO L745 eck$LassoCheckResult]: Stem: 2063#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 2064#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 2059#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 2060#$Ultimate##0 ~n := #in~n; 2066#L8 assume !(~n < 1); 2067#L10 assume !(1 == ~n); 2050#L13 call #t~ret4 := fibo(~n - 1);< 2049#$Ultimate##0 ~n := #in~n; 2051#L8 assume !(~n < 1); 2091#L10 assume !(1 == ~n); 2055#L13 call #t~ret4 := fibo(~n - 1);< 2056#$Ultimate##0 ~n := #in~n; 2090#L8 assume !(~n < 1); 2089#L10 assume !(1 == ~n); 2085#L13 call #t~ret4 := fibo(~n - 1);< 2088#$Ultimate##0 ~n := #in~n; 2087#L8 assume !(~n < 1); 2086#L10 assume !(1 == ~n); 2081#L13 call #t~ret4 := fibo(~n - 1);< 2084#$Ultimate##0 ~n := #in~n; 2083#L8 assume !(~n < 1); 2082#L10 assume !(1 == ~n); 2077#L13 call #t~ret4 := fibo(~n - 1);< 2080#$Ultimate##0 ~n := #in~n; 2079#L8 assume !(~n < 1); 2078#L10 assume !(1 == ~n); 2069#L13 call #t~ret4 := fibo(~n - 1);< 2075#$Ultimate##0 ~n := #in~n; 2076#L8 assume !(~n < 1); 2144#L10 assume !(1 == ~n); 2070#L13 call #t~ret4 := fibo(~n - 1);< 2075#$Ultimate##0 ~n := #in~n; 2076#L8 assume !(~n < 1); 2144#L10 assume !(1 == ~n); 2070#L13 call #t~ret4 := fibo(~n - 1);< 2075#$Ultimate##0 ~n := #in~n; 2074#L8 assume !(~n < 1); 2068#L10 assume 1 == ~n;#res := 1; 2071#fiboFINAL assume true; 2102#fiboEXIT >#35#return; 2047#L13-1 call #t~ret5 := fibo(~n - 2);< 2046#$Ultimate##0 ~n := #in~n; 2048#L8 assume ~n < 1;#res := 0; 2065#fiboFINAL assume true; 2119#fiboEXIT >#37#return; 2117#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 2111#fiboFINAL assume true; 2107#fiboEXIT >#35#return; 2097#L13-1 [2024-10-13 17:41:51,448 INFO L747 eck$LassoCheckResult]: Loop: 2097#L13-1 call #t~ret5 := fibo(~n - 2);< 2103#$Ultimate##0 ~n := #in~n; 2115#L8 assume !(~n < 1); 2110#L10 assume !(1 == ~n); 2096#L13 call #t~ret4 := fibo(~n - 1);< 2103#$Ultimate##0 ~n := #in~n; 2115#L8 assume !(~n < 1); 2110#L10 assume !(1 == ~n); 2096#L13 call #t~ret4 := fibo(~n - 1);< 2103#$Ultimate##0 ~n := #in~n; 2115#L8 assume !(~n < 1); 2110#L10 assume 1 == ~n;#res := 1; 2104#fiboFINAL assume true; 2100#fiboEXIT >#35#return; 2093#L13-1 call #t~ret5 := fibo(~n - 2);< 2099#$Ultimate##0 ~n := #in~n; 2124#L8 assume ~n < 1;#res := 0; 2116#fiboFINAL assume true; 2120#fiboEXIT >#37#return; 2121#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 2143#fiboFINAL assume true; 2105#fiboEXIT >#35#return; 2097#L13-1 [2024-10-13 17:41:51,448 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:51,448 INFO L85 PathProgramCache]: Analyzing trace with hash -683438758, now seen corresponding path program 3 times [2024-10-13 17:41:51,448 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:51,449 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [523806048] [2024-10-13 17:41:51,449 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:51,449 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:51,456 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:51,595 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-13 17:41:51,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:51,639 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:51,640 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:51,655 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:51,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:51,659 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 2 proven. 153 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-13 17:41:51,659 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:51,661 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [523806048] [2024-10-13 17:41:51,661 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [523806048] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:51,661 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1239411259] [2024-10-13 17:41:51,661 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-10-13 17:41:51,661 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:51,662 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:51,665 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:41:51,666 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (28)] Waiting until timeout for monitored process [2024-10-13 17:41:51,703 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2024-10-13 17:41:51,703 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-13 17:41:51,704 INFO L255 TraceCheckSpWp]: Trace formula consists of 118 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-10-13 17:41:51,705 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:51,770 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 2 proven. 153 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-10-13 17:41:51,770 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:52,009 INFO L134 CoverageAnalysis]: Checked inductivity of 160 backedges. 2 proven. 155 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-10-13 17:41:52,009 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1239411259] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:52,009 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:52,009 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19, 20] total 23 [2024-10-13 17:41:52,009 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [409655130] [2024-10-13 17:41:52,009 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:52,010 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:52,010 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:52,010 INFO L85 PathProgramCache]: Analyzing trace with hash -2000232554, now seen corresponding path program 2 times [2024-10-13 17:41:52,010 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:52,010 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [764971957] [2024-10-13 17:41:52,010 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:52,010 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:52,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:52,013 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:52,014 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:52,015 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:52,187 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:52,187 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:52,187 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:52,187 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:52,187 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:52,187 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:52,188 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:52,188 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:52,188 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration6_Loop [2024-10-13 17:41:52,188 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:52,188 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:52,188 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:52,195 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:52,196 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:52,198 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:52,234 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:52,234 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:52,235 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:52,235 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:52,236 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:52,238 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-10-13 17:41:52,238 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:52,238 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:52,265 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:52,265 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:52,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:52,266 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-10-13 17:41:52,267 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-10-13 17:41:52,268 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:52,268 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:52,704 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:52,708 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-10-13 17:41:52,709 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:52,709 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:52,709 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:52,709 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:52,709 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:52,709 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:52,709 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:52,709 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:52,709 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration6_Loop [2024-10-13 17:41:52,709 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:52,709 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:52,710 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:52,716 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:52,717 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:52,719 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:52,748 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:52,748 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:52,748 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:52,748 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:52,749 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-10-13 17:41:52,750 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-10-13 17:41:52,753 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:52,763 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:52,763 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:52,763 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:52,763 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:52,763 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:52,764 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:52,764 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:52,767 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:52,771 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-13 17:41:52,771 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-13 17:41:52,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:52,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:52,772 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-10-13 17:41:52,773 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-10-13 17:41:52,774 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:52,774 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:52,774 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:52,775 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2024-10-13 17:41:52,784 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2024-10-13 17:41:52,785 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:52,793 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:52,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:52,842 INFO L255 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-10-13 17:41:52,844 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:53,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:53,005 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:41:53,006 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:53,092 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:53,093 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2024-10-13 17:41:53,093 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21 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-10-13 17:41:53,164 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21. 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 106 states and 125 transitions. Complement of second has 11 states. [2024-10-13 17:41:53,164 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:53,165 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-10-13 17:41:53,165 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-10-13 17:41:53,165 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 48 letters. Loop has 22 letters. [2024-10-13 17:41:53,165 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:53,165 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:53,173 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:53,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:53,218 INFO L255 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-10-13 17:41:53,219 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:53,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:53,374 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:41:53,375 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:53,425 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-10-13 17:41:53,483 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:53,484 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-10-13 17:41:53,484 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21 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-10-13 17:41:53,552 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21. 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 106 states and 125 transitions. Complement of second has 11 states. [2024-10-13 17:41:53,556 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:53,556 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-10-13 17:41:53,556 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2024-10-13 17:41:53,556 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 48 letters. Loop has 22 letters. [2024-10-13 17:41:53,557 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:53,557 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:53,563 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:53,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:53,607 INFO L255 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-10-13 17:41:53,608 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:53,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:53,771 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-13 17:41:53,772 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:53,866 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-13 17:41:53,867 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-10-13 17:41:53,867 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21 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-10-13 17:41:54,032 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 99 states and 118 transitions. cyclomatic complexity: 21. 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 537 states and 697 transitions. Complement of second has 132 states. [2024-10-13 17:41:54,035 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 11 states 2 stem states 8 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:54,036 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-10-13 17:41:54,036 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 45 transitions. [2024-10-13 17:41:54,036 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 48 letters. Loop has 22 letters. [2024-10-13 17:41:54,037 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:54,037 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 70 letters. Loop has 22 letters. [2024-10-13 17:41:54,037 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:54,037 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 45 transitions. Stem has 48 letters. Loop has 44 letters. [2024-10-13 17:41:54,038 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:54,038 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 537 states and 697 transitions. [2024-10-13 17:41:54,044 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:54,050 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 537 states to 382 states and 513 transitions. [2024-10-13 17:41:54,050 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 161 [2024-10-13 17:41:54,050 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 186 [2024-10-13 17:41:54,050 INFO L73 IsDeterministic]: Start isDeterministic. Operand 382 states and 513 transitions. [2024-10-13 17:41:54,051 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:54,051 INFO L218 hiAutomatonCegarLoop]: Abstraction has 382 states and 513 transitions. [2024-10-13 17:41:54,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 382 states and 513 transitions. [2024-10-13 17:41:54,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 382 to 337. [2024-10-13 17:41:54,064 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 337 states, 206 states have (on average 1.0922330097087378) internal successors, (225), 219 states have internal predecessors, (225), 80 states have call successors, (84), 42 states have call predecessors, (84), 51 states have return successors, (126), 75 states have call predecessors, (126), 70 states have call successors, (126) [2024-10-13 17:41:54,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 337 states to 337 states and 435 transitions. [2024-10-13 17:41:54,067 INFO L240 hiAutomatonCegarLoop]: Abstraction has 337 states and 435 transitions. [2024-10-13 17:41:54,067 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:54,067 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-10-13 17:41:54,068 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=437, Unknown=0, NotChecked=0, Total=552 [2024-10-13 17:41:54,068 INFO L87 Difference]: Start difference. First operand 337 states and 435 transitions. Second operand has 24 states, 21 states have (on average 2.0476190476190474) internal successors, (43), 15 states have internal predecessors, (43), 13 states have call successors, (13), 8 states have call predecessors, (13), 3 states have return successors, (6), 3 states have call predecessors, (6), 6 states have call successors, (6) [2024-10-13 17:41:54,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:54,337 INFO L93 Difference]: Finished difference Result 462 states and 593 transitions. [2024-10-13 17:41:54,338 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 462 states and 593 transitions. [2024-10-13 17:41:54,341 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:54,346 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 462 states to 455 states and 580 transitions. [2024-10-13 17:41:54,346 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 210 [2024-10-13 17:41:54,346 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 210 [2024-10-13 17:41:54,346 INFO L73 IsDeterministic]: Start isDeterministic. Operand 455 states and 580 transitions. [2024-10-13 17:41:54,346 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:54,346 INFO L218 hiAutomatonCegarLoop]: Abstraction has 455 states and 580 transitions. [2024-10-13 17:41:54,347 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 455 states and 580 transitions. [2024-10-13 17:41:54,362 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 455 to 435. [2024-10-13 17:41:54,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 435 states, 267 states have (on average 1.0823970037453183) internal successors, (289), 281 states have internal predecessors, (289), 106 states have call successors, (110), 55 states have call predecessors, (110), 62 states have return successors, (159), 98 states have call predecessors, (159), 94 states have call successors, (159) [2024-10-13 17:41:54,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 435 states to 435 states and 558 transitions. [2024-10-13 17:41:54,372 INFO L240 hiAutomatonCegarLoop]: Abstraction has 435 states and 558 transitions. [2024-10-13 17:41:54,374 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-13 17:41:54,374 INFO L425 stractBuchiCegarLoop]: Abstraction has 435 states and 558 transitions. [2024-10-13 17:41:54,375 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-10-13 17:41:54,375 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 435 states and 558 transitions. [2024-10-13 17:41:54,377 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:54,377 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-13 17:41:54,377 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-13 17:41:54,380 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [13, 12, 11, 11, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-10-13 17:41:54,380 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-13 17:41:54,380 INFO L745 eck$LassoCheckResult]: Stem: 4917#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(12, 2);call #Ultimate.allocInit(12, 3); 4918#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 10; 4908#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 4909#$Ultimate##0 ~n := #in~n; 4958#L8 assume !(~n < 1); 4957#L10 assume !(1 == ~n); 4953#L13 call #t~ret4 := fibo(~n - 1);< 4956#$Ultimate##0 ~n := #in~n; 4955#L8 assume !(~n < 1); 4954#L10 assume !(1 == ~n); 4949#L13 call #t~ret4 := fibo(~n - 1);< 4952#$Ultimate##0 ~n := #in~n; 4951#L8 assume !(~n < 1); 4950#L10 assume !(1 == ~n); 4945#L13 call #t~ret4 := fibo(~n - 1);< 4948#$Ultimate##0 ~n := #in~n; 4947#L8 assume !(~n < 1); 4946#L10 assume !(1 == ~n); 4941#L13 call #t~ret4 := fibo(~n - 1);< 4944#$Ultimate##0 ~n := #in~n; 4943#L8 assume !(~n < 1); 4942#L10 assume !(1 == ~n); 4937#L13 call #t~ret4 := fibo(~n - 1);< 4940#$Ultimate##0 ~n := #in~n; 4939#L8 assume !(~n < 1); 4938#L10 assume !(1 == ~n); 4933#L13 call #t~ret4 := fibo(~n - 1);< 4936#$Ultimate##0 ~n := #in~n; 4935#L8 assume !(~n < 1); 4934#L10 assume !(1 == ~n); 4914#L13 call #t~ret4 := fibo(~n - 1);< 4930#$Ultimate##0 ~n := #in~n; 4932#L8 assume !(~n < 1); 5268#L10 assume !(1 == ~n); 4913#L13 call #t~ret4 := fibo(~n - 1);< 4930#$Ultimate##0 ~n := #in~n; 4932#L8 assume !(~n < 1); 5268#L10 assume !(1 == ~n); 4913#L13 call #t~ret4 := fibo(~n - 1);< 4930#$Ultimate##0 ~n := #in~n; 4931#L8 assume !(~n < 1); 5315#L10 assume 1 == ~n;#res := 1; 5313#fiboFINAL assume true; 4912#fiboEXIT >#35#return; 4915#L13-1 call #t~ret5 := fibo(~n - 2);< 5284#$Ultimate##0 ~n := #in~n; 5288#L8 assume ~n < 1;#res := 0; 5287#fiboFINAL assume true; 5283#fiboEXIT >#37#return; 5282#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 5281#fiboFINAL assume true; 5267#fiboEXIT >#35#return; 4923#L13-1 call #t~ret5 := fibo(~n - 2);< 5244#$Ultimate##0 ~n := #in~n; 5273#L8 assume !(~n < 1); 5272#L10 assume !(1 == ~n); 4903#L13 call #t~ret4 := fibo(~n - 1);< 5046#$Ultimate##0 ~n := #in~n; 5045#L8 assume !(~n < 1); 5003#L10 assume !(1 == ~n); 4984#L13 call #t~ret4 := fibo(~n - 1);< 4992#$Ultimate##0 [2024-10-13 17:41:54,380 INFO L747 eck$LassoCheckResult]: Loop: 4992#$Ultimate##0 ~n := #in~n; 4999#L8 assume !(~n < 1); 4998#L10 assume !(1 == ~n); 4983#L13 call #t~ret4 := fibo(~n - 1);< 4992#$Ultimate##0 [2024-10-13 17:41:54,381 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:54,381 INFO L85 PathProgramCache]: Analyzing trace with hash -366223317, now seen corresponding path program 4 times [2024-10-13 17:41:54,381 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:54,381 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1710242156] [2024-10-13 17:41:54,381 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:54,381 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:54,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:54,604 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-13 17:41:54,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:54,608 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-13 17:41:54,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:54,609 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-13 17:41:54,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:54,624 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 198 proven. 72 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-10-13 17:41:54,625 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-13 17:41:54,625 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1710242156] [2024-10-13 17:41:54,625 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1710242156] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-13 17:41:54,625 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [816514475] [2024-10-13 17:41:54,625 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-10-13 17:41:54,625 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-13 17:41:54,626 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:54,627 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-13 17:41:54,628 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (33)] Waiting until timeout for monitored process [2024-10-13 17:41:54,668 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-10-13 17:41:54,668 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-13 17:41:54,669 INFO L255 TraceCheckSpWp]: Trace formula consists of 127 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-10-13 17:41:54,670 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:54,742 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 199 proven. 72 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-10-13 17:41:54,742 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-13 17:41:54,922 INFO L134 CoverageAnalysis]: Checked inductivity of 284 backedges. 199 proven. 72 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-10-13 17:41:54,922 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [816514475] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-13 17:41:54,922 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-13 17:41:54,922 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 23, 23] total 24 [2024-10-13 17:41:54,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2058683121] [2024-10-13 17:41:54,922 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-13 17:41:54,922 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-13 17:41:54,923 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:54,923 INFO L85 PathProgramCache]: Analyzing trace with hash 1512524, now seen corresponding path program 2 times [2024-10-13 17:41:54,923 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-13 17:41:54,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1228440863] [2024-10-13 17:41:54,923 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-13 17:41:54,923 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-13 17:41:54,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:54,924 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-13 17:41:54,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-13 17:41:54,926 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-13 17:41:54,949 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:54,949 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:54,949 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:54,950 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:54,950 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-13 17:41:54,950 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:54,950 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:54,950 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:54,950 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration7_Loop [2024-10-13 17:41:54,950 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:54,950 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:54,950 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:54,952 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:54,953 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:54,954 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:54,955 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:54,981 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:54,981 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-13 17:41:54,981 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:54,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:54,983 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-10-13 17:41:54,983 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-10-13 17:41:54,984 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:54,984 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:54,995 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:54,995 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:55,006 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-10-13 17:41:55,006 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,006 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:55,007 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-10-13 17:41:55,008 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-10-13 17:41:55,009 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:55,009 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:55,019 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:55,020 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-13 17:41:55,030 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:55,031 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,031 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:55,032 INFO L229 MonitoredProcess]: Starting monitored process 36 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-10-13 17:41:55,033 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-10-13 17:41:55,034 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:55,034 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:55,045 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:55,045 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-10-13 17:41:55,055 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:55,056 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,056 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:55,057 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:55,058 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-10-13 17:41:55,059 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:55,059 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:55,070 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-13 17:41:55,070 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-10-13 17:41:55,080 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Ended with exit code 0 [2024-10-13 17:41:55,081 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,081 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:55,082 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:55,083 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-10-13 17:41:55,084 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-13 17:41:55,084 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:55,104 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:55,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:55,105 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:55,106 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-10-13 17:41:55,106 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-13 17:41:55,106 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-13 17:41:55,156 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-13 17:41:55,160 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:55,160 INFO L204 LassoAnalysis]: Preferences: [2024-10-13 17:41:55,160 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-13 17:41:55,160 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-13 17:41:55,160 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-13 17:41:55,160 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-13 17:41:55,160 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,160 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-13 17:41:55,160 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-13 17:41:55,160 INFO L132 ssoRankerPreferences]: Filename of dumped script: fibo_10-1.c_Iteration7_Loop [2024-10-13 17:41:55,160 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-13 17:41:55,160 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-13 17:41:55,161 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:55,162 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:55,163 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:55,167 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:55,168 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-13 17:41:55,192 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-13 17:41:55,192 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-13 17:41:55,192 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,192 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:55,193 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:55,194 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-10-13 17:41:55,195 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:55,204 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:55,204 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:55,205 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:55,205 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:55,205 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:55,208 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:55,208 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:55,209 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:55,219 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:55,219 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,220 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:55,220 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:55,221 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-10-13 17:41:55,222 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:55,231 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:55,231 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:55,231 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:55,231 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:55,231 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:55,232 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:55,232 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:55,233 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-13 17:41:55,242 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:55,242 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,243 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:55,244 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-13 17:41:55,244 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-10-13 17:41:55,245 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-10-13 17:41:55,254 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-13 17:41:55,255 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-13 17:41:55,255 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-13 17:41:55,255 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-13 17:41:55,255 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-13 17:41:55,255 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-13 17:41:55,255 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-13 17:41:55,257 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-13 17:41:55,258 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-13 17:41:55,258 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-13 17:41:55,259 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-13 17:41:55,259 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-10-13 17:41:55,260 INFO L229 MonitoredProcess]: Starting monitored process 43 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-10-13 17:41:55,260 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2024-10-13 17:41:55,261 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-13 17:41:55,261 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-13 17:41:55,261 INFO L474 LassoAnalysis]: Proved termination. [2024-10-13 17:41:55,261 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2024-10-13 17:41:55,270 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:55,271 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-13 17:41:55,282 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:55,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:55,336 INFO L255 TraceCheckSpWp]: Trace formula consists of 538 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-10-13 17:41:55,338 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:55,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:55,472 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:55,472 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:55,488 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:55,489 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-13 17:41:55,489 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127 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-10-13 17:41:55,536 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127. 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 460 states and 583 transitions. Complement of second has 15 states. [2024-10-13 17:41:55,536 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:55,537 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-10-13 17:41:55,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-13 17:41:55,537 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 61 letters. Loop has 4 letters. [2024-10-13 17:41:55,537 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:55,537 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:55,544 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:55,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:55,605 INFO L255 TraceCheckSpWp]: Trace formula consists of 538 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-10-13 17:41:55,606 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:55,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:55,739 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:55,739 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:55,754 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:55,755 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-13 17:41:55,755 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127 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-10-13 17:41:55,795 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127. 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 460 states and 583 transitions. Complement of second has 15 states. [2024-10-13 17:41:55,796 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:55,797 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-10-13 17:41:55,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-13 17:41:55,798 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 61 letters. Loop has 4 letters. [2024-10-13 17:41:55,799 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:55,799 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-13 17:41:55,807 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-13 17:41:55,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:55,861 INFO L255 TraceCheckSpWp]: Trace formula consists of 538 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-10-13 17:41:55,863 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:55,978 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:56,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-13 17:41:56,025 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-13 17:41:56,026 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-13 17:41:56,041 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-10-13 17:41:56,042 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-10-13 17:41:56,042 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127 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-10-13 17:41:56,095 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 435 states and 558 transitions. cyclomatic complexity: 127. 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 589 states and 714 transitions. Complement of second has 19 states. [2024-10-13 17:41:56,096 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-10-13 17:41:56,097 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-10-13 17:41:56,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-10-13 17:41:56,097 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 61 letters. Loop has 4 letters. [2024-10-13 17:41:56,100 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:56,100 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 65 letters. Loop has 4 letters. [2024-10-13 17:41:56,101 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:56,102 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 61 letters. Loop has 8 letters. [2024-10-13 17:41:56,102 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-13 17:41:56,102 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 589 states and 714 transitions. [2024-10-13 17:41:56,107 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2024-10-13 17:41:56,111 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 589 states to 450 states and 574 transitions. [2024-10-13 17:41:56,111 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 160 [2024-10-13 17:41:56,112 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 163 [2024-10-13 17:41:56,112 INFO L73 IsDeterministic]: Start isDeterministic. Operand 450 states and 574 transitions. [2024-10-13 17:41:56,112 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-13 17:41:56,112 INFO L218 hiAutomatonCegarLoop]: Abstraction has 450 states and 574 transitions. [2024-10-13 17:41:56,112 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 450 states and 574 transitions. [2024-10-13 17:41:56,119 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 450 to 445. [2024-10-13 17:41:56,120 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 445 states, 276 states have (on average 1.0797101449275361) internal successors, (298), 290 states have internal predecessors, (298), 107 states have call successors, (111), 56 states have call predecessors, (111), 62 states have return successors, (159), 98 states have call predecessors, (159), 94 states have call successors, (159) [2024-10-13 17:41:56,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 445 states to 445 states and 568 transitions. [2024-10-13 17:41:56,122 INFO L240 hiAutomatonCegarLoop]: Abstraction has 445 states and 568 transitions. [2024-10-13 17:41:56,122 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-13 17:41:56,122 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-10-13 17:41:56,122 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=408, Unknown=0, NotChecked=0, Total=552 [2024-10-13 17:41:56,123 INFO L87 Difference]: Start difference. First operand 445 states and 568 transitions. Second operand has 24 states, 23 states have (on average 1.8695652173913044) internal successors, (43), 14 states have internal predecessors, (43), 12 states have call successors, (14), 12 states have call predecessors, (14), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-10-13 17:41:56,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-13 17:41:56,359 INFO L93 Difference]: Finished difference Result 469 states and 569 transitions. [2024-10-13 17:41:56,359 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 469 states and 569 transitions. [2024-10-13 17:41:56,364 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:41:56,364 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 469 states to 0 states and 0 transitions. [2024-10-13 17:41:56,364 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-13 17:41:56,364 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-13 17:41:56,364 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-13 17:41:56,364 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-13 17:41:56,364 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:41:56,364 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:41:56,365 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-10-13 17:41:56,365 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-13 17:41:56,365 INFO L332 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2024-10-13 17:41:56,365 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-13 17:41:56,365 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-13 17:41:56,365 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-13 17:41:56,371 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 13.10 05:41:56 BoogieIcfgContainer [2024-10-13 17:41:56,372 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-13 17:41:56,372 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-13 17:41:56,372 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-13 17:41:56,372 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-13 17:41:56,373 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.10 05:41:47" (3/4) ... [2024-10-13 17:41:56,374 INFO L142 WitnessPrinter]: No result that supports witness generation found [2024-10-13 17:41:56,375 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-13 17:41:56,375 INFO L158 Benchmark]: Toolchain (without parser) took 9789.27ms. Allocated memory was 180.4MB in the beginning and 293.6MB in the end (delta: 113.2MB). Free memory was 150.6MB in the beginning and 205.5MB in the end (delta: -54.9MB). Peak memory consumption was 57.4MB. Max. memory is 16.1GB. [2024-10-13 17:41:56,375 INFO L158 Benchmark]: CDTParser took 0.12ms. Allocated memory is still 180.4MB. Free memory is still 152.8MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:41:56,375 INFO L158 Benchmark]: CACSL2BoogieTranslator took 188.57ms. Allocated memory is still 180.4MB. Free memory was 150.6MB in the beginning and 139.2MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-13 17:41:56,376 INFO L158 Benchmark]: Boogie Procedure Inliner took 20.66ms. Allocated memory is still 180.4MB. Free memory was 139.2MB in the beginning and 137.6MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-13 17:41:56,377 INFO L158 Benchmark]: Boogie Preprocessor took 21.08ms. Allocated memory is still 180.4MB. Free memory was 137.6MB in the beginning and 136.3MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-13 17:41:56,377 INFO L158 Benchmark]: RCFGBuilder took 193.21ms. Allocated memory is still 180.4MB. Free memory was 136.3MB in the beginning and 125.8MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-13 17:41:56,377 INFO L158 Benchmark]: BuchiAutomizer took 9358.03ms. Allocated memory was 180.4MB in the beginning and 293.6MB in the end (delta: 113.2MB). Free memory was 125.8MB in the beginning and 205.5MB in the end (delta: -79.7MB). Peak memory consumption was 34.4MB. Max. memory is 16.1GB. [2024-10-13 17:41:56,377 INFO L158 Benchmark]: Witness Printer took 2.61ms. Allocated memory is still 293.6MB. Free memory is still 205.5MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-13 17:41:56,378 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.12ms. Allocated memory is still 180.4MB. Free memory is still 152.8MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 188.57ms. Allocated memory is still 180.4MB. Free memory was 150.6MB in the beginning and 139.2MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 20.66ms. Allocated memory is still 180.4MB. Free memory was 139.2MB in the beginning and 137.6MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 21.08ms. Allocated memory is still 180.4MB. Free memory was 137.6MB in the beginning and 136.3MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 193.21ms. Allocated memory is still 180.4MB. Free memory was 136.3MB in the beginning and 125.8MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 9358.03ms. Allocated memory was 180.4MB in the beginning and 293.6MB in the end (delta: 113.2MB). Free memory was 125.8MB in the beginning and 205.5MB in the end (delta: -79.7MB). Peak memory consumption was 34.4MB. Max. memory is 16.1GB. * Witness Printer took 2.61ms. Allocated memory is still 293.6MB. Free memory is still 205.5MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (6 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 10 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. 6 modules have a trivial ranking function, the largest among these consists of 24 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 9.3s and 8 iterations. TraceHistogramMax:13. Analysis of lassos took 5.3s. Construction of modules took 0.7s. Büchi inclusion checks took 2.9s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.1s AutomataMinimizationTime, 9 MinimizatonAttempts, 92 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: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 517 SdHoareTripleChecker+Valid, 1.0s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 485 mSDsluCounter, 720 SdHoareTripleChecker+Invalid, 0.8s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 509 mSDsCounter, 308 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1524 IncrementalHoareTripleChecker+Invalid, 1832 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 308 mSolverCounterUnsat, 211 mSDtfsCounter, 1524 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI3 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: 20ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 10 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-10-13 17:41:56,399 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (33)] Ended with exit code 0 [2024-10-13 17:41:56,599 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (28)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:56,799 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (27)] Ended with exit code 0 [2024-10-13 17:41:56,999 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (26)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:57,201 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Forceful destruction successful, exit code 0 [2024-10-13 17:41:57,400 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (24)] Ended with exit code 0 [2024-10-13 17:41:57,601 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-13 17:41:57,802 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE