./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 ff03de63 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/termination-numeric/Fibonacci01-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness.graphml --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash 14cfbc3a2ba2bfe3a03d4d1ebff24b0baf1851f06dbbd2468b59e09322e4ce16 --- Real Ultimate output --- This is Ultimate 0.2.2-dev-ff03de6 [2021-12-21 21:56:52,120 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-21 21:56:52,122 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-21 21:56:52,146 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-21 21:56:52,147 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-21 21:56:52,149 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-21 21:56:52,152 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-21 21:56:52,156 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-21 21:56:52,158 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-21 21:56:52,159 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-21 21:56:52,159 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-21 21:56:52,160 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-21 21:56:52,161 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-21 21:56:52,165 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-21 21:56:52,167 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-21 21:56:52,168 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-21 21:56:52,169 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-21 21:56:52,170 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-21 21:56:52,171 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-21 21:56:52,174 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-21 21:56:52,178 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-21 21:56:52,179 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-21 21:56:52,180 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-21 21:56:52,181 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-21 21:56:52,182 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-21 21:56:52,183 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-21 21:56:52,184 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-21 21:56:52,185 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-21 21:56:52,185 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-21 21:56:52,186 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-21 21:56:52,186 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-21 21:56:52,187 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-21 21:56:52,188 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-21 21:56:52,189 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-21 21:56:52,190 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-21 21:56:52,190 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-21 21:56:52,190 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-21 21:56:52,191 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-21 21:56:52,191 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-21 21:56:52,191 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-21 21:56:52,192 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-21 21:56:52,192 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2021-12-21 21:56:52,221 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-21 21:56:52,222 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-21 21:56:52,222 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-21 21:56:52,222 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-21 21:56:52,223 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-21 21:56:52,223 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-21 21:56:52,223 INFO L138 SettingsManager]: * Use SBE=true [2021-12-21 21:56:52,224 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2021-12-21 21:56:52,224 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2021-12-21 21:56:52,224 INFO L138 SettingsManager]: * Use old map elimination=false [2021-12-21 21:56:52,225 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2021-12-21 21:56:52,225 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2021-12-21 21:56:52,225 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2021-12-21 21:56:52,225 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-21 21:56:52,225 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-21 21:56:52,225 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-21 21:56:52,225 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-21 21:56:52,226 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2021-12-21 21:56:52,226 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2021-12-21 21:56:52,226 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2021-12-21 21:56:52,226 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-21 21:56:52,226 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2021-12-21 21:56:52,226 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-21 21:56:52,227 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2021-12-21 21:56:52,228 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-21 21:56:52,228 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-21 21:56:52,228 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-21 21:56:52,228 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-21 21:56:52,228 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-21 21:56:52,229 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2021-12-21 21:56:52,229 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-21 21:56:52,402 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-21 21:56:52,425 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-21 21:56:52,428 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-21 21:56:52,429 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-21 21:56:52,429 INFO L275 PluginConnector]: CDTParser initialized [2021-12-21 21:56:52,430 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-21 21:56:52,503 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/700e796a2/b6aaced886934f09bced0b1e161dca89/FLAG5d9e41038 [2021-12-21 21:56:52,865 INFO L306 CDTParser]: Found 1 translation units. [2021-12-21 21:56:52,866 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-numeric/Fibonacci01-2.c [2021-12-21 21:56:52,872 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/700e796a2/b6aaced886934f09bced0b1e161dca89/FLAG5d9e41038 [2021-12-21 21:56:52,885 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/700e796a2/b6aaced886934f09bced0b1e161dca89 [2021-12-21 21:56:52,889 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-21 21:56:52,890 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-21 21:56:52,891 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-21 21:56:52,891 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-21 21:56:52,893 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-21 21:56:52,894 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 09:56:52" (1/1) ... [2021-12-21 21:56:52,894 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@38d931f7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:52, skipping insertion in model container [2021-12-21 21:56:52,895 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 09:56:52" (1/1) ... [2021-12-21 21:56:52,900 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-21 21:56:52,913 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-21 21:56:53,024 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-21 21:56:53,025 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 21:56:53,042 INFO L203 MainTranslator]: Completed pre-run [2021-12-21 21:56:53,051 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-21 21:56:53,051 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 21:56:53,058 INFO L208 MainTranslator]: Completed translation [2021-12-21 21:56:53,059 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53 WrapperNode [2021-12-21 21:56:53,059 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-21 21:56:53,060 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-21 21:56:53,060 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-21 21:56:53,060 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-21 21:56:53,064 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,068 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,076 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 24 [2021-12-21 21:56:53,076 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-21 21:56:53,077 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-21 21:56:53,077 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-21 21:56:53,077 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-21 21:56:53,081 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,082 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,082 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,082 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,084 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,085 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,086 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,086 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-21 21:56:53,087 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-21 21:56:53,087 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-21 21:56:53,087 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-21 21:56:53,088 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (1/1) ... [2021-12-21 21:56:53,092 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:53,098 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:53,107 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-21 21:56:53,136 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-21 21:56:53,155 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2021-12-21 21:56:53,156 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2021-12-21 21:56:53,156 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-21 21:56:53,156 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-21 21:56:53,156 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-21 21:56:53,156 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-21 21:56:53,192 INFO L234 CfgBuilder]: Building ICFG [2021-12-21 21:56:53,193 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-21 21:56:53,264 INFO L275 CfgBuilder]: Performing block encoding [2021-12-21 21:56:53,268 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-21 21:56:53,268 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2021-12-21 21:56:53,269 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 09:56:53 BoogieIcfgContainer [2021-12-21 21:56:53,269 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-21 21:56:53,270 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2021-12-21 21:56:53,270 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2021-12-21 21:56:53,272 INFO L275 PluginConnector]: BuchiAutomizer initialized [2021-12-21 21:56:53,272 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-21 21:56:53,273 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 21.12 09:56:52" (1/3) ... [2021-12-21 21:56:53,273 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1285ba75 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 21.12 09:56:53, skipping insertion in model container [2021-12-21 21:56:53,273 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-21 21:56:53,273 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 09:56:53" (2/3) ... [2021-12-21 21:56:53,274 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1285ba75 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 21.12 09:56:53, skipping insertion in model container [2021-12-21 21:56:53,274 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-21 21:56:53,274 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 09:56:53" (3/3) ... [2021-12-21 21:56:53,275 INFO L388 chiAutomizerObserver]: Analyzing ICFG Fibonacci01-2.c [2021-12-21 21:56:53,301 INFO L359 BuchiCegarLoop]: Interprodecural is true [2021-12-21 21:56:53,302 INFO L360 BuchiCegarLoop]: Hoare is false [2021-12-21 21:56:53,302 INFO L361 BuchiCegarLoop]: Compute interpolants for ForwardPredicates [2021-12-21 21:56:53,302 INFO L362 BuchiCegarLoop]: Backedges is STRAIGHT_LINE [2021-12-21 21:56:53,302 INFO L363 BuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-12-21 21:56:53,302 INFO L364 BuchiCegarLoop]: Difference is false [2021-12-21 21:56:53,302 INFO L365 BuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-12-21 21:56:53,302 INFO L368 BuchiCegarLoop]: ======== Iteration 0==of CEGAR loop == BuchiCegarLoop======== [2021-12-21 21:56:53,311 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-21 21:56:53,324 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-21 21:56:53,324 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-21 21:56:53,324 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-21 21:56:53,328 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1, 1] [2021-12-21 21:56:53,328 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-21 21:56:53,329 INFO L425 BuchiCegarLoop]: ======== Iteration 1============ [2021-12-21 21:56:53,329 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-21 21:56:53,330 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-21 21:56:53,330 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-21 21:56:53,330 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-21 21:56:53,331 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1, 1] [2021-12-21 21:56:53,331 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-21 21:56:53,335 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-21 21:56:53,335 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-21 21:56:53,339 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:53,339 INFO L85 PathProgramCache]: Analyzing trace with hash 1325876, now seen corresponding path program 1 times [2021-12-21 21:56:53,344 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:53,345 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [765469215] [2021-12-21 21:56:53,345 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:53,345 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:53,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:53,396 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-21 21:56:53,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:53,422 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-21 21:56:53,424 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:53,425 INFO L85 PathProgramCache]: Analyzing trace with hash 927646, now seen corresponding path program 1 times [2021-12-21 21:56:53,425 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:53,425 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [108617846] [2021-12-21 21:56:53,426 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:53,426 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:53,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:53,436 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-21 21:56:53,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:53,442 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-21 21:56:53,443 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:53,443 INFO L85 PathProgramCache]: Analyzing trace with hash 408654161, now seen corresponding path program 1 times [2021-12-21 21:56:53,443 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:53,443 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1136280725] [2021-12-21 21:56:53,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:53,444 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:53,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:53,466 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-21 21:56:53,474 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:53,478 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-21 21:56:53,587 INFO L210 LassoAnalysis]: Preferences: [2021-12-21 21:56:53,588 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-21 21:56:53,588 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-21 21:56:53,588 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-21 21:56:53,588 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-21 21:56:53,588 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:53,589 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-21 21:56:53,589 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-21 21:56:53,589 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration1_Loop [2021-12-21 21:56:53,589 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-21 21:56:53,589 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-21 21:56:53,597 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-21 21:56:53,601 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-21 21:56:53,603 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-21 21:56:53,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-21 21:56:53,612 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-21 21:56:53,654 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-21 21:56:53,654 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-21 21:56:53,656 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:53,656 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:53,672 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-21 21:56:53,676 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-21 21:56:53,676 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:53,677 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:53,700 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:56:53,701 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-21 21:56:53,716 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2021-12-21 21:56:53,716 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:53,717 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:53,718 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-21 21:56:53,719 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-21 21:56:53,735 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:53,735 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:53,750 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:56:53,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-21 21:56:53,768 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-21 21:56:53,768 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:53,768 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:53,770 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-21 21:56:53,771 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-21 21:56:53,772 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:53,772 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:53,791 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:56:53,791 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-21 21:56:53,807 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2021-12-21 21:56:53,808 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:53,808 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:53,821 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-21 21:56:53,822 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-21 21:56:53,824 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:53,824 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:53,860 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-21 21:56:53,861 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:53,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:53,862 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-21 21:56:53,863 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-21 21:56:53,864 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-21 21:56:53,864 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:53,934 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-21 21:56:53,937 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2021-12-21 21:56:53,937 INFO L210 LassoAnalysis]: Preferences: [2021-12-21 21:56:53,937 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-21 21:56:53,937 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-21 21:56:53,938 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-21 21:56:53,938 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-21 21:56:53,938 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:53,938 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-21 21:56:53,938 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-21 21:56:53,938 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration1_Loop [2021-12-21 21:56:53,938 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-21 21:56:53,938 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-21 21:56:53,939 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-21 21:56:53,943 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-21 21:56:53,946 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-21 21:56:53,948 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-21 21:56:53,957 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-21 21:56:54,003 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-21 21:56:54,007 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-21 21:56:54,008 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:54,009 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:54,036 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-21 21:56:54,037 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-21 21:56:54,038 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-21 21:56:54,044 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:54,045 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:54,045 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:54,045 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:54,045 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:54,047 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:54,047 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:54,048 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-21 21:56:54,066 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-21 21:56:54,066 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:54,066 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:54,067 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-21 21:56:54,068 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-21 21:56:54,069 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-21 21:56:54,075 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:54,075 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:54,075 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:54,076 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:54,076 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:54,076 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:54,076 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:54,077 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-21 21:56:54,094 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-21 21:56:54,095 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:54,095 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:54,096 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-21 21:56:54,112 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-21 21:56:54,112 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-21 21:56:54,118 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:54,118 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:54,118 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:54,118 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:54,118 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:54,118 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:54,118 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:54,134 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-21 21:56:54,149 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2021-12-21 21:56:54,149 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:54,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:54,150 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-21 21:56:54,151 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-21 21:56:54,153 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-21 21:56:54,158 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:54,159 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:54,159 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:54,159 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:54,159 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:54,162 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:54,162 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:54,187 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-21 21:56:54,200 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-21 21:56:54,200 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-21 21:56:54,201 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:54,201 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:54,202 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-21 21:56:54,203 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-21 21:56:54,204 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-21 21:56:54,204 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-21 21:56:54,204 INFO L513 LassoAnalysis]: Proved termination. [2021-12-21 21:56:54,204 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2021-12-21 21:56:54,222 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2021-12-21 21:56:54,224 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-21 21:56:54,240 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:54,253 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,254 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-21 21:56:54,254 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:54,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,270 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 21:56:54,271 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:54,299 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-21 21:56:54,319 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-21 21:56:54,320 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-21 21:56:54,379 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-21 21:56:54,380 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-21 21:56:54,383 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-21 21:56:54,384 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 15 transitions. [2021-12-21 21:56:54,384 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 4 letters. Loop has 4 letters. [2021-12-21 21:56:54,385 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:54,385 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 8 letters. Loop has 4 letters. [2021-12-21 21:56:54,385 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:54,386 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 15 transitions. Stem has 4 letters. Loop has 8 letters. [2021-12-21 21:56:54,386 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:54,386 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 51 states and 63 transitions. [2021-12-21 21:56:54,389 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-21 21:56:54,392 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 51 states to 26 states and 35 transitions. [2021-12-21 21:56:54,393 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 18 [2021-12-21 21:56:54,393 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 19 [2021-12-21 21:56:54,393 INFO L73 IsDeterministic]: Start isDeterministic. Operand 26 states and 35 transitions. [2021-12-21 21:56:54,394 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-21 21:56:54,394 INFO L681 BuchiCegarLoop]: Abstraction has 26 states and 35 transitions. [2021-12-21 21:56:54,403 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states and 35 transitions. [2021-12-21 21:56:54,409 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 21. [2021-12-21 21:56:54,410 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-21 21:56:54,410 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2021-12-21 21:56:54,411 INFO L704 BuchiCegarLoop]: Abstraction has 21 states and 27 transitions. [2021-12-21 21:56:54,411 INFO L587 BuchiCegarLoop]: Abstraction has 21 states and 27 transitions. [2021-12-21 21:56:54,413 INFO L425 BuchiCegarLoop]: ======== Iteration 2============ [2021-12-21 21:56:54,413 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 21 states and 27 transitions. [2021-12-21 21:56:54,414 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-21 21:56:54,414 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-21 21:56:54,414 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-21 21:56:54,415 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 21:56:54,415 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 21:56:54,415 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-21 21:56:54,416 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-21 21:56:54,416 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:54,416 INFO L85 PathProgramCache]: Analyzing trace with hash 1923124650, now seen corresponding path program 1 times [2021-12-21 21:56:54,416 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:54,417 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [642104609] [2021-12-21 21:56:54,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:54,417 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:54,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,449 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-21 21:56:54,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,467 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-21 21:56:54,467 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 21:56:54,467 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [642104609] [2021-12-21 21:56:54,468 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [642104609] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 21:56:54,468 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 21:56:54,468 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-21 21:56:54,468 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [945081236] [2021-12-21 21:56:54,469 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 21:56:54,470 INFO L796 eck$LassoCheckResult]: stem already infeasible [2021-12-21 21:56:54,470 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:54,470 INFO L85 PathProgramCache]: Analyzing trace with hash 481649848, now seen corresponding path program 1 times [2021-12-21 21:56:54,471 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:54,471 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [617731584] [2021-12-21 21:56:54,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:54,471 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:54,475 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,487 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-21 21:56:54,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,500 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-21 21:56:54,500 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 21:56:54,501 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [617731584] [2021-12-21 21:56:54,501 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [617731584] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 21:56:54,501 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 21:56:54,501 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-21 21:56:54,501 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2005190997] [2021-12-21 21:56:54,501 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 21:56:54,502 INFO L808 eck$LassoCheckResult]: loop already infeasible [2021-12-21 21:56:54,502 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 21:56:54,504 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-21 21:56:54,505 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2021-12-21 21:56:54,505 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-21 21:56:54,558 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 21:56:54,559 INFO L93 Difference]: Finished difference Result 27 states and 33 transitions. [2021-12-21 21:56:54,559 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-21 21:56:54,560 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 27 states and 33 transitions. [2021-12-21 21:56:54,561 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-21 21:56:54,561 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 27 states to 25 states and 31 transitions. [2021-12-21 21:56:54,562 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 21 [2021-12-21 21:56:54,562 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 21 [2021-12-21 21:56:54,562 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 31 transitions. [2021-12-21 21:56:54,562 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-21 21:56:54,562 INFO L681 BuchiCegarLoop]: Abstraction has 25 states and 31 transitions. [2021-12-21 21:56:54,562 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 31 transitions. [2021-12-21 21:56:54,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2021-12-21 21:56:54,564 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-21 21:56:54,565 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 31 transitions. [2021-12-21 21:56:54,565 INFO L704 BuchiCegarLoop]: Abstraction has 25 states and 31 transitions. [2021-12-21 21:56:54,565 INFO L587 BuchiCegarLoop]: Abstraction has 25 states and 31 transitions. [2021-12-21 21:56:54,565 INFO L425 BuchiCegarLoop]: ======== Iteration 3============ [2021-12-21 21:56:54,565 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 25 states and 31 transitions. [2021-12-21 21:56:54,566 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-21 21:56:54,566 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-21 21:56:54,566 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-21 21:56:54,567 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 21:56:54,567 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2021-12-21 21:56:54,567 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-21 21:56:54,567 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-21 21:56:54,568 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:54,568 INFO L85 PathProgramCache]: Analyzing trace with hash -512653656, now seen corresponding path program 1 times [2021-12-21 21:56:54,568 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:54,568 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1933139630] [2021-12-21 21:56:54,568 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:54,568 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:54,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:54,574 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-21 21:56:54,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:54,580 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-21 21:56:54,581 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:54,581 INFO L85 PathProgramCache]: Analyzing trace with hash 319636608, now seen corresponding path program 1 times [2021-12-21 21:56:54,581 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:54,581 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [395923073] [2021-12-21 21:56:54,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:54,581 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:54,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:54,588 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-21 21:56:54,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:54,595 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-21 21:56:54,595 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:54,595 INFO L85 PathProgramCache]: Analyzing trace with hash 911295463, now seen corresponding path program 1 times [2021-12-21 21:56:54,595 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:54,595 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1513570361] [2021-12-21 21:56:54,596 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:54,596 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:54,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,640 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-21 21:56:54,642 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,655 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2021-12-21 21:56:54,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,662 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-21 21:56:54,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,665 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-21 21:56:54,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,672 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-21 21:56:54,672 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 21:56:54,672 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1513570361] [2021-12-21 21:56:54,672 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1513570361] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 21:56:54,672 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [377500166] [2021-12-21 21:56:54,672 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:54,673 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 21:56:54,673 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:54,674 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-21 21:56:54,718 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-21 21:56:54,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:54,740 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-21 21:56:54,741 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:54,830 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-21 21:56:54,830 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 21:56:54,939 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-21 21:56:54,939 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [377500166] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 21:56:54,939 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-21 21:56:54,939 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 9 [2021-12-21 21:56:54,939 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1322790969] [2021-12-21 21:56:54,939 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-21 21:56:55,185 INFO L210 LassoAnalysis]: Preferences: [2021-12-21 21:56:55,185 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-21 21:56:55,185 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-21 21:56:55,185 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-21 21:56:55,185 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-21 21:56:55,185 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:55,185 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-21 21:56:55,185 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-21 21:56:55,185 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration3_Loop [2021-12-21 21:56:55,185 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-21 21:56:55,185 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-21 21:56:55,186 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-21 21:56:55,188 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-21 21:56:55,190 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-21 21:56:55,191 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-21 21:56:55,257 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Ended with exit code 0 [2021-12-21 21:56:55,261 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-21 21:56:55,261 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-21 21:56:55,261 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:55,261 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:55,275 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-21 21:56:55,299 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-21 21:56:55,299 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:55,300 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:55,306 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:56:55,306 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-21 21:56:55,322 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-21 21:56:55,322 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:55,322 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:55,323 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-21 21:56:55,327 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-21 21:56:55,328 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:55,328 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:55,334 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:56:55,335 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-21 21:56:55,351 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2021-12-21 21:56:55,351 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:55,351 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:55,367 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-21 21:56:55,382 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:55,383 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:55,391 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-21 21:56:55,400 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:56:55,400 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-21 21:56:55,423 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-21 21:56:55,423 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:55,423 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:55,424 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-21 21:56:55,426 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-21 21:56:55,426 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:55,426 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:55,454 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-21 21:56:55,454 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:55,454 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:55,455 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-21 21:56:55,455 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-21 21:56:55,456 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-21 21:56:55,457 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:56,041 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-21 21:56:56,045 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2021-12-21 21:56:56,045 INFO L210 LassoAnalysis]: Preferences: [2021-12-21 21:56:56,045 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-21 21:56:56,045 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-21 21:56:56,045 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-21 21:56:56,045 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-21 21:56:56,045 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:56,045 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-21 21:56:56,045 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-21 21:56:56,045 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration3_Loop [2021-12-21 21:56:56,045 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-21 21:56:56,045 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-21 21:56:56,046 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-21 21:56:56,049 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-21 21:56:56,056 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-21 21:56:56,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-21 21:56:56,107 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-21 21:56:56,107 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-21 21:56:56,108 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:56,108 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:56,109 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-21 21:56:56,120 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-21 21:56:56,120 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-21 21:56:56,126 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:56,126 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:56,126 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:56,127 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:56,127 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:56,127 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:56,127 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:56,136 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-21 21:56:56,150 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2021-12-21 21:56:56,151 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:56,151 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:56,152 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-21 21:56:56,154 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-21 21:56:56,154 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-21 21:56:56,160 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:56,160 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:56,160 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:56,161 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:56,161 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:56,161 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:56,161 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:56,172 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-21 21:56:56,187 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2021-12-21 21:56:56,188 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:56,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:56,190 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-21 21:56:56,191 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-21 21:56:56,192 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-21 21:56:56,198 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:56,199 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:56,199 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:56,199 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:56,199 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:56,200 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:56,200 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:56,216 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-21 21:56:56,232 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2021-12-21 21:56:56,232 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:56,232 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:56,233 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-21 21:56:56,237 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-21 21:56:56,237 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-21 21:56:56,243 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:56,244 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:56,244 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:56,244 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:56,244 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:56,247 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:56,247 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:56,248 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-21 21:56:56,253 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-21 21:56:56,253 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-21 21:56:56,254 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:56,254 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:56,255 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-21 21:56:56,255 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-21 21:56:56,256 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-21 21:56:56,256 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-21 21:56:56,256 INFO L513 LassoAnalysis]: Proved termination. [2021-12-21 21:56:56,256 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2021-12-21 21:56:56,272 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-21 21:56:56,273 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-21 21:56:56,287 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:56,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:56,313 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-21 21:56:56,314 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:56,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:56,406 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-21 21:56:56,407 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:56,533 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-21 21:56:56,534 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-21 21:56:56,534 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-21 21:56:56,715 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-21 21:56:56,715 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-21 21:56:56,717 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-21 21:56:56,719 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 42 transitions. [2021-12-21 21:56:56,719 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 42 transitions. Stem has 13 letters. Loop has 22 letters. [2021-12-21 21:56:56,720 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:56,720 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 42 transitions. Stem has 35 letters. Loop has 22 letters. [2021-12-21 21:56:56,721 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:56,721 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 42 transitions. Stem has 13 letters. Loop has 44 letters. [2021-12-21 21:56:56,724 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:56,724 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 160 states and 216 transitions. [2021-12-21 21:56:56,736 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 15 [2021-12-21 21:56:56,739 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 160 states to 129 states and 181 transitions. [2021-12-21 21:56:56,739 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 75 [2021-12-21 21:56:56,739 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 80 [2021-12-21 21:56:56,739 INFO L73 IsDeterministic]: Start isDeterministic. Operand 129 states and 181 transitions. [2021-12-21 21:56:56,740 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-21 21:56:56,740 INFO L681 BuchiCegarLoop]: Abstraction has 129 states and 181 transitions. [2021-12-21 21:56:56,740 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states and 181 transitions. [2021-12-21 21:56:56,752 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 107. [2021-12-21 21:56:56,752 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-21 21:56:56,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 141 transitions. [2021-12-21 21:56:56,755 INFO L704 BuchiCegarLoop]: Abstraction has 107 states and 141 transitions. [2021-12-21 21:56:56,755 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 21:56:56,756 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-12-21 21:56:56,756 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2021-12-21 21:56:56,756 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-21 21:56:56,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 21:56:56,797 INFO L93 Difference]: Finished difference Result 45 states and 58 transitions. [2021-12-21 21:56:56,798 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-21 21:56:56,798 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 45 states and 58 transitions. [2021-12-21 21:56:56,801 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-21 21:56:56,804 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 45 states to 42 states and 54 transitions. [2021-12-21 21:56:56,804 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 35 [2021-12-21 21:56:56,805 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 35 [2021-12-21 21:56:56,805 INFO L73 IsDeterministic]: Start isDeterministic. Operand 42 states and 54 transitions. [2021-12-21 21:56:56,805 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-21 21:56:56,805 INFO L681 BuchiCegarLoop]: Abstraction has 42 states and 54 transitions. [2021-12-21 21:56:56,805 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states and 54 transitions. [2021-12-21 21:56:56,815 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 39. [2021-12-21 21:56:56,815 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-21 21:56:56,817 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 48 transitions. [2021-12-21 21:56:56,817 INFO L704 BuchiCegarLoop]: Abstraction has 39 states and 48 transitions. [2021-12-21 21:56:56,817 INFO L587 BuchiCegarLoop]: Abstraction has 39 states and 48 transitions. [2021-12-21 21:56:56,817 INFO L425 BuchiCegarLoop]: ======== Iteration 4============ [2021-12-21 21:56:56,817 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 39 states and 48 transitions. [2021-12-21 21:56:56,818 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-21 21:56:56,818 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-21 21:56:56,818 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-21 21:56:56,819 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 21:56:56,819 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2021-12-21 21:56:56,820 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-21 21:56:56,820 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-21 21:56:56,820 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:56,820 INFO L85 PathProgramCache]: Analyzing trace with hash 506180814, now seen corresponding path program 2 times [2021-12-21 21:56:56,820 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:56,820 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [929590798] [2021-12-21 21:56:56,820 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:56,820 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:56,833 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:56,833 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-21 21:56:56,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:56,849 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-21 21:56:56,849 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:56,849 INFO L85 PathProgramCache]: Analyzing trace with hash 319636608, now seen corresponding path program 2 times [2021-12-21 21:56:56,849 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:56,849 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1634076281] [2021-12-21 21:56:56,850 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:56,850 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:56,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:56,861 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-21 21:56:56,864 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:56:56,865 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-21 21:56:56,865 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:56,865 INFO L85 PathProgramCache]: Analyzing trace with hash -1200508531, now seen corresponding path program 3 times [2021-12-21 21:56:56,865 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:56:56,865 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [784691779] [2021-12-21 21:56:56,865 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:56:56,865 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:56:56,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:56,908 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-21 21:56:56,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:56,946 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-21 21:56:56,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:56,958 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-21 21:56:56,959 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:56,972 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2021-12-21 21:56:56,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:56,976 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-21 21:56:56,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:56,978 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-21 21:56:56,979 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:56,980 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-21 21:56:56,980 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 21:56:56,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [784691779] [2021-12-21 21:56:56,980 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [784691779] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 21:56:56,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2132403274] [2021-12-21 21:56:56,980 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-21 21:56:56,981 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 21:56:56,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:56,984 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-21 21:56:57,000 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-21 21:56:57,033 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2021-12-21 21:56:57,033 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 21:56:57,034 INFO L263 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-21 21:56:57,038 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:57,139 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-21 21:56:57,208 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-21 21:56:57,209 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 21:56:57,491 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-21 21:56:57,492 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2132403274] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 21:56:57,492 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-21 21:56:57,492 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10, 12] total 21 [2021-12-21 21:56:57,492 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [486573943] [2021-12-21 21:56:57,492 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-21 21:56:57,712 INFO L210 LassoAnalysis]: Preferences: [2021-12-21 21:56:57,712 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-21 21:56:57,712 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-21 21:56:57,712 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-21 21:56:57,712 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-21 21:56:57,712 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:57,712 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-21 21:56:57,712 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-21 21:56:57,712 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration4_Loop [2021-12-21 21:56:57,712 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-21 21:56:57,712 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-21 21:56:57,713 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-21 21:56:57,714 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-21 21:56:57,722 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-21 21:56:57,724 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-21 21:56:57,766 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-21 21:56:57,766 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-21 21:56:57,766 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:57,766 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:57,767 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-21 21:56:57,769 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:57,769 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:57,777 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:56:57,777 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-21 21:56:57,791 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-21 21:56:57,791 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2021-12-21 21:56:57,792 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:57,792 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:57,792 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-21 21:56:57,794 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-21 21:56:57,794 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:56:57,794 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:57,821 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2021-12-21 21:56:57,822 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:57,822 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:57,822 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-21 21:56:57,823 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-21 21:56:57,824 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-21 21:56:57,824 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:56:58,396 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-21 21:56:58,400 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-21 21:56:58,400 INFO L210 LassoAnalysis]: Preferences: [2021-12-21 21:56:58,400 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-21 21:56:58,400 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-21 21:56:58,400 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-21 21:56:58,400 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-21 21:56:58,400 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:58,400 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-21 21:56:58,400 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-21 21:56:58,400 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration4_Loop [2021-12-21 21:56:58,400 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-21 21:56:58,400 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-21 21:56:58,401 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-21 21:56:58,404 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-21 21:56:58,411 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-21 21:56:58,413 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-21 21:56:58,473 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-21 21:56:58,473 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-21 21:56:58,474 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:58,474 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:58,475 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-21 21:56:58,476 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-21 21:56:58,477 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-21 21:56:58,484 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:58,484 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:58,484 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:58,484 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:58,484 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:58,484 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:58,484 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:58,507 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-21 21:56:58,523 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2021-12-21 21:56:58,523 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:58,523 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:58,524 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-21 21:56:58,525 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-21 21:56:58,526 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-21 21:56:58,532 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:56:58,532 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:56:58,533 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:56:58,533 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:56:58,533 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:56:58,534 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:56:58,534 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:56:58,553 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-21 21:56:58,555 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2021-12-21 21:56:58,555 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2021-12-21 21:56:58,555 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:56:58,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:56:58,557 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-21 21:56:58,557 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-21 21:56:58,558 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-21 21:56:58,558 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-21 21:56:58,558 INFO L513 LassoAnalysis]: Proved termination. [2021-12-21 21:56:58,558 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2021-12-21 21:56:58,579 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2021-12-21 21:56:58,579 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-21 21:56:58,587 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:58,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:58,616 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-21 21:56:58,617 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:58,859 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:58,860 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-21 21:56:58,861 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:58,944 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-21 21:56:58,990 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-21 21:56:58,991 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-21 21:56:58,991 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-21 21:56:59,054 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-21 21:56:59,055 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-21 21:56:59,056 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-21 21:56:59,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2021-12-21 21:56:59,056 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 25 letters. Loop has 22 letters. [2021-12-21 21:56:59,056 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:59,056 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-21 21:56:59,063 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:59,084 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:59,085 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-21 21:56:59,086 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:59,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:59,270 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-21 21:56:59,271 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:59,365 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-21 21:56:59,366 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-21 21:56:59,366 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-21 21:56:59,421 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-21 21:56:59,422 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-21 21:56:59,422 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-21 21:56:59,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 18 transitions. [2021-12-21 21:56:59,423 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 18 transitions. Stem has 25 letters. Loop has 22 letters. [2021-12-21 21:56:59,423 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:59,423 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-21 21:56:59,428 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:56:59,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:59,447 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 10 conjunts are in the unsatisfiable core [2021-12-21 21:56:59,448 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:59,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:56:59,630 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-21 21:56:59,631 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:56:59,741 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-21 21:56:59,741 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-21 21:56:59,742 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-21 21:56:59,905 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-21 21:56:59,906 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-21 21:56:59,906 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-21 21:56:59,906 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 47 transitions. [2021-12-21 21:56:59,907 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 47 transitions. Stem has 25 letters. Loop has 22 letters. [2021-12-21 21:56:59,907 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:59,907 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 47 transitions. Stem has 47 letters. Loop has 22 letters. [2021-12-21 21:56:59,907 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:59,907 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 47 transitions. Stem has 25 letters. Loop has 44 letters. [2021-12-21 21:56:59,908 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:56:59,908 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 345 states and 444 transitions. [2021-12-21 21:56:59,911 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-21 21:56:59,914 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 345 states to 220 states and 297 transitions. [2021-12-21 21:56:59,914 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 99 [2021-12-21 21:56:59,915 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 116 [2021-12-21 21:56:59,915 INFO L73 IsDeterministic]: Start isDeterministic. Operand 220 states and 297 transitions. [2021-12-21 21:56:59,915 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-21 21:56:59,915 INFO L681 BuchiCegarLoop]: Abstraction has 220 states and 297 transitions. [2021-12-21 21:56:59,916 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 220 states and 297 transitions. [2021-12-21 21:56:59,923 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 220 to 172. [2021-12-21 21:56:59,923 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-21 21:56:59,924 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 172 states to 172 states and 223 transitions. [2021-12-21 21:56:59,924 INFO L704 BuchiCegarLoop]: Abstraction has 172 states and 223 transitions. [2021-12-21 21:56:59,924 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 21:56:59,924 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-21 21:56:59,924 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=89, Invalid=331, Unknown=0, NotChecked=0, Total=420 [2021-12-21 21:56:59,925 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-21 21:57:00,116 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 21:57:00,116 INFO L93 Difference]: Finished difference Result 349 states and 503 transitions. [2021-12-21 21:57:00,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2021-12-21 21:57:00,118 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 349 states and 503 transitions. [2021-12-21 21:57:00,121 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-21 21:57:00,125 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 349 states to 339 states and 490 transitions. [2021-12-21 21:57:00,125 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 173 [2021-12-21 21:57:00,125 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 193 [2021-12-21 21:57:00,125 INFO L73 IsDeterministic]: Start isDeterministic. Operand 339 states and 490 transitions. [2021-12-21 21:57:00,125 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-21 21:57:00,125 INFO L681 BuchiCegarLoop]: Abstraction has 339 states and 490 transitions. [2021-12-21 21:57:00,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 339 states and 490 transitions. [2021-12-21 21:57:00,134 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 339 to 274. [2021-12-21 21:57:00,135 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-21 21:57:00,136 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 401 transitions. [2021-12-21 21:57:00,136 INFO L704 BuchiCegarLoop]: Abstraction has 274 states and 401 transitions. [2021-12-21 21:57:00,136 INFO L587 BuchiCegarLoop]: Abstraction has 274 states and 401 transitions. [2021-12-21 21:57:00,136 INFO L425 BuchiCegarLoop]: ======== Iteration 5============ [2021-12-21 21:57:00,136 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 274 states and 401 transitions. [2021-12-21 21:57:00,138 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-21 21:57:00,138 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-21 21:57:00,138 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-21 21:57:00,139 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [12, 10, 9, 7, 7, 5, 5, 4, 4, 3, 2, 1, 1, 1, 1] [2021-12-21 21:57:00,139 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-21 21:57:00,139 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-21 21:57:00,139 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-21 21:57:00,139 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:57:00,139 INFO L85 PathProgramCache]: Analyzing trace with hash -1489009265, now seen corresponding path program 4 times [2021-12-21 21:57:00,139 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:57:00,139 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [274025525] [2021-12-21 21:57:00,139 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:57:00,139 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:57:00,150 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:57:00,150 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-21 21:57:00,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:57:00,161 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-21 21:57:00,162 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:57:00,162 INFO L85 PathProgramCache]: Analyzing trace with hash 927646, now seen corresponding path program 2 times [2021-12-21 21:57:00,162 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:57:00,162 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1043016236] [2021-12-21 21:57:00,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:57:00,162 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:57:00,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:57:00,164 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-21 21:57:00,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-21 21:57:00,165 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-21 21:57:00,165 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:57:00,165 INFO L85 PathProgramCache]: Analyzing trace with hash 1238644268, now seen corresponding path program 5 times [2021-12-21 21:57:00,165 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 21:57:00,165 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [499582863] [2021-12-21 21:57:00,165 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 21:57:00,165 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 21:57:00,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,225 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-21 21:57:00,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,263 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-21 21:57:00,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,294 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-21 21:57:00,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,314 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-21 21:57:00,316 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,321 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-21 21:57:00,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,324 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2021-12-21 21:57:00,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,328 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2021-12-21 21:57:00,330 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,334 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-21 21:57:00,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,336 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-21 21:57:00,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:00,339 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-21 21:57:00,339 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 21:57:00,339 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [499582863] [2021-12-21 21:57:00,340 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [499582863] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 21:57:00,340 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [35254299] [2021-12-21 21:57:00,340 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-21 21:57:00,340 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 21:57:00,340 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:00,341 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-21 21:57:00,363 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-21 21:57:00,401 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2021-12-21 21:57:00,401 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 21:57:00,402 INFO L263 TraceCheckSpWp]: Trace formula consists of 181 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-21 21:57:00,404 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:57:00,527 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-21 21:57:00,527 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 21:57:00,845 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-21 21:57:00,845 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [35254299] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 21:57:00,846 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-21 21:57:00,846 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13, 16] total 21 [2021-12-21 21:57:00,846 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2004818302] [2021-12-21 21:57:00,846 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-21 21:57:00,879 INFO L210 LassoAnalysis]: Preferences: [2021-12-21 21:57:00,880 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-21 21:57:00,880 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-21 21:57:00,880 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-21 21:57:00,880 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-21 21:57:00,880 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:00,880 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-21 21:57:00,880 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-21 21:57:00,880 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration5_Loop [2021-12-21 21:57:00,880 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-21 21:57:00,880 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-21 21:57:00,880 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-21 21:57:00,881 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-21 21:57:00,882 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-21 21:57:00,883 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-21 21:57:00,886 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-21 21:57:00,900 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-21 21:57:00,900 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-21 21:57:00,900 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:00,900 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:00,920 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-21 21:57:00,932 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-21 21:57:00,933 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:57:00,933 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:57:00,952 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:57:00,952 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-21 21:57:00,970 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-21 21:57:00,970 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:00,970 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:00,971 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-21 21:57:00,988 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-21 21:57:00,993 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:57:00,993 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:57:01,010 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:57:01,010 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-21 21:57:01,027 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2021-12-21 21:57:01,028 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:01,028 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:01,043 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-21 21:57:01,044 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-21 21:57:01,045 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:57:01,045 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:57:01,065 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-21 21:57:01,066 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-21 21:57:01,083 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2021-12-21 21:57:01,083 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:01,083 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:01,093 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-21 21:57:01,094 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-21 21:57:01,095 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-21 21:57:01,095 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:57:01,132 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2021-12-21 21:57:01,133 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:01,133 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:01,143 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-21 21:57:01,143 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-21 21:57:01,144 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-21 21:57:01,144 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-21 21:57:01,177 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-21 21:57:01,182 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2021-12-21 21:57:01,182 INFO L210 LassoAnalysis]: Preferences: [2021-12-21 21:57:01,182 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-21 21:57:01,182 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-21 21:57:01,182 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-21 21:57:01,182 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-21 21:57:01,182 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:01,182 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-21 21:57:01,182 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-21 21:57:01,182 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci01-2.c_Iteration5_Loop [2021-12-21 21:57:01,182 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-21 21:57:01,182 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-21 21:57:01,183 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-21 21:57:01,185 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-21 21:57:01,186 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-21 21:57:01,190 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-21 21:57:01,192 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-21 21:57:01,212 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-21 21:57:01,212 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-21 21:57:01,212 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:01,212 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:01,216 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-21 21:57:01,217 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-21 21:57:01,218 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-21 21:57:01,224 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:57:01,224 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:57:01,224 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:57:01,224 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:57:01,224 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:57:01,225 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:57:01,225 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:57:01,239 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-21 21:57:01,256 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2021-12-21 21:57:01,256 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:01,256 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:01,257 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-21 21:57:01,265 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-21 21:57:01,271 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:57:01,271 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:57:01,271 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:57:01,271 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:57:01,271 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:57:01,271 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:57:01,271 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:57:01,272 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-21 21:57:01,286 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-21 21:57:01,289 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-21 21:57:01,290 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:01,290 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:01,291 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-21 21:57:01,291 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-21 21:57:01,292 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-21 21:57:01,299 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-21 21:57:01,299 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-21 21:57:01,299 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-21 21:57:01,299 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-21 21:57:01,299 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-21 21:57:01,300 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-21 21:57:01,300 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-21 21:57:01,301 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-21 21:57:01,303 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-21 21:57:01,303 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-21 21:57:01,303 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-21 21:57:01,303 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 21:57:01,304 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-21 21:57:01,305 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-21 21:57:01,306 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-21 21:57:01,306 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-21 21:57:01,306 INFO L513 LassoAnalysis]: Proved termination. [2021-12-21 21:57:01,306 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2021-12-21 21:57:01,321 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-21 21:57:01,322 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-21 21:57:01,329 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:57:01,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:01,392 INFO L263 TraceCheckSpWp]: Trace formula consists of 537 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-21 21:57:01,394 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:57:01,976 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-21 21:57:02,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:02,031 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 21:57:02,032 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:57:02,054 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-21 21:57:02,054 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-21 21:57:02,054 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-21 21:57:02,099 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-21 21:57:02,100 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-21 21:57:02,100 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-21 21:57:02,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2021-12-21 21:57:02,100 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 72 letters. Loop has 4 letters. [2021-12-21 21:57:02,100 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:57:02,101 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-21 21:57:02,108 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:57:02,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:02,171 INFO L263 TraceCheckSpWp]: Trace formula consists of 537 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-21 21:57:02,173 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:57:02,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:02,775 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 21:57:02,775 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:57:02,797 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-21 21:57:02,798 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-21 21:57:02,798 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-21 21:57:02,860 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-21 21:57:02,863 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-21 21:57:02,863 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-21 21:57:02,863 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 14 transitions. [2021-12-21 21:57:02,863 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 14 transitions. Stem has 72 letters. Loop has 4 letters. [2021-12-21 21:57:02,863 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:57:02,863 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-21 21:57:02,870 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 21:57:02,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:02,919 INFO L263 TraceCheckSpWp]: Trace formula consists of 537 conjuncts, 28 conjunts are in the unsatisfiable core [2021-12-21 21:57:02,920 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:57:03,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 21:57:03,416 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 21:57:03,416 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 21:57:03,431 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-21 21:57:03,432 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-21 21:57:03,432 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-21 21:57:03,484 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-21 21:57:03,484 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-21 21:57:03,485 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-21 21:57:03,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 22 transitions. [2021-12-21 21:57:03,485 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 22 transitions. Stem has 72 letters. Loop has 4 letters. [2021-12-21 21:57:03,487 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:57:03,487 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 22 transitions. Stem has 76 letters. Loop has 4 letters. [2021-12-21 21:57:03,487 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:57:03,487 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 22 transitions. Stem has 72 letters. Loop has 8 letters. [2021-12-21 21:57:03,487 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-21 21:57:03,488 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 349 states and 484 transitions. [2021-12-21 21:57:03,491 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-21 21:57:03,494 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 349 states to 288 states and 417 transitions. [2021-12-21 21:57:03,494 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 138 [2021-12-21 21:57:03,494 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 143 [2021-12-21 21:57:03,494 INFO L73 IsDeterministic]: Start isDeterministic. Operand 288 states and 417 transitions. [2021-12-21 21:57:03,495 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-21 21:57:03,495 INFO L681 BuchiCegarLoop]: Abstraction has 288 states and 417 transitions. [2021-12-21 21:57:03,495 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 288 states and 417 transitions. [2021-12-21 21:57:03,501 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 288 to 280. [2021-12-21 21:57:03,502 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-21 21:57:03,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 280 states to 280 states and 409 transitions. [2021-12-21 21:57:03,504 INFO L704 BuchiCegarLoop]: Abstraction has 280 states and 409 transitions. [2021-12-21 21:57:03,504 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 21:57:03,504 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-21 21:57:03,504 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=305, Unknown=0, NotChecked=0, Total=420 [2021-12-21 21:57:03,505 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-21 21:57:03,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 21:57:03,694 INFO L93 Difference]: Finished difference Result 408 states and 601 transitions. [2021-12-21 21:57:03,694 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2021-12-21 21:57:03,694 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 408 states and 601 transitions. [2021-12-21 21:57:03,698 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-21 21:57:03,698 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 408 states to 0 states and 0 transitions. [2021-12-21 21:57:03,699 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2021-12-21 21:57:03,699 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2021-12-21 21:57:03,699 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2021-12-21 21:57:03,699 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2021-12-21 21:57:03,699 INFO L681 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-21 21:57:03,699 INFO L704 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-21 21:57:03,699 INFO L587 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-21 21:57:03,699 INFO L425 BuchiCegarLoop]: ======== Iteration 6============ [2021-12-21 21:57:03,699 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2021-12-21 21:57:03,699 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-21 21:57:03,700 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2021-12-21 21:57:03,704 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 21.12 09:57:03 BoogieIcfgContainer [2021-12-21 21:57:03,704 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2021-12-21 21:57:03,705 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2021-12-21 21:57:03,705 INFO L271 PluginConnector]: Initializing Witness Printer... [2021-12-21 21:57:03,705 INFO L275 PluginConnector]: Witness Printer initialized [2021-12-21 21:57:03,706 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 09:56:53" (3/4) ... [2021-12-21 21:57:03,708 INFO L140 WitnessPrinter]: No result that supports witness generation found [2021-12-21 21:57:03,708 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2021-12-21 21:57:03,709 INFO L158 Benchmark]: Toolchain (without parser) took 10818.16ms. Allocated memory was 134.2MB in the beginning and 264.2MB in the end (delta: 130.0MB). Free memory was 111.1MB in the beginning and 229.7MB in the end (delta: -118.6MB). Peak memory consumption was 12.4MB. Max. memory is 16.1GB. [2021-12-21 21:57:03,709 INFO L158 Benchmark]: CDTParser took 0.19ms. Allocated memory is still 134.2MB. Free memory is still 92.3MB. There was no memory consumed. Max. memory is 16.1GB. [2021-12-21 21:57:03,709 INFO L158 Benchmark]: CACSL2BoogieTranslator took 168.17ms. Allocated memory is still 134.2MB. Free memory was 111.1MB in the beginning and 110.0MB in the end (delta: 1.1MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2021-12-21 21:57:03,709 INFO L158 Benchmark]: Boogie Procedure Inliner took 16.83ms. Allocated memory is still 134.2MB. Free memory was 110.0MB in the beginning and 108.8MB in the end (delta: 1.2MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2021-12-21 21:57:03,710 INFO L158 Benchmark]: Boogie Preprocessor took 9.55ms. Allocated memory is still 134.2MB. Free memory was 108.8MB in the beginning and 107.9MB in the end (delta: 909.8kB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-21 21:57:03,710 INFO L158 Benchmark]: RCFGBuilder took 182.26ms. Allocated memory is still 134.2MB. Free memory was 107.9MB in the beginning and 99.1MB in the end (delta: 8.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-12-21 21:57:03,710 INFO L158 Benchmark]: BuchiAutomizer took 10434.89ms. Allocated memory was 134.2MB in the beginning and 264.2MB in the end (delta: 130.0MB). Free memory was 99.1MB in the beginning and 230.7MB in the end (delta: -131.7MB). Peak memory consumption was 2.2MB. Max. memory is 16.1GB. [2021-12-21 21:57:03,710 INFO L158 Benchmark]: Witness Printer took 3.16ms. Allocated memory is still 264.2MB. Free memory was 230.7MB in the beginning and 229.7MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-21 21:57:03,712 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.19ms. Allocated memory is still 134.2MB. Free memory is still 92.3MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 168.17ms. Allocated memory is still 134.2MB. Free memory was 111.1MB in the beginning and 110.0MB in the end (delta: 1.1MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 16.83ms. Allocated memory is still 134.2MB. Free memory was 110.0MB in the beginning and 108.8MB in the end (delta: 1.2MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 9.55ms. Allocated memory is still 134.2MB. Free memory was 108.8MB in the beginning and 107.9MB in the end (delta: 909.8kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 182.26ms. Allocated memory is still 134.2MB. Free memory was 107.9MB in the beginning and 99.1MB in the end (delta: 8.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 10434.89ms. Allocated memory was 134.2MB in the beginning and 264.2MB in the end (delta: 130.0MB). Free memory was 99.1MB in the beginning and 230.7MB in the end (delta: -131.7MB). Peak memory consumption was 2.2MB. Max. memory is 16.1GB. * Witness Printer took 3.16ms. Allocated memory is still 264.2MB. Free memory was 230.7MB in the beginning and 229.7MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 8 terminating modules (4 trivial, 2 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 4 locations. One deterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function \old(n) and consists of 5 locations. 4 modules have a trivial ranking function, the largest among these consists of 21 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 10.4s and 6 iterations. TraceHistogramMax:12. Analysis of lassos took 5.6s. Construction of modules took 0.4s. Büchi inclusion checks took 4.1s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 7. Automata minimization 0.1s AutomataMinimizationTime, 7 MinimizatonAttempts, 151 StatesRemovedByMinimization, 6 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had 274 states and ocurred in iteration 4. Nontrivial modules had stage [2, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 16/46 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 471 SdHoareTripleChecker+Valid, 0.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 442 mSDsluCounter, 384 SdHoareTripleChecker+Invalid, 0.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 223 mSDsCounter, 318 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 711 IncrementalHoareTripleChecker+Invalid, 1029 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 318 mSolverCounterUnsat, 161 mSDtfsCounter, 711 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT3 SILN0 SILU0 SILI1 SILT0 lasso0 LassoPreprocessingBenchmarks: Lassos: inital21 mio100 ax100 hnf100 lsp94 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq171 hnf95 smp62 dnf100 smp100 tf110 neg95 sie113 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 40ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 10 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 1.7s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2021-12-21 21:57:03,736 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-21 21:57:03,952 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Ended with exit code 0 [2021-12-21 21:57:04,149 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-21 21:57:04,351 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE