./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 0e0057cc 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_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/config/AutomizerTermination.xml -i ../../sv-benchmarks/c/recursive/Fibonacci02.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya --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.4-dev-0e0057c [2023-11-28 23:43:59,234 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-28 23:43:59,297 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/config/svcomp-Termination-32bit-Automizer_Default.epf [2023-11-28 23:43:59,302 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-28 23:43:59,302 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-28 23:43:59,328 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-28 23:43:59,328 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-28 23:43:59,329 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-28 23:43:59,330 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-11-28 23:43:59,330 INFO L153 SettingsManager]: * Use memory slicer=true [2023-11-28 23:43:59,331 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-28 23:43:59,331 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-28 23:43:59,332 INFO L153 SettingsManager]: * Use SBE=true [2023-11-28 23:43:59,332 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2023-11-28 23:43:59,333 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2023-11-28 23:43:59,333 INFO L153 SettingsManager]: * Use old map elimination=false [2023-11-28 23:43:59,334 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2023-11-28 23:43:59,334 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2023-11-28 23:43:59,335 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2023-11-28 23:43:59,335 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-28 23:43:59,336 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2023-11-28 23:43:59,336 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-28 23:43:59,337 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-28 23:43:59,337 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-28 23:43:59,338 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-28 23:43:59,338 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2023-11-28 23:43:59,339 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2023-11-28 23:43:59,339 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2023-11-28 23:43:59,339 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2023-11-28 23:43:59,340 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-28 23:43:59,340 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-28 23:43:59,341 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2023-11-28 23:43:59,341 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-28 23:43:59,341 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-28 23:43:59,342 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-11-28 23:43:59,342 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-28 23:43:59,342 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-11-28 23:43:59,343 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2023-11-28 23:43:59,343 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_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/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_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya 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 [2023-11-28 23:43:59,541 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-28 23:43:59,561 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-28 23:43:59,564 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-28 23:43:59,565 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-28 23:43:59,565 INFO L274 PluginConnector]: CDTParser initialized [2023-11-28 23:43:59,566 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/../../sv-benchmarks/c/recursive/Fibonacci02.c [2023-11-28 23:44:02,326 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-28 23:44:02,466 INFO L384 CDTParser]: Found 1 translation units. [2023-11-28 23:44:02,467 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/sv-benchmarks/c/recursive/Fibonacci02.c [2023-11-28 23:44:02,472 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/data/d14bb1871/81ffda92856a4466adf0ba78c6338c60/FLAGcd42e2218 [2023-11-28 23:44:02,486 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/data/d14bb1871/81ffda92856a4466adf0ba78c6338c60 [2023-11-28 23:44:02,489 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-28 23:44:02,491 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-28 23:44:02,492 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-28 23:44:02,492 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-28 23:44:02,497 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-28 23:44:02,498 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,499 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4d5974b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02, skipping insertion in model container [2023-11-28 23:44:02,500 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,520 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-28 23:44:02,670 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-28 23:44:02,683 INFO L202 MainTranslator]: Completed pre-run [2023-11-28 23:44:02,697 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-28 23:44:02,711 INFO L206 MainTranslator]: Completed translation [2023-11-28 23:44:02,711 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02 WrapperNode [2023-11-28 23:44:02,711 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-28 23:44:02,712 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-28 23:44:02,713 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-28 23:44:02,713 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-28 23:44:02,720 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,726 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,742 INFO L138 Inliner]: procedures = 13, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 20 [2023-11-28 23:44:02,742 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-28 23:44:02,743 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-28 23:44:02,743 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-28 23:44:02,743 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-28 23:44:02,753 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,754 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,755 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,765 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]. [2023-11-28 23:44:02,765 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,765 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,768 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,770 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,771 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,771 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,773 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-28 23:44:02,774 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-28 23:44:02,774 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-28 23:44:02,774 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-28 23:44:02,775 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (1/1) ... [2023-11-28 23:44:02,781 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:02,792 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:02,804 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:02,810 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2023-11-28 23:44:02,837 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2023-11-28 23:44:02,838 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2023-11-28 23:44:02,838 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-28 23:44:02,838 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-28 23:44:02,838 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-28 23:44:02,838 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-11-28 23:44:02,893 INFO L241 CfgBuilder]: Building ICFG [2023-11-28 23:44:02,895 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-28 23:44:02,973 INFO L282 CfgBuilder]: Performing block encoding [2023-11-28 23:44:02,980 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-28 23:44:02,980 INFO L309 CfgBuilder]: Removed 0 assume(true) statements. [2023-11-28 23:44:02,982 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 11:44:02 BoogieIcfgContainer [2023-11-28 23:44:02,982 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-28 23:44:02,983 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2023-11-28 23:44:02,983 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2023-11-28 23:44:02,986 INFO L274 PluginConnector]: BuchiAutomizer initialized [2023-11-28 23:44:02,987 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2023-11-28 23:44:02,987 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 28.11 11:44:02" (1/3) ... [2023-11-28 23:44:02,988 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@5d78c7e7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 28.11 11:44:02, skipping insertion in model container [2023-11-28 23:44:02,988 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2023-11-28 23:44:02,988 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.11 11:44:02" (2/3) ... [2023-11-28 23:44:02,989 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@5d78c7e7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 28.11 11:44:02, skipping insertion in model container [2023-11-28 23:44:02,989 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2023-11-28 23:44:02,989 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 11:44:02" (3/3) ... [2023-11-28 23:44:02,990 INFO L332 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2023-11-28 23:44:03,044 INFO L303 stractBuchiCegarLoop]: Interprodecural is true [2023-11-28 23:44:03,045 INFO L304 stractBuchiCegarLoop]: Hoare is false [2023-11-28 23:44:03,045 INFO L305 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2023-11-28 23:44:03,045 INFO L306 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2023-11-28 23:44:03,045 INFO L307 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2023-11-28 23:44:03,045 INFO L308 stractBuchiCegarLoop]: Difference is false [2023-11-28 23:44:03,045 INFO L309 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2023-11-28 23:44:03,045 INFO L313 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2023-11-28 23:44:03,048 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) [2023-11-28 23:44:03,064 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2023-11-28 23:44:03,064 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-11-28 23:44:03,064 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-11-28 23:44:03,069 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2023-11-28 23:44:03,069 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2023-11-28 23:44:03,069 INFO L335 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2023-11-28 23:44:03,069 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) [2023-11-28 23:44:03,071 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2023-11-28 23:44:03,072 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-11-28 23:44:03,072 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-11-28 23:44:03,072 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2023-11-28 23:44:03,072 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2023-11-28 23:44:03,078 INFO L748 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 [2023-11-28 23:44:03,079 INFO L750 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 [2023-11-28 23:44:03,083 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:03,083 INFO L85 PathProgramCache]: Analyzing trace with hash 42783, now seen corresponding path program 1 times [2023-11-28 23:44:03,092 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:03,092 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1626990417] [2023-11-28 23:44:03,092 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:03,093 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:03,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:03,181 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-28 23:44:03,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:03,207 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-28 23:44:03,209 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:03,209 INFO L85 PathProgramCache]: Analyzing trace with hash 927643, now seen corresponding path program 1 times [2023-11-28 23:44:03,210 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:03,210 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1908662377] [2023-11-28 23:44:03,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:03,210 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:03,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:03,217 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-28 23:44:03,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:03,223 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-28 23:44:03,225 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:03,225 INFO L85 PathProgramCache]: Analyzing trace with hash 856297401, now seen corresponding path program 1 times [2023-11-28 23:44:03,226 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:03,226 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1089698449] [2023-11-28 23:44:03,226 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:03,226 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:03,238 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:03,239 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-28 23:44:03,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:03,251 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-28 23:44:03,354 INFO L210 LassoAnalysis]: Preferences: [2023-11-28 23:44:03,354 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-11-28 23:44:03,355 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-11-28 23:44:03,355 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-11-28 23:44:03,355 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2023-11-28 23:44:03,355 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,355 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-11-28 23:44:03,355 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-11-28 23:44:03,356 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2023-11-28 23:44:03,356 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-11-28 23:44:03,356 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-11-28 23:44:03,368 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,377 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,380 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,383 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,393 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,478 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-11-28 23:44:03,478 INFO L404 LassoAnalysis]: Checking for nontermination... [2023-11-28 23:44:03,481 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,481 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,482 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,490 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2023-11-28 23:44:03,495 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:03,496 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:03,515 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-11-28 23:44:03,515 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-11-28 23:44:03,521 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2023-11-28 23:44:03,522 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,522 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,523 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,525 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2023-11-28 23:44:03,526 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:03,526 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:03,541 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-11-28 23:44:03,541 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-11-28 23:44:03,545 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2023-11-28 23:44:03,545 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,545 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,546 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,549 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2023-11-28 23:44:03,550 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:03,550 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:03,565 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-11-28 23:44:03,565 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-11-28 23:44:03,573 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2023-11-28 23:44:03,574 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,574 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,575 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,577 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2023-11-28 23:44:03,582 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:03,582 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:03,600 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2023-11-28 23:44:03,600 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,600 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,601 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,604 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2023-11-28 23:44:03,604 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2023-11-28 23:44:03,605 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:03,669 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2023-11-28 23:44:03,672 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2023-11-28 23:44:03,672 INFO L210 LassoAnalysis]: Preferences: [2023-11-28 23:44:03,672 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-11-28 23:44:03,673 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-11-28 23:44:03,673 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-11-28 23:44:03,673 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2023-11-28 23:44:03,673 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,673 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-11-28 23:44:03,673 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-11-28 23:44:03,673 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2023-11-28 23:44:03,673 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-11-28 23:44:03,674 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-11-28 23:44:03,675 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,679 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,682 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,686 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,695 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:03,746 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-11-28 23:44:03,750 INFO L490 LassoAnalysis]: Using template 'affine'. [2023-11-28 23:44:03,751 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,752 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,753 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,755 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2023-11-28 23:44:03,757 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 [2023-11-28 23:44:03,771 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-11-28 23:44:03,771 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-11-28 23:44:03,771 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-11-28 23:44:03,772 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-11-28 23:44:03,772 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-11-28 23:44:03,774 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-11-28 23:44:03,774 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-11-28 23:44:03,777 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-11-28 23:44:03,780 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2023-11-28 23:44:03,780 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,780 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,781 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,784 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2023-11-28 23:44:03,784 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 [2023-11-28 23:44:03,796 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-11-28 23:44:03,797 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-11-28 23:44:03,797 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-11-28 23:44:03,797 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-11-28 23:44:03,797 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-11-28 23:44:03,798 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-11-28 23:44:03,798 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-11-28 23:44:03,800 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-11-28 23:44:03,802 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2023-11-28 23:44:03,803 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,803 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,804 INFO L229 MonitoredProcess]: Starting monitored process 9 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,805 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2023-11-28 23:44:03,806 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 [2023-11-28 23:44:03,816 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-11-28 23:44:03,816 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-11-28 23:44:03,816 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-11-28 23:44:03,816 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-11-28 23:44:03,816 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-11-28 23:44:03,817 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-11-28 23:44:03,817 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-11-28 23:44:03,819 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-11-28 23:44:03,822 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2023-11-28 23:44:03,822 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,823 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,823 INFO L229 MonitoredProcess]: Starting monitored process 10 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,824 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2023-11-28 23:44:03,826 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 [2023-11-28 23:44:03,836 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-11-28 23:44:03,836 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-11-28 23:44:03,836 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-11-28 23:44:03,836 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-11-28 23:44:03,836 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-11-28 23:44:03,837 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-11-28 23:44:03,837 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-11-28 23:44:03,841 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2023-11-28 23:44:03,863 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2023-11-28 23:44:03,863 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2023-11-28 23:44:03,864 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:03,864 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:03,886 INFO L229 MonitoredProcess]: Starting monitored process 11 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:03,887 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2023-11-28 23:44:03,888 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2023-11-28 23:44:03,888 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2023-11-28 23:44:03,888 INFO L513 LassoAnalysis]: Proved termination. [2023-11-28 23:44:03,888 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2023-11-28 23:44:03,891 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2023-11-28 23:44:03,894 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2023-11-28 23:44:03,914 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:03,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:03,938 INFO L262 TraceCheckSpWp]: Trace formula consists of 55 conjuncts, 4 conjunts are in the unsatisfiable core [2023-11-28 23:44:03,940 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:03,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:03,961 INFO L262 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2023-11-28 23:44:03,962 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:04,006 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-28 23:44:04,039 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 [2023-11-28 23:44:04,041 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) [2023-11-28 23:44:04,142 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 48 states and 60 transitions. Complement of second has 12 states. [2023-11-28 23:44:04,144 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 4 states 1 stem states 2 non-accepting loop states 1 accepting loop states [2023-11-28 23:44:04,149 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) [2023-11-28 23:44:04,150 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 11 transitions. [2023-11-28 23:44:04,151 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 4 letters. [2023-11-28 23:44:04,153 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:04,153 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 7 letters. Loop has 4 letters. [2023-11-28 23:44:04,153 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:04,153 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 8 letters. [2023-11-28 23:44:04,153 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:04,154 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 48 states and 60 transitions. [2023-11-28 23:44:04,159 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2023-11-28 23:44:04,165 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 48 states to 25 states and 34 transitions. [2023-11-28 23:44:04,166 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2023-11-28 23:44:04,166 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 18 [2023-11-28 23:44:04,167 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 34 transitions. [2023-11-28 23:44:04,167 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-11-28 23:44:04,167 INFO L218 hiAutomatonCegarLoop]: Abstraction has 25 states and 34 transitions. [2023-11-28 23:44:04,183 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 34 transitions. [2023-11-28 23:44:04,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 20. [2023-11-28 23:44:04,195 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) [2023-11-28 23:44:04,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2023-11-28 23:44:04,197 INFO L240 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2023-11-28 23:44:04,197 INFO L428 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2023-11-28 23:44:04,197 INFO L335 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2023-11-28 23:44:04,198 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2023-11-28 23:44:04,198 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2023-11-28 23:44:04,199 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-11-28 23:44:04,199 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-11-28 23:44:04,200 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-28 23:44:04,200 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2023-11-28 23:44:04,200 INFO L748 eck$LassoCheckResult]: Stem: 133#$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); 134#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; 123#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 135#$Ultimate##0 ~n := #in~n; 129#L17 assume !(~n < 1); 130#L19 assume !(1 == ~n); 122#L22 call #t~ret4 := fibonacci(~n - 1);< 131#$Ultimate##0 ~n := #in~n; 126#L17 assume ~n < 1;#res := 0; 127#fibonacciFINAL assume true; 132#fibonacciEXIT >#31#return; 121#L22-1 [2023-11-28 23:44:04,200 INFO L750 eck$LassoCheckResult]: Loop: 121#L22-1 call #t~ret5 := fibonacci(~n - 2);< 125#$Ultimate##0 ~n := #in~n; 140#L17 assume !(~n < 1); 139#L19 assume !(1 == ~n); 124#L22 call #t~ret4 := fibonacci(~n - 1);< 125#$Ultimate##0 ~n := #in~n; 140#L17 assume ~n < 1;#res := 0; 137#fibonacciFINAL assume true; 138#fibonacciEXIT >#31#return; 121#L22-1 [2023-11-28 23:44:04,201 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:04,201 INFO L85 PathProgramCache]: Analyzing trace with hash 2073663503, now seen corresponding path program 1 times [2023-11-28 23:44:04,201 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:04,201 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [64162564] [2023-11-28 23:44:04,202 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:04,202 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:04,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:04,295 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2023-11-28 23:44:04,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:04,331 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-28 23:44:04,332 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-28 23:44:04,332 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [64162564] [2023-11-28 23:44:04,332 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [64162564] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-28 23:44:04,332 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-28 23:44:04,333 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-28 23:44:04,333 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [379931518] [2023-11-28 23:44:04,334 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-28 23:44:04,335 INFO L753 eck$LassoCheckResult]: stem already infeasible [2023-11-28 23:44:04,336 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:04,336 INFO L85 PathProgramCache]: Analyzing trace with hash 1606275375, now seen corresponding path program 1 times [2023-11-28 23:44:04,336 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:04,337 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2004255213] [2023-11-28 23:44:04,337 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:04,337 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:04,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:04,378 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-28 23:44:04,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:04,411 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-11-28 23:44:04,411 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-28 23:44:04,412 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2004255213] [2023-11-28 23:44:04,412 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2004255213] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-28 23:44:04,412 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-28 23:44:04,412 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-28 23:44:04,412 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1677641832] [2023-11-28 23:44:04,412 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-28 23:44:04,413 INFO L765 eck$LassoCheckResult]: loop already infeasible [2023-11-28 23:44:04,413 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-28 23:44:04,414 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-28 23:44:04,415 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-28 23:44:04,416 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) [2023-11-28 23:44:04,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-28 23:44:04,482 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2023-11-28 23:44:04,482 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2023-11-28 23:44:04,484 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2023-11-28 23:44:04,485 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2023-11-28 23:44:04,485 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2023-11-28 23:44:04,486 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2023-11-28 23:44:04,486 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2023-11-28 23:44:04,486 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-11-28 23:44:04,486 INFO L218 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2023-11-28 23:44:04,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2023-11-28 23:44:04,489 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2023-11-28 23:44:04,489 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) [2023-11-28 23:44:04,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2023-11-28 23:44:04,490 INFO L240 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2023-11-28 23:44:04,490 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-11-28 23:44:04,491 INFO L428 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2023-11-28 23:44:04,491 INFO L335 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2023-11-28 23:44:04,491 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2023-11-28 23:44:04,492 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2023-11-28 23:44:04,492 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-11-28 23:44:04,492 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-11-28 23:44:04,493 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-28 23:44:04,493 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2023-11-28 23:44:04,493 INFO L748 eck$LassoCheckResult]: Stem: 207#$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); 208#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; 195#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 209#$Ultimate##0 ~n := #in~n; 202#L17 assume !(~n < 1); 203#L19 assume !(1 == ~n); 196#L22 call #t~ret4 := fibonacci(~n - 1);< 204#$Ultimate##0 ~n := #in~n; 212#L17 assume !(~n < 1); 217#L19 assume 1 == ~n;#res := 1; 216#fibonacciFINAL assume true; 215#fibonacciEXIT >#31#return; 194#L22-1 [2023-11-28 23:44:04,494 INFO L750 eck$LassoCheckResult]: Loop: 194#L22-1 call #t~ret5 := fibonacci(~n - 2);< 198#$Ultimate##0 ~n := #in~n; 199#L17 assume !(~n < 1); 201#L19 assume !(1 == ~n); 197#L22 call #t~ret4 := fibonacci(~n - 1);< 198#$Ultimate##0 ~n := #in~n; 199#L17 assume !(~n < 1); 201#L19 assume 1 == ~n;#res := 1; 211#fibonacciFINAL assume true; 213#fibonacciEXIT >#31#return; 194#L22-1 [2023-11-28 23:44:04,494 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:04,494 INFO L85 PathProgramCache]: Analyzing trace with hash -140916419, now seen corresponding path program 1 times [2023-11-28 23:44:04,494 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:04,494 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [698773531] [2023-11-28 23:44:04,494 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:04,495 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:04,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:04,549 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2023-11-28 23:44:04,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:04,584 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-28 23:44:04,584 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-28 23:44:04,584 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [698773531] [2023-11-28 23:44:04,584 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [698773531] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-28 23:44:04,585 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1335531424] [2023-11-28 23:44:04,585 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:04,585 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-28 23:44:04,585 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:04,586 INFO L229 MonitoredProcess]: Starting monitored process 12 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-28 23:44:04,586 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-11-28 23:44:04,618 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:04,619 INFO L262 TraceCheckSpWp]: Trace formula consists of 45 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-28 23:44:04,620 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:04,650 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-28 23:44:04,650 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-28 23:44:04,747 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-28 23:44:04,748 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1335531424] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-28 23:44:04,748 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-28 23:44:04,748 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2023-11-28 23:44:04,748 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [139409393] [2023-11-28 23:44:04,748 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-28 23:44:04,749 INFO L753 eck$LassoCheckResult]: stem already infeasible [2023-11-28 23:44:04,749 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:04,749 INFO L85 PathProgramCache]: Analyzing trace with hash -1745046499, now seen corresponding path program 1 times [2023-11-28 23:44:04,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:04,749 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1180599415] [2023-11-28 23:44:04,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:04,750 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:04,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:04,755 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-28 23:44:04,758 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:04,760 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-28 23:44:04,890 INFO L210 LassoAnalysis]: Preferences: [2023-11-28 23:44:04,890 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-11-28 23:44:04,890 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-11-28 23:44:04,890 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-11-28 23:44:04,890 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2023-11-28 23:44:04,890 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:04,890 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-11-28 23:44:04,890 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-11-28 23:44:04,890 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2023-11-28 23:44:04,890 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-11-28 23:44:04,890 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-11-28 23:44:04,891 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:04,896 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:04,898 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:04,900 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:04,909 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:04,910 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2023-11-28 23:44:04,949 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-11-28 23:44:04,949 INFO L404 LassoAnalysis]: Checking for nontermination... [2023-11-28 23:44:04,949 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:04,949 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:04,951 INFO L229 MonitoredProcess]: Starting monitored process 13 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:04,953 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2023-11-28 23:44:04,957 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:04,958 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:04,975 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2023-11-28 23:44:04,975 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:04,975 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:04,976 INFO L229 MonitoredProcess]: Starting monitored process 14 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:04,977 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2023-11-28 23:44:04,978 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2023-11-28 23:44:04,978 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:04,992 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2023-11-28 23:44:04,995 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2023-11-28 23:44:04,996 INFO L210 LassoAnalysis]: Preferences: [2023-11-28 23:44:04,996 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-11-28 23:44:04,996 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-11-28 23:44:04,996 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-11-28 23:44:04,996 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2023-11-28 23:44:04,996 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:04,996 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-11-28 23:44:04,996 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-11-28 23:44:04,996 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2023-11-28 23:44:04,997 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-11-28 23:44:04,997 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-11-28 23:44:04,998 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:05,003 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:05,006 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:05,008 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:05,011 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:05,048 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-11-28 23:44:05,049 INFO L490 LassoAnalysis]: Using template 'affine'. [2023-11-28 23:44:05,049 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:05,049 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:05,050 INFO L229 MonitoredProcess]: Starting monitored process 15 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:05,052 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2023-11-28 23:44:05,053 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 [2023-11-28 23:44:05,065 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-11-28 23:44:05,065 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-11-28 23:44:05,065 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-11-28 23:44:05,065 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-11-28 23:44:05,065 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-11-28 23:44:05,066 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-11-28 23:44:05,066 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-11-28 23:44:05,069 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2023-11-28 23:44:05,071 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2023-11-28 23:44:05,071 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2023-11-28 23:44:05,072 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:05,072 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:05,073 INFO L229 MonitoredProcess]: Starting monitored process 16 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:05,074 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2023-11-28 23:44:05,075 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2023-11-28 23:44:05,075 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2023-11-28 23:44:05,075 INFO L513 LassoAnalysis]: Proved termination. [2023-11-28 23:44:05,075 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2023-11-28 23:44:05,078 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2023-11-28 23:44:05,079 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2023-11-28 23:44:05,091 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:05,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:05,112 INFO L262 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-28 23:44:05,114 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:05,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:05,202 INFO L262 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2023-11-28 23:44:05,203 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:05,284 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-11-28 23:44:05,284 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 [2023-11-28 23:44:05,285 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-28 23:44:05,488 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 135 states and 183 transitions. Complement of second has 36 states. [2023-11-28 23:44:05,489 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 9 states 2 stem states 6 non-accepting loop states 1 accepting loop states [2023-11-28 23:44:05,490 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2023-11-28 23:44:05,491 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 37 transitions. [2023-11-28 23:44:05,491 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 10 letters. [2023-11-28 23:44:05,492 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:05,492 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 22 letters. Loop has 10 letters. [2023-11-28 23:44:05,492 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:05,492 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 20 letters. [2023-11-28 23:44:05,493 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:05,494 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2023-11-28 23:44:05,500 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2023-11-28 23:44:05,505 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 108 states and 152 transitions. [2023-11-28 23:44:05,506 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 64 [2023-11-28 23:44:05,506 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 69 [2023-11-28 23:44:05,506 INFO L73 IsDeterministic]: Start isDeterministic. Operand 108 states and 152 transitions. [2023-11-28 23:44:05,507 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-11-28 23:44:05,507 INFO L218 hiAutomatonCegarLoop]: Abstraction has 108 states and 152 transitions. [2023-11-28 23:44:05,507 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states and 152 transitions. [2023-11-28 23:44:05,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 94. [2023-11-28 23:44:05,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 64 states have internal predecessors, (71), 21 states have call successors, (22), 11 states have call predecessors, (22), 15 states have return successors, (33), 18 states have call predecessors, (33), 19 states have call successors, (33) [2023-11-28 23:44:05,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 126 transitions. [2023-11-28 23:44:05,522 INFO L240 hiAutomatonCegarLoop]: Abstraction has 94 states and 126 transitions. [2023-11-28 23:44:05,522 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-28 23:44:05,522 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-11-28 23:44:05,522 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2023-11-28 23:44:05,523 INFO L87 Difference]: Start difference. First operand 94 states and 126 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) [2023-11-28 23:44:05,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-28 23:44:05,633 INFO L93 Difference]: Finished difference Result 123 states and 165 transitions. [2023-11-28 23:44:05,633 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 123 states and 165 transitions. [2023-11-28 23:44:05,638 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2023-11-28 23:44:05,642 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 123 states to 118 states and 160 transitions. [2023-11-28 23:44:05,642 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 77 [2023-11-28 23:44:05,642 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 77 [2023-11-28 23:44:05,642 INFO L73 IsDeterministic]: Start isDeterministic. Operand 118 states and 160 transitions. [2023-11-28 23:44:05,643 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-11-28 23:44:05,643 INFO L218 hiAutomatonCegarLoop]: Abstraction has 118 states and 160 transitions. [2023-11-28 23:44:05,643 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states and 160 transitions. [2023-11-28 23:44:05,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 106. [2023-11-28 23:44:05,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.196969696969697) internal successors, (79), 72 states have internal predecessors, (79), 24 states have call successors, (25), 13 states have call predecessors, (25), 16 states have return successors, (37), 20 states have call predecessors, (37), 22 states have call successors, (37) [2023-11-28 23:44:05,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 141 transitions. [2023-11-28 23:44:05,656 INFO L240 hiAutomatonCegarLoop]: Abstraction has 106 states and 141 transitions. [2023-11-28 23:44:05,657 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-11-28 23:44:05,658 INFO L428 stractBuchiCegarLoop]: Abstraction has 106 states and 141 transitions. [2023-11-28 23:44:05,658 INFO L335 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2023-11-28 23:44:05,658 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 141 transitions. [2023-11-28 23:44:05,660 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2023-11-28 23:44:05,660 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-11-28 23:44:05,661 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-11-28 23:44:05,663 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-28 23:44:05,663 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 5, 3, 3, 3, 3, 2, 2, 2, 1] [2023-11-28 23:44:05,663 INFO L748 eck$LassoCheckResult]: Stem: 808#$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); 809#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; 788#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 810#$Ultimate##0 ~n := #in~n; 853#L17 assume !(~n < 1); 852#L19 assume !(1 == ~n); 798#L22 call #t~ret4 := fibonacci(~n - 1);< 802#$Ultimate##0 ~n := #in~n; 797#L17 assume !(~n < 1); 799#L19 assume !(1 == ~n); 819#L22 call #t~ret4 := fibonacci(~n - 1);< 845#$Ultimate##0 ~n := #in~n; 848#L17 assume !(~n < 1); 847#L19 assume !(1 == ~n); 840#L22 call #t~ret4 := fibonacci(~n - 1);< 845#$Ultimate##0 ~n := #in~n; 848#L17 assume !(~n < 1); 847#L19 assume !(1 == ~n); 840#L22 call #t~ret4 := fibonacci(~n - 1);< 845#$Ultimate##0 ~n := #in~n; 849#L17 assume !(~n < 1); 851#L19 assume 1 == ~n;#res := 1; 850#fibonacciFINAL assume true; 844#fibonacciEXIT >#31#return; 791#L22-1 call #t~ret5 := fibonacci(~n - 2);< 841#$Ultimate##0 ~n := #in~n; 891#L17 assume ~n < 1;#res := 0; 890#fibonacciFINAL assume true; 889#fibonacciEXIT >#33#return; 888#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 886#fibonacciFINAL assume true; 879#fibonacciEXIT >#31#return; 815#L22-1 [2023-11-28 23:44:05,663 INFO L750 eck$LassoCheckResult]: Loop: 815#L22-1 call #t~ret5 := fibonacci(~n - 2);< 801#$Ultimate##0 ~n := #in~n; 885#L17 assume !(~n < 1); 814#L19 assume !(1 == ~n); 817#L22 call #t~ret4 := fibonacci(~n - 1);< 801#$Ultimate##0 ~n := #in~n; 885#L17 assume !(~n < 1); 814#L19 assume !(1 == ~n); 817#L22 call #t~ret4 := fibonacci(~n - 1);< 801#$Ultimate##0 ~n := #in~n; 885#L17 assume !(~n < 1); 814#L19 assume 1 == ~n;#res := 1; 818#fibonacciFINAL assume true; 875#fibonacciEXIT >#31#return; 815#L22-1 call #t~ret5 := fibonacci(~n - 2);< 801#$Ultimate##0 ~n := #in~n; 885#L17 assume !(~n < 1); 814#L19 assume !(1 == ~n); 817#L22 call #t~ret4 := fibonacci(~n - 1);< 801#$Ultimate##0 ~n := #in~n; 885#L17 assume !(~n < 1); 814#L19 assume 1 == ~n;#res := 1; 818#fibonacciFINAL assume true; 875#fibonacciEXIT >#31#return; 815#L22-1 call #t~ret5 := fibonacci(~n - 2);< 801#$Ultimate##0 ~n := #in~n; 885#L17 assume ~n < 1;#res := 0; 884#fibonacciFINAL assume true; 883#fibonacciEXIT >#33#return; 876#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 882#fibonacciFINAL assume true; 880#fibonacciEXIT >#33#return; 876#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 882#fibonacciFINAL assume true; 880#fibonacciEXIT >#31#return; 815#L22-1 [2023-11-28 23:44:05,664 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:05,664 INFO L85 PathProgramCache]: Analyzing trace with hash 3324437, now seen corresponding path program 1 times [2023-11-28 23:44:05,664 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:05,664 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [754532605] [2023-11-28 23:44:05,664 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:05,664 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:05,679 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:05,795 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2023-11-28 23:44:05,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:05,852 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-28 23:44:05,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:05,874 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2023-11-28 23:44:05,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:05,882 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-11-28 23:44:05,882 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-28 23:44:05,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [754532605] [2023-11-28 23:44:05,882 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [754532605] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-28 23:44:05,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [278278391] [2023-11-28 23:44:05,882 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:05,883 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-28 23:44:05,883 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:05,884 INFO L229 MonitoredProcess]: Starting monitored process 17 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-28 23:44:05,889 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-11-28 23:44:05,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:05,937 INFO L262 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-28 23:44:05,940 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:06,001 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-11-28 23:44:06,001 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-28 23:44:06,284 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2023-11-28 23:44:06,284 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [278278391] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-28 23:44:06,284 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-28 23:44:06,284 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2023-11-28 23:44:06,284 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [885456065] [2023-11-28 23:44:06,285 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-28 23:44:06,285 INFO L753 eck$LassoCheckResult]: stem already infeasible [2023-11-28 23:44:06,285 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:06,286 INFO L85 PathProgramCache]: Analyzing trace with hash -929430729, now seen corresponding path program 1 times [2023-11-28 23:44:06,286 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:06,286 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [409921982] [2023-11-28 23:44:06,286 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:06,286 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:06,295 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:06,318 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2023-11-28 23:44:06,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:06,348 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2023-11-28 23:44:06,363 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-28 23:44:06,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:06,381 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2023-11-28 23:44:06,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:06,419 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-28 23:44:06,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:06,424 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2023-11-28 23:44:06,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:06,431 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 26 proven. 13 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2023-11-28 23:44:06,431 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-28 23:44:06,431 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [409921982] [2023-11-28 23:44:06,431 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [409921982] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-28 23:44:06,431 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [495989666] [2023-11-28 23:44:06,431 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:06,432 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-28 23:44:06,432 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:06,433 INFO L229 MonitoredProcess]: Starting monitored process 18 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-28 23:44:06,438 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2023-11-28 23:44:06,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:06,478 INFO L262 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 6 conjunts are in the unsatisfiable core [2023-11-28 23:44:06,480 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:06,524 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 25 proven. 15 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2023-11-28 23:44:06,524 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-28 23:44:06,682 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 25 proven. 15 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2023-11-28 23:44:06,683 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [495989666] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-28 23:44:06,683 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-28 23:44:06,683 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2023-11-28 23:44:06,683 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1515550890] [2023-11-28 23:44:06,683 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-28 23:44:06,684 INFO L765 eck$LassoCheckResult]: loop already infeasible [2023-11-28 23:44:06,684 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-28 23:44:06,684 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2023-11-28 23:44:06,685 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2023-11-28 23:44:06,685 INFO L87 Difference]: Start difference. First operand 106 states and 141 transitions. cyclomatic complexity: 40 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) [2023-11-28 23:44:07,033 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-28 23:44:07,033 INFO L93 Difference]: Finished difference Result 174 states and 225 transitions. [2023-11-28 23:44:07,033 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 174 states and 225 transitions. [2023-11-28 23:44:07,038 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 15 [2023-11-28 23:44:07,043 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 174 states to 163 states and 214 transitions. [2023-11-28 23:44:07,043 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 110 [2023-11-28 23:44:07,043 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 110 [2023-11-28 23:44:07,044 INFO L73 IsDeterministic]: Start isDeterministic. Operand 163 states and 214 transitions. [2023-11-28 23:44:07,045 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-11-28 23:44:07,045 INFO L218 hiAutomatonCegarLoop]: Abstraction has 163 states and 214 transitions. [2023-11-28 23:44:07,045 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states and 214 transitions. [2023-11-28 23:44:07,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 163. [2023-11-28 23:44:07,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 163 states, 102 states have (on average 1.1470588235294117) internal successors, (117), 108 states have internal predecessors, (117), 39 states have call successors, (40), 21 states have call predecessors, (40), 22 states have return successors, (57), 33 states have call predecessors, (57), 36 states have call successors, (57) [2023-11-28 23:44:07,060 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 214 transitions. [2023-11-28 23:44:07,060 INFO L240 hiAutomatonCegarLoop]: Abstraction has 163 states and 214 transitions. [2023-11-28 23:44:07,060 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2023-11-28 23:44:07,061 INFO L428 stractBuchiCegarLoop]: Abstraction has 163 states and 214 transitions. [2023-11-28 23:44:07,061 INFO L335 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2023-11-28 23:44:07,061 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 163 states and 214 transitions. [2023-11-28 23:44:07,063 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 15 [2023-11-28 23:44:07,063 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2023-11-28 23:44:07,063 INFO L119 BuchiIsEmpty]: Starting construction of run [2023-11-28 23:44:07,065 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 9, 8, 8, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-28 23:44:07,066 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2023-11-28 23:44:07,066 INFO L748 eck$LassoCheckResult]: Stem: 1620#$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); 1621#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; 1601#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 1622#$Ultimate##0 ~n := #in~n; 1610#L17 assume !(~n < 1); 1611#L19 assume !(1 == ~n); 1614#L22 call #t~ret4 := fibonacci(~n - 1);< 1615#$Ultimate##0 ~n := #in~n; 1635#L17 assume !(~n < 1); 1678#L19 assume !(1 == ~n); 1674#L22 call #t~ret4 := fibonacci(~n - 1);< 1677#$Ultimate##0 ~n := #in~n; 1676#L17 assume !(~n < 1); 1675#L19 assume !(1 == ~n); 1670#L22 call #t~ret4 := fibonacci(~n - 1);< 1673#$Ultimate##0 ~n := #in~n; 1672#L17 assume !(~n < 1); 1671#L19 assume !(1 == ~n); 1666#L22 call #t~ret4 := fibonacci(~n - 1);< 1669#$Ultimate##0 ~n := #in~n; 1668#L17 assume !(~n < 1); 1667#L19 assume !(1 == ~n); 1662#L22 call #t~ret4 := fibonacci(~n - 1);< 1665#$Ultimate##0 ~n := #in~n; 1664#L17 assume !(~n < 1); 1663#L19 assume !(1 == ~n); 1652#L22 call #t~ret4 := fibonacci(~n - 1);< 1656#$Ultimate##0 ~n := #in~n; 1660#L17 assume !(~n < 1); 1658#L19 assume !(1 == ~n); 1653#L22 call #t~ret4 := fibonacci(~n - 1);< 1656#$Ultimate##0 ~n := #in~n; 1660#L17 assume !(~n < 1); 1658#L19 assume !(1 == ~n); 1653#L22 call #t~ret4 := fibonacci(~n - 1);< 1656#$Ultimate##0 ~n := #in~n; 1661#L17 assume !(~n < 1); 1659#L19 assume 1 == ~n;#res := 1; 1657#fibonacciFINAL assume true; 1655#fibonacciEXIT >#31#return; 1604#L22-1 call #t~ret5 := fibonacci(~n - 2);< 1654#$Ultimate##0 ~n := #in~n; 1741#L17 assume ~n < 1;#res := 0; 1740#fibonacciFINAL assume true; 1737#fibonacciEXIT >#33#return; 1736#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1735#fibonacciFINAL assume true; 1719#fibonacciEXIT >#31#return; 1707#L22-1 [2023-11-28 23:44:07,066 INFO L750 eck$LassoCheckResult]: Loop: 1707#L22-1 call #t~ret5 := fibonacci(~n - 2);< 1727#$Ultimate##0 ~n := #in~n; 1747#L17 assume !(~n < 1); 1746#L19 assume !(1 == ~n); 1711#L22 call #t~ret4 := fibonacci(~n - 1);< 1727#$Ultimate##0 ~n := #in~n; 1747#L17 assume !(~n < 1); 1746#L19 assume !(1 == ~n); 1711#L22 call #t~ret4 := fibonacci(~n - 1);< 1727#$Ultimate##0 ~n := #in~n; 1747#L17 assume !(~n < 1); 1746#L19 assume 1 == ~n;#res := 1; 1743#fibonacciFINAL assume true; 1704#fibonacciEXIT >#31#return; 1710#L22-1 call #t~ret5 := fibonacci(~n - 2);< 1729#$Ultimate##0 ~n := #in~n; 1744#L17 assume ~n < 1;#res := 0; 1745#fibonacciFINAL assume true; 1752#fibonacciEXIT >#33#return; 1713#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1749#fibonacciFINAL assume true; 1720#fibonacciEXIT >#31#return; 1707#L22-1 [2023-11-28 23:44:07,066 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:07,066 INFO L85 PathProgramCache]: Analyzing trace with hash -407339347, now seen corresponding path program 2 times [2023-11-28 23:44:07,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:07,067 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1120783223] [2023-11-28 23:44:07,067 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:07,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:07,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:07,080 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-28 23:44:07,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:07,094 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-28 23:44:07,094 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:07,095 INFO L85 PathProgramCache]: Analyzing trace with hash -1749360471, now seen corresponding path program 2 times [2023-11-28 23:44:07,095 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:07,095 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [366154646] [2023-11-28 23:44:07,095 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:07,095 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:07,100 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:07,100 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2023-11-28 23:44:07,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2023-11-28 23:44:07,105 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2023-11-28 23:44:07,106 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:07,106 INFO L85 PathProgramCache]: Analyzing trace with hash -1472997803, now seen corresponding path program 3 times [2023-11-28 23:44:07,106 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-28 23:44:07,106 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1680289549] [2023-11-28 23:44:07,106 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-28 23:44:07,106 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-28 23:44:07,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:07,400 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2023-11-28 23:44:07,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:07,408 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-28 23:44:07,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:07,411 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2023-11-28 23:44:07,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:07,413 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 52 [2023-11-28 23:44:07,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:07,419 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2023-11-28 23:44:07,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:07,421 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2023-11-28 23:44:07,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:07,424 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 122 proven. 136 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2023-11-28 23:44:07,424 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-28 23:44:07,424 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1680289549] [2023-11-28 23:44:07,424 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1680289549] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-28 23:44:07,425 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [914807436] [2023-11-28 23:44:07,425 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-28 23:44:07,425 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-28 23:44:07,425 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:07,426 INFO L229 MonitoredProcess]: Starting monitored process 19 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-11-28 23:44:07,430 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2023-11-28 23:44:07,496 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2023-11-28 23:44:07,496 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-28 23:44:07,497 INFO L262 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 12 conjunts are in the unsatisfiable core [2023-11-28 23:44:07,500 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:07,635 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 113 proven. 47 refuted. 0 times theorem prover too weak. 167 trivial. 0 not checked. [2023-11-28 23:44:07,635 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-28 23:44:08,023 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 113 proven. 49 refuted. 0 times theorem prover too weak. 165 trivial. 0 not checked. [2023-11-28 23:44:08,024 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [914807436] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-28 23:44:08,024 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-28 23:44:08,024 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 10, 12] total 31 [2023-11-28 23:44:08,024 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1622543533] [2023-11-28 23:44:08,025 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-28 23:44:08,236 INFO L210 LassoAnalysis]: Preferences: [2023-11-28 23:44:08,236 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-11-28 23:44:08,236 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-11-28 23:44:08,236 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-11-28 23:44:08,237 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2023-11-28 23:44:08,237 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,237 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-11-28 23:44:08,237 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-11-28 23:44:08,237 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2023-11-28 23:44:08,237 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-11-28 23:44:08,237 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-11-28 23:44:08,238 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,241 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,243 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,246 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,248 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,285 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-11-28 23:44:08,285 INFO L404 LassoAnalysis]: Checking for nontermination... [2023-11-28 23:44:08,285 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,285 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,288 INFO L229 MonitoredProcess]: Starting monitored process 20 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,290 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2023-11-28 23:44:08,290 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:08,291 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:08,304 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-11-28 23:44:08,304 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=1} Honda state: {fibonacci_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-11-28 23:44:08,306 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2023-11-28 23:44:08,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,307 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,308 INFO L229 MonitoredProcess]: Starting monitored process 21 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,310 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2023-11-28 23:44:08,311 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:08,311 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:08,323 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-11-28 23:44:08,323 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#in~n=3} Honda state: {fibonacci_#in~n=3} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-11-28 23:44:08,325 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2023-11-28 23:44:08,326 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,326 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,327 INFO L229 MonitoredProcess]: Starting monitored process 22 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,329 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2023-11-28 23:44:08,330 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:08,330 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:08,342 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-11-28 23:44:08,342 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-11-28 23:44:08,344 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2023-11-28 23:44:08,345 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,345 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,346 INFO L229 MonitoredProcess]: Starting monitored process 23 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,348 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2023-11-28 23:44:08,349 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:08,349 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:08,361 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2023-11-28 23:44:08,361 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2023-11-28 23:44:08,364 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2023-11-28 23:44:08,365 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,365 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,366 INFO L229 MonitoredProcess]: Starting monitored process 24 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,374 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2023-11-28 23:44:08,374 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:08,382 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2023-11-28 23:44:08,389 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2023-11-28 23:44:08,390 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,390 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,391 INFO L229 MonitoredProcess]: Starting monitored process 25 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,391 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2023-11-28 23:44:08,393 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2023-11-28 23:44:08,394 INFO L160 nArgumentSynthesizer]: Using integer mode. [2023-11-28 23:44:08,409 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2023-11-28 23:44:08,412 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2023-11-28 23:44:08,412 INFO L210 LassoAnalysis]: Preferences: [2023-11-28 23:44:08,413 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2023-11-28 23:44:08,413 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2023-11-28 23:44:08,413 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2023-11-28 23:44:08,413 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2023-11-28 23:44:08,413 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,413 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2023-11-28 23:44:08,413 INFO L132 ssoRankerPreferences]: Path of dumped script: [2023-11-28 23:44:08,413 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2023-11-28 23:44:08,413 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2023-11-28 23:44:08,413 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2023-11-28 23:44:08,414 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,417 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,419 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,421 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,426 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2023-11-28 23:44:08,461 INFO L294 LassoAnalysis]: Preprocessing complete. [2023-11-28 23:44:08,461 INFO L490 LassoAnalysis]: Using template 'affine'. [2023-11-28 23:44:08,461 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,462 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,462 INFO L229 MonitoredProcess]: Starting monitored process 26 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,465 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2023-11-28 23:44:08,465 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 [2023-11-28 23:44:08,475 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-11-28 23:44:08,475 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-11-28 23:44:08,475 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-11-28 23:44:08,475 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-11-28 23:44:08,476 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-11-28 23:44:08,476 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-11-28 23:44:08,476 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-11-28 23:44:08,478 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-11-28 23:44:08,481 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2023-11-28 23:44:08,481 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,481 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,482 INFO L229 MonitoredProcess]: Starting monitored process 27 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,482 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2023-11-28 23:44:08,484 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 [2023-11-28 23:44:08,494 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-11-28 23:44:08,494 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-11-28 23:44:08,494 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-11-28 23:44:08,494 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-11-28 23:44:08,494 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-11-28 23:44:08,495 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-11-28 23:44:08,495 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-11-28 23:44:08,497 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-11-28 23:44:08,499 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2023-11-28 23:44:08,499 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,499 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,500 INFO L229 MonitoredProcess]: Starting monitored process 28 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,501 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2023-11-28 23:44:08,502 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 [2023-11-28 23:44:08,512 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-11-28 23:44:08,512 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-11-28 23:44:08,512 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-11-28 23:44:08,512 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-11-28 23:44:08,512 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-11-28 23:44:08,513 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-11-28 23:44:08,513 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-11-28 23:44:08,521 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2023-11-28 23:44:08,523 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2023-11-28 23:44:08,523 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,523 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,524 INFO L229 MonitoredProcess]: Starting monitored process 29 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,526 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2023-11-28 23:44:08,527 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 [2023-11-28 23:44:08,536 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2023-11-28 23:44:08,537 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2023-11-28 23:44:08,537 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2023-11-28 23:44:08,537 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2023-11-28 23:44:08,537 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2023-11-28 23:44:08,538 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2023-11-28 23:44:08,538 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2023-11-28 23:44:08,540 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2023-11-28 23:44:08,543 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2023-11-28 23:44:08,543 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2023-11-28 23:44:08,543 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2023-11-28 23:44:08,543 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 [2023-11-28 23:44:08,553 INFO L229 MonitoredProcess]: Starting monitored process 30 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2023-11-28 23:44:08,554 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2023-11-28 23:44:08,554 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2023-11-28 23:44:08,554 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2023-11-28 23:44:08,554 INFO L513 LassoAnalysis]: Proved termination. [2023-11-28 23:44:08,554 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2023-11-28 23:44:08,557 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2023-11-28 23:44:08,557 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2023-11-28 23:44:08,568 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:08,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:08,636 INFO L262 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 22 conjunts are in the unsatisfiable core [2023-11-28 23:44:08,640 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:08,831 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2023-11-28 23:44:08,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:08,892 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-28 23:44:08,894 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:09,012 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-28 23:44:09,012 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 [2023-11-28 23:44:09,013 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 163 states and 214 transitions. cyclomatic complexity: 57 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-28 23:44:09,251 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 163 states and 214 transitions. cyclomatic complexity: 57. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 296 states and 402 transitions. Complement of second has 45 states. [2023-11-28 23:44:09,253 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 [2023-11-28 23:44:09,254 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-28 23:44:09,254 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 41 transitions. [2023-11-28 23:44:09,255 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 41 transitions. Stem has 48 letters. Loop has 22 letters. [2023-11-28 23:44:09,255 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:09,255 INFO L681 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2023-11-28 23:44:09,265 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:09,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:09,328 INFO L262 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 22 conjunts are in the unsatisfiable core [2023-11-28 23:44:09,330 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:09,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:09,544 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-28 23:44:09,546 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:09,663 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-28 23:44:09,664 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2023-11-28 23:44:09,664 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 163 states and 214 transitions. cyclomatic complexity: 57 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-28 23:44:09,812 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 163 states and 214 transitions. cyclomatic complexity: 57. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 357 states and 475 transitions. Complement of second has 25 states. [2023-11-28 23:44:09,813 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 [2023-11-28 23:44:09,814 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-28 23:44:09,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 24 transitions. [2023-11-28 23:44:09,814 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 24 transitions. Stem has 48 letters. Loop has 22 letters. [2023-11-28 23:44:09,814 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:09,815 INFO L681 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2023-11-28 23:44:09,824 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-28 23:44:09,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:09,888 INFO L262 TraceCheckSpWp]: Trace formula consists of 398 conjuncts, 22 conjunts are in the unsatisfiable core [2023-11-28 23:44:09,890 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:10,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-28 23:44:10,110 INFO L262 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2023-11-28 23:44:10,112 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-28 23:44:10,225 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-28 23:44:10,225 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2023-11-28 23:44:10,226 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 163 states and 214 transitions. cyclomatic complexity: 57 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-28 23:44:10,475 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 163 states and 214 transitions. cyclomatic complexity: 57. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 1307 states and 1827 transitions. Complement of second has 138 states. [2023-11-28 23:44:10,475 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 [2023-11-28 23:44:10,476 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2023-11-28 23:44:10,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 46 transitions. [2023-11-28 23:44:10,477 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 48 letters. Loop has 22 letters. [2023-11-28 23:44:10,479 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:10,479 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 70 letters. Loop has 22 letters. [2023-11-28 23:44:10,481 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:10,481 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 48 letters. Loop has 44 letters. [2023-11-28 23:44:10,483 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2023-11-28 23:44:10,484 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 1307 states and 1827 transitions. [2023-11-28 23:44:10,509 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 58 [2023-11-28 23:44:10,528 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 1307 states to 789 states and 1177 transitions. [2023-11-28 23:44:10,528 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 305 [2023-11-28 23:44:10,529 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 344 [2023-11-28 23:44:10,529 INFO L73 IsDeterministic]: Start isDeterministic. Operand 789 states and 1177 transitions. [2023-11-28 23:44:10,530 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2023-11-28 23:44:10,530 INFO L218 hiAutomatonCegarLoop]: Abstraction has 789 states and 1177 transitions. [2023-11-28 23:44:10,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 789 states and 1177 transitions. [2023-11-28 23:44:10,568 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 789 to 637. [2023-11-28 23:44:10,570 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 637 states, 388 states have (on average 1.1623711340206186) internal successors, (451), 413 states have internal predecessors, (451), 153 states have call successors, (167), 77 states have call predecessors, (167), 96 states have return successors, (281), 146 states have call predecessors, (281), 142 states have call successors, (281) [2023-11-28 23:44:10,577 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 637 states to 637 states and 899 transitions. [2023-11-28 23:44:10,577 INFO L240 hiAutomatonCegarLoop]: Abstraction has 637 states and 899 transitions. [2023-11-28 23:44:10,578 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-28 23:44:10,578 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2023-11-28 23:44:10,579 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=165, Invalid=765, Unknown=0, NotChecked=0, Total=930 [2023-11-28 23:44:10,579 INFO L87 Difference]: Start difference. First operand 637 states and 899 transitions. Second operand has 31 states, 29 states have (on average 2.2758620689655173) internal successors, (66), 24 states have internal predecessors, (66), 17 states have call successors, (23), 10 states have call predecessors, (23), 6 states have return successors, (15), 9 states have call predecessors, (15), 10 states have call successors, (15) [2023-11-28 23:44:11,350 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-28 23:44:11,350 INFO L93 Difference]: Finished difference Result 533 states and 626 transitions. [2023-11-28 23:44:11,350 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 533 states and 626 transitions. [2023-11-28 23:44:11,358 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2023-11-28 23:44:11,358 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 533 states to 0 states and 0 transitions. [2023-11-28 23:44:11,358 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2023-11-28 23:44:11,358 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2023-11-28 23:44:11,358 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2023-11-28 23:44:11,358 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2023-11-28 23:44:11,358 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-11-28 23:44:11,358 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-11-28 23:44:11,358 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2023-11-28 23:44:11,359 INFO L428 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2023-11-28 23:44:11,359 INFO L335 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2023-11-28 23:44:11,359 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2023-11-28 23:44:11,359 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2023-11-28 23:44:11,359 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2023-11-28 23:44:11,366 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 28.11 11:44:11 BoogieIcfgContainer [2023-11-28 23:44:11,366 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2023-11-28 23:44:11,367 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2023-11-28 23:44:11,367 INFO L270 PluginConnector]: Initializing Witness Printer... [2023-11-28 23:44:11,367 INFO L274 PluginConnector]: Witness Printer initialized [2023-11-28 23:44:11,368 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.11 11:44:02" (3/4) ... [2023-11-28 23:44:11,369 INFO L140 WitnessPrinter]: No result that supports witness generation found [2023-11-28 23:44:11,370 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2023-11-28 23:44:11,371 INFO L158 Benchmark]: Toolchain (without parser) took 8880.05ms. Allocated memory was 146.8MB in the beginning and 188.7MB in the end (delta: 41.9MB). Free memory was 102.0MB in the beginning and 136.2MB in the end (delta: -34.2MB). Peak memory consumption was 9.2MB. Max. memory is 16.1GB. [2023-11-28 23:44:11,371 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 100.7MB. Free memory is still 54.6MB. There was no memory consumed. Max. memory is 16.1GB. [2023-11-28 23:44:11,371 INFO L158 Benchmark]: CACSL2BoogieTranslator took 219.46ms. Allocated memory is still 146.8MB. Free memory was 102.0MB in the beginning and 92.1MB in the end (delta: 9.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2023-11-28 23:44:11,372 INFO L158 Benchmark]: Boogie Procedure Inliner took 29.62ms. Allocated memory is still 146.8MB. Free memory was 92.1MB in the beginning and 90.5MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-11-28 23:44:11,372 INFO L158 Benchmark]: Boogie Preprocessor took 30.12ms. Allocated memory is still 146.8MB. Free memory was 90.5MB in the beginning and 88.9MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-11-28 23:44:11,373 INFO L158 Benchmark]: RCFGBuilder took 208.40ms. Allocated memory is still 146.8MB. Free memory was 88.9MB in the beginning and 80.0MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2023-11-28 23:44:11,373 INFO L158 Benchmark]: BuchiAutomizer took 8383.93ms. Allocated memory was 146.8MB in the beginning and 188.7MB in the end (delta: 41.9MB). Free memory was 80.0MB in the beginning and 137.3MB in the end (delta: -57.3MB). There was no memory consumed. Max. memory is 16.1GB. [2023-11-28 23:44:11,373 INFO L158 Benchmark]: Witness Printer took 3.22ms. Allocated memory is still 188.7MB. Free memory was 137.3MB in the beginning and 136.2MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2023-11-28 23:44:11,375 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.13ms. Allocated memory is still 100.7MB. Free memory is still 54.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 219.46ms. Allocated memory is still 146.8MB. Free memory was 102.0MB in the beginning and 92.1MB in the end (delta: 9.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 29.62ms. Allocated memory is still 146.8MB. Free memory was 92.1MB in the beginning and 90.5MB in the end (delta: 1.5MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 30.12ms. Allocated memory is still 146.8MB. Free memory was 90.5MB in the beginning and 88.9MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 208.40ms. Allocated memory is still 146.8MB. Free memory was 88.9MB in the beginning and 80.0MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 8383.93ms. Allocated memory was 146.8MB in the beginning and 188.7MB in the end (delta: 41.9MB). Free memory was 80.0MB in the beginning and 137.3MB in the end (delta: -57.3MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 3.22ms. Allocated memory is still 188.7MB. Free memory was 137.3MB in the beginning and 136.2MB in the end (delta: 1.1MB). Peak memory consumption was 2.1MB. 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 7 terminating modules (4 trivial, 2 deterministic, 1 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 4 locations. One deterministic module has affine ranking function n and consists of 9 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. 4 modules have a trivial ranking function, the largest among these consists of 31 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 8.3s and 6 iterations. TraceHistogramMax:10. Analysis of lassos took 4.1s. Construction of modules took 0.8s. Büchi inclusion checks took 3.0s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 6. Automata minimization 0.1s AutomataMinimizationTime, 6 MinimizatonAttempts, 183 StatesRemovedByMinimization, 4 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 1, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 583 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 567 mSDsluCounter, 442 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 296 mSDsCounter, 396 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1125 IncrementalHoareTripleChecker+Invalid, 1521 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 396 mSolverCounterUnsat, 146 mSDtfsCounter, 1125 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT1 SILN0 SILU0 SILI2 SILT1 lasso0 LassoPreprocessingBenchmarks: Lassos: inital14 mio100 ax100 hnf100 lsp71 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq190 hnf90 smp88 dnf100 smp100 tf113 neg100 sie103 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 25ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 7 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 3 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.3s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2023-11-28 23:44:11,390 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2023-11-28 23:44:11,589 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Ended with exit code 0 [2023-11-28 23:44:11,789 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2023-11-28 23:44:11,989 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2023-11-28 23:44:12,190 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_14ab7ec6-0b6d-4d24-9d81-92a2c19ef509/bin/uautomizer-verify-BQ2R08f2Ya/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE