./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/termination-numeric/Fibonacci01-2.c --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version ae007674 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/termination-numeric/Fibonacci01-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --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 64bit --witnessprinter.graph.data.programhash 14cfbc3a2ba2bfe3a03d4d1ebff24b0baf1851f06dbbd2468b59e09322e4ce16 --- Real Ultimate output --- This is Ultimate 0.2.2-dev-ae00767 [2021-12-28 09:03:25,623 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-28 09:03:25,624 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-28 09:03:25,649 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-28 09:03:25,650 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-28 09:03:25,650 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-28 09:03:25,651 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-28 09:03:25,652 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-28 09:03:25,653 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-28 09:03:25,654 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-28 09:03:25,654 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-28 09:03:25,655 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-28 09:03:25,655 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-28 09:03:25,656 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-28 09:03:25,656 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-28 09:03:25,657 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-28 09:03:25,658 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-28 09:03:25,658 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-28 09:03:25,659 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-28 09:03:25,660 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-28 09:03:25,661 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-28 09:03:25,662 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-28 09:03:25,663 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-28 09:03:25,663 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-28 09:03:25,665 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-28 09:03:25,665 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-28 09:03:25,665 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-28 09:03:25,666 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-28 09:03:25,666 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-28 09:03:25,667 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-28 09:03:25,667 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-28 09:03:25,667 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-28 09:03:25,668 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-28 09:03:25,668 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-28 09:03:25,669 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-28 09:03:25,669 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-28 09:03:25,669 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-28 09:03:25,670 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-28 09:03:25,670 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-28 09:03:25,670 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-28 09:03:25,671 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-28 09:03:25,671 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2021-12-28 09:03:25,692 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-28 09:03:25,692 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-28 09:03:25,692 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-28 09:03:25,693 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-28 09:03:25,693 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-28 09:03:25,693 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-28 09:03:25,694 INFO L138 SettingsManager]: * Use SBE=true [2021-12-28 09:03:25,694 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2021-12-28 09:03:25,694 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2021-12-28 09:03:25,694 INFO L138 SettingsManager]: * Use old map elimination=false [2021-12-28 09:03:25,694 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2021-12-28 09:03:25,694 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2021-12-28 09:03:25,695 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2021-12-28 09:03:25,695 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-28 09:03:25,695 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-28 09:03:25,695 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-28 09:03:25,695 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-28 09:03:25,695 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2021-12-28 09:03:25,695 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2021-12-28 09:03:25,695 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2021-12-28 09:03:25,696 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-28 09:03:25,696 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2021-12-28 09:03:25,696 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-28 09:03:25,696 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2021-12-28 09:03:25,696 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-28 09:03:25,696 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-28 09:03:25,696 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-28 09:03:25,697 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-28 09:03:25,697 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2021-12-28 09:03:25,697 INFO L138 SettingsManager]: * TransformationType=MODULO_NEIGHBOR WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml 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 -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 14cfbc3a2ba2bfe3a03d4d1ebff24b0baf1851f06dbbd2468b59e09322e4ce16 [2021-12-28 09:03:25,914 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-28 09:03:25,934 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-28 09:03:25,936 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-28 09:03:25,937 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-28 09:03:25,939 INFO L275 PluginConnector]: CDTParser initialized [2021-12-28 09:03:25,940 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-numeric/Fibonacci01-2.c [2021-12-28 09:03:25,986 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/69518beba/e5753452e55a4a79a0e81d530890eef7/FLAG4d4afc767 [2021-12-28 09:03:26,283 INFO L306 CDTParser]: Found 1 translation units. [2021-12-28 09:03:26,283 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-numeric/Fibonacci01-2.c [2021-12-28 09:03:26,287 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/69518beba/e5753452e55a4a79a0e81d530890eef7/FLAG4d4afc767 [2021-12-28 09:03:26,716 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/69518beba/e5753452e55a4a79a0e81d530890eef7 [2021-12-28 09:03:26,717 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-28 09:03:26,718 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-28 09:03:26,719 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-28 09:03:26,719 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-28 09:03:26,725 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-28 09:03:26,726 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,727 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7553874f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26, skipping insertion in model container [2021-12-28 09:03:26,727 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,732 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-28 09:03:26,740 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-28 09:03:26,814 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-numeric/Fibonacci01-2.c[761,774] [2021-12-28 09:03:26,815 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-28 09:03:26,820 INFO L203 MainTranslator]: Completed pre-run [2021-12-28 09:03:26,828 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-numeric/Fibonacci01-2.c[761,774] [2021-12-28 09:03:26,828 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-28 09:03:26,835 INFO L208 MainTranslator]: Completed translation [2021-12-28 09:03:26,836 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26 WrapperNode [2021-12-28 09:03:26,836 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-28 09:03:26,837 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-28 09:03:26,837 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-28 09:03:26,837 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-28 09:03:26,841 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,845 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,853 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 24 [2021-12-28 09:03:26,853 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-28 09:03:26,854 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-28 09:03:26,854 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-28 09:03:26,854 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-28 09:03:26,858 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,859 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,859 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,859 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,861 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,862 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,862 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,863 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-28 09:03:26,863 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-28 09:03:26,864 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-28 09:03:26,864 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-28 09:03:26,864 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (1/1) ... [2021-12-28 09:03:26,895 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:26,901 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:26,924 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:26,942 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2021-12-28 09:03:26,952 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2021-12-28 09:03:26,952 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2021-12-28 09:03:26,953 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-28 09:03:26,953 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-28 09:03:26,953 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-28 09:03:26,953 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-28 09:03:26,998 INFO L234 CfgBuilder]: Building ICFG [2021-12-28 09:03:26,999 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-28 09:03:27,073 INFO L275 CfgBuilder]: Performing block encoding [2021-12-28 09:03:27,076 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-28 09:03:27,077 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2021-12-28 09:03:27,078 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.12 09:03:27 BoogieIcfgContainer [2021-12-28 09:03:27,078 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-28 09:03:27,079 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2021-12-28 09:03:27,079 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2021-12-28 09:03:27,081 INFO L275 PluginConnector]: BuchiAutomizer initialized [2021-12-28 09:03:27,081 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-28 09:03:27,081 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 28.12 09:03:26" (1/3) ... [2021-12-28 09:03:27,082 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@3c24ccab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 28.12 09:03:27, skipping insertion in model container [2021-12-28 09:03:27,082 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-28 09:03:27,082 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 28.12 09:03:26" (2/3) ... [2021-12-28 09:03:27,082 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@3c24ccab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 28.12 09:03:27, skipping insertion in model container [2021-12-28 09:03:27,083 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-28 09:03:27,083 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.12 09:03:27" (3/3) ... [2021-12-28 09:03:27,084 INFO L388 chiAutomizerObserver]: Analyzing ICFG Fibonacci01-2.c [2021-12-28 09:03:27,125 INFO L359 BuchiCegarLoop]: Interprodecural is true [2021-12-28 09:03:27,139 INFO L360 BuchiCegarLoop]: Hoare is false [2021-12-28 09:03:27,139 INFO L361 BuchiCegarLoop]: Compute interpolants for ForwardPredicates [2021-12-28 09:03:27,139 INFO L362 BuchiCegarLoop]: Backedges is STRAIGHT_LINE [2021-12-28 09:03:27,139 INFO L363 BuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-12-28 09:03:27,139 INFO L364 BuchiCegarLoop]: Difference is false [2021-12-28 09:03:27,139 INFO L365 BuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-12-28 09:03:27,140 INFO L368 BuchiCegarLoop]: ======== Iteration 0==of CEGAR loop == BuchiCegarLoop======== [2021-12-28 09:03:27,160 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2021-12-28 09:03:27,174 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-28 09:03:27,174 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-28 09:03:27,174 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-28 09:03:27,178 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1, 1] [2021-12-28 09:03:27,178 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-28 09:03:27,178 INFO L425 BuchiCegarLoop]: ======== Iteration 1============ [2021-12-28 09:03:27,179 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2021-12-28 09:03:27,181 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-28 09:03:27,181 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-28 09:03:27,181 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-28 09:03:27,181 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1, 1] [2021-12-28 09:03:27,181 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-28 09:03:27,198 INFO L791 eck$LassoCheckResult]: Stem: 7#ULTIMATE.startENTRYtrue assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(16, 2);call #Ultimate.allocInit(12, 3); 13#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 10#L29true assume !(main_~x~0#1 < 1); 12#L31true call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 5#fibonacciENTRYtrue [2021-12-28 09:03:27,199 INFO L793 eck$LassoCheckResult]: Loop: 5#fibonacciENTRYtrue ~n := #in~n; 6#L17true assume !(~n < 1); 18#L19true assume !(1 == ~n); 16#L22true call #t~ret4 := fibonacci(~n - 1);< 5#fibonacciENTRYtrue [2021-12-28 09:03:27,202 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:27,210 INFO L85 PathProgramCache]: Analyzing trace with hash 1325876, now seen corresponding path program 1 times [2021-12-28 09:03:27,221 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:27,221 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [855077949] [2021-12-28 09:03:27,221 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:27,222 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:27,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:27,303 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-28 09:03:27,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:27,355 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-28 09:03:27,357 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:27,358 INFO L85 PathProgramCache]: Analyzing trace with hash 927646, now seen corresponding path program 1 times [2021-12-28 09:03:27,358 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:27,359 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1868196113] [2021-12-28 09:03:27,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:27,360 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:27,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:27,367 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-28 09:03:27,371 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:27,373 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-28 09:03:27,374 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:27,374 INFO L85 PathProgramCache]: Analyzing trace with hash 408654161, now seen corresponding path program 1 times [2021-12-28 09:03:27,374 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:27,375 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1346448921] [2021-12-28 09:03:27,375 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:27,375 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:27,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:27,395 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-28 09:03:27,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:27,409 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-28 09:03:27,520 INFO L210 LassoAnalysis]: Preferences: [2021-12-28 09:03:27,520 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-28 09:03:27,521 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-28 09:03:27,521 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-28 09:03:27,521 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-28 09:03:27,521 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:27,521 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-28 09:03:27,522 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-28 09:03:27,522 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration1_Loop [2021-12-28 09:03:27,522 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-28 09:03:27,522 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-28 09:03:27,531 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,535 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,537 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,539 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,546 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,607 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-28 09:03:27,610 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-28 09:03:27,611 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:27,618 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:27,625 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:27,643 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2021-12-28 09:03:27,645 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:27,646 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:27,669 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:27,669 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:27,684 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2021-12-28 09:03:27,684 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:27,684 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:27,685 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:27,686 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2021-12-28 09:03:27,692 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:27,693 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:27,713 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:27,714 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:27,737 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:27,737 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:27,737 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:27,738 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:27,739 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2021-12-28 09:03:27,740 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:27,740 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:27,761 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:27,761 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:27,779 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:27,779 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:27,780 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:27,796 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:27,797 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2021-12-28 09:03:27,798 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:27,798 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:27,836 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:27,837 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:27,837 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:27,838 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:27,854 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2021-12-28 09:03:27,855 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-28 09:03:27,855 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:27,914 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-28 09:03:27,919 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:27,919 INFO L210 LassoAnalysis]: Preferences: [2021-12-28 09:03:27,919 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-28 09:03:27,919 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-28 09:03:27,919 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-28 09:03:27,919 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-28 09:03:27,919 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:27,920 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-28 09:03:27,920 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-28 09:03:27,920 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration1_Loop [2021-12-28 09:03:27,920 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-28 09:03:27,920 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-28 09:03:27,920 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,923 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,924 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,926 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,932 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:27,972 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-28 09:03:27,975 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-28 09:03:27,976 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:27,976 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:27,977 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:27,998 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 [2021-12-28 09:03:27,998 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2021-12-28 09:03:28,004 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:28,005 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:28,005 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:28,005 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:28,005 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:28,006 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:28,007 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:28,011 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-28 09:03:28,028 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:28,028 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:28,028 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:28,029 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:28,030 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2021-12-28 09:03:28,031 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 [2021-12-28 09:03:28,036 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:28,036 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:28,037 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:28,037 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:28,037 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:28,037 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:28,037 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:28,040 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-28 09:03:28,056 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:28,056 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:28,057 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:28,057 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:28,058 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2021-12-28 09:03:28,059 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 [2021-12-28 09:03:28,065 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:28,066 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:28,066 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:28,066 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:28,066 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:28,066 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:28,066 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:28,073 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-28 09:03:28,088 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:28,088 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:28,088 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:28,089 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:28,090 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2021-12-28 09:03:28,091 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 [2021-12-28 09:03:28,097 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:28,097 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:28,097 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:28,098 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:28,098 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:28,098 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:28,099 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:28,113 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-28 09:03:28,116 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-28 09:03:28,116 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-28 09:03:28,117 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:28,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:28,118 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:28,120 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2021-12-28 09:03:28,120 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-28 09:03:28,120 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-28 09:03:28,120 INFO L513 LassoAnalysis]: Proved termination. [2021-12-28 09:03:28,121 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2021-12-28 09:03:28,148 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:28,150 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-28 09:03:28,173 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:28,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,208 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-28 09:03:28,209 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:28,220 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:28,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,230 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-28 09:03:28,231 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:28,261 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-28 09:03:28,282 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2021-12-28 09:03:28,283 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 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) [2021-12-28 09:03:28,349 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 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 51 states and 63 transitions. Complement of second has 12 states. [2021-12-28 09:03:28,350 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 [2021-12-28 09:03:28,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.5) internal successors, (6), 3 states have internal predecessors, (6), 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) [2021-12-28 09:03:28,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 15 transitions. [2021-12-28 09:03:28,355 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 4 letters. Loop has 4 letters. [2021-12-28 09:03:28,356 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:28,356 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 8 letters. Loop has 4 letters. [2021-12-28 09:03:28,356 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:28,356 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 4 letters. Loop has 8 letters. [2021-12-28 09:03:28,356 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:28,357 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 63 transitions. [2021-12-28 09:03:28,360 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-28 09:03:28,363 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 26 states and 35 transitions. [2021-12-28 09:03:28,364 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 18 [2021-12-28 09:03:28,364 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 19 [2021-12-28 09:03:28,365 INFO L73 IsDeterministic]: Start isDeterministic. Operand 26 states and 35 transitions. [2021-12-28 09:03:28,365 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-28 09:03:28,365 INFO L681 BuchiCegarLoop]: Abstraction has 26 states and 35 transitions. [2021-12-28 09:03:28,374 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states and 35 transitions. [2021-12-28 09:03:28,381 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 21. [2021-12-28 09:03:28,382 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 15 states have internal predecessors, (19), 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) [2021-12-28 09:03:28,382 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2021-12-28 09:03:28,383 INFO L704 BuchiCegarLoop]: Abstraction has 21 states and 27 transitions. [2021-12-28 09:03:28,383 INFO L587 BuchiCegarLoop]: Abstraction has 21 states and 27 transitions. [2021-12-28 09:03:28,383 INFO L425 BuchiCegarLoop]: ======== Iteration 2============ [2021-12-28 09:03:28,383 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 21 states and 27 transitions. [2021-12-28 09:03:28,384 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-28 09:03:28,384 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-28 09:03:28,384 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-28 09:03:28,385 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 09:03:28,385 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 09:03:28,385 INFO L791 eck$LassoCheckResult]: Stem: 140#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(16, 2);call #Ultimate.allocInit(12, 3); 141#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 143#L29 assume !(main_~x~0#1 < 1); 131#L31 call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 133#fibonacciENTRY ~n := #in~n; 134#L17 assume !(~n < 1); 139#L19 assume !(1 == ~n); 129#L22 call #t~ret4 := fibonacci(~n - 1);< 135#fibonacciENTRY ~n := #in~n; 136#L17 assume ~n < 1;#res := 0; 137#fibonacciFINAL assume true; 142#fibonacciEXIT >#34#return; 128#L22-1 [2021-12-28 09:03:28,385 INFO L793 eck$LassoCheckResult]: Loop: 128#L22-1 call #t~ret5 := fibonacci(~n - 2);< 132#fibonacciENTRY ~n := #in~n; 148#L17 assume !(~n < 1); 147#L19 assume !(1 == ~n); 130#L22 call #t~ret4 := fibonacci(~n - 1);< 132#fibonacciENTRY ~n := #in~n; 148#L17 assume ~n < 1;#res := 0; 145#fibonacciFINAL assume true; 146#fibonacciEXIT >#34#return; 128#L22-1 [2021-12-28 09:03:28,386 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:28,386 INFO L85 PathProgramCache]: Analyzing trace with hash 1923124650, now seen corresponding path program 1 times [2021-12-28 09:03:28,386 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:28,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1281738045] [2021-12-28 09:03:28,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:28,386 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:28,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,435 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-28 09:03:28,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,453 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-28 09:03:28,453 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 09:03:28,453 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1281738045] [2021-12-28 09:03:28,453 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1281738045] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-28 09:03:28,454 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-28 09:03:28,454 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-28 09:03:28,454 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [96434409] [2021-12-28 09:03:28,455 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-28 09:03:28,456 INFO L796 eck$LassoCheckResult]: stem already infeasible [2021-12-28 09:03:28,456 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:28,456 INFO L85 PathProgramCache]: Analyzing trace with hash 481649848, now seen corresponding path program 1 times [2021-12-28 09:03:28,456 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:28,456 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [647276272] [2021-12-28 09:03:28,457 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:28,457 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:28,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,474 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-28 09:03:28,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,489 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-28 09:03:28,490 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 09:03:28,490 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [647276272] [2021-12-28 09:03:28,490 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [647276272] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-28 09:03:28,490 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-28 09:03:28,490 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-28 09:03:28,490 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [128918664] [2021-12-28 09:03:28,491 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-28 09:03:28,491 INFO L808 eck$LassoCheckResult]: loop already infeasible [2021-12-28 09:03:28,491 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 09:03:28,493 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-28 09:03:28,493 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2021-12-28 09:03:28,494 INFO L87 Difference]: Start difference. First operand 21 states and 27 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) [2021-12-28 09:03:28,536 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 09:03:28,537 INFO L93 Difference]: Finished difference Result 27 states and 33 transitions. [2021-12-28 09:03:28,537 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-28 09:03:28,538 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 27 states and 33 transitions. [2021-12-28 09:03:28,539 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-28 09:03:28,540 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 27 states to 25 states and 31 transitions. [2021-12-28 09:03:28,540 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 21 [2021-12-28 09:03:28,540 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 21 [2021-12-28 09:03:28,540 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 31 transitions. [2021-12-28 09:03:28,540 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-28 09:03:28,540 INFO L681 BuchiCegarLoop]: Abstraction has 25 states and 31 transitions. [2021-12-28 09:03:28,540 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 31 transitions. [2021-12-28 09:03:28,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2021-12-28 09:03:28,542 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 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) [2021-12-28 09:03:28,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 31 transitions. [2021-12-28 09:03:28,543 INFO L704 BuchiCegarLoop]: Abstraction has 25 states and 31 transitions. [2021-12-28 09:03:28,543 INFO L587 BuchiCegarLoop]: Abstraction has 25 states and 31 transitions. [2021-12-28 09:03:28,543 INFO L425 BuchiCegarLoop]: ======== Iteration 3============ [2021-12-28 09:03:28,543 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 25 states and 31 transitions. [2021-12-28 09:03:28,544 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-28 09:03:28,544 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-28 09:03:28,544 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-28 09:03:28,544 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 09:03:28,545 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2021-12-28 09:03:28,545 INFO L791 eck$LassoCheckResult]: Stem: 215#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(16, 2);call #Ultimate.allocInit(12, 3); 216#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 219#L29 assume !(main_~x~0#1 < 1); 204#L31 call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 221#fibonacciENTRY ~n := #in~n; 210#L17 assume !(~n < 1); 214#L19 assume !(1 == ~n); 205#L22 call #t~ret4 := fibonacci(~n - 1);< 209#fibonacciENTRY ~n := #in~n; 211#L17 assume !(~n < 1); 227#L19 assume 1 == ~n;#res := 1; 226#fibonacciFINAL assume true; 225#fibonacciEXIT >#34#return; 203#L22-1 [2021-12-28 09:03:28,545 INFO L793 eck$LassoCheckResult]: Loop: 203#L22-1 call #t~ret5 := fibonacci(~n - 2);< 207#fibonacciENTRY ~n := #in~n; 208#L17 assume !(~n < 1); 213#L19 assume !(1 == ~n); 206#L22 call #t~ret4 := fibonacci(~n - 1);< 207#fibonacciENTRY ~n := #in~n; 208#L17 assume !(~n < 1); 213#L19 assume !(1 == ~n); 206#L22 call #t~ret4 := fibonacci(~n - 1);< 207#fibonacciENTRY ~n := #in~n; 208#L17 assume !(~n < 1); 213#L19 assume 1 == ~n;#res := 1; 222#fibonacciFINAL assume true; 223#fibonacciEXIT >#34#return; 203#L22-1 call #t~ret5 := fibonacci(~n - 2);< 207#fibonacciENTRY ~n := #in~n; 208#L17 assume ~n < 1;#res := 0; 212#fibonacciFINAL assume true; 217#fibonacciEXIT >#36#return; 218#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 220#fibonacciFINAL assume true; 224#fibonacciEXIT >#34#return; 203#L22-1 [2021-12-28 09:03:28,545 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:28,545 INFO L85 PathProgramCache]: Analyzing trace with hash -512653656, now seen corresponding path program 1 times [2021-12-28 09:03:28,545 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:28,546 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [840357246] [2021-12-28 09:03:28,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:28,546 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:28,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:28,551 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-28 09:03:28,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:28,557 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-28 09:03:28,557 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:28,557 INFO L85 PathProgramCache]: Analyzing trace with hash 319636608, now seen corresponding path program 1 times [2021-12-28 09:03:28,557 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:28,558 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1635728529] [2021-12-28 09:03:28,558 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:28,558 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:28,564 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:28,564 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-28 09:03:28,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:28,570 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-28 09:03:28,570 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:28,570 INFO L85 PathProgramCache]: Analyzing trace with hash 911295463, now seen corresponding path program 1 times [2021-12-28 09:03:28,570 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:28,571 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1003130741] [2021-12-28 09:03:28,571 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:28,571 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:28,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,599 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-28 09:03:28,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,627 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2021-12-28 09:03:28,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,633 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-28 09:03:28,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,635 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-28 09:03:28,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,638 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 22 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-12-28 09:03:28,638 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 09:03:28,638 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1003130741] [2021-12-28 09:03:28,638 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1003130741] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 09:03:28,639 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1146887736] [2021-12-28 09:03:28,639 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:28,639 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 09:03:28,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:28,640 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 09:03:28,673 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-12-28 09:03:28,674 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:28,675 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-28 09:03:28,676 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:28,752 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 38 proven. 1 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2021-12-28 09:03:28,752 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 09:03:28,846 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 8 proven. 22 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2021-12-28 09:03:28,847 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1146887736] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-28 09:03:28,847 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-28 09:03:28,847 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 9 [2021-12-28 09:03:28,847 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2075375204] [2021-12-28 09:03:28,847 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-28 09:03:29,082 INFO L210 LassoAnalysis]: Preferences: [2021-12-28 09:03:29,083 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-28 09:03:29,083 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-28 09:03:29,083 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-28 09:03:29,083 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-28 09:03:29,083 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:29,083 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-28 09:03:29,083 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-28 09:03:29,083 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration3_Loop [2021-12-28 09:03:29,083 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-28 09:03:29,083 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-28 09:03:29,083 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:29,085 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:29,087 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:29,089 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:29,142 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-28 09:03:29,142 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-28 09:03:29,143 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:29,143 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:29,144 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:29,145 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2021-12-28 09:03:29,146 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:29,146 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:29,167 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:29,167 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:29,183 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:29,184 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:29,184 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:29,185 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:29,185 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2021-12-28 09:03:29,187 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:29,187 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:29,208 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:29,208 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:29,225 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:29,225 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:29,225 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:29,226 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:29,227 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2021-12-28 09:03:29,228 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:29,228 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:29,249 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:29,249 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=1} Honda state: {fibonacci_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:29,266 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:29,266 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:29,266 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:29,267 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:29,269 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2021-12-28 09:03:29,269 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:29,270 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:29,299 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:29,301 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:29,301 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:29,302 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:29,302 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2021-12-28 09:03:29,303 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-28 09:03:29,303 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:29,886 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-28 09:03:29,889 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2021-12-28 09:03:29,890 INFO L210 LassoAnalysis]: Preferences: [2021-12-28 09:03:29,890 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-28 09:03:29,890 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-28 09:03:29,890 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-28 09:03:29,890 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-28 09:03:29,890 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:29,890 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-28 09:03:29,890 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-28 09:03:29,890 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration3_Loop [2021-12-28 09:03:29,890 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-28 09:03:29,890 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-28 09:03:29,891 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:29,894 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:29,896 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:29,898 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:29,949 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-28 09:03:29,949 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-28 09:03:29,950 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:29,950 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:29,959 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:29,960 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2021-12-28 09:03:29,962 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 [2021-12-28 09:03:29,967 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:29,967 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:29,967 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:29,968 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:29,968 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:29,969 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:29,969 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:29,978 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-28 09:03:29,993 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:29,993 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:29,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:29,995 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:29,995 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2021-12-28 09:03:29,996 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 [2021-12-28 09:03:30,003 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:30,003 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:30,003 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:30,003 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:30,003 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:30,004 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:30,004 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:30,005 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-28 09:03:30,022 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:30,023 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:30,023 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:30,024 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:30,029 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2021-12-28 09:03:30,029 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 [2021-12-28 09:03:30,035 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:30,035 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:30,035 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:30,035 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:30,035 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:30,036 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:30,036 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:30,051 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-28 09:03:30,066 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:30,066 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:30,066 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:30,067 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:30,070 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2021-12-28 09:03:30,073 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 [2021-12-28 09:03:30,079 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:30,079 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:30,079 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:30,079 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:30,079 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:30,081 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:30,081 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:30,092 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-28 09:03:30,095 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-28 09:03:30,095 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-28 09:03:30,096 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:30,096 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:30,097 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:30,098 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2021-12-28 09:03:30,099 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-28 09:03:30,099 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-28 09:03:30,099 INFO L513 LassoAnalysis]: Proved termination. [2021-12-28 09:03:30,099 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2021-12-28 09:03:30,114 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:30,115 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-28 09:03:30,141 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:30,159 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:30,160 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-28 09:03:30,160 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:30,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:30,254 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-28 09:03:30,255 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:30,365 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:30,391 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-28 09:03:30,392 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2021-12-28 09:03:30,392 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 25 states and 31 transitions. cyclomatic complexity: 8 Second operand has 9 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-28 09:03:30,555 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 25 states and 31 transitions. cyclomatic complexity: 8. Second operand has 9 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) Result 160 states and 216 transitions. Complement of second has 48 states. [2021-12-28 09:03:30,557 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 [2021-12-28 09:03:30,558 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.0) internal successors, (24), 7 states have internal predecessors, (24), 5 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (4), 2 states have call predecessors, (4), 4 states have call successors, (4) [2021-12-28 09:03:30,558 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 42 transitions. [2021-12-28 09:03:30,559 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 42 transitions. Stem has 13 letters. Loop has 22 letters. [2021-12-28 09:03:30,559 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:30,559 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 42 transitions. Stem has 35 letters. Loop has 22 letters. [2021-12-28 09:03:30,560 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:30,560 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 42 transitions. Stem has 13 letters. Loop has 44 letters. [2021-12-28 09:03:30,561 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:30,561 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 160 states and 216 transitions. [2021-12-28 09:03:30,566 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2021-12-28 09:03:30,569 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 160 states to 129 states and 181 transitions. [2021-12-28 09:03:30,569 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 75 [2021-12-28 09:03:30,569 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 80 [2021-12-28 09:03:30,569 INFO L73 IsDeterministic]: Start isDeterministic. Operand 129 states and 181 transitions. [2021-12-28 09:03:30,570 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-28 09:03:30,570 INFO L681 BuchiCegarLoop]: Abstraction has 129 states and 181 transitions. [2021-12-28 09:03:30,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states and 181 transitions. [2021-12-28 09:03:30,584 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 107. [2021-12-28 09:03:30,584 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 67 states have (on average 1.2238805970149254) internal successors, (82), 71 states have internal predecessors, (82), 25 states have call successors, (26), 13 states have call predecessors, (26), 15 states have return successors, (33), 22 states have call predecessors, (33), 23 states have call successors, (33) [2021-12-28 09:03:30,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 141 transitions. [2021-12-28 09:03:30,586 INFO L704 BuchiCegarLoop]: Abstraction has 107 states and 141 transitions. [2021-12-28 09:03:30,586 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 09:03:30,587 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-12-28 09:03:30,587 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2021-12-28 09:03:30,587 INFO L87 Difference]: Start difference. First operand 107 states and 141 transitions. Second operand has 9 states, 8 states have (on average 3.625) internal successors, (29), 7 states have internal predecessors, (29), 3 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2021-12-28 09:03:30,634 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 09:03:30,635 INFO L93 Difference]: Finished difference Result 45 states and 58 transitions. [2021-12-28 09:03:30,635 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-28 09:03:30,635 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 45 states and 58 transitions. [2021-12-28 09:03:30,636 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-28 09:03:30,637 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 45 states to 42 states and 54 transitions. [2021-12-28 09:03:30,637 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 35 [2021-12-28 09:03:30,638 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 35 [2021-12-28 09:03:30,638 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 54 transitions. [2021-12-28 09:03:30,638 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-28 09:03:30,638 INFO L681 BuchiCegarLoop]: Abstraction has 42 states and 54 transitions. [2021-12-28 09:03:30,638 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 54 transitions. [2021-12-28 09:03:30,640 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 39. [2021-12-28 09:03:30,641 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 26 states have (on average 1.1153846153846154) internal successors, (29), 28 states have internal predecessors, (29), 7 states have call successors, (7), 5 states have call predecessors, (7), 6 states have return successors, (12), 5 states have call predecessors, (12), 6 states have call successors, (12) [2021-12-28 09:03:30,641 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 48 transitions. [2021-12-28 09:03:30,641 INFO L704 BuchiCegarLoop]: Abstraction has 39 states and 48 transitions. [2021-12-28 09:03:30,641 INFO L587 BuchiCegarLoop]: Abstraction has 39 states and 48 transitions. [2021-12-28 09:03:30,641 INFO L425 BuchiCegarLoop]: ======== Iteration 4============ [2021-12-28 09:03:30,641 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 39 states and 48 transitions. [2021-12-28 09:03:30,642 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-28 09:03:30,642 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-28 09:03:30,642 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-28 09:03:30,643 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-28 09:03:30,644 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2021-12-28 09:03:30,644 INFO L791 eck$LassoCheckResult]: Stem: 991#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(16, 2);call #Ultimate.allocInit(12, 3); 992#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 995#L29 assume !(main_~x~0#1 < 1); 981#L31 call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 983#fibonacciENTRY ~n := #in~n; 984#L17 assume !(~n < 1); 990#L19 assume !(1 == ~n); 980#L22 call #t~ret4 := fibonacci(~n - 1);< 982#fibonacciENTRY ~n := #in~n; 986#L17 assume !(~n < 1); 1013#L19 assume !(1 == ~n); 985#L22 call #t~ret4 := fibonacci(~n - 1);< 982#fibonacciENTRY ~n := #in~n; 987#L17 assume !(~n < 1); 997#L19 assume 1 == ~n;#res := 1; 998#fibonacciFINAL assume true; 1012#fibonacciEXIT >#34#return; 1007#L22-1 call #t~ret5 := fibonacci(~n - 2);< 1008#fibonacciENTRY ~n := #in~n; 1011#L17 assume ~n < 1;#res := 0; 1009#fibonacciFINAL assume true; 1006#fibonacciEXIT >#36#return; 1005#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1004#fibonacciFINAL assume true; 1003#fibonacciEXIT >#34#return; 977#L22-1 [2021-12-28 09:03:30,644 INFO L793 eck$LassoCheckResult]: Loop: 977#L22-1 call #t~ret5 := fibonacci(~n - 2);< 979#fibonacciENTRY ~n := #in~n; 1002#L17 assume !(~n < 1); 1000#L19 assume !(1 == ~n); 976#L22 call #t~ret4 := fibonacci(~n - 1);< 979#fibonacciENTRY ~n := #in~n; 1002#L17 assume !(~n < 1); 1000#L19 assume !(1 == ~n); 976#L22 call #t~ret4 := fibonacci(~n - 1);< 979#fibonacciENTRY ~n := #in~n; 1002#L17 assume !(~n < 1); 1000#L19 assume 1 == ~n;#res := 1; 1001#fibonacciFINAL assume true; 1010#fibonacciEXIT >#34#return; 975#L22-1 call #t~ret5 := fibonacci(~n - 2);< 978#fibonacciENTRY ~n := #in~n; 988#L17 assume ~n < 1;#res := 0; 989#fibonacciFINAL assume true; 993#fibonacciEXIT >#36#return; 994#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 996#fibonacciFINAL assume true; 999#fibonacciEXIT >#34#return; 977#L22-1 [2021-12-28 09:03:30,644 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:30,645 INFO L85 PathProgramCache]: Analyzing trace with hash 506180814, now seen corresponding path program 2 times [2021-12-28 09:03:30,645 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:30,645 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [81176494] [2021-12-28 09:03:30,645 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:30,645 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:30,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:30,652 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-28 09:03:30,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:30,661 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-28 09:03:30,661 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:30,662 INFO L85 PathProgramCache]: Analyzing trace with hash 319636608, now seen corresponding path program 2 times [2021-12-28 09:03:30,662 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:30,662 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1354730011] [2021-12-28 09:03:30,662 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:30,662 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:30,666 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:30,666 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-28 09:03:30,670 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:30,671 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-28 09:03:30,672 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:30,672 INFO L85 PathProgramCache]: Analyzing trace with hash -1200508531, now seen corresponding path program 3 times [2021-12-28 09:03:30,672 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:30,672 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [261522511] [2021-12-28 09:03:30,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:30,672 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:30,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:30,703 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-28 09:03:30,706 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:30,726 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-28 09:03:30,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:30,732 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-28 09:03:30,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:30,735 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2021-12-28 09:03:30,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:30,740 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-28 09:03:30,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:30,742 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-28 09:03:30,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:30,744 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 16 proven. 46 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2021-12-28 09:03:30,745 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 09:03:30,745 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [261522511] [2021-12-28 09:03:30,745 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [261522511] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 09:03:30,745 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2103557017] [2021-12-28 09:03:30,745 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-28 09:03:30,745 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 09:03:30,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:30,746 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 09:03:30,747 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2021-12-28 09:03:30,776 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2021-12-28 09:03:30,776 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 09:03:30,777 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-28 09:03:30,778 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:30,884 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 35 proven. 47 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2021-12-28 09:03:30,884 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 09:03:31,141 INFO L134 CoverageAnalysis]: Checked inductivity of 111 backedges. 35 proven. 49 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-12-28 09:03:31,142 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2103557017] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-28 09:03:31,142 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-28 09:03:31,142 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 12] total 21 [2021-12-28 09:03:31,142 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [821554319] [2021-12-28 09:03:31,142 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-28 09:03:31,361 INFO L210 LassoAnalysis]: Preferences: [2021-12-28 09:03:31,361 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-28 09:03:31,361 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-28 09:03:31,361 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-28 09:03:31,361 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-28 09:03:31,362 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:31,362 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-28 09:03:31,362 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-28 09:03:31,362 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration4_Loop [2021-12-28 09:03:31,362 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-28 09:03:31,362 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-28 09:03:31,362 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:31,364 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:31,372 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:31,373 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:31,417 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-28 09:03:31,417 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-28 09:03:31,417 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:31,417 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:31,419 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:31,443 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2021-12-28 09:03:31,444 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:31,444 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:31,451 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:31,452 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:31,468 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:31,469 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:31,469 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:31,470 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:31,491 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:31,491 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:31,502 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2021-12-28 09:03:31,519 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:31,520 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:31,520 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:31,520 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:31,522 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2021-12-28 09:03:31,522 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-28 09:03:31,522 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:32,104 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-28 09:03:32,110 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:32,111 INFO L210 LassoAnalysis]: Preferences: [2021-12-28 09:03:32,112 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-28 09:03:32,112 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-28 09:03:32,112 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-28 09:03:32,112 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-28 09:03:32,112 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:32,112 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-28 09:03:32,112 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-28 09:03:32,112 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration4_Loop [2021-12-28 09:03:32,112 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-28 09:03:32,112 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-28 09:03:32,112 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:32,122 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:32,128 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:32,129 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:32,169 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-28 09:03:32,169 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-28 09:03:32,169 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:32,169 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:32,171 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:32,174 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2021-12-28 09:03:32,174 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 [2021-12-28 09:03:32,180 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:32,180 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:32,180 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:32,180 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:32,180 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:32,181 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:32,181 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:32,195 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-28 09:03:32,212 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:32,212 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:32,213 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:32,213 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:32,216 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2021-12-28 09:03:32,216 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 [2021-12-28 09:03:32,223 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:32,223 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:32,224 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:32,224 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:32,224 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:32,225 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:32,225 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:32,228 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-28 09:03:32,230 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2021-12-28 09:03:32,230 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2021-12-28 09:03:32,230 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:32,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:32,231 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:32,232 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2021-12-28 09:03:32,232 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-28 09:03:32,233 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-28 09:03:32,233 INFO L513 LassoAnalysis]: Proved termination. [2021-12-28 09:03:32,233 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2021-12-28 09:03:32,248 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2021-12-28 09:03:32,249 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-28 09:03:32,260 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:32,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:32,308 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-28 09:03:32,309 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:32,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:32,532 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-28 09:03:32,533 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:32,641 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-28 09:03:32,642 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2021-12-28 09:03:32,642 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 39 states and 48 transitions. cyclomatic complexity: 11 Second operand has 9 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 6 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2021-12-28 09:03:32,700 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 39 states and 48 transitions. cyclomatic complexity: 11. Second operand has 9 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 6 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 46 states and 55 transitions. Complement of second has 11 states. [2021-12-28 09:03:32,700 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2021-12-28 09:03:32,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 6 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2021-12-28 09:03:32,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2021-12-28 09:03:32,701 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 25 letters. Loop has 22 letters. [2021-12-28 09:03:32,701 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:32,702 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-28 09:03:32,708 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:32,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:32,727 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-28 09:03:32,728 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:32,805 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:32,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:32,931 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-28 09:03:32,932 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:33,025 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-28 09:03:33,026 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2021-12-28 09:03:33,026 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 39 states and 48 transitions. cyclomatic complexity: 11 Second operand has 9 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 6 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2021-12-28 09:03:33,079 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 39 states and 48 transitions. cyclomatic complexity: 11. Second operand has 9 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 6 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 46 states and 55 transitions. Complement of second has 11 states. [2021-12-28 09:03:33,080 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2021-12-28 09:03:33,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 6 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2021-12-28 09:03:33,081 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2021-12-28 09:03:33,081 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 25 letters. Loop has 22 letters. [2021-12-28 09:03:33,081 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:33,081 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-28 09:03:33,087 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:33,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,109 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-28 09:03:33,109 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:33,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,294 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-28 09:03:33,295 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:33,390 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-28 09:03:33,390 INFO L152 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 [2021-12-28 09:03:33,391 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 39 states and 48 transitions. cyclomatic complexity: 11 Second operand has 9 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 6 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2021-12-28 09:03:33,553 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 39 states and 48 transitions. cyclomatic complexity: 11. Second operand has 9 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 6 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 345 states and 444 transitions. Complement of second has 125 states. [2021-12-28 09:03:33,553 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 [2021-12-28 09:03:33,554 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.375) internal successors, (27), 7 states have internal predecessors, (27), 6 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2021-12-28 09:03:33,554 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 47 transitions. [2021-12-28 09:03:33,554 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 47 transitions. Stem has 25 letters. Loop has 22 letters. [2021-12-28 09:03:33,555 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:33,555 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 47 transitions. Stem has 47 letters. Loop has 22 letters. [2021-12-28 09:03:33,555 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:33,556 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 47 transitions. Stem has 25 letters. Loop has 44 letters. [2021-12-28 09:03:33,556 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:33,556 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 345 states and 444 transitions. [2021-12-28 09:03:33,560 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-28 09:03:33,563 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 345 states to 220 states and 297 transitions. [2021-12-28 09:03:33,563 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 99 [2021-12-28 09:03:33,564 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 116 [2021-12-28 09:03:33,564 INFO L73 IsDeterministic]: Start isDeterministic. Operand 220 states and 297 transitions. [2021-12-28 09:03:33,564 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-28 09:03:33,565 INFO L681 BuchiCegarLoop]: Abstraction has 220 states and 297 transitions. [2021-12-28 09:03:33,565 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states and 297 transitions. [2021-12-28 09:03:33,573 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 172. [2021-12-28 09:03:33,573 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 172 states, 107 states have (on average 1.1401869158878504) internal successors, (122), 112 states have internal predecessors, (122), 38 states have call successors, (42), 23 states have call predecessors, (42), 27 states have return successors, (59), 36 states have call predecessors, (59), 36 states have call successors, (59) [2021-12-28 09:03:33,574 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 172 states to 172 states and 223 transitions. [2021-12-28 09:03:33,575 INFO L704 BuchiCegarLoop]: Abstraction has 172 states and 223 transitions. [2021-12-28 09:03:33,575 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 09:03:33,575 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-28 09:03:33,575 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=331, Unknown=0, NotChecked=0, Total=420 [2021-12-28 09:03:33,575 INFO L87 Difference]: Start difference. First operand 172 states and 223 transitions. Second operand has 21 states, 17 states have (on average 2.9411764705882355) internal successors, (50), 18 states have internal predecessors, (50), 13 states have call successors, (17), 3 states have call predecessors, (17), 7 states have return successors, (16), 10 states have call predecessors, (16), 11 states have call successors, (16) [2021-12-28 09:03:33,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 09:03:33,769 INFO L93 Difference]: Finished difference Result 349 states and 503 transitions. [2021-12-28 09:03:33,769 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2021-12-28 09:03:33,770 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 349 states and 503 transitions. [2021-12-28 09:03:33,773 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-28 09:03:33,778 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 349 states to 339 states and 490 transitions. [2021-12-28 09:03:33,778 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 173 [2021-12-28 09:03:33,778 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 193 [2021-12-28 09:03:33,778 INFO L73 IsDeterministic]: Start isDeterministic. Operand 339 states and 490 transitions. [2021-12-28 09:03:33,779 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-28 09:03:33,779 INFO L681 BuchiCegarLoop]: Abstraction has 339 states and 490 transitions. [2021-12-28 09:03:33,779 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 339 states and 490 transitions. [2021-12-28 09:03:33,790 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 339 to 274. [2021-12-28 09:03:33,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 274 states, 171 states have (on average 1.128654970760234) internal successors, (193), 174 states have internal predecessors, (193), 60 states have call successors, (72), 36 states have call predecessors, (72), 43 states have return successors, (136), 63 states have call predecessors, (136), 58 states have call successors, (136) [2021-12-28 09:03:33,792 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 401 transitions. [2021-12-28 09:03:33,793 INFO L704 BuchiCegarLoop]: Abstraction has 274 states and 401 transitions. [2021-12-28 09:03:33,793 INFO L587 BuchiCegarLoop]: Abstraction has 274 states and 401 transitions. [2021-12-28 09:03:33,793 INFO L425 BuchiCegarLoop]: ======== Iteration 5============ [2021-12-28 09:03:33,793 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 274 states and 401 transitions. [2021-12-28 09:03:33,794 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-28 09:03:33,794 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-28 09:03:33,794 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-28 09:03:33,795 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [12, 10, 9, 7, 7, 5, 5, 4, 4, 3, 2, 1, 1, 1, 1] [2021-12-28 09:03:33,795 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-28 09:03:33,796 INFO L791 eck$LassoCheckResult]: Stem: 3005#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(16, 2);call #Ultimate.allocInit(12, 3); 3006#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~ret7#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 3010#L29 assume !(main_~x~0#1 < 1); 3011#L31 call main_#t~ret7#1 := fibonacci(main_~x~0#1);< 3015#fibonacciENTRY ~n := #in~n; 3048#L17 assume !(~n < 1); 3046#L19 assume !(1 == ~n); 3038#L22 call #t~ret4 := fibonacci(~n - 1);< 3041#fibonacciENTRY ~n := #in~n; 3047#L17 assume !(~n < 1); 3045#L19 assume !(1 == ~n); 3039#L22 call #t~ret4 := fibonacci(~n - 1);< 3041#fibonacciENTRY ~n := #in~n; 3047#L17 assume !(~n < 1); 3045#L19 assume !(1 == ~n); 3039#L22 call #t~ret4 := fibonacci(~n - 1);< 3041#fibonacciENTRY ~n := #in~n; 3047#L17 assume !(~n < 1); 3045#L19 assume !(1 == ~n); 3039#L22 call #t~ret4 := fibonacci(~n - 1);< 3041#fibonacciENTRY ~n := #in~n; 3049#L17 assume !(~n < 1); 3145#L19 assume 1 == ~n;#res := 1; 3144#fibonacciFINAL assume true; 3142#fibonacciEXIT >#34#return; 3135#L22-1 call #t~ret5 := fibonacci(~n - 2);< 3137#fibonacciENTRY ~n := #in~n; 3143#L17 assume ~n < 1;#res := 0; 3138#fibonacciFINAL assume true; 3134#fibonacciEXIT >#36#return; 3133#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3132#fibonacciFINAL assume true; 3129#fibonacciEXIT >#34#return; 3077#L22-1 call #t~ret5 := fibonacci(~n - 2);< 3079#fibonacciENTRY ~n := #in~n; 3127#L17 assume !(~n < 1); 3123#L19 assume 1 == ~n;#res := 1; 3026#fibonacciFINAL assume true; 3076#fibonacciEXIT >#36#return; 3072#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3064#fibonacciFINAL assume true; 3054#fibonacciEXIT >#34#return; 3053#L22-1 call #t~ret5 := fibonacci(~n - 2);< 3056#fibonacciENTRY ~n := #in~n; 3128#L17 assume !(~n < 1); 3124#L19 assume !(1 == ~n); 3125#L22 call #t~ret4 := fibonacci(~n - 1);< 3238#fibonacciENTRY ~n := #in~n; 3185#L17 assume !(~n < 1); 3186#L19 assume 1 == ~n;#res := 1; 3239#fibonacciFINAL assume true; 3236#fibonacciEXIT >#34#return; 3068#L22-1 call #t~ret5 := fibonacci(~n - 2);< 3071#fibonacciENTRY ~n := #in~n; 3130#L17 assume ~n < 1;#res := 0; 3081#fibonacciFINAL assume true; 3067#fibonacciEXIT >#36#return; 3070#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3063#fibonacciFINAL assume true; 3052#fibonacciEXIT >#36#return; 3040#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3043#fibonacciFINAL assume true; 3037#fibonacciEXIT >#34#return; 3025#L22-1 call #t~ret5 := fibonacci(~n - 2);< 3031#fibonacciENTRY ~n := #in~n; 3032#L17 assume !(~n < 1); 3023#L19 assume !(1 == ~n); 2996#L22 call #t~ret4 := fibonacci(~n - 1);< 3235#fibonacciENTRY ~n := #in~n; 2994#L17 assume !(~n < 1); 2997#L19 assume !(1 == ~n); 3206#L22 call #t~ret4 := fibonacci(~n - 1);< 3207#fibonacciENTRY [2021-12-28 09:03:33,796 INFO L793 eck$LassoCheckResult]: Loop: 3207#fibonacciENTRY ~n := #in~n; 3218#L17 assume !(~n < 1); 3215#L19 assume !(1 == ~n); 3205#L22 call #t~ret4 := fibonacci(~n - 1);< 3207#fibonacciENTRY [2021-12-28 09:03:33,796 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:33,796 INFO L85 PathProgramCache]: Analyzing trace with hash -1489009265, now seen corresponding path program 4 times [2021-12-28 09:03:33,796 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:33,796 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [209270725] [2021-12-28 09:03:33,796 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:33,797 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:33,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:33,807 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-28 09:03:33,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:33,820 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-28 09:03:33,821 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:33,821 INFO L85 PathProgramCache]: Analyzing trace with hash 927646, now seen corresponding path program 2 times [2021-12-28 09:03:33,821 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:33,821 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2005536143] [2021-12-28 09:03:33,821 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:33,821 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:33,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:33,823 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-28 09:03:33,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-28 09:03:33,824 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-28 09:03:33,834 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:33,835 INFO L85 PathProgramCache]: Analyzing trace with hash 1238644268, now seen corresponding path program 5 times [2021-12-28 09:03:33,835 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-28 09:03:33,835 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [543833307] [2021-12-28 09:03:33,835 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-28 09:03:33,835 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-28 09:03:33,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,891 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-28 09:03:33,896 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,921 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-28 09:03:33,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,946 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-28 09:03:33,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,967 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-28 09:03:33,970 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,977 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-28 09:03:33,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,983 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2021-12-28 09:03:33,986 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,990 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2021-12-28 09:03:33,991 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,996 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-28 09:03:33,996 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:33,999 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-28 09:03:34,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:34,003 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 110 proven. 115 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2021-12-28 09:03:34,003 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-28 09:03:34,003 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [543833307] [2021-12-28 09:03:34,003 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [543833307] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-28 09:03:34,003 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2088599455] [2021-12-28 09:03:34,003 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-28 09:03:34,003 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-28 09:03:34,003 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:34,009 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-28 09:03:34,010 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Waiting until timeout for monitored process [2021-12-28 09:03:34,048 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2021-12-28 09:03:34,048 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-28 09:03:34,049 INFO L263 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-28 09:03:34,051 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:34,182 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 115 proven. 109 refuted. 0 times theorem prover too weak. 103 trivial. 0 not checked. [2021-12-28 09:03:34,182 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-28 09:03:34,645 INFO L134 CoverageAnalysis]: Checked inductivity of 327 backedges. 115 proven. 121 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2021-12-28 09:03:34,646 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2088599455] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-28 09:03:34,646 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-28 09:03:34,646 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 16] total 21 [2021-12-28 09:03:34,646 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [7710066] [2021-12-28 09:03:34,646 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-28 09:03:34,666 INFO L210 LassoAnalysis]: Preferences: [2021-12-28 09:03:34,666 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-28 09:03:34,666 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-28 09:03:34,666 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-28 09:03:34,666 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-28 09:03:34,666 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:34,666 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-28 09:03:34,666 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-28 09:03:34,666 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration5_Loop [2021-12-28 09:03:34,666 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-28 09:03:34,666 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-28 09:03:34,666 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,667 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,668 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,669 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,672 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,684 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-28 09:03:34,684 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-28 09:03:34,684 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:34,684 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:34,699 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:34,723 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2021-12-28 09:03:34,724 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:34,724 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:34,747 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:34,747 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=0} Honda state: {fibonacci_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:34,777 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:34,778 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:34,778 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:34,785 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:34,786 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2021-12-28 09:03:34,788 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:34,788 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:34,810 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:34,811 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:34,839 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:34,840 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:34,840 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:34,847 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:34,849 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2021-12-28 09:03:34,850 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:34,850 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:34,856 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-28 09:03:34,856 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-28 09:03:34,871 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Ended with exit code 0 [2021-12-28 09:03:34,872 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:34,872 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:34,872 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:34,873 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2021-12-28 09:03:34,874 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-28 09:03:34,874 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:34,910 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2021-12-28 09:03:34,910 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:34,910 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:34,913 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:34,914 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2021-12-28 09:03:34,915 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-28 09:03:34,915 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-28 09:03:34,947 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-28 09:03:34,964 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:34,965 INFO L210 LassoAnalysis]: Preferences: [2021-12-28 09:03:34,965 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-28 09:03:34,965 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-28 09:03:34,965 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-28 09:03:34,965 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-28 09:03:34,965 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:34,965 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-28 09:03:34,965 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-28 09:03:34,965 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration5_Loop [2021-12-28 09:03:34,965 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-28 09:03:34,965 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-28 09:03:34,965 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,967 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,968 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,973 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,975 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-28 09:03:34,995 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-28 09:03:34,996 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-28 09:03:34,996 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:34,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:34,997 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:35,000 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2021-12-28 09:03:35,000 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 [2021-12-28 09:03:35,013 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:35,013 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:35,013 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:35,013 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:35,013 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:35,014 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:35,014 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:35,015 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-28 09:03:35,029 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Ended with exit code 0 [2021-12-28 09:03:35,030 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:35,030 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:35,030 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:35,032 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2021-12-28 09:03:35,032 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 [2021-12-28 09:03:35,037 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:35,037 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:35,038 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:35,038 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:35,038 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:35,038 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:35,038 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:35,039 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-28 09:03:35,053 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Ended with exit code 0 [2021-12-28 09:03:35,054 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:35,054 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:35,055 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:35,056 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2021-12-28 09:03:35,057 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 [2021-12-28 09:03:35,062 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-28 09:03:35,062 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-28 09:03:35,062 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-28 09:03:35,062 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-28 09:03:35,062 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-28 09:03:35,071 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-28 09:03:35,071 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-28 09:03:35,098 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-28 09:03:35,100 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-28 09:03:35,100 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-28 09:03:35,100 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-28 09:03:35,100 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-28 09:03:35,101 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-28 09:03:35,102 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2021-12-28 09:03:35,103 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-28 09:03:35,103 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-28 09:03:35,103 INFO L513 LassoAnalysis]: Proved termination. [2021-12-28 09:03:35,103 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2021-12-28 09:03:35,118 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2021-12-28 09:03:35,119 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-28 09:03:35,126 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:35,203 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:35,205 INFO L263 TraceCheckSpWp]: Trace formula consists of 537 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-28 09:03:35,207 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:35,417 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:35,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:35,754 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-28 09:03:35,754 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:35,771 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-28 09:03:35,772 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2021-12-28 09:03:35,772 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 274 states and 401 transitions. cyclomatic complexity: 131 Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-28 09:03:35,841 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 274 states and 401 transitions. cyclomatic complexity: 131. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 296 states and 427 transitions. Complement of second has 13 states. [2021-12-28 09:03:35,841 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2021-12-28 09:03:35,842 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-28 09:03:35,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2021-12-28 09:03:35,842 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 72 letters. Loop has 4 letters. [2021-12-28 09:03:35,842 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:35,842 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-28 09:03:35,848 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:35,899 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:35,901 INFO L263 TraceCheckSpWp]: Trace formula consists of 537 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-28 09:03:35,903 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:36,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:36,422 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-28 09:03:36,422 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:36,450 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-28 09:03:36,451 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2021-12-28 09:03:36,451 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 274 states and 401 transitions. cyclomatic complexity: 131 Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-28 09:03:36,498 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 274 states and 401 transitions. cyclomatic complexity: 131. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 296 states and 427 transitions. Complement of second has 13 states. [2021-12-28 09:03:36,498 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2021-12-28 09:03:36,499 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-28 09:03:36,499 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2021-12-28 09:03:36,499 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 72 letters. Loop has 4 letters. [2021-12-28 09:03:36,499 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:36,499 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-28 09:03:36,506 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-28 09:03:36,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:36,573 INFO L263 TraceCheckSpWp]: Trace formula consists of 537 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-28 09:03:36,575 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:37,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-28 09:03:37,112 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-28 09:03:37,113 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-28 09:03:37,134 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-28 09:03:37,135 INFO L152 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2021-12-28 09:03:37,135 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 274 states and 401 transitions. cyclomatic complexity: 131 Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-28 09:03:37,182 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 274 states and 401 transitions. cyclomatic complexity: 131. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 349 states and 484 transitions. Complement of second has 14 states. [2021-12-28 09:03:37,182 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2021-12-28 09:03:37,182 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-28 09:03:37,182 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 22 transitions. [2021-12-28 09:03:37,182 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 22 transitions. Stem has 72 letters. Loop has 4 letters. [2021-12-28 09:03:37,183 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:37,183 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 22 transitions. Stem has 76 letters. Loop has 4 letters. [2021-12-28 09:03:37,184 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:37,184 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 22 transitions. Stem has 72 letters. Loop has 8 letters. [2021-12-28 09:03:37,185 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-28 09:03:37,185 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 349 states and 484 transitions. [2021-12-28 09:03:37,189 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-28 09:03:37,192 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 349 states to 288 states and 417 transitions. [2021-12-28 09:03:37,192 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 138 [2021-12-28 09:03:37,193 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 143 [2021-12-28 09:03:37,193 INFO L73 IsDeterministic]: Start isDeterministic. Operand 288 states and 417 transitions. [2021-12-28 09:03:37,195 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-28 09:03:37,195 INFO L681 BuchiCegarLoop]: Abstraction has 288 states and 417 transitions. [2021-12-28 09:03:37,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 288 states and 417 transitions. [2021-12-28 09:03:37,208 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 288 to 280. [2021-12-28 09:03:37,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 280 states, 176 states have (on average 1.125) internal successors, (198), 179 states have internal predecessors, (198), 61 states have call successors, (73), 37 states have call predecessors, (73), 43 states have return successors, (138), 63 states have call predecessors, (138), 59 states have call successors, (138) [2021-12-28 09:03:37,211 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 280 states to 280 states and 409 transitions. [2021-12-28 09:03:37,211 INFO L704 BuchiCegarLoop]: Abstraction has 280 states and 409 transitions. [2021-12-28 09:03:37,211 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-28 09:03:37,211 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-28 09:03:37,212 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=305, Unknown=0, NotChecked=0, Total=420 [2021-12-28 09:03:37,212 INFO L87 Difference]: Start difference. First operand 280 states and 409 transitions. Second operand has 21 states, 16 states have (on average 2.875) internal successors, (46), 17 states have internal predecessors, (46), 15 states have call successors, (19), 5 states have call predecessors, (19), 6 states have return successors, (19), 10 states have call predecessors, (19), 11 states have call successors, (19) [2021-12-28 09:03:37,362 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-28 09:03:37,362 INFO L93 Difference]: Finished difference Result 408 states and 601 transitions. [2021-12-28 09:03:37,362 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-12-28 09:03:37,363 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 601 transitions. [2021-12-28 09:03:37,366 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-28 09:03:37,366 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 0 states and 0 transitions. [2021-12-28 09:03:37,366 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2021-12-28 09:03:37,366 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2021-12-28 09:03:37,366 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2021-12-28 09:03:37,366 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2021-12-28 09:03:37,366 INFO L681 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-28 09:03:37,366 INFO L704 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-28 09:03:37,366 INFO L587 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-28 09:03:37,366 INFO L425 BuchiCegarLoop]: ======== Iteration 6============ [2021-12-28 09:03:37,366 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2021-12-28 09:03:37,366 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-28 09:03:37,366 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2021-12-28 09:03:37,370 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 28.12 09:03:37 BoogieIcfgContainer [2021-12-28 09:03:37,370 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2021-12-28 09:03:37,371 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2021-12-28 09:03:37,371 INFO L271 PluginConnector]: Initializing Witness Printer... [2021-12-28 09:03:37,372 INFO L275 PluginConnector]: Witness Printer initialized [2021-12-28 09:03:37,372 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.12 09:03:27" (3/4) ... [2021-12-28 09:03:37,374 INFO L140 WitnessPrinter]: No result that supports witness generation found [2021-12-28 09:03:37,374 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2021-12-28 09:03:37,375 INFO L158 Benchmark]: Toolchain (without parser) took 10656.30ms. Allocated memory was 65.0MB in the beginning and 159.4MB in the end (delta: 94.4MB). Free memory was 46.6MB in the beginning and 95.4MB in the end (delta: -48.8MB). Peak memory consumption was 45.6MB. Max. memory is 16.1GB. [2021-12-28 09:03:37,375 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 65.0MB. Free memory was 47.5MB in the beginning and 47.4MB in the end (delta: 83.9kB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-28 09:03:37,376 INFO L158 Benchmark]: CACSL2BoogieTranslator took 117.44ms. Allocated memory is still 65.0MB. Free memory was 46.4MB in the beginning and 37.1MB in the end (delta: 9.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-12-28 09:03:37,376 INFO L158 Benchmark]: Boogie Procedure Inliner took 16.92ms. Allocated memory is still 65.0MB. Free memory was 36.9MB in the beginning and 35.5MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2021-12-28 09:03:37,376 INFO L158 Benchmark]: Boogie Preprocessor took 9.17ms. Allocated memory is still 65.0MB. Free memory was 35.5MB in the beginning and 34.6MB in the end (delta: 928.9kB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-28 09:03:37,376 INFO L158 Benchmark]: RCFGBuilder took 214.55ms. Allocated memory is still 65.0MB. Free memory was 34.6MB in the beginning and 41.7MB in the end (delta: -7.1MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. [2021-12-28 09:03:37,377 INFO L158 Benchmark]: BuchiAutomizer took 10291.88ms. Allocated memory was 65.0MB in the beginning and 159.4MB in the end (delta: 94.4MB). Free memory was 41.7MB in the beginning and 96.4MB in the end (delta: -54.7MB). Peak memory consumption was 42.7MB. Max. memory is 16.1GB. [2021-12-28 09:03:37,377 INFO L158 Benchmark]: Witness Printer took 3.13ms. Allocated memory is still 159.4MB. Free memory was 96.4MB in the beginning and 95.4MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-28 09:03:37,378 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.18ms. Allocated memory is still 65.0MB. Free memory was 47.5MB in the beginning and 47.4MB in the end (delta: 83.9kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 117.44ms. Allocated memory is still 65.0MB. Free memory was 46.4MB in the beginning and 37.1MB in the end (delta: 9.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 16.92ms. Allocated memory is still 65.0MB. Free memory was 36.9MB in the beginning and 35.5MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 9.17ms. Allocated memory is still 65.0MB. Free memory was 35.5MB in the beginning and 34.6MB in the end (delta: 928.9kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 214.55ms. Allocated memory is still 65.0MB. Free memory was 34.6MB in the beginning and 41.7MB in the end (delta: -7.1MB). Peak memory consumption was 4.2MB. Max. memory is 16.1GB. * BuchiAutomizer took 10291.88ms. Allocated memory was 65.0MB in the beginning and 159.4MB in the end (delta: 94.4MB). Free memory was 41.7MB in the beginning and 96.4MB in the end (delta: -54.7MB). Peak memory consumption was 42.7MB. Max. memory is 16.1GB. * Witness Printer took 3.13ms. Allocated memory is still 159.4MB. Free memory was 96.4MB in the beginning and 95.4MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 8 terminating modules (4 trivial, 2 deterministic, 2 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 10 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function \old(n) and consists of 5 locations. 4 modules have a trivial ranking function, the largest among these consists of 21 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 10.2s and 6 iterations. TraceHistogramMax:12. Analysis of lassos took 5.5s. Construction of modules took 0.4s. Büchi inclusion checks took 4.0s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 7. Automata minimization 0.1s AutomataMinimizationTime, 7 MinimizatonAttempts, 151 StatesRemovedByMinimization, 6 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had 274 states and ocurred in iteration 4. Nontrivial modules had stage [2, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 16/46 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 471 SdHoareTripleChecker+Valid, 0.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 442 mSDsluCounter, 384 SdHoareTripleChecker+Invalid, 0.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 223 mSDsCounter, 318 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 711 IncrementalHoareTripleChecker+Invalid, 1029 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 318 mSolverCounterUnsat, 161 mSDtfsCounter, 711 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT3 SILN0 SILU0 SILI1 SILT0 lasso0 LassoPreprocessingBenchmarks: Lassos: inital21 mio100 ax100 hnf100 lsp94 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq171 hnf95 smp62 dnf100 smp100 tf110 neg95 sie113 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 35ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 10 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.7s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2021-12-28 09:03:37,426 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:37,621 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:37,832 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2021-12-28 09:03:38,035 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE