./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 839c364b 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-839c364b5d67a0f615c82cb70ab247790648d4a9-839c364 [2021-12-14 22:59:33,938 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-14 22:59:33,940 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-14 22:59:33,989 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-14 22:59:33,990 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-14 22:59:33,991 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-14 22:59:33,992 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-14 22:59:33,993 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-14 22:59:33,995 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-14 22:59:33,999 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-14 22:59:34,000 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-14 22:59:34,002 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-14 22:59:34,002 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-14 22:59:34,004 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-14 22:59:34,006 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-14 22:59:34,010 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-14 22:59:34,010 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-14 22:59:34,012 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-14 22:59:34,015 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-14 22:59:34,019 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-14 22:59:34,021 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-14 22:59:34,022 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-14 22:59:34,023 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-14 22:59:34,024 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-14 22:59:34,029 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-14 22:59:34,029 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-14 22:59:34,030 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-14 22:59:34,031 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-14 22:59:34,032 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-14 22:59:34,033 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-14 22:59:34,033 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-14 22:59:34,034 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-14 22:59:34,036 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-14 22:59:34,037 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-14 22:59:34,038 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-14 22:59:34,038 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-14 22:59:34,039 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-14 22:59:34,039 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-14 22:59:34,039 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-14 22:59:34,039 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-14 22:59:34,040 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-14 22:59:34,042 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2021-12-14 22:59:34,074 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-14 22:59:34,075 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-14 22:59:34,075 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-14 22:59:34,075 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-14 22:59:34,076 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-14 22:59:34,076 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-14 22:59:34,076 INFO L138 SettingsManager]: * Use SBE=true [2021-12-14 22:59:34,076 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2021-12-14 22:59:34,076 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2021-12-14 22:59:34,076 INFO L138 SettingsManager]: * Use old map elimination=false [2021-12-14 22:59:34,076 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2021-12-14 22:59:34,076 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2021-12-14 22:59:34,076 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2021-12-14 22:59:34,076 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-14 22:59:34,076 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-14 22:59:34,076 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2021-12-14 22:59:34,077 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-14 22:59:34,077 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-14 22:59:34,077 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-14 22:59:34,078 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-14 22:59:34,078 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2021-12-14 22:59:34,078 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-14 22:59:34,259 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-14 22:59:34,272 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-14 22:59:34,274 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-14 22:59:34,275 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-14 22:59:34,275 INFO L275 PluginConnector]: CDTParser initialized [2021-12-14 22:59:34,277 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-14 22:59:34,347 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f85e1baf3/e925576196564ee8b0d071f6189134b6/FLAG2462c7c89 [2021-12-14 22:59:34,713 INFO L306 CDTParser]: Found 1 translation units. [2021-12-14 22:59:34,713 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-numeric/Fibonacci01-2.c [2021-12-14 22:59:34,717 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f85e1baf3/e925576196564ee8b0d071f6189134b6/FLAG2462c7c89 [2021-12-14 22:59:34,729 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f85e1baf3/e925576196564ee8b0d071f6189134b6 [2021-12-14 22:59:34,731 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-14 22:59:34,733 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-14 22:59:34,735 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-14 22:59:34,735 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-14 22:59:34,740 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-14 22:59:34,741 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,742 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@40f3de2b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34, skipping insertion in model container [2021-12-14 22:59:34,742 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,746 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-14 22:59:34,755 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-14 22:59:34,869 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-14 22:59:34,870 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 22:59:34,876 INFO L203 MainTranslator]: Completed pre-run [2021-12-14 22:59:34,888 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-14 22:59:34,888 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-14 22:59:34,899 INFO L208 MainTranslator]: Completed translation [2021-12-14 22:59:34,900 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34 WrapperNode [2021-12-14 22:59:34,901 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-14 22:59:34,903 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-14 22:59:34,903 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-14 22:59:34,903 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-14 22:59:34,910 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,916 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,935 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 24 [2021-12-14 22:59:34,935 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-14 22:59:34,936 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-14 22:59:34,936 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-14 22:59:34,936 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-14 22:59:34,941 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,941 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,943 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,943 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,946 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,947 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,951 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,953 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-14 22:59:34,955 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-14 22:59:34,955 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-14 22:59:34,955 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-14 22:59:34,956 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (1/1) ... [2021-12-14 22:59:34,962 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:34,971 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:34,989 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-14 22:59:35,007 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-14 22:59:35,021 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2021-12-14 22:59:35,022 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2021-12-14 22:59:35,022 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-14 22:59:35,023 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-14 22:59:35,023 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-14 22:59:35,023 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-14 22:59:35,065 INFO L236 CfgBuilder]: Building ICFG [2021-12-14 22:59:35,066 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-14 22:59:35,160 INFO L277 CfgBuilder]: Performing block encoding [2021-12-14 22:59:35,164 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-14 22:59:35,165 INFO L301 CfgBuilder]: Removed 0 assume(true) statements. [2021-12-14 22:59:35,166 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 10:59:35 BoogieIcfgContainer [2021-12-14 22:59:35,166 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-14 22:59:35,167 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2021-12-14 22:59:35,167 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2021-12-14 22:59:35,169 INFO L275 PluginConnector]: BuchiAutomizer initialized [2021-12-14 22:59:35,170 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-14 22:59:35,170 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 14.12 10:59:34" (1/3) ... [2021-12-14 22:59:35,171 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@36f4a41d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 14.12 10:59:35, skipping insertion in model container [2021-12-14 22:59:35,171 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-14 22:59:35,171 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.12 10:59:34" (2/3) ... [2021-12-14 22:59:35,172 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@36f4a41d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 14.12 10:59:35, skipping insertion in model container [2021-12-14 22:59:35,172 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-14 22:59:35,172 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 10:59:35" (3/3) ... [2021-12-14 22:59:35,173 INFO L388 chiAutomizerObserver]: Analyzing ICFG Fibonacci01-2.c [2021-12-14 22:59:35,204 INFO L359 BuchiCegarLoop]: Interprodecural is true [2021-12-14 22:59:35,206 INFO L360 BuchiCegarLoop]: Hoare is false [2021-12-14 22:59:35,206 INFO L361 BuchiCegarLoop]: Compute interpolants for ForwardPredicates [2021-12-14 22:59:35,206 INFO L362 BuchiCegarLoop]: Backedges is STRAIGHT_LINE [2021-12-14 22:59:35,206 INFO L363 BuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-12-14 22:59:35,206 INFO L364 BuchiCegarLoop]: Difference is false [2021-12-14 22:59:35,207 INFO L365 BuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-12-14 22:59:35,207 INFO L368 BuchiCegarLoop]: ======== Iteration 0==of CEGAR loop == BuchiCegarLoop======== [2021-12-14 22:59:35,219 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-14 22:59:35,241 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-14 22:59:35,242 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-14 22:59:35,242 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-14 22:59:35,249 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1, 1] [2021-12-14 22:59:35,249 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-14 22:59:35,250 INFO L425 BuchiCegarLoop]: ======== Iteration 1============ [2021-12-14 22:59:35,250 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-14 22:59:35,253 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-14 22:59:35,253 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-14 22:59:35,253 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-14 22:59:35,254 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1, 1] [2021-12-14 22:59:35,254 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-14 22:59:35,259 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-14 22:59:35,260 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-14 22:59:35,263 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:35,264 INFO L85 PathProgramCache]: Analyzing trace with hash 1325876, now seen corresponding path program 1 times [2021-12-14 22:59:35,270 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:35,271 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1551559936] [2021-12-14 22:59:35,271 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:35,272 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:35,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:35,370 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-14 22:59:35,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:35,422 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-14 22:59:35,424 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:35,424 INFO L85 PathProgramCache]: Analyzing trace with hash 927646, now seen corresponding path program 1 times [2021-12-14 22:59:35,425 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:35,426 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [83087480] [2021-12-14 22:59:35,426 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:35,426 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:35,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:35,434 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-14 22:59:35,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:35,441 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-14 22:59:35,442 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:35,443 INFO L85 PathProgramCache]: Analyzing trace with hash 408654161, now seen corresponding path program 1 times [2021-12-14 22:59:35,443 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:35,443 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [761840568] [2021-12-14 22:59:35,444 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:35,444 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:35,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:35,463 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-14 22:59:35,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:35,482 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-14 22:59:35,585 INFO L210 LassoAnalysis]: Preferences: [2021-12-14 22:59:35,586 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-14 22:59:35,586 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-14 22:59:35,586 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-14 22:59:35,586 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-14 22:59:35,586 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:35,587 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-14 22:59:35,587 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-14 22:59:35,587 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration1_Loop [2021-12-14 22:59:35,587 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-14 22:59:35,587 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-14 22:59:35,598 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-14 22:59:35,602 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-14 22:59:35,605 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-14 22:59:35,607 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-14 22:59:35,614 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-14 22:59:35,662 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-14 22:59:35,663 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-14 22:59:35,664 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:35,665 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:35,666 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-14 22:59:35,668 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-14 22:59:35,680 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:35,680 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:35,701 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:35,702 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-14 22:59:35,722 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2021-12-14 22:59:35,723 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:35,723 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:35,724 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-14 22:59:35,725 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-14 22:59:35,726 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:35,726 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:35,749 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:35,750 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-14 22:59:35,767 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-14 22:59:35,767 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:35,768 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:35,769 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-14 22:59:35,770 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-14 22:59:35,792 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:35,793 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:35,804 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:35,804 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-14 22:59:35,826 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2021-12-14 22:59:35,827 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:35,827 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:35,828 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-14 22:59:35,829 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-14 22:59:35,830 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:35,830 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:35,904 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-14 22:59:35,905 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:35,905 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:35,906 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-14 22:59:35,919 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-14 22:59:35,920 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-14 22:59:35,920 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:35,986 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-14 22:59:35,990 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2021-12-14 22:59:35,991 INFO L210 LassoAnalysis]: Preferences: [2021-12-14 22:59:35,991 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-14 22:59:35,991 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-14 22:59:35,991 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-14 22:59:35,991 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-14 22:59:35,991 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:35,991 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-14 22:59:35,991 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-14 22:59:35,991 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration1_Loop [2021-12-14 22:59:35,991 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-14 22:59:35,991 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-14 22:59:35,992 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-14 22:59:35,995 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-14 22:59:35,999 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-14 22:59:36,001 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-14 22:59:36,007 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-14 22:59:36,049 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-14 22:59:36,052 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-14 22:59:36,053 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:36,054 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:36,054 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-14 22:59:36,062 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-14 22:59:36,068 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:36,068 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:36,069 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:36,069 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:36,069 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:36,071 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:36,071 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:36,075 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-14 22:59:36,083 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-14 22:59:36,101 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-14 22:59:36,102 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:36,102 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:36,103 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-14 22:59:36,105 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-14 22:59:36,106 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-14 22:59:36,112 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:36,112 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:36,112 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:36,112 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:36,112 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:36,113 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:36,113 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:36,132 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-14 22:59:36,150 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-14 22:59:36,151 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:36,151 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:36,152 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-14 22:59:36,153 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-14 22:59:36,155 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-14 22:59:36,162 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:36,162 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:36,162 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:36,162 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:36,162 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:36,163 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:36,163 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:36,177 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-14 22:59:36,194 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2021-12-14 22:59:36,194 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:36,194 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:36,195 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-14 22:59:36,196 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-14 22:59:36,198 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-14 22:59:36,204 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:36,204 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:36,204 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:36,204 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:36,204 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:36,205 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:36,205 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:36,212 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-14 22:59:36,215 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-14 22:59:36,215 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-14 22:59:36,216 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:36,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:36,218 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-14 22:59:36,218 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-14 22:59:36,264 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-14 22:59:36,264 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-14 22:59:36,264 INFO L513 LassoAnalysis]: Proved termination. [2021-12-14 22:59:36,264 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2021-12-14 22:59:36,281 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-14 22:59:36,283 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-14 22:59:36,310 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:36,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,330 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-14 22:59:36,331 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:36,351 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,352 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-14 22:59:36,353 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:36,396 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-14 22:59:36,417 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-14 22:59:36,418 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-14 22:59:36,497 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-14 22:59:36,506 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-14 22:59:36,513 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-14 22:59:36,516 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 15 transitions. [2021-12-14 22:59:36,518 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 4 letters. Loop has 4 letters. [2021-12-14 22:59:36,519 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:36,519 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 8 letters. Loop has 4 letters. [2021-12-14 22:59:36,519 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:36,519 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 4 letters. Loop has 8 letters. [2021-12-14 22:59:36,520 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:36,520 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 63 transitions. [2021-12-14 22:59:36,530 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-14 22:59:36,536 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 26 states and 35 transitions. [2021-12-14 22:59:36,537 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 18 [2021-12-14 22:59:36,537 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 19 [2021-12-14 22:59:36,540 INFO L73 IsDeterministic]: Start isDeterministic. Operand 26 states and 35 transitions. [2021-12-14 22:59:36,540 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-14 22:59:36,541 INFO L681 BuchiCegarLoop]: Abstraction has 26 states and 35 transitions. [2021-12-14 22:59:36,550 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states and 35 transitions. [2021-12-14 22:59:36,563 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 21. [2021-12-14 22:59:36,563 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-14 22:59:36,563 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2021-12-14 22:59:36,564 INFO L704 BuchiCegarLoop]: Abstraction has 21 states and 27 transitions. [2021-12-14 22:59:36,564 INFO L587 BuchiCegarLoop]: Abstraction has 21 states and 27 transitions. [2021-12-14 22:59:36,564 INFO L425 BuchiCegarLoop]: ======== Iteration 2============ [2021-12-14 22:59:36,564 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 21 states and 27 transitions. [2021-12-14 22:59:36,565 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-14 22:59:36,565 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-14 22:59:36,565 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-14 22:59:36,565 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 22:59:36,565 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 22:59:36,566 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-14 22:59:36,566 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-14 22:59:36,566 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:36,566 INFO L85 PathProgramCache]: Analyzing trace with hash 1923124650, now seen corresponding path program 1 times [2021-12-14 22:59:36,566 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:36,566 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [961662909] [2021-12-14 22:59:36,566 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:36,566 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:36,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,616 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 22:59:36,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,639 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-14 22:59:36,639 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 22:59:36,640 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [961662909] [2021-12-14 22:59:36,640 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [961662909] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 22:59:36,640 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 22:59:36,641 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-14 22:59:36,641 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [954730949] [2021-12-14 22:59:36,642 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 22:59:36,643 INFO L796 eck$LassoCheckResult]: stem already infeasible [2021-12-14 22:59:36,644 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:36,644 INFO L85 PathProgramCache]: Analyzing trace with hash 481649848, now seen corresponding path program 1 times [2021-12-14 22:59:36,644 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:36,644 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1074147215] [2021-12-14 22:59:36,644 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:36,645 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:36,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,663 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-14 22:59:36,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,678 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-14 22:59:36,678 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 22:59:36,678 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1074147215] [2021-12-14 22:59:36,678 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1074147215] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-14 22:59:36,679 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-14 22:59:36,679 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-14 22:59:36,679 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1162799022] [2021-12-14 22:59:36,679 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-14 22:59:36,680 INFO L808 eck$LassoCheckResult]: loop already infeasible [2021-12-14 22:59:36,680 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 22:59:36,682 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-14 22:59:36,682 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2021-12-14 22:59:36,683 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-14 22:59:36,727 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 22:59:36,727 INFO L93 Difference]: Finished difference Result 27 states and 33 transitions. [2021-12-14 22:59:36,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-14 22:59:36,728 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 27 states and 33 transitions. [2021-12-14 22:59:36,729 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-14 22:59:36,730 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 27 states to 25 states and 31 transitions. [2021-12-14 22:59:36,731 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 21 [2021-12-14 22:59:36,731 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 21 [2021-12-14 22:59:36,731 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 31 transitions. [2021-12-14 22:59:36,731 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-14 22:59:36,731 INFO L681 BuchiCegarLoop]: Abstraction has 25 states and 31 transitions. [2021-12-14 22:59:36,731 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 31 transitions. [2021-12-14 22:59:36,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2021-12-14 22:59:36,733 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-14 22:59:36,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 31 transitions. [2021-12-14 22:59:36,734 INFO L704 BuchiCegarLoop]: Abstraction has 25 states and 31 transitions. [2021-12-14 22:59:36,734 INFO L587 BuchiCegarLoop]: Abstraction has 25 states and 31 transitions. [2021-12-14 22:59:36,734 INFO L425 BuchiCegarLoop]: ======== Iteration 3============ [2021-12-14 22:59:36,734 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 25 states and 31 transitions. [2021-12-14 22:59:36,735 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-14 22:59:36,735 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-14 22:59:36,735 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-14 22:59:36,736 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 22:59:36,736 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2021-12-14 22:59:36,737 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-14 22:59:36,737 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-14 22:59:36,737 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:36,737 INFO L85 PathProgramCache]: Analyzing trace with hash -512653656, now seen corresponding path program 1 times [2021-12-14 22:59:36,737 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:36,738 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [908778629] [2021-12-14 22:59:36,738 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:36,738 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:36,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:36,743 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-14 22:59:36,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:36,749 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-14 22:59:36,750 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:36,750 INFO L85 PathProgramCache]: Analyzing trace with hash 319636608, now seen corresponding path program 1 times [2021-12-14 22:59:36,750 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:36,751 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1934133429] [2021-12-14 22:59:36,751 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:36,751 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:36,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:36,757 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-14 22:59:36,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:36,766 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-14 22:59:36,766 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:36,766 INFO L85 PathProgramCache]: Analyzing trace with hash 911295463, now seen corresponding path program 1 times [2021-12-14 22:59:36,767 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:36,767 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [922821284] [2021-12-14 22:59:36,767 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:36,767 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:36,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,803 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 22:59:36,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,837 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2021-12-14 22:59:36,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,843 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 22:59:36,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,847 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-14 22:59:36,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,851 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-14 22:59:36,851 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 22:59:36,855 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [922821284] [2021-12-14 22:59:36,855 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [922821284] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 22:59:36,855 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1050299522] [2021-12-14 22:59:36,856 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:36,856 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 22:59:36,856 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:36,870 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-14 22:59:36,872 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-14 22:59:36,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:36,909 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-14 22:59:36,915 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:36,950 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-14 22:59:36,997 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-14 22:59:36,997 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 22:59:37,097 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-14 22:59:37,098 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1050299522] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 22:59:37,098 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 22:59:37,098 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 9 [2021-12-14 22:59:37,098 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [865647182] [2021-12-14 22:59:37,098 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 22:59:37,328 INFO L210 LassoAnalysis]: Preferences: [2021-12-14 22:59:37,328 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-14 22:59:37,329 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-14 22:59:37,329 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-14 22:59:37,329 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-14 22:59:37,329 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:37,329 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-14 22:59:37,329 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-14 22:59:37,329 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration3_Loop [2021-12-14 22:59:37,329 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-14 22:59:37,329 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-14 22:59:37,330 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-14 22:59:37,332 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-14 22:59:37,334 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-14 22:59:37,337 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-14 22:59:37,398 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-14 22:59:37,399 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-14 22:59:37,399 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:37,399 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:37,404 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-14 22:59:37,405 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-14 22:59:37,406 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:37,406 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:37,427 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:37,427 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-14 22:59:37,444 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2021-12-14 22:59:37,444 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:37,444 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:37,445 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-14 22:59:37,448 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-14 22:59:37,449 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:37,449 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:37,455 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:37,456 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-14 22:59:37,471 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2021-12-14 22:59:37,471 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:37,471 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:37,472 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-14 22:59:37,473 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-14 22:59:37,474 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:37,474 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:37,481 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:37,481 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-14 22:59:37,498 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-14 22:59:37,499 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:37,499 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:37,500 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-14 22:59:37,500 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-14 22:59:37,502 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:37,502 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:37,533 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-14 22:59:37,534 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:37,534 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:37,534 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-14 22:59:37,535 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-14 22:59:37,536 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-14 22:59:37,536 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:38,116 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-14 22:59:38,119 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-14 22:59:38,120 INFO L210 LassoAnalysis]: Preferences: [2021-12-14 22:59:38,120 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-14 22:59:38,120 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-14 22:59:38,120 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-14 22:59:38,120 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-14 22:59:38,120 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:38,120 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-14 22:59:38,120 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-14 22:59:38,120 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration3_Loop [2021-12-14 22:59:38,120 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-14 22:59:38,120 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-14 22:59:38,121 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-14 22:59:38,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-14 22:59:38,124 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-14 22:59:38,126 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-14 22:59:38,184 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-14 22:59:38,185 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-14 22:59:38,185 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:38,185 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:38,197 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-14 22:59:38,200 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-14 22:59:38,200 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-14 22:59:38,206 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:38,206 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:38,206 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:38,206 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:38,206 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:38,207 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:38,207 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:38,222 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-14 22:59:38,237 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-14 22:59:38,237 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:38,237 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:38,238 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-14 22:59:38,239 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-14 22:59:38,240 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-14 22:59:38,247 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:38,247 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:38,247 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:38,247 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:38,247 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:38,248 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:38,248 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:38,249 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-14 22:59:38,266 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2021-12-14 22:59:38,266 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:38,266 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:38,267 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-14 22:59:38,269 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-14 22:59:38,269 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-14 22:59:38,275 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:38,275 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:38,275 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:38,275 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:38,276 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:38,276 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:38,276 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:38,279 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-14 22:59:38,295 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-14 22:59:38,296 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:38,296 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:38,296 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-14 22:59:38,299 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-14 22:59:38,302 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-14 22:59:38,305 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:38,306 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:38,306 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:38,306 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:38,306 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:38,307 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:38,307 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:38,309 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-14 22:59:38,313 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-14 22:59:38,313 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-14 22:59:38,313 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:38,313 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:38,314 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-14 22:59:38,318 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-14 22:59:38,319 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-14 22:59:38,319 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-14 22:59:38,319 INFO L513 LassoAnalysis]: Proved termination. [2021-12-14 22:59:38,319 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2021-12-14 22:59:38,336 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-14 22:59:38,337 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-14 22:59:38,358 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:38,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:38,376 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-14 22:59:38,377 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:38,477 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-14 22:59:38,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:38,486 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 22:59:38,487 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:38,605 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-14 22:59:38,606 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-14 22:59:38,606 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-14 22:59:38,795 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-14 22:59:38,796 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-14 22:59:38,796 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-14 22:59:38,797 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 42 transitions. [2021-12-14 22:59:38,797 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 42 transitions. Stem has 13 letters. Loop has 22 letters. [2021-12-14 22:59:38,798 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:38,798 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 42 transitions. Stem has 35 letters. Loop has 22 letters. [2021-12-14 22:59:38,798 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:38,798 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 42 transitions. Stem has 13 letters. Loop has 44 letters. [2021-12-14 22:59:38,799 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:38,800 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 160 states and 216 transitions. [2021-12-14 22:59:38,804 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2021-12-14 22:59:38,807 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 160 states to 129 states and 181 transitions. [2021-12-14 22:59:38,807 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 75 [2021-12-14 22:59:38,808 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 80 [2021-12-14 22:59:38,808 INFO L73 IsDeterministic]: Start isDeterministic. Operand 129 states and 181 transitions. [2021-12-14 22:59:38,808 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-14 22:59:38,808 INFO L681 BuchiCegarLoop]: Abstraction has 129 states and 181 transitions. [2021-12-14 22:59:38,808 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states and 181 transitions. [2021-12-14 22:59:38,816 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 107. [2021-12-14 22:59:38,817 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-14 22:59:38,818 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 141 transitions. [2021-12-14 22:59:38,818 INFO L704 BuchiCegarLoop]: Abstraction has 107 states and 141 transitions. [2021-12-14 22:59:38,818 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 22:59:38,818 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-12-14 22:59:38,819 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2021-12-14 22:59:38,819 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-14 22:59:38,861 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 22:59:38,861 INFO L93 Difference]: Finished difference Result 45 states and 58 transitions. [2021-12-14 22:59:38,862 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-14 22:59:38,862 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 45 states and 58 transitions. [2021-12-14 22:59:38,863 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-14 22:59:38,864 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 45 states to 42 states and 54 transitions. [2021-12-14 22:59:38,864 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 35 [2021-12-14 22:59:38,865 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 35 [2021-12-14 22:59:38,865 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 54 transitions. [2021-12-14 22:59:38,865 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-14 22:59:38,865 INFO L681 BuchiCegarLoop]: Abstraction has 42 states and 54 transitions. [2021-12-14 22:59:38,865 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 54 transitions. [2021-12-14 22:59:38,867 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 39. [2021-12-14 22:59:38,868 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-14 22:59:38,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 48 transitions. [2021-12-14 22:59:38,868 INFO L704 BuchiCegarLoop]: Abstraction has 39 states and 48 transitions. [2021-12-14 22:59:38,869 INFO L587 BuchiCegarLoop]: Abstraction has 39 states and 48 transitions. [2021-12-14 22:59:38,869 INFO L425 BuchiCegarLoop]: ======== Iteration 4============ [2021-12-14 22:59:38,869 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 39 states and 48 transitions. [2021-12-14 22:59:38,869 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-14 22:59:38,869 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-14 22:59:38,870 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-14 22:59:38,871 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-14 22:59:38,871 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2021-12-14 22:59:38,871 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-14 22:59:38,871 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-14 22:59:38,872 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:38,872 INFO L85 PathProgramCache]: Analyzing trace with hash 506180814, now seen corresponding path program 2 times [2021-12-14 22:59:38,872 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:38,872 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [862056849] [2021-12-14 22:59:38,872 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:38,872 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:38,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:38,885 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-14 22:59:38,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:38,892 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-14 22:59:38,893 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:38,893 INFO L85 PathProgramCache]: Analyzing trace with hash 319636608, now seen corresponding path program 2 times [2021-12-14 22:59:38,893 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:38,893 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [477488613] [2021-12-14 22:59:38,893 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:38,893 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:38,897 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:38,897 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-14 22:59:38,903 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:38,904 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-14 22:59:38,904 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:38,905 INFO L85 PathProgramCache]: Analyzing trace with hash -1200508531, now seen corresponding path program 3 times [2021-12-14 22:59:38,905 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:38,905 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [631118311] [2021-12-14 22:59:38,905 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:38,905 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:38,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:38,951 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 22:59:38,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:38,973 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 22:59:38,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:38,987 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-14 22:59:38,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:38,991 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2021-12-14 22:59:38,992 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:39,008 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 22:59:39,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:39,011 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-14 22:59:39,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:39,013 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-14 22:59:39,013 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 22:59:39,013 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [631118311] [2021-12-14 22:59:39,013 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [631118311] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 22:59:39,014 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [965940028] [2021-12-14 22:59:39,014 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-14 22:59:39,014 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 22:59:39,014 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:39,024 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-14 22:59:39,039 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-14 22:59:39,079 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2021-12-14 22:59:39,079 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 22:59:39,080 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-14 22:59:39,082 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:39,192 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-14 22:59:39,192 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 22:59:39,472 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-14 22:59:39,472 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [965940028] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 22:59:39,472 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 22:59:39,473 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 12] total 21 [2021-12-14 22:59:39,473 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1895198482] [2021-12-14 22:59:39,473 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 22:59:39,626 INFO L210 LassoAnalysis]: Preferences: [2021-12-14 22:59:39,627 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-14 22:59:39,627 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-14 22:59:39,627 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-14 22:59:39,627 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-14 22:59:39,627 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:39,627 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-14 22:59:39,627 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-14 22:59:39,627 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration4_Loop [2021-12-14 22:59:39,627 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-14 22:59:39,627 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-14 22:59:39,627 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-14 22:59:39,629 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-14 22:59:39,633 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-14 22:59:39,635 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-14 22:59:39,658 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-14 22:59:39,658 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-14 22:59:39,658 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:39,658 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:39,659 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-14 22:59:39,660 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-14 22:59:39,661 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:39,661 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:39,682 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:39,682 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-14 22:59:39,699 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-14 22:59:39,699 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:39,699 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:39,700 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-14 22:59:39,702 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-14 22:59:39,703 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:39,703 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:39,730 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2021-12-14 22:59:39,730 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:39,730 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:39,731 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-14 22:59:39,731 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-14 22:59:39,733 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-14 22:59:39,733 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:40,313 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-14 22:59:40,317 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-14 22:59:40,317 INFO L210 LassoAnalysis]: Preferences: [2021-12-14 22:59:40,317 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-14 22:59:40,317 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-14 22:59:40,317 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-14 22:59:40,317 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-14 22:59:40,317 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:40,317 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-14 22:59:40,317 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-14 22:59:40,317 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration4_Loop [2021-12-14 22:59:40,317 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-14 22:59:40,318 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-14 22:59:40,318 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-14 22:59:40,325 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-14 22:59:40,330 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-14 22:59:40,332 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-14 22:59:40,356 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-14 22:59:40,356 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-14 22:59:40,357 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:40,357 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:40,358 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-14 22:59:40,361 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-14 22:59:40,362 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-14 22:59:40,368 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:40,368 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:40,368 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:40,368 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:40,368 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:40,369 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:40,369 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:40,370 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-14 22:59:40,384 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2021-12-14 22:59:40,384 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:40,384 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:40,385 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-14 22:59:40,386 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-14 22:59:40,387 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-14 22:59:40,393 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:40,393 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:40,393 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:40,393 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:40,393 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:40,394 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:40,394 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:40,415 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-14 22:59:40,421 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-14 22:59:40,421 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-14 22:59:40,422 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:40,422 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:40,423 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-14 22:59:40,424 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-14 22:59:40,425 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-14 22:59:40,425 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-14 22:59:40,425 INFO L513 LassoAnalysis]: Proved termination. [2021-12-14 22:59:40,425 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2021-12-14 22:59:40,441 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-14 22:59:40,442 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-14 22:59:40,451 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:40,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:40,480 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-14 22:59:40,481 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:40,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:40,687 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 22:59:40,688 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:40,773 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-14 22:59:40,830 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-14 22:59:40,830 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-14 22:59:40,831 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-14 22:59:40,900 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-14 22:59:40,900 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-14 22:59:40,901 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-14 22:59:40,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2021-12-14 22:59:40,901 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 25 letters. Loop has 22 letters. [2021-12-14 22:59:40,902 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:40,902 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-14 22:59:40,908 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:40,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:40,932 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-14 22:59:40,933 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:41,142 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:41,143 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 22:59:41,144 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:41,261 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-14 22:59:41,263 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-14 22:59:41,264 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-14 22:59:41,338 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-14 22:59:41,338 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-14 22:59:41,340 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-14 22:59:41,340 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2021-12-14 22:59:41,340 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 25 letters. Loop has 22 letters. [2021-12-14 22:59:41,341 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:41,341 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-14 22:59:41,348 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:41,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:41,374 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-14 22:59:41,375 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:41,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:41,579 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 22:59:41,580 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:41,691 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-14 22:59:41,692 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-14 22:59:41,692 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-14 22:59:41,885 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-14 22:59:41,885 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-14 22:59:41,886 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-14 22:59:41,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 47 transitions. [2021-12-14 22:59:41,887 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 47 transitions. Stem has 25 letters. Loop has 22 letters. [2021-12-14 22:59:41,887 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:41,888 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 47 transitions. Stem has 47 letters. Loop has 22 letters. [2021-12-14 22:59:41,888 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:41,888 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 47 transitions. Stem has 25 letters. Loop has 44 letters. [2021-12-14 22:59:41,890 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:41,890 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 345 states and 444 transitions. [2021-12-14 22:59:41,896 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-14 22:59:41,900 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 345 states to 220 states and 297 transitions. [2021-12-14 22:59:41,900 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 99 [2021-12-14 22:59:41,901 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 116 [2021-12-14 22:59:41,901 INFO L73 IsDeterministic]: Start isDeterministic. Operand 220 states and 297 transitions. [2021-12-14 22:59:41,902 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-14 22:59:41,902 INFO L681 BuchiCegarLoop]: Abstraction has 220 states and 297 transitions. [2021-12-14 22:59:41,902 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states and 297 transitions. [2021-12-14 22:59:41,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 172. [2021-12-14 22:59:41,914 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-14 22:59:41,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 172 states to 172 states and 223 transitions. [2021-12-14 22:59:41,916 INFO L704 BuchiCegarLoop]: Abstraction has 172 states and 223 transitions. [2021-12-14 22:59:41,916 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 22:59:41,916 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-14 22:59:41,917 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=331, Unknown=0, NotChecked=0, Total=420 [2021-12-14 22:59:41,917 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-14 22:59:42,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 22:59:42,157 INFO L93 Difference]: Finished difference Result 349 states and 503 transitions. [2021-12-14 22:59:42,158 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2021-12-14 22:59:42,159 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 349 states and 503 transitions. [2021-12-14 22:59:42,163 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-14 22:59:42,168 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 349 states to 339 states and 490 transitions. [2021-12-14 22:59:42,168 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 173 [2021-12-14 22:59:42,169 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 193 [2021-12-14 22:59:42,169 INFO L73 IsDeterministic]: Start isDeterministic. Operand 339 states and 490 transitions. [2021-12-14 22:59:42,169 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-14 22:59:42,169 INFO L681 BuchiCegarLoop]: Abstraction has 339 states and 490 transitions. [2021-12-14 22:59:42,169 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 339 states and 490 transitions. [2021-12-14 22:59:42,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 339 to 274. [2021-12-14 22:59:42,193 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-14 22:59:42,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 401 transitions. [2021-12-14 22:59:42,199 INFO L704 BuchiCegarLoop]: Abstraction has 274 states and 401 transitions. [2021-12-14 22:59:42,199 INFO L587 BuchiCegarLoop]: Abstraction has 274 states and 401 transitions. [2021-12-14 22:59:42,199 INFO L425 BuchiCegarLoop]: ======== Iteration 5============ [2021-12-14 22:59:42,199 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 274 states and 401 transitions. [2021-12-14 22:59:42,201 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-14 22:59:42,202 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-14 22:59:42,202 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-14 22:59:42,205 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [12, 10, 9, 7, 7, 5, 5, 4, 4, 3, 2, 1, 1, 1, 1] [2021-12-14 22:59:42,205 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-14 22:59:42,205 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-14 22:59:42,205 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-14 22:59:42,205 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:42,205 INFO L85 PathProgramCache]: Analyzing trace with hash -1489009265, now seen corresponding path program 4 times [2021-12-14 22:59:42,206 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:42,206 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [501864536] [2021-12-14 22:59:42,206 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:42,206 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:42,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:42,221 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-14 22:59:42,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:42,233 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-14 22:59:42,233 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:42,233 INFO L85 PathProgramCache]: Analyzing trace with hash 927646, now seen corresponding path program 2 times [2021-12-14 22:59:42,233 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:42,233 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1525579758] [2021-12-14 22:59:42,233 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:42,234 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:42,235 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:42,235 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-14 22:59:42,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-14 22:59:42,236 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-14 22:59:42,237 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:42,237 INFO L85 PathProgramCache]: Analyzing trace with hash 1238644268, now seen corresponding path program 5 times [2021-12-14 22:59:42,237 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-14 22:59:42,237 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1026581729] [2021-12-14 22:59:42,237 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-14 22:59:42,237 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-14 22:59:42,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,293 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-14 22:59:42,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,320 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 22:59:42,323 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,341 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 22:59:42,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,360 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 22:59:42,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,366 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-14 22:59:42,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,368 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2021-12-14 22:59:42,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,376 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2021-12-14 22:59:42,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,389 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-14 22:59:42,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,392 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-14 22:59:42,392 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:42,394 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-14 22:59:42,395 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-14 22:59:42,395 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1026581729] [2021-12-14 22:59:42,395 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1026581729] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-14 22:59:42,395 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [801609751] [2021-12-14 22:59:42,395 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-14 22:59:42,395 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-14 22:59:42,395 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:42,396 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-14 22:59:42,397 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-14 22:59:42,433 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2021-12-14 22:59:42,433 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-14 22:59:42,434 INFO L263 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-14 22:59:42,435 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:42,570 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-14 22:59:42,571 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-14 22:59:43,025 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-14 22:59:43,026 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [801609751] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-14 22:59:43,026 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-14 22:59:43,026 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 16] total 21 [2021-12-14 22:59:43,026 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [728401319] [2021-12-14 22:59:43,026 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-14 22:59:43,058 INFO L210 LassoAnalysis]: Preferences: [2021-12-14 22:59:43,059 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-14 22:59:43,059 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-14 22:59:43,059 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-14 22:59:43,059 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-14 22:59:43,059 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,059 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-14 22:59:43,059 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-14 22:59:43,059 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration5_Loop [2021-12-14 22:59:43,059 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-14 22:59:43,059 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-14 22:59:43,059 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-14 22:59:43,061 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-14 22:59:43,063 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-14 22:59:43,064 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-14 22:59:43,069 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-14 22:59:43,096 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-14 22:59:43,096 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-14 22:59:43,096 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,096 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:43,097 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-14 22:59:43,098 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-14 22:59:43,099 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:43,099 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:43,105 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:43,105 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-14 22:59:43,122 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-14 22:59:43,122 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,122 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:43,123 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-14 22:59:43,123 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-14 22:59:43,125 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:43,125 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:43,142 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:43,143 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-14 22:59:43,163 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2021-12-14 22:59:43,163 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,164 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:43,164 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-14 22:59:43,165 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-14 22:59:43,166 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:43,167 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:43,173 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-14 22:59:43,173 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-14 22:59:43,188 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-14 22:59:43,188 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:43,189 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-14 22:59:43,190 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-14 22:59:43,191 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-14 22:59:43,191 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:43,231 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-14 22:59:43,232 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,232 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:43,233 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-14 22:59:43,234 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-14 22:59:43,235 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-14 22:59:43,235 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-14 22:59:43,267 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-14 22:59:43,269 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2021-12-14 22:59:43,270 INFO L210 LassoAnalysis]: Preferences: [2021-12-14 22:59:43,270 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-14 22:59:43,270 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-14 22:59:43,270 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-14 22:59:43,270 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-14 22:59:43,270 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,270 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-14 22:59:43,270 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-14 22:59:43,270 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration5_Loop [2021-12-14 22:59:43,270 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-14 22:59:43,270 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-14 22:59:43,271 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-14 22:59:43,272 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-14 22:59:43,274 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-14 22:59:43,278 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-14 22:59:43,281 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-14 22:59:43,313 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-14 22:59:43,313 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-14 22:59:43,313 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,313 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:43,314 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-14 22:59:43,315 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-14 22:59:43,316 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-14 22:59:43,321 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:43,321 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:43,321 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:43,322 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:43,322 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:43,322 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:43,322 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:43,331 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-14 22:59:43,345 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-14 22:59:43,346 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,346 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:43,346 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-14 22:59:43,347 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-14 22:59:43,348 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-14 22:59:43,354 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:43,354 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:43,354 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:43,354 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:43,354 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:43,354 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:43,354 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:43,356 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-14 22:59:43,374 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2021-12-14 22:59:43,374 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,374 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:43,375 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-14 22:59:43,375 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-14 22:59:43,377 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-14 22:59:43,382 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-14 22:59:43,382 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-14 22:59:43,382 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-14 22:59:43,382 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-14 22:59:43,382 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-14 22:59:43,383 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-14 22:59:43,383 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-14 22:59:43,394 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-14 22:59:43,396 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-14 22:59:43,396 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-14 22:59:43,396 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-14 22:59:43,396 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-14 22:59:43,397 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-14 22:59:43,397 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-14 22:59:43,399 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-14 22:59:43,399 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-14 22:59:43,399 INFO L513 LassoAnalysis]: Proved termination. [2021-12-14 22:59:43,399 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2021-12-14 22:59:43,416 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2021-12-14 22:59:43,417 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-14 22:59:43,424 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:43,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:43,501 INFO L263 TraceCheckSpWp]: Trace formula consists of 537 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-14 22:59:43,507 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:43,775 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-14 22:59:44,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:44,055 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-14 22:59:44,055 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:44,070 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-14 22:59:44,071 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-14 22:59:44,072 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-14 22:59:44,109 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-14 22:59:44,109 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-14 22:59:44,110 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-14 22:59:44,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2021-12-14 22:59:44,110 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 72 letters. Loop has 4 letters. [2021-12-14 22:59:44,111 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:44,111 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-14 22:59:44,116 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:44,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:44,166 INFO L263 TraceCheckSpWp]: Trace formula consists of 537 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-14 22:59:44,169 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:44,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:44,762 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-14 22:59:44,762 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:44,785 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-14 22:59:44,785 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-14 22:59:44,786 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-14 22:59:44,833 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-14 22:59:44,834 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-14 22:59:44,834 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-14 22:59:44,834 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2021-12-14 22:59:44,834 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 72 letters. Loop has 4 letters. [2021-12-14 22:59:44,835 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:44,835 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-14 22:59:44,842 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-14 22:59:44,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:44,897 INFO L263 TraceCheckSpWp]: Trace formula consists of 537 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-14 22:59:44,899 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:45,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-14 22:59:45,455 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-14 22:59:45,456 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-14 22:59:45,482 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-14 22:59:45,482 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-14 22:59:45,483 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-14 22:59:45,535 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-14 22:59:45,535 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-14 22:59:45,536 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-14 22:59:45,536 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 22 transitions. [2021-12-14 22:59:45,536 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 22 transitions. Stem has 72 letters. Loop has 4 letters. [2021-12-14 22:59:45,536 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:45,536 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 22 transitions. Stem has 76 letters. Loop has 4 letters. [2021-12-14 22:59:45,536 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:45,536 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 22 transitions. Stem has 72 letters. Loop has 8 letters. [2021-12-14 22:59:45,537 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-14 22:59:45,537 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 349 states and 484 transitions. [2021-12-14 22:59:45,540 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-14 22:59:45,542 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 349 states to 288 states and 417 transitions. [2021-12-14 22:59:45,542 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 138 [2021-12-14 22:59:45,543 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 143 [2021-12-14 22:59:45,543 INFO L73 IsDeterministic]: Start isDeterministic. Operand 288 states and 417 transitions. [2021-12-14 22:59:45,543 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-14 22:59:45,543 INFO L681 BuchiCegarLoop]: Abstraction has 288 states and 417 transitions. [2021-12-14 22:59:45,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 288 states and 417 transitions. [2021-12-14 22:59:45,553 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 288 to 280. [2021-12-14 22:59:45,553 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-14 22:59:45,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 280 states to 280 states and 409 transitions. [2021-12-14 22:59:45,555 INFO L704 BuchiCegarLoop]: Abstraction has 280 states and 409 transitions. [2021-12-14 22:59:45,555 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-14 22:59:45,555 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-14 22:59:45,555 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=305, Unknown=0, NotChecked=0, Total=420 [2021-12-14 22:59:45,556 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-14 22:59:45,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-14 22:59:45,726 INFO L93 Difference]: Finished difference Result 408 states and 601 transitions. [2021-12-14 22:59:45,727 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-12-14 22:59:45,727 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 601 transitions. [2021-12-14 22:59:45,732 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-14 22:59:45,732 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 0 states and 0 transitions. [2021-12-14 22:59:45,732 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2021-12-14 22:59:45,732 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2021-12-14 22:59:45,732 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2021-12-14 22:59:45,732 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2021-12-14 22:59:45,732 INFO L681 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-14 22:59:45,732 INFO L704 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-14 22:59:45,733 INFO L587 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-14 22:59:45,733 INFO L425 BuchiCegarLoop]: ======== Iteration 6============ [2021-12-14 22:59:45,733 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2021-12-14 22:59:45,733 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-14 22:59:45,733 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2021-12-14 22:59:45,739 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 14.12 10:59:45 BoogieIcfgContainer [2021-12-14 22:59:45,739 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2021-12-14 22:59:45,740 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2021-12-14 22:59:45,740 INFO L271 PluginConnector]: Initializing Witness Printer... [2021-12-14 22:59:45,740 INFO L275 PluginConnector]: Witness Printer initialized [2021-12-14 22:59:45,740 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.12 10:59:35" (3/4) ... [2021-12-14 22:59:45,742 INFO L140 WitnessPrinter]: No result that supports witness generation found [2021-12-14 22:59:45,742 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2021-12-14 22:59:45,743 INFO L158 Benchmark]: Toolchain (without parser) took 11010.13ms. Allocated memory was 100.7MB in the beginning and 172.0MB in the end (delta: 71.3MB). Free memory was 73.3MB in the beginning and 50.4MB in the end (delta: 22.8MB). Peak memory consumption was 93.6MB. Max. memory is 16.1GB. [2021-12-14 22:59:45,743 INFO L158 Benchmark]: CDTParser took 0.21ms. Allocated memory is still 100.7MB. Free memory was 58.0MB in the beginning and 57.9MB in the end (delta: 45.9kB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-14 22:59:45,743 INFO L158 Benchmark]: CACSL2BoogieTranslator took 166.70ms. Allocated memory was 100.7MB in the beginning and 142.6MB in the end (delta: 41.9MB). Free memory was 73.3MB in the beginning and 119.4MB in the end (delta: -46.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-12-14 22:59:45,744 INFO L158 Benchmark]: Boogie Procedure Inliner took 32.96ms. Allocated memory is still 142.6MB. Free memory was 119.4MB in the beginning and 117.8MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2021-12-14 22:59:45,744 INFO L158 Benchmark]: Boogie Preprocessor took 17.80ms. Allocated memory is still 142.6MB. Free memory was 117.8MB in the beginning and 117.3MB in the end (delta: 492.6kB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-14 22:59:45,744 INFO L158 Benchmark]: RCFGBuilder took 211.58ms. Allocated memory is still 142.6MB. Free memory was 117.3MB in the beginning and 108.4MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-12-14 22:59:45,745 INFO L158 Benchmark]: BuchiAutomizer took 10572.25ms. Allocated memory was 142.6MB in the beginning and 172.0MB in the end (delta: 29.4MB). Free memory was 108.4MB in the beginning and 50.4MB in the end (delta: 58.0MB). Peak memory consumption was 88.9MB. Max. memory is 16.1GB. [2021-12-14 22:59:45,745 INFO L158 Benchmark]: Witness Printer took 2.98ms. Allocated memory is still 172.0MB. Free memory is still 50.4MB. There was no memory consumed. Max. memory is 16.1GB. [2021-12-14 22:59:45,746 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.21ms. Allocated memory is still 100.7MB. Free memory was 58.0MB in the beginning and 57.9MB in the end (delta: 45.9kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 166.70ms. Allocated memory was 100.7MB in the beginning and 142.6MB in the end (delta: 41.9MB). Free memory was 73.3MB in the beginning and 119.4MB in the end (delta: -46.2MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 32.96ms. Allocated memory is still 142.6MB. Free memory was 119.4MB in the beginning and 117.8MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 17.80ms. Allocated memory is still 142.6MB. Free memory was 117.8MB in the beginning and 117.3MB in the end (delta: 492.6kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 211.58ms. Allocated memory is still 142.6MB. Free memory was 117.3MB in the beginning and 108.4MB in the end (delta: 8.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 10572.25ms. Allocated memory was 142.6MB in the beginning and 172.0MB in the end (delta: 29.4MB). Free memory was 108.4MB in the beginning and 50.4MB in the end (delta: 58.0MB). Peak memory consumption was 88.9MB. Max. memory is 16.1GB. * Witness Printer took 2.98ms. Allocated memory is still 172.0MB. Free memory is still 50.4MB. 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.5s and 6 iterations. TraceHistogramMax:12. Analysis of lassos took 5.5s. Construction of modules took 0.4s. Büchi inclusion checks took 4.2s. 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.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 442 mSDsluCounter, 384 SdHoareTripleChecker+Invalid, 0.5s 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: inital17 mio100 ax100 hnf96 lsp92 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq180 hnf93 smp79 dnf100 smp100 tf110 neg96 sie109 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 30ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 10 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.6s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2021-12-14 22:59:45,790 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-14 22:59:45,985 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-14 22:59:46,179 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2021-12-14 22:59:46,388 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE