./Ultimate.py --spec ../../sv-benchmarks/c/properties/termination.prp --file ../../sv-benchmarks/c/recursive/Fibonacci02.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 4fc63b2a Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/config/AutomizerTermination.xml -i ../../sv-benchmarks/c/recursive/Fibonacci02.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 --- Real Ultimate output --- This is Ultimate 0.2.5-dev-4fc63b2 [2024-10-31 22:02:28,345 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-10-31 22:02:28,433 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-10-31 22:02:28,441 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-10-31 22:02:28,442 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-10-31 22:02:28,478 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-10-31 22:02:28,480 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-10-31 22:02:28,481 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-10-31 22:02:28,482 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-10-31 22:02:28,484 INFO L153 SettingsManager]: * Use memory slicer=true [2024-10-31 22:02:28,484 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-10-31 22:02:28,485 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-10-31 22:02:28,485 INFO L153 SettingsManager]: * Use SBE=true [2024-10-31 22:02:28,488 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-10-31 22:02:28,488 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-10-31 22:02:28,489 INFO L153 SettingsManager]: * Use old map elimination=false [2024-10-31 22:02:28,490 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-10-31 22:02:28,491 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-10-31 22:02:28,491 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-10-31 22:02:28,492 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-10-31 22:02:28,492 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-10-31 22:02:28,493 INFO L153 SettingsManager]: * sizeof long=4 [2024-10-31 22:02:28,496 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-10-31 22:02:28,497 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-10-31 22:02:28,497 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-10-31 22:02:28,498 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-10-31 22:02:28,498 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-10-31 22:02:28,498 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-10-31 22:02:28,499 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-10-31 22:02:28,499 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-10-31 22:02:28,499 INFO L153 SettingsManager]: * sizeof long double=12 [2024-10-31 22:02:28,500 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-10-31 22:02:28,500 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-10-31 22:02:28,500 INFO L153 SettingsManager]: * Use constant arrays=true [2024-10-31 22:02:28,501 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-10-31 22:02:28,501 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-10-31 22:02:28,501 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-10-31 22:02:28,502 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-10-31 22:02:28,502 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-10-31 22:02:28,502 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:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/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 -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(F end) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 [2024-10-31 22:02:28,826 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-10-31 22:02:28,857 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-10-31 22:02:28,860 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-10-31 22:02:28,862 INFO L270 PluginConnector]: Initializing CDTParser... [2024-10-31 22:02:28,864 INFO L274 PluginConnector]: CDTParser initialized [2024-10-31 22:02:28,865 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/../../sv-benchmarks/c/recursive/Fibonacci02.c Unable to find full path for "g++" [2024-10-31 22:02:30,894 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-10-31 22:02:31,106 INFO L384 CDTParser]: Found 1 translation units. [2024-10-31 22:02:31,106 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/sv-benchmarks/c/recursive/Fibonacci02.c [2024-10-31 22:02:31,113 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/data/0bc8ecfe1/778f67513d884163a5b0dbaee2fda78b/FLAGd211c4383 [2024-10-31 22:02:31,133 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/data/0bc8ecfe1/778f67513d884163a5b0dbaee2fda78b [2024-10-31 22:02:31,136 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-10-31 22:02:31,138 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-10-31 22:02:31,139 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-10-31 22:02:31,139 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-10-31 22:02:31,147 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-10-31 22:02:31,148 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,149 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@c68aca2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31, skipping insertion in model container [2024-10-31 22:02:31,149 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,169 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-10-31 22:02:31,352 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-31 22:02:31,364 INFO L200 MainTranslator]: Completed pre-run [2024-10-31 22:02:31,376 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-10-31 22:02:31,396 INFO L204 MainTranslator]: Completed translation [2024-10-31 22:02:31,396 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31 WrapperNode [2024-10-31 22:02:31,397 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-10-31 22:02:31,398 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-10-31 22:02:31,398 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-10-31 22:02:31,398 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-10-31 22:02:31,407 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,413 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,428 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2024-10-31 22:02:31,428 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-10-31 22:02:31,429 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-10-31 22:02:31,429 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-10-31 22:02:31,429 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-10-31 22:02:31,442 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,443 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,445 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,456 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-31 22:02:31,457 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,457 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,459 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,463 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,464 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,468 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,470 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-10-31 22:02:31,471 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-10-31 22:02:31,476 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-10-31 22:02:31,476 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-10-31 22:02:31,477 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (1/1) ... [2024-10-31 22:02:31,484 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:31,497 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:31,514 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:31,517 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-10-31 22:02:31,553 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2024-10-31 22:02:31,553 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2024-10-31 22:02:31,553 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-10-31 22:02:31,553 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-10-31 22:02:31,554 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-10-31 22:02:31,554 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-10-31 22:02:31,621 INFO L238 CfgBuilder]: Building ICFG [2024-10-31 22:02:31,624 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-10-31 22:02:31,726 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-10-31 22:02:31,726 INFO L287 CfgBuilder]: Performing block encoding [2024-10-31 22:02:31,737 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-10-31 22:02:31,737 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-10-31 22:02:31,738 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.10 10:02:31 BoogieIcfgContainer [2024-10-31 22:02:31,738 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-10-31 22:02:31,739 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-10-31 22:02:31,739 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-10-31 22:02:31,742 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-10-31 22:02:31,743 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-31 22:02:31,743 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 31.10 10:02:31" (1/3) ... [2024-10-31 22:02:31,744 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@116baaa and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 31.10 10:02:31, skipping insertion in model container [2024-10-31 22:02:31,744 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-31 22:02:31,745 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 31.10 10:02:31" (2/3) ... [2024-10-31 22:02:31,745 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@116baaa and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 31.10 10:02:31, skipping insertion in model container [2024-10-31 22:02:31,745 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-10-31 22:02:31,745 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.10 10:02:31" (3/3) ... [2024-10-31 22:02:31,747 INFO L332 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2024-10-31 22:02:31,804 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-10-31 22:02:31,804 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-10-31 22:02:31,804 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-10-31 22:02:31,804 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-10-31 22:02:31,804 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-10-31 22:02:31,805 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-10-31 22:02:31,805 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-10-31 22:02:31,805 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-10-31 22:02:31,810 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-31 22:02:31,837 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-31 22:02:31,838 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-31 22:02:31,838 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-31 22:02:31,846 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-31 22:02:31,846 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-31 22:02:31,846 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-10-31 22:02:31,847 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-10-31 22:02:31,850 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-31 22:02:31,851 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-31 22:02:31,852 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-31 22:02:31,852 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-10-31 22:02:31,852 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-31 22:02:31,861 INFO L745 eck$LassoCheckResult]: Stem: 17#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 12#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 8#L29true call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 14#$Ultimate##0true [2024-10-31 22:02:31,862 INFO L747 eck$LassoCheckResult]: Loop: 14#$Ultimate##0true ~n := #in~n; 4#L17true assume !(~n < 1); 18#L19true assume !(1 == ~n); 16#L22true call #t~ret4 := fibonacci(~n - 1);< 14#$Ultimate##0true [2024-10-31 22:02:31,871 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:31,871 INFO L85 PathProgramCache]: Analyzing trace with hash 42783, now seen corresponding path program 1 times [2024-10-31 22:02:31,885 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:31,886 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1939938693] [2024-10-31 22:02:31,886 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:31,887 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:32,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:32,021 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-31 22:02:32,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:32,062 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-31 22:02:32,066 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:32,068 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 1 times [2024-10-31 22:02:32,068 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:32,069 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [535760166] [2024-10-31 22:02:32,069 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:32,069 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:32,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:32,082 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-31 22:02:32,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:32,091 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-31 22:02:32,097 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:32,097 INFO L85 PathProgramCache]: Analyzing trace with hash 856297401, now seen corresponding path program 1 times [2024-10-31 22:02:32,097 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:32,098 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1316046094] [2024-10-31 22:02:32,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:32,098 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:32,122 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:32,123 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-31 22:02:32,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:32,141 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-31 22:02:32,307 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:32,308 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:32,308 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:32,308 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:32,309 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-31 22:02:32,309 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,309 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:32,309 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:32,309 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-10-31 22:02:32,309 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:32,310 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:32,325 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,337 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,345 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,350 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,367 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,458 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:32,459 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-31 22:02:32,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,462 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:32,465 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:32,467 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-10-31 22:02:32,469 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:32,469 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:32,492 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-31 22:02:32,492 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-31 22:02:32,512 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:32,513 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,514 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:32,516 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:32,519 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-10-31 22:02:32,520 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:32,520 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:32,534 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-31 22:02:32,535 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-31 22:02:32,553 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-10-31 22:02:32,554 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,554 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:32,557 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:32,559 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-10-31 22:02:32,562 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:32,562 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:32,582 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-31 22:02:32,582 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-31 22:02:32,601 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-10-31 22:02:32,602 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,602 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:32,604 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:32,620 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-10-31 22:02:32,623 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:32,623 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:32,668 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:32,669 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,669 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:32,670 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:32,671 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-10-31 22:02:32,673 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-31 22:02:32,673 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:32,769 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-31 22:02:32,775 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2024-10-31 22:02:32,775 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:32,775 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:32,776 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:32,776 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:32,776 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-31 22:02:32,776 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,776 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:32,776 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:32,776 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2024-10-31 22:02:32,776 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:32,776 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:32,778 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,784 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,787 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,803 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,815 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:32,883 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:32,890 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-31 22:02:32,892 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,893 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:32,895 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:32,897 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-10-31 22:02:32,898 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-31 22:02:32,914 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:32,914 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:32,914 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:32,915 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:32,915 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:32,917 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:32,917 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:32,923 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-31 22:02:32,942 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2024-10-31 22:02:32,943 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,943 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:32,944 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:32,946 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-10-31 22:02:32,947 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-31 22:02:32,961 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:32,962 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:32,962 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:32,962 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:32,962 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:32,963 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:32,963 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:32,965 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-31 22:02:32,980 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:32,980 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:32,980 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:32,981 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:32,982 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-10-31 22:02:32,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-31 22:02:32,994 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:32,994 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:32,995 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:32,995 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:32,995 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:32,995 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:32,996 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:32,998 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-31 22:02:33,010 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:33,010 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:33,010 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:33,012 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:33,013 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-10-31 22:02:33,014 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-31 22:02:33,025 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:33,025 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:33,025 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:33,026 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:33,026 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:33,027 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:33,027 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:33,035 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-31 22:02:33,040 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-31 22:02:33,041 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-31 22:02:33,042 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:33,042 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:33,052 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:33,057 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-10-31 22:02:33,058 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-31 22:02:33,059 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-31 22:02:33,059 INFO L474 LassoAnalysis]: Proved termination. [2024-10-31 22:02:33,059 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-31 22:02:33,074 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:33,078 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-31 22:02:33,107 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:33,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:33,141 INFO L255 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-10-31 22:02:33,145 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:33,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:33,168 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-31 22:02:33,169 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:33,236 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-31 22:02:33,266 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-31 22:02:33,267 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-10-31 22:02:33,384 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 40 states and 53 transitions. Complement of second has 16 states. [2024-10-31 22:02:33,389 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-31 22:02:33,395 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-31 22:02:33,396 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 10 transitions. [2024-10-31 22:02:33,398 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 4 letters. [2024-10-31 22:02:33,400 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:33,400 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 7 letters. Loop has 4 letters. [2024-10-31 22:02:33,400 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:33,401 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 10 transitions. Stem has 3 letters. Loop has 8 letters. [2024-10-31 22:02:33,401 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:33,402 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 40 states and 53 transitions. [2024-10-31 22:02:33,405 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-31 22:02:33,411 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 40 states to 23 states and 31 transitions. [2024-10-31 22:02:33,412 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 15 [2024-10-31 22:02:33,412 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 16 [2024-10-31 22:02:33,413 INFO L73 IsDeterministic]: Start isDeterministic. Operand 23 states and 31 transitions. [2024-10-31 22:02:33,414 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-31 22:02:33,415 INFO L218 hiAutomatonCegarLoop]: Abstraction has 23 states and 31 transitions. [2024-10-31 22:02:33,432 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states and 31 transitions. [2024-10-31 22:02:33,444 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 20. [2024-10-31 22:02:33,445 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-31 22:02:33,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2024-10-31 22:02:33,447 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-31 22:02:33,447 INFO L425 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2024-10-31 22:02:33,447 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-10-31 22:02:33,447 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2024-10-31 22:02:33,448 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-31 22:02:33,448 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-31 22:02:33,448 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-31 22:02:33,449 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:02:33,450 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:02:33,450 INFO L745 eck$LassoCheckResult]: Stem: 130#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 131#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 120#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 132#$Ultimate##0 ~n := #in~n; 126#L17 assume !(~n < 1); 127#L19 assume !(1 == ~n); 119#L22 call #t~ret4 := fibonacci(~n - 1);< 128#$Ultimate##0 ~n := #in~n; 123#L17 assume ~n < 1;#res := 0; 124#fibonacciFINAL assume true; 129#fibonacciEXIT >#31#return; 118#L22-1 [2024-10-31 22:02:33,450 INFO L747 eck$LassoCheckResult]: Loop: 118#L22-1 call #t~ret5 := fibonacci(~n - 2);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume !(~n < 1); 136#L19 assume !(1 == ~n); 121#L22 call #t~ret4 := fibonacci(~n - 1);< 122#$Ultimate##0 ~n := #in~n; 137#L17 assume ~n < 1;#res := 0; 134#fibonacciFINAL assume true; 135#fibonacciEXIT >#31#return; 118#L22-1 [2024-10-31 22:02:33,451 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:33,451 INFO L85 PathProgramCache]: Analyzing trace with hash 2073663503, now seen corresponding path program 1 times [2024-10-31 22:02:33,451 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:33,451 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [810570278] [2024-10-31 22:02:33,451 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:33,452 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:33,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:33,554 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-31 22:02:33,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:33,596 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-31 22:02:33,597 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:02:33,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [810570278] [2024-10-31 22:02:33,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [810570278] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 22:02:33,598 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-31 22:02:33,598 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-31 22:02:33,598 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1146851081] [2024-10-31 22:02:33,599 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 22:02:33,601 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-31 22:02:33,601 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:33,602 INFO L85 PathProgramCache]: Analyzing trace with hash 1606275375, now seen corresponding path program 1 times [2024-10-31 22:02:33,602 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:33,602 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2034116283] [2024-10-31 22:02:33,602 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:33,602 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:33,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:33,685 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2024-10-31 22:02:33,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:33,729 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-31 22:02:33,729 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:02:33,729 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2034116283] [2024-10-31 22:02:33,730 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2034116283] provided 1 perfect and 0 imperfect interpolant sequences [2024-10-31 22:02:33,730 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-10-31 22:02:33,730 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-10-31 22:02:33,730 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [518990753] [2024-10-31 22:02:33,730 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-10-31 22:02:33,731 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-10-31 22:02:33,731 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:02:33,733 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-10-31 22:02:33,734 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-10-31 22:02:33,735 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-31 22:02:33,852 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:02:33,854 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2024-10-31 22:02:33,854 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2024-10-31 22:02:33,856 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-31 22:02:33,859 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2024-10-31 22:02:33,860 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2024-10-31 22:02:33,860 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2024-10-31 22:02:33,860 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2024-10-31 22:02:33,860 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-31 22:02:33,860 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-31 22:02:33,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2024-10-31 22:02:33,864 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2024-10-31 22:02:33,866 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-31 22:02:33,867 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2024-10-31 22:02:33,867 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-31 22:02:33,868 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-10-31 22:02:33,869 INFO L425 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2024-10-31 22:02:33,869 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-10-31 22:02:33,869 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2024-10-31 22:02:33,870 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2024-10-31 22:02:33,870 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-31 22:02:33,870 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-31 22:02:33,871 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:02:33,871 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2024-10-31 22:02:33,872 INFO L745 eck$LassoCheckResult]: Stem: 202#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 203#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 191#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 201#$Ultimate##0 ~n := #in~n; 196#L17 assume !(~n < 1); 197#L19 assume !(1 == ~n); 192#L22 call #t~ret4 := fibonacci(~n - 1);< 198#$Ultimate##0 ~n := #in~n; 194#L17 assume !(~n < 1); 195#L19 assume 1 == ~n;#res := 1; 205#fibonacciFINAL assume true; 208#fibonacciEXIT >#31#return; 189#L22-1 [2024-10-31 22:02:33,874 INFO L747 eck$LassoCheckResult]: Loop: 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume !(1 == ~n); 190#L22 call #t~ret4 := fibonacci(~n - 1);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume !(~n < 1); 209#L19 assume 1 == ~n;#res := 1; 210#fibonacciFINAL assume true; 207#fibonacciEXIT >#31#return; 189#L22-1 call #t~ret5 := fibonacci(~n - 2);< 193#$Ultimate##0 ~n := #in~n; 211#L17 assume ~n < 1;#res := 0; 212#fibonacciFINAL assume true; 199#fibonacciEXIT >#33#return; 200#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 204#fibonacciFINAL assume true; 206#fibonacciEXIT >#31#return; 189#L22-1 [2024-10-31 22:02:33,874 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:33,875 INFO L85 PathProgramCache]: Analyzing trace with hash -140916419, now seen corresponding path program 1 times [2024-10-31 22:02:33,875 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:33,875 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1966019431] [2024-10-31 22:02:33,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:33,876 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:33,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:33,982 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2024-10-31 22:02:33,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:34,049 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-31 22:02:34,050 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:02:34,050 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1966019431] [2024-10-31 22:02:34,051 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1966019431] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 22:02:34,051 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1731232191] [2024-10-31 22:02:34,051 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:34,052 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:02:34,052 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:34,054 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:02:34,055 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2024-10-31 22:02:34,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:34,101 INFO L255 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-31 22:02:34,103 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:34,153 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-31 22:02:34,153 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 22:02:34,312 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-31 22:02:34,312 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1731232191] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 22:02:34,312 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 22:02:34,312 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2024-10-31 22:02:34,313 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1066966753] [2024-10-31 22:02:34,313 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 22:02:34,313 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-31 22:02:34,314 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:34,314 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 1 times [2024-10-31 22:02:34,314 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:34,314 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [386684198] [2024-10-31 22:02:34,314 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:34,315 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:34,340 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:34,340 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-31 22:02:34,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:34,359 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-31 22:02:34,379 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:34,752 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:34,753 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:34,753 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:34,753 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:34,753 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-31 22:02:34,753 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:34,754 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:34,754 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:34,754 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-10-31 22:02:34,754 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:34,754 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:34,755 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:34,760 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:34,767 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:34,770 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:34,774 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:34,836 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:34,836 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-31 22:02:34,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:34,837 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:34,839 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:34,841 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-10-31 22:02:34,842 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:34,842 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:34,861 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-31 22:02:34,861 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=3} Honda state: {fibonacci_#in~n=3} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-31 22:02:34,880 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-10-31 22:02:34,881 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:34,882 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:34,884 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:34,886 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-10-31 22:02:34,887 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:34,888 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:34,919 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:34,920 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:34,920 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:34,922 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:34,924 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-10-31 22:02:34,925 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-31 22:02:34,925 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:34,943 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-31 22:02:34,962 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:34,962 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:34,963 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:34,963 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:34,963 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:34,963 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-31 22:02:34,963 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:34,963 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:34,963 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:34,963 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2024-10-31 22:02:34,964 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:34,964 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:34,965 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:34,977 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:34,985 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:34,991 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:34,995 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:35,054 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:35,054 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-31 22:02:35,054 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:35,055 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:35,057 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:35,059 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-10-31 22:02:35,060 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-31 22:02:35,071 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:35,071 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:35,071 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:35,071 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:35,072 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:35,073 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:35,073 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:35,076 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-31 22:02:35,079 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-31 22:02:35,079 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-31 22:02:35,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:35,080 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:35,081 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:35,082 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-10-31 22:02:35,083 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-31 22:02:35,083 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-31 22:02:35,083 INFO L474 LassoAnalysis]: Proved termination. [2024-10-31 22:02:35,083 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-31 22:02:35,096 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-10-31 22:02:35,097 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-31 22:02:35,130 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:35,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:35,159 INFO L255 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-10-31 22:02:35,160 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:35,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:35,323 INFO L255 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-10-31 22:02:35,326 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:35,570 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-31 22:02:35,571 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-31 22:02:35,572 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-31 22:02:35,910 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Result 152 states and 210 transitions. Complement of second has 54 states. [2024-10-31 22:02:35,912 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-31 22:02:35,913 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2024-10-31 22:02:35,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 40 transitions. [2024-10-31 22:02:35,915 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 22 letters. [2024-10-31 22:02:35,916 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:35,916 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 34 letters. Loop has 22 letters. [2024-10-31 22:02:35,916 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:35,916 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 11 states and 40 transitions. Stem has 12 letters. Loop has 44 letters. [2024-10-31 22:02:35,919 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:35,920 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 152 states and 210 transitions. [2024-10-31 22:02:35,928 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-31 22:02:35,934 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 152 states to 125 states and 179 transitions. [2024-10-31 22:02:35,934 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-10-31 22:02:35,935 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-10-31 22:02:35,935 INFO L73 IsDeterministic]: Start isDeterministic. Operand 125 states and 179 transitions. [2024-10-31 22:02:35,935 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-31 22:02:35,936 INFO L218 hiAutomatonCegarLoop]: Abstraction has 125 states and 179 transitions. [2024-10-31 22:02:35,936 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states and 179 transitions. [2024-10-31 22:02:35,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 106. [2024-10-31 22:02:35,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.2272727272727273) internal successors, (81), 70 states have internal predecessors, (81), 25 states have call successors, (26), 13 states have call predecessors, (26), 15 states have return successors, (35), 22 states have call predecessors, (35), 23 states have call successors, (35) [2024-10-31 22:02:35,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 142 transitions. [2024-10-31 22:02:35,951 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 142 transitions. [2024-10-31 22:02:35,951 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:02:35,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-10-31 22:02:35,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2024-10-31 22:02:35,952 INFO L87 Difference]: Start difference. First operand 106 states and 142 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2024-10-31 22:02:36,135 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:02:36,136 INFO L93 Difference]: Finished difference Result 135 states and 183 transitions. [2024-10-31 22:02:36,136 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2024-10-31 22:02:36,140 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-31 22:02:36,144 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 130 states and 178 transitions. [2024-10-31 22:02:36,144 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 81 [2024-10-31 22:02:36,145 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 81 [2024-10-31 22:02:36,145 INFO L73 IsDeterministic]: Start isDeterministic. Operand 130 states and 178 transitions. [2024-10-31 22:02:36,145 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-31 22:02:36,146 INFO L218 hiAutomatonCegarLoop]: Abstraction has 130 states and 178 transitions. [2024-10-31 22:02:36,146 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states and 178 transitions. [2024-10-31 22:02:36,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2024-10-31 22:02:36,157 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 74 states have (on average 1.2027027027027026) internal successors, (89), 78 states have internal predecessors, (89), 28 states have call successors, (29), 15 states have call predecessors, (29), 16 states have return successors, (39), 24 states have call predecessors, (39), 26 states have call successors, (39) [2024-10-31 22:02:36,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 157 transitions. [2024-10-31 22:02:36,163 INFO L240 hiAutomatonCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-10-31 22:02:36,164 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-10-31 22:02:36,164 INFO L425 stractBuchiCegarLoop]: Abstraction has 118 states and 157 transitions. [2024-10-31 22:02:36,164 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-10-31 22:02:36,165 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 118 states and 157 transitions. [2024-10-31 22:02:36,167 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2024-10-31 22:02:36,171 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-31 22:02:36,171 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-31 22:02:36,172 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:02:36,172 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2024-10-31 22:02:36,172 INFO L745 eck$LassoCheckResult]: Stem: 905#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 906#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 880#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 907#$Ultimate##0 ~n := #in~n; 887#L17 assume !(~n < 1); 888#L19 assume !(1 == ~n); 891#L22 call #t~ret4 := fibonacci(~n - 1);< 892#$Ultimate##0 ~n := #in~n; 949#L17 assume !(~n < 1); 948#L19 assume !(1 == ~n); 937#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 946#L17 assume !(~n < 1); 944#L19 assume !(1 == ~n); 938#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 946#L17 assume !(~n < 1); 944#L19 assume !(1 == ~n); 938#L22 call #t~ret4 := fibonacci(~n - 1);< 942#$Ultimate##0 ~n := #in~n; 947#L17 assume !(~n < 1); 945#L19 assume 1 == ~n;#res := 1; 943#fibonacciFINAL assume true; 941#fibonacciEXIT >#31#return; 883#L22-1 call #t~ret5 := fibonacci(~n - 2);< 940#$Ultimate##0 ~n := #in~n; 885#L17 assume ~n < 1;#res := 0; 886#fibonacciFINAL assume true; 992#fibonacciEXIT >#33#return; 990#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 987#fibonacciFINAL assume true; 980#fibonacciEXIT >#31#return; 913#L22-1 [2024-10-31 22:02:36,173 INFO L747 eck$LassoCheckResult]: Loop: 913#L22-1 call #t~ret5 := fibonacci(~n - 2);< 890#$Ultimate##0 ~n := #in~n; 986#L17 assume !(~n < 1); 911#L19 assume !(1 == ~n); 914#L22 call #t~ret4 := fibonacci(~n - 1);< 890#$Ultimate##0 ~n := #in~n; 986#L17 assume !(~n < 1); 911#L19 assume 1 == ~n;#res := 1; 915#fibonacciFINAL assume true; 916#fibonacciEXIT >#31#return; 913#L22-1 [2024-10-31 22:02:36,173 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:36,175 INFO L85 PathProgramCache]: Analyzing trace with hash 3324437, now seen corresponding path program 1 times [2024-10-31 22:02:36,175 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:36,175 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1036492] [2024-10-31 22:02:36,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:36,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:36,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:36,385 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-10-31 22:02:36,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:36,490 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-10-31 22:02:36,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:36,546 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-10-31 22:02:36,560 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2024-10-31 22:02:36,562 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:36,573 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-31 22:02:36,573 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:02:36,573 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1036492] [2024-10-31 22:02:36,574 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1036492] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 22:02:36,574 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1031854037] [2024-10-31 22:02:36,575 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:36,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:02:36,576 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:36,579 INFO L229 MonitoredProcess]: Starting monitored process 18 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:02:36,581 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2024-10-31 22:02:36,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:36,635 INFO L255 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-10-31 22:02:36,637 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:36,742 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-31 22:02:36,743 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 22:02:37,128 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-31 22:02:37,128 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1031854037] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 22:02:37,128 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 22:02:37,128 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2024-10-31 22:02:37,129 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [595814925] [2024-10-31 22:02:37,129 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 22:02:37,129 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-31 22:02:37,130 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:37,130 INFO L85 PathProgramCache]: Analyzing trace with hash -1745046499, now seen corresponding path program 1 times [2024-10-31 22:02:37,130 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:37,130 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1122680423] [2024-10-31 22:02:37,131 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:37,131 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:37,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:37,135 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-31 22:02:37,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:37,140 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-31 22:02:37,268 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:37,269 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:37,269 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:37,269 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:37,269 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-31 22:02:37,269 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:37,269 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:37,269 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:37,270 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-10-31 22:02:37,270 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:37,270 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:37,271 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,276 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,283 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,286 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,288 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,336 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:37,336 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-31 22:02:37,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:37,336 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:37,339 INFO L229 MonitoredProcess]: Starting monitored process 19 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:37,341 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-10-31 22:02:37,342 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:37,342 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:37,359 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-31 22:02:37,359 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=2} Honda state: {fibonacci_#in~n=2} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-31 22:02:37,377 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:37,378 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:37,378 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:37,380 INFO L229 MonitoredProcess]: Starting monitored process 20 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:37,381 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-10-31 22:02:37,383 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:37,383 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:37,418 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-10-31 22:02:37,419 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:37,419 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:37,421 INFO L229 MonitoredProcess]: Starting monitored process 21 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:37,423 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-10-31 22:02:37,424 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-31 22:02:37,424 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:37,445 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-31 22:02:37,463 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2024-10-31 22:02:37,463 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:37,464 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:37,464 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:37,464 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:37,464 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-31 22:02:37,464 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:37,464 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:37,464 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:37,465 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2024-10-31 22:02:37,465 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:37,465 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:37,466 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,473 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,479 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,483 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,485 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:37,533 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:37,533 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-31 22:02:37,533 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:37,533 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:37,535 INFO L229 MonitoredProcess]: Starting monitored process 22 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:37,537 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-10-31 22:02:37,538 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-31 22:02:37,552 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:37,552 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:37,552 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:37,553 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:37,553 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:37,554 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:37,554 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:37,559 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-31 22:02:37,577 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2024-10-31 22:02:37,578 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:37,578 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:37,580 INFO L229 MonitoredProcess]: Starting monitored process 23 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:37,581 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-10-31 22:02:37,582 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-31 22:02:37,597 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:37,597 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:37,597 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:37,597 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:37,597 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:37,599 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:37,599 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:37,602 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-31 22:02:37,606 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-31 22:02:37,606 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-31 22:02:37,606 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:37,607 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:37,609 INFO L229 MonitoredProcess]: Starting monitored process 24 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:37,610 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-10-31 22:02:37,611 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-31 22:02:37,611 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-31 22:02:37,612 INFO L474 LassoAnalysis]: Proved termination. [2024-10-31 22:02:37,612 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-31 22:02:37,626 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:37,628 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-31 22:02:37,639 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:37,695 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:37,697 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-31 22:02:37,699 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:37,978 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:37,979 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-31 22:02:37,980 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:38,076 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-31 22:02:38,077 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-31 22:02:38,078 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-31 22:02:38,340 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 230 states and 321 transitions. Complement of second has 37 states. [2024-10-31 22:02:38,347 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:38,348 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-31 22:02:38,349 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-31 22:02:38,350 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 40 transitions. [2024-10-31 22:02:38,350 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 40 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-31 22:02:38,351 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:38,352 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-31 22:02:38,368 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:38,413 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:38,415 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-31 22:02:38,417 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:38,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:38,679 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-31 22:02:38,680 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:38,778 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-31 22:02:38,779 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-31 22:02:38,784 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-31 22:02:39,076 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 300 states and 408 transitions. Complement of second has 29 states. [2024-10-31 22:02:39,077 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-10-31 22:02:39,077 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-31 22:02:39,078 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 24 transitions. [2024-10-31 22:02:39,078 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-31 22:02:39,078 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:39,079 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-31 22:02:39,093 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:39,136 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:39,138 INFO L255 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-10-31 22:02:39,140 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:39,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:39,388 INFO L255 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-10-31 22:02:39,389 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:39,486 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-31 22:02:39,487 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-10-31 22:02:39,487 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-31 22:02:39,788 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 118 states and 157 transitions. cyclomatic complexity: 44. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 808 states and 1112 transitions. Complement of second has 135 states. [2024-10-31 22:02:39,789 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-31 22:02:39,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2024-10-31 22:02:39,792 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 45 transitions. [2024-10-31 22:02:39,792 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 10 letters. [2024-10-31 22:02:39,793 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:39,793 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 42 letters. Loop has 10 letters. [2024-10-31 22:02:39,793 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:39,793 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 45 transitions. Stem has 32 letters. Loop has 20 letters. [2024-10-31 22:02:39,794 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:39,794 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 808 states and 1112 transitions. [2024-10-31 22:02:39,838 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2024-10-31 22:02:39,860 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 808 states to 427 states and 634 transitions. [2024-10-31 22:02:39,860 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 166 [2024-10-31 22:02:39,863 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 186 [2024-10-31 22:02:39,864 INFO L73 IsDeterministic]: Start isDeterministic. Operand 427 states and 634 transitions. [2024-10-31 22:02:39,864 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-31 22:02:39,864 INFO L218 hiAutomatonCegarLoop]: Abstraction has 427 states and 634 transitions. [2024-10-31 22:02:39,865 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 427 states and 634 transitions. [2024-10-31 22:02:39,916 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 427 to 352. [2024-10-31 22:02:39,917 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 352 states, 221 states have (on average 1.1990950226244343) internal successors, (265), 235 states have internal predecessors, (265), 75 states have call successors, (84), 46 states have call predecessors, (84), 56 states have return successors, (130), 70 states have call predecessors, (130), 71 states have call successors, (130) [2024-10-31 22:02:39,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 352 states to 352 states and 479 transitions. [2024-10-31 22:02:39,923 INFO L240 hiAutomatonCegarLoop]: Abstraction has 352 states and 479 transitions. [2024-10-31 22:02:39,925 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:02:39,925 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2024-10-31 22:02:39,926 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2024-10-31 22:02:39,926 INFO L87 Difference]: Start difference. First operand 352 states and 479 transitions. Second operand has 23 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 15 states have internal predecessors, (41), 13 states have call successors, (13), 7 states have call predecessors, (13), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2024-10-31 22:02:40,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:02:40,357 INFO L93 Difference]: Finished difference Result 707 states and 1054 transitions. [2024-10-31 22:02:40,357 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 707 states and 1054 transitions. [2024-10-31 22:02:40,370 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-31 22:02:40,386 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 707 states to 676 states and 1009 transitions. [2024-10-31 22:02:40,387 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 296 [2024-10-31 22:02:40,388 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 299 [2024-10-31 22:02:40,389 INFO L73 IsDeterministic]: Start isDeterministic. Operand 676 states and 1009 transitions. [2024-10-31 22:02:40,389 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-31 22:02:40,389 INFO L218 hiAutomatonCegarLoop]: Abstraction has 676 states and 1009 transitions. [2024-10-31 22:02:40,390 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 676 states and 1009 transitions. [2024-10-31 22:02:40,416 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 676 to 628. [2024-10-31 22:02:40,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 628 states, 383 states have (on average 1.1618798955613576) internal successors, (445), 406 states have internal predecessors, (445), 151 states have call successors, (165), 76 states have call predecessors, (165), 94 states have return successors, (326), 145 states have call predecessors, (326), 141 states have call successors, (326) [2024-10-31 22:02:40,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 628 states to 628 states and 936 transitions. [2024-10-31 22:02:40,425 INFO L240 hiAutomatonCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-10-31 22:02:40,426 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-31 22:02:40,426 INFO L425 stractBuchiCegarLoop]: Abstraction has 628 states and 936 transitions. [2024-10-31 22:02:40,426 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-10-31 22:02:40,427 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 628 states and 936 transitions. [2024-10-31 22:02:40,432 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-31 22:02:40,432 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-31 22:02:40,432 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-31 22:02:40,433 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:02:40,433 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-31 22:02:40,434 INFO L745 eck$LassoCheckResult]: Stem: 4310#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 4311#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 4312#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 4313#$Ultimate##0 ~n := #in~n; 4329#L17 assume !(~n < 1); 4398#L19 assume !(1 == ~n); 4394#L22 call #t~ret4 := fibonacci(~n - 1);< 4395#$Ultimate##0 ~n := #in~n; 4427#L17 assume !(~n < 1); 4414#L19 assume !(1 == ~n); 4407#L22 call #t~ret4 := fibonacci(~n - 1);< 4410#$Ultimate##0 ~n := #in~n; 4421#L17 assume !(~n < 1); 4412#L19 assume !(1 == ~n); 4402#L22 call #t~ret4 := fibonacci(~n - 1);< 4408#$Ultimate##0 ~n := #in~n; 4431#L17 assume !(~n < 1); 4430#L19 assume !(1 == ~n); 4424#L22 call #t~ret4 := fibonacci(~n - 1);< 4429#$Ultimate##0 ~n := #in~n; 4448#L17 assume !(~n < 1); 4447#L19 assume !(1 == ~n); 4416#L22 call #t~ret4 := fibonacci(~n - 1);< 4446#$Ultimate##0 ~n := #in~n; 4461#L17 assume !(~n < 1); 4460#L19 assume !(1 == ~n); 4344#L22 call #t~ret4 := fibonacci(~n - 1);< 4342#$Ultimate##0 ~n := #in~n; 4345#L17 assume !(~n < 1); 4464#L19 assume !(1 == ~n); 4343#L22 call #t~ret4 := fibonacci(~n - 1);< 4342#$Ultimate##0 ~n := #in~n; 4346#L17 assume !(~n < 1); 4536#L19 assume 1 == ~n;#res := 1; 4535#fibonacciFINAL assume true; 4530#fibonacciEXIT >#31#return; 4514#L22-1 call #t~ret5 := fibonacci(~n - 2);< 4528#$Ultimate##0 ~n := #in~n; 4777#L17 assume !(~n < 1); 4655#L19 assume !(1 == ~n); 4656#L22 call #t~ret4 := fibonacci(~n - 1);< 4707#$Ultimate##0 ~n := #in~n; 4821#L17 assume !(~n < 1); 4818#L19 assume !(1 == ~n); 4819#L22 call #t~ret4 := fibonacci(~n - 1);< 4828#$Ultimate##0 [2024-10-31 22:02:40,434 INFO L747 eck$LassoCheckResult]: Loop: 4828#$Ultimate##0 ~n := #in~n; 4850#L17 assume !(~n < 1); 4847#L19 assume !(1 == ~n); 4827#L22 call #t~ret4 := fibonacci(~n - 1);< 4828#$Ultimate##0 [2024-10-31 22:02:40,434 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:40,434 INFO L85 PathProgramCache]: Analyzing trace with hash 1729544275, now seen corresponding path program 1 times [2024-10-31 22:02:40,434 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:40,435 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [417547651] [2024-10-31 22:02:40,435 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:40,435 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:40,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:40,714 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2024-10-31 22:02:40,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:40,752 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-31 22:02:40,753 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:02:40,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [417547651] [2024-10-31 22:02:40,753 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [417547651] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 22:02:40,753 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1912119506] [2024-10-31 22:02:40,753 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:40,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:02:40,754 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:40,756 INFO L229 MonitoredProcess]: Starting monitored process 25 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:02:40,759 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Waiting until timeout for monitored process [2024-10-31 22:02:40,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:40,810 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-10-31 22:02:40,813 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:40,914 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-31 22:02:40,915 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 22:02:41,195 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-10-31 22:02:41,196 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1912119506] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 22:02:41,196 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 22:02:41,196 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 21 [2024-10-31 22:02:41,197 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2056494545] [2024-10-31 22:02:41,197 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 22:02:41,197 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-31 22:02:41,197 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:41,199 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 2 times [2024-10-31 22:02:41,199 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:41,200 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1354605141] [2024-10-31 22:02:41,200 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:41,200 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:41,202 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:41,203 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-31 22:02:41,204 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:41,207 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-31 22:02:41,248 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:41,248 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:41,249 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:41,249 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:41,249 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-31 22:02:41,249 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,249 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:41,249 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:41,249 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-10-31 22:02:41,249 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:41,249 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:41,250 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,254 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,257 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,265 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,268 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,306 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:41,306 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-31 22:02:41,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,307 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:41,309 INFO L229 MonitoredProcess]: Starting monitored process 26 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:41,312 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:41,312 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:41,313 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-10-31 22:02:41,327 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-31 22:02:41,327 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-31 22:02:41,340 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:41,340 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,340 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:41,341 INFO L229 MonitoredProcess]: Starting monitored process 27 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:41,342 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-10-31 22:02:41,343 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:41,343 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:41,355 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-31 22:02:41,355 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-31 22:02:41,367 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2024-10-31 22:02:41,368 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,368 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:41,369 INFO L229 MonitoredProcess]: Starting monitored process 28 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:41,370 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-10-31 22:02:41,371 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:41,371 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:41,394 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:41,394 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,394 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:41,395 INFO L229 MonitoredProcess]: Starting monitored process 29 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:41,396 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-10-31 22:02:41,397 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-31 22:02:41,397 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:41,427 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-31 22:02:41,430 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:41,431 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:41,431 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:41,431 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:41,431 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:41,431 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-31 22:02:41,431 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,431 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:41,431 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:41,432 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2024-10-31 22:02:41,432 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:41,432 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:41,432 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,438 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,441 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,450 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,453 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:41,488 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:41,489 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-31 22:02:41,489 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,489 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:41,491 INFO L229 MonitoredProcess]: Starting monitored process 30 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:41,493 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-10-31 22:02:41,494 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-31 22:02:41,508 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:41,508 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:41,509 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:41,509 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:41,509 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:41,512 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:41,512 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:41,517 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-31 22:02:41,534 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:41,535 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,535 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:41,537 INFO L229 MonitoredProcess]: Starting monitored process 31 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:41,538 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-10-31 22:02:41,539 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-31 22:02:41,554 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:41,554 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:41,554 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:41,554 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:41,554 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:41,555 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:41,555 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:41,559 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-31 22:02:41,576 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Ended with exit code 0 [2024-10-31 22:02:41,577 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,577 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:41,579 INFO L229 MonitoredProcess]: Starting monitored process 32 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:41,581 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-10-31 22:02:41,582 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-31 22:02:41,596 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:41,596 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:41,596 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:41,596 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:41,597 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:41,597 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:41,598 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:41,604 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-31 22:02:41,608 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-10-31 22:02:41,608 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-10-31 22:02:41,609 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:41,609 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:41,611 INFO L229 MonitoredProcess]: Starting monitored process 33 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:41,613 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-10-31 22:02:41,614 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-31 22:02:41,614 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-31 22:02:41,614 INFO L474 LassoAnalysis]: Proved termination. [2024-10-31 22:02:41,614 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2024-10-31 22:02:41,629 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:41,630 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-31 22:02:41,641 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:41,715 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:41,718 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-31 22:02:41,720 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:41,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:41,845 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-31 22:02:41,846 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:41,878 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-31 22:02:41,879 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-31 22:02:41,879 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:41,963 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 650 states and 958 transitions. Complement of second has 15 states. [2024-10-31 22:02:41,964 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-31 22:02:41,964 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:41,965 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-31 22:02:41,965 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-31 22:02:41,965 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:41,965 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-31 22:02:41,979 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:42,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:42,053 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-31 22:02:42,055 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:42,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:42,180 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-31 22:02:42,181 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:42,210 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-31 22:02:42,210 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-31 22:02:42,211 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:42,285 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 650 states and 958 transitions. Complement of second has 15 states. [2024-10-31 22:02:42,285 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-31 22:02:42,286 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:42,286 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2024-10-31 22:02:42,286 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-31 22:02:42,287 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:42,287 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-31 22:02:42,299 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:42,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:42,372 INFO L255 TraceCheckSpWp]: Trace formula consists of 421 conjuncts, 24 conjuncts are in the unsatisfiable core [2024-10-31 22:02:42,375 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:42,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:42,509 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-31 22:02:42,510 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:42,544 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-31 22:02:42,545 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-31 22:02:42,546 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:42,667 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Ended with exit code 0 [2024-10-31 22:02:42,680 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 628 states and 936 transitions. cyclomatic complexity: 318. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 839 states and 1163 transitions. Complement of second has 19 states. [2024-10-31 22:02:42,681 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-31 22:02:42,682 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:42,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 21 transitions. [2024-10-31 22:02:42,683 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2024-10-31 22:02:42,683 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:42,683 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2024-10-31 22:02:42,684 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:42,684 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2024-10-31 22:02:42,684 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:42,684 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 839 states and 1163 transitions. [2024-10-31 22:02:42,698 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-31 22:02:42,709 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 839 states to 684 states and 996 transitions. [2024-10-31 22:02:42,709 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 241 [2024-10-31 22:02:42,710 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 250 [2024-10-31 22:02:42,710 INFO L73 IsDeterministic]: Start isDeterministic. Operand 684 states and 996 transitions. [2024-10-31 22:02:42,710 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-31 22:02:42,710 INFO L218 hiAutomatonCegarLoop]: Abstraction has 684 states and 996 transitions. [2024-10-31 22:02:42,711 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 684 states and 996 transitions. [2024-10-31 22:02:42,738 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 684 to 654. [2024-10-31 22:02:42,740 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 654 states, 407 states have (on average 1.1523341523341524) internal successors, (469), 432 states have internal predecessors, (469), 151 states have call successors, (165), 76 states have call predecessors, (165), 96 states have return successors, (326), 145 states have call predecessors, (326), 141 states have call successors, (326) [2024-10-31 22:02:42,747 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 654 states to 654 states and 960 transitions. [2024-10-31 22:02:42,748 INFO L240 hiAutomatonCegarLoop]: Abstraction has 654 states and 960 transitions. [2024-10-31 22:02:42,748 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:02:42,748 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-31 22:02:42,748 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2024-10-31 22:02:42,749 INFO L87 Difference]: Start difference. First operand 654 states and 960 transitions. Second operand has 21 states, 20 states have (on average 1.8) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (10), 9 states have call predecessors, (10), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:43,168 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:02:43,168 INFO L93 Difference]: Finished difference Result 781 states and 1180 transitions. [2024-10-31 22:02:43,169 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 781 states and 1180 transitions. [2024-10-31 22:02:43,179 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-31 22:02:43,191 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 781 states to 760 states and 1148 transitions. [2024-10-31 22:02:43,191 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 279 [2024-10-31 22:02:43,192 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 282 [2024-10-31 22:02:43,192 INFO L73 IsDeterministic]: Start isDeterministic. Operand 760 states and 1148 transitions. [2024-10-31 22:02:43,193 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-31 22:02:43,193 INFO L218 hiAutomatonCegarLoop]: Abstraction has 760 states and 1148 transitions. [2024-10-31 22:02:43,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 760 states and 1148 transitions. [2024-10-31 22:02:43,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 760 to 702. [2024-10-31 22:02:43,217 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 702 states, 437 states have (on average 1.1464530892448512) internal successors, (501), 462 states have internal predecessors, (501), 169 states have call successors, (185), 86 states have call predecessors, (185), 96 states have return successors, (336), 153 states have call predecessors, (336), 159 states have call successors, (336) [2024-10-31 22:02:43,222 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 702 states to 702 states and 1022 transitions. [2024-10-31 22:02:43,222 INFO L240 hiAutomatonCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-10-31 22:02:43,223 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-10-31 22:02:43,223 INFO L425 stractBuchiCegarLoop]: Abstraction has 702 states and 1022 transitions. [2024-10-31 22:02:43,223 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-10-31 22:02:43,223 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 702 states and 1022 transitions. [2024-10-31 22:02:43,230 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-31 22:02:43,230 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-10-31 22:02:43,230 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-10-31 22:02:43,233 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1, 1] [2024-10-31 22:02:43,234 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-10-31 22:02:43,234 INFO L745 eck$LassoCheckResult]: Stem: 9342#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 9343#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 9; 9344#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 9345#$Ultimate##0 ~n := #in~n; 9513#L17 assume !(~n < 1); 9512#L19 assume !(1 == ~n); 9490#L22 call #t~ret4 := fibonacci(~n - 1);< 9491#$Ultimate##0 ~n := #in~n; 9555#L17 assume !(~n < 1); 9553#L19 assume !(1 == ~n); 9545#L22 call #t~ret4 := fibonacci(~n - 1);< 9551#$Ultimate##0 ~n := #in~n; 9550#L17 assume !(~n < 1); 9547#L19 assume !(1 == ~n); 9509#L22 call #t~ret4 := fibonacci(~n - 1);< 9546#$Ultimate##0 ~n := #in~n; 9661#L17 assume !(~n < 1); 9657#L19 assume !(1 == ~n); 9653#L22 call #t~ret4 := fibonacci(~n - 1);< 9655#$Ultimate##0 ~n := #in~n; 9680#L17 assume !(~n < 1); 9679#L19 assume !(1 == ~n); 9319#L22 call #t~ret4 := fibonacci(~n - 1);< 9678#$Ultimate##0 ~n := #in~n; 9723#L17 assume !(~n < 1); 9721#L19 assume !(1 == ~n); 9674#L22 call #t~ret4 := fibonacci(~n - 1);< 9698#$Ultimate##0 ~n := #in~n; 9792#L17 assume !(~n < 1); 9777#L19 assume !(1 == ~n); 9694#L22 call #t~ret4 := fibonacci(~n - 1);< 9761#$Ultimate##0 ~n := #in~n; 9819#L17 assume !(~n < 1); 9815#L19 assume !(1 == ~n); 9693#L22 call #t~ret4 := fibonacci(~n - 1);< 9761#$Ultimate##0 ~n := #in~n; 9822#L17 assume !(~n < 1); 9820#L19 assume 1 == ~n;#res := 1; 9816#fibonacciFINAL assume true; 9808#fibonacciEXIT >#31#return; 9715#L22-1 call #t~ret5 := fibonacci(~n - 2);< 9726#$Ultimate##0 ~n := #in~n; 9846#L17 assume !(~n < 1); 9909#L19 assume !(1 == ~n); 9368#L22 call #t~ret4 := fibonacci(~n - 1);< 9374#$Ultimate##0 ~n := #in~n; 9375#L17 assume !(~n < 1); 9973#L19 assume !(1 == ~n); 9354#L22 call #t~ret4 := fibonacci(~n - 1);< 9376#$Ultimate##0 ~n := #in~n; 9377#L17 assume !(~n < 1); 9972#L19 assume !(1 == ~n); 9355#L22 [2024-10-31 22:02:43,234 INFO L747 eck$LassoCheckResult]: Loop: 9355#L22 call #t~ret4 := fibonacci(~n - 1);< 9376#$Ultimate##0 ~n := #in~n; 9377#L17 assume !(~n < 1); 9972#L19 assume !(1 == ~n); 9355#L22 [2024-10-31 22:02:43,235 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:43,235 INFO L85 PathProgramCache]: Analyzing trace with hash 1537328375, now seen corresponding path program 2 times [2024-10-31 22:02:43,235 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:43,235 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [287281369] [2024-10-31 22:02:43,235 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:43,235 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:43,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:43,628 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2024-10-31 22:02:43,630 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:43,634 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-31 22:02:43,634 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-10-31 22:02:43,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [287281369] [2024-10-31 22:02:43,634 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [287281369] provided 0 perfect and 1 imperfect interpolant sequences [2024-10-31 22:02:43,634 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1412895504] [2024-10-31 22:02:43,635 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-10-31 22:02:43,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-10-31 22:02:43,635 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:43,637 INFO L229 MonitoredProcess]: Starting monitored process 34 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-10-31 22:02:43,638 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Waiting until timeout for monitored process [2024-10-31 22:02:43,703 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-10-31 22:02:43,704 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-10-31 22:02:43,705 INFO L255 TraceCheckSpWp]: Trace formula consists of 125 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-10-31 22:02:43,707 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:43,809 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-31 22:02:43,812 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-10-31 22:02:44,104 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-10-31 22:02:44,104 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1412895504] provided 0 perfect and 2 imperfect interpolant sequences [2024-10-31 22:02:44,105 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-10-31 22:02:44,105 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2024-10-31 22:02:44,105 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1756164539] [2024-10-31 22:02:44,105 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-10-31 22:02:44,106 INFO L750 eck$LassoCheckResult]: stem already infeasible [2024-10-31 22:02:44,106 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:44,106 INFO L85 PathProgramCache]: Analyzing trace with hash 1817383, now seen corresponding path program 3 times [2024-10-31 22:02:44,107 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-10-31 22:02:44,107 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1782653036] [2024-10-31 22:02:44,107 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-10-31 22:02:44,107 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-10-31 22:02:44,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:44,111 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-10-31 22:02:44,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-10-31 22:02:44,115 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-10-31 22:02:44,187 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:44,187 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:44,187 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:44,187 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:44,188 INFO L128 ssoRankerPreferences]: Use exernal solver: true [2024-10-31 22:02:44,188 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:44,188 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:44,188 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:44,188 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-10-31 22:02:44,188 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:44,188 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:44,189 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:44,192 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:44,195 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:44,206 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:44,261 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:44,261 INFO L365 LassoAnalysis]: Checking for nontermination... [2024-10-31 22:02:44,261 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:44,262 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:44,265 INFO L229 MonitoredProcess]: Starting monitored process 35 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:44,267 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-10-31 22:02:44,268 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:44,268 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:44,284 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-31 22:02:44,284 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-31 22:02:44,302 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2024-10-31 22:02:44,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:44,303 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:44,304 INFO L229 MonitoredProcess]: Starting monitored process 36 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:44,306 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-10-31 22:02:44,307 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:44,307 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:44,323 INFO L398 LassoAnalysis]: Proved nontermination for one component. [2024-10-31 22:02:44,323 INFO L401 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2024-10-31 22:02:44,340 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:44,341 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:44,341 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:44,343 INFO L229 MonitoredProcess]: Starting monitored process 37 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:44,344 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-10-31 22:02:44,345 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2024-10-31 22:02:44,345 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:44,389 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:44,390 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:44,391 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:44,392 INFO L229 MonitoredProcess]: Starting monitored process 38 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:44,394 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-10-31 22:02:44,395 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2024-10-31 22:02:44,395 INFO L160 nArgumentSynthesizer]: Using integer mode. [2024-10-31 22:02:46,726 INFO L405 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2024-10-31 22:02:46,730 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2024-10-31 22:02:46,730 INFO L204 LassoAnalysis]: Preferences: [2024-10-31 22:02:46,731 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-10-31 22:02:46,731 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-10-31 22:02:46,731 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-10-31 22:02:46,731 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-10-31 22:02:46,731 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:46,731 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-10-31 22:02:46,731 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-10-31 22:02:46,731 INFO L132 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2024-10-31 22:02:46,731 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-10-31 22:02:46,731 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-10-31 22:02:46,732 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:46,734 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:46,736 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:46,744 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-10-31 22:02:46,792 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-10-31 22:02:46,792 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-10-31 22:02:46,792 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:46,792 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:46,794 INFO L229 MonitoredProcess]: Starting monitored process 39 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:46,796 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-10-31 22:02:46,798 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-31 22:02:46,813 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:46,813 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:46,813 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:46,813 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:46,813 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:46,814 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:46,814 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:46,816 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-31 22:02:46,837 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:46,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:46,837 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:46,839 INFO L229 MonitoredProcess]: Starting monitored process 40 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:46,840 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-10-31 22:02:46,841 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-31 22:02:46,854 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:46,854 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:46,854 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:46,855 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:46,855 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:46,855 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:46,855 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:46,857 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-10-31 22:02:46,870 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:46,870 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:46,870 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:46,871 INFO L229 MonitoredProcess]: Starting monitored process 41 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:46,872 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-10-31 22:02:46,873 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-31 22:02:46,884 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-10-31 22:02:46,884 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-10-31 22:02:46,884 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-10-31 22:02:46,884 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-10-31 22:02:46,884 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-10-31 22:02:46,885 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-10-31 22:02:46,886 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-10-31 22:02:46,892 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-10-31 22:02:46,895 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-10-31 22:02:46,895 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-10-31 22:02:46,895 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-10-31 22:02:46,895 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 [2024-10-31 22:02:46,898 INFO L229 MonitoredProcess]: Starting monitored process 42 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-10-31 22:02:46,902 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-10-31 22:02:46,903 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-10-31 22:02:46,903 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-10-31 22:02:46,904 INFO L474 LassoAnalysis]: Proved termination. [2024-10-31 22:02:46,904 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2024-10-31 22:02:46,923 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:46,924 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-10-31 22:02:46,939 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:47,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:47,023 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-10-31 22:02:47,026 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:47,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:47,169 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-31 22:02:47,170 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:47,210 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-31 22:02:47,211 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2024-10-31 22:02:47,211 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:47,269 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 724 states and 1045 transitions. Complement of second has 18 states. [2024-10-31 22:02:47,269 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-31 22:02:47,270 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:47,270 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 11 transitions. [2024-10-31 22:02:47,270 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 11 transitions. Stem has 52 letters. Loop has 4 letters. [2024-10-31 22:02:47,271 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:47,271 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-10-31 22:02:47,285 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-10-31 22:02:47,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:47,362 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 26 conjuncts are in the unsatisfiable core [2024-10-31 22:02:47,365 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:47,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-10-31 22:02:47,507 INFO L255 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-10-31 22:02:47,508 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-10-31 22:02:47,547 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-31 22:02:47,548 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2024-10-31 22:02:47,548 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:47,654 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 702 states and 1022 transitions. cyclomatic complexity: 330. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 944 states and 1356 transitions. Complement of second has 22 states. [2024-10-31 22:02:47,654 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-10-31 22:02:47,655 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:47,655 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 15 transitions. [2024-10-31 22:02:47,655 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 4 letters. [2024-10-31 22:02:47,655 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:47,656 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 56 letters. Loop has 4 letters. [2024-10-31 22:02:47,656 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:47,656 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 15 transitions. Stem has 52 letters. Loop has 8 letters. [2024-10-31 22:02:47,656 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-10-31 22:02:47,656 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 944 states and 1356 transitions. [2024-10-31 22:02:47,669 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2024-10-31 22:02:47,681 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 944 states to 874 states and 1278 transitions. [2024-10-31 22:02:47,681 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 282 [2024-10-31 22:02:47,682 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 310 [2024-10-31 22:02:47,682 INFO L73 IsDeterministic]: Start isDeterministic. Operand 874 states and 1278 transitions. [2024-10-31 22:02:47,682 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-10-31 22:02:47,683 INFO L218 hiAutomatonCegarLoop]: Abstraction has 874 states and 1278 transitions. [2024-10-31 22:02:47,684 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 874 states and 1278 transitions. [2024-10-31 22:02:47,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 874 to 854. [2024-10-31 22:02:47,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 854 states, 537 states have (on average 1.1340782122905029) internal successors, (609), 569 states have internal predecessors, (609), 202 states have call successors, (236), 111 states have call predecessors, (236), 115 states have return successors, (409), 173 states have call predecessors, (409), 192 states have call successors, (409) [2024-10-31 22:02:47,711 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 854 states to 854 states and 1254 transitions. [2024-10-31 22:02:47,712 INFO L240 hiAutomatonCegarLoop]: Abstraction has 854 states and 1254 transitions. [2024-10-31 22:02:47,712 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-10-31 22:02:47,712 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-10-31 22:02:47,712 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2024-10-31 22:02:47,713 INFO L87 Difference]: Start difference. First operand 854 states and 1254 transitions. Second operand has 21 states, 20 states have (on average 1.75) internal successors, (35), 12 states have internal predecessors, (35), 10 states have call successors, (11), 11 states have call predecessors, (11), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-10-31 22:02:47,765 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:48,130 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-10-31 22:02:48,130 INFO L93 Difference]: Finished difference Result 471 states and 558 transitions. [2024-10-31 22:02:48,130 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 471 states and 558 transitions. [2024-10-31 22:02:48,134 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-31 22:02:48,134 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 471 states to 0 states and 0 transitions. [2024-10-31 22:02:48,135 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-10-31 22:02:48,135 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-10-31 22:02:48,135 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-10-31 22:02:48,135 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-10-31 22:02:48,135 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-31 22:02:48,135 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-31 22:02:48,135 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-10-31 22:02:48,136 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-10-31 22:02:48,136 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-10-31 22:02:48,136 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-10-31 22:02:48,136 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-10-31 22:02:48,136 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-10-31 22:02:48,145 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 31.10 10:02:48 BoogieIcfgContainer [2024-10-31 22:02:48,146 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-10-31 22:02:48,147 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-10-31 22:02:48,147 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-10-31 22:02:48,147 INFO L274 PluginConnector]: Witness Printer initialized [2024-10-31 22:02:48,147 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 31.10 10:02:31" (3/4) ... [2024-10-31 22:02:48,150 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-10-31 22:02:48,151 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-10-31 22:02:48,152 INFO L158 Benchmark]: Toolchain (without parser) took 17014.22ms. Allocated memory was 151.0MB in the beginning and 220.2MB in the end (delta: 69.2MB). Free memory was 119.0MB in the beginning and 161.5MB in the end (delta: -42.5MB). Peak memory consumption was 27.3MB. Max. memory is 16.1GB. [2024-10-31 22:02:48,152 INFO L158 Benchmark]: CDTParser took 0.32ms. Allocated memory is still 117.4MB. Free memory is still 67.6MB. There was no memory consumed. Max. memory is 16.1GB. [2024-10-31 22:02:48,152 INFO L158 Benchmark]: CACSL2BoogieTranslator took 257.81ms. Allocated memory is still 151.0MB. Free memory was 118.4MB in the beginning and 107.0MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-10-31 22:02:48,153 INFO L158 Benchmark]: Boogie Procedure Inliner took 30.60ms. Allocated memory is still 151.0MB. Free memory was 107.0MB in the beginning and 105.2MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-31 22:02:48,154 INFO L158 Benchmark]: Boogie Preprocessor took 41.63ms. Allocated memory is still 151.0MB. Free memory was 105.2MB in the beginning and 103.7MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-10-31 22:02:48,154 INFO L158 Benchmark]: RCFGBuilder took 266.48ms. Allocated memory is still 151.0MB. Free memory was 103.7MB in the beginning and 94.4MB in the end (delta: 9.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-10-31 22:02:48,155 INFO L158 Benchmark]: BuchiAutomizer took 16407.15ms. Allocated memory was 151.0MB in the beginning and 220.2MB in the end (delta: 69.2MB). Free memory was 94.4MB in the beginning and 162.6MB in the end (delta: -68.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2024-10-31 22:02:48,155 INFO L158 Benchmark]: Witness Printer took 4.67ms. Allocated memory is still 220.2MB. Free memory was 162.6MB in the beginning and 161.5MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2024-10-31 22:02:48,159 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.32ms. Allocated memory is still 117.4MB. Free memory is still 67.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 257.81ms. Allocated memory is still 151.0MB. Free memory was 118.4MB in the beginning and 107.0MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 30.60ms. Allocated memory is still 151.0MB. Free memory was 107.0MB in the beginning and 105.2MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 41.63ms. Allocated memory is still 151.0MB. Free memory was 105.2MB in the beginning and 103.7MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 266.48ms. Allocated memory is still 151.0MB. Free memory was 103.7MB in the beginning and 94.4MB in the end (delta: 9.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 16407.15ms. Allocated memory was 151.0MB in the beginning and 220.2MB in the end (delta: 69.2MB). Free memory was 94.4MB in the beginning and 162.6MB in the end (delta: -68.2MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * Witness Printer took 4.67ms. Allocated memory is still 220.2MB. Free memory was 162.6MB in the beginning and 161.5MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (5 trivial, 3 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 5 locations. One deterministic module has affine ranking function n and consists of 11 locations. One deterministic module has affine ranking function n and consists of 7 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function \old(n) and consists of 6 locations. 5 modules have a trivial ranking function, the largest among these consists of 23 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 16.3s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 9.0s. Construction of modules took 1.5s. Büchi inclusion checks took 5.3s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.2s AutomataMinimizationTime, 9 MinimizatonAttempts, 265 StatesRemovedByMinimization, 8 NontrivialMinimizations. Non-live state removal took 0.2s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 1, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 596 SdHoareTripleChecker+Valid, 1.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 571 mSDsluCounter, 658 SdHoareTripleChecker+Invalid, 1.5s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 425 mSDsCounter, 357 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1357 IncrementalHoareTripleChecker+Invalid, 1714 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 357 mSolverCounterUnsat, 233 mSDtfsCounter, 1357 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI1 SILT4 lasso0 LassoPreprocessingBenchmarks: Lassos: inital14 mio100 ax100 hnf100 lsp82 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq185 hnf92 smp80 dnf100 smp100 tf112 neg100 sie106 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 32ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 2.9s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-10-31 22:02:48,196 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (34)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:48,401 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (25)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:48,598 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2024-10-31 22:02:48,823 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2024-10-31 22:02:49,007 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_41be7413-fca8-47e4-97cb-040988a9de44/bin/uautomizer-verify-4GaUIPS5ZU/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