./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_5-2.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 35987657 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/recursive-simple/fibo_5-2.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-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 32bit --witnessprinter.graph.data.programhash 02dc726982da9e300f34803a4bdbb3c0165037d3f4471bd0e009c42cfb19ed24 --- Real Ultimate output --- This is Ultimate 0.2.2-?-3598765 [2022-07-22 02:40:34,314 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-22 02:40:34,316 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-22 02:40:34,343 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-22 02:40:34,343 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-22 02:40:34,344 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-22 02:40:34,347 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-22 02:40:34,349 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-22 02:40:34,355 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-22 02:40:34,359 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-22 02:40:34,359 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-22 02:40:34,361 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-22 02:40:34,361 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-22 02:40:34,363 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-22 02:40:34,364 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-22 02:40:34,369 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-22 02:40:34,370 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-22 02:40:34,371 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-22 02:40:34,372 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-22 02:40:34,376 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-22 02:40:34,378 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-22 02:40:34,379 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-22 02:40:34,380 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-22 02:40:34,381 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-22 02:40:34,382 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-22 02:40:34,385 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-22 02:40:34,388 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-22 02:40:34,388 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-22 02:40:34,389 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-22 02:40:34,389 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-22 02:40:34,389 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-22 02:40:34,390 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-22 02:40:34,391 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-22 02:40:34,391 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-22 02:40:34,392 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-22 02:40:34,393 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-22 02:40:34,393 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-22 02:40:34,393 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-22 02:40:34,394 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-22 02:40:34,394 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-22 02:40:34,394 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-22 02:40:34,395 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-22 02:40:34,399 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2022-07-22 02:40:34,419 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-22 02:40:34,420 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-22 02:40:34,420 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-22 02:40:34,420 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-22 02:40:34,422 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-22 02:40:34,422 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-22 02:40:34,422 INFO L138 SettingsManager]: * Use SBE=true [2022-07-22 02:40:34,422 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2022-07-22 02:40:34,422 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2022-07-22 02:40:34,423 INFO L138 SettingsManager]: * Use old map elimination=false [2022-07-22 02:40:34,423 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2022-07-22 02:40:34,423 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2022-07-22 02:40:34,424 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2022-07-22 02:40:34,424 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-22 02:40:34,424 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-22 02:40:34,424 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2022-07-22 02:40:34,424 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-22 02:40:34,424 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-22 02:40:34,424 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-22 02:40:34,424 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2022-07-22 02:40:34,425 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2022-07-22 02:40:34,425 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2022-07-22 02:40:34,425 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-22 02:40:34,425 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-22 02:40:34,425 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2022-07-22 02:40:34,425 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-22 02:40:34,426 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2022-07-22 02:40:34,426 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-22 02:40:34,426 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-22 02:40:34,426 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-22 02:40:34,426 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-22 02:40:34,428 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-07-22 02:40:34,428 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 -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 02dc726982da9e300f34803a4bdbb3c0165037d3f4471bd0e009c42cfb19ed24 [2022-07-22 02:40:34,697 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-22 02:40:34,738 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-22 02:40:34,740 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-22 02:40:34,741 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-22 02:40:34,742 INFO L275 PluginConnector]: CDTParser initialized [2022-07-22 02:40:34,743 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_5-2.c [2022-07-22 02:40:34,826 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8312ea1c9/9e5a3973e9fc4447897f8b2d0657ee7a/FLAGaac18ba2a [2022-07-22 02:40:35,216 INFO L306 CDTParser]: Found 1 translation units. [2022-07-22 02:40:35,216 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-2.c [2022-07-22 02:40:35,220 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8312ea1c9/9e5a3973e9fc4447897f8b2d0657ee7a/FLAGaac18ba2a [2022-07-22 02:40:35,597 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8312ea1c9/9e5a3973e9fc4447897f8b2d0657ee7a [2022-07-22 02:40:35,599 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-22 02:40:35,600 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-22 02:40:35,602 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-22 02:40:35,603 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-22 02:40:35,605 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-22 02:40:35,606 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,606 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7d874acd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35, skipping insertion in model container [2022-07-22 02:40:35,606 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,611 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-22 02:40:35,620 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-22 02:40:35,727 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/recursive-simple/fibo_5-2.c[740,753] [2022-07-22 02:40:35,739 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-22 02:40:35,746 INFO L203 MainTranslator]: Completed pre-run [2022-07-22 02:40:35,781 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/recursive-simple/fibo_5-2.c[740,753] [2022-07-22 02:40:35,787 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-22 02:40:35,813 INFO L208 MainTranslator]: Completed translation [2022-07-22 02:40:35,814 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35 WrapperNode [2022-07-22 02:40:35,814 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-22 02:40:35,815 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-22 02:40:35,815 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-22 02:40:35,815 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-22 02:40:35,819 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,839 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,850 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2022-07-22 02:40:35,863 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-22 02:40:35,865 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-22 02:40:35,865 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-22 02:40:35,865 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-22 02:40:35,870 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,870 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,872 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,872 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,874 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,875 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,879 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,881 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-22 02:40:35,885 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-22 02:40:35,886 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-22 02:40:35,886 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-22 02:40:35,887 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (1/1) ... [2022-07-22 02:40:35,893 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:35,901 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:35,917 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) [2022-07-22 02:40:35,920 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 [2022-07-22 02:40:35,957 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-22 02:40:35,957 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-22 02:40:35,957 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-22 02:40:35,958 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-22 02:40:35,958 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2022-07-22 02:40:35,958 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2022-07-22 02:40:36,007 INFO L234 CfgBuilder]: Building ICFG [2022-07-22 02:40:36,009 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-22 02:40:36,112 INFO L275 CfgBuilder]: Performing block encoding [2022-07-22 02:40:36,116 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-22 02:40:36,117 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2022-07-22 02:40:36,119 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.07 02:40:36 BoogieIcfgContainer [2022-07-22 02:40:36,119 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-22 02:40:36,120 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2022-07-22 02:40:36,120 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2022-07-22 02:40:36,122 INFO L275 PluginConnector]: BuchiAutomizer initialized [2022-07-22 02:40:36,123 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-22 02:40:36,123 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 22.07 02:40:35" (1/3) ... [2022-07-22 02:40:36,124 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@10197a48 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 22.07 02:40:36, skipping insertion in model container [2022-07-22 02:40:36,124 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-22 02:40:36,124 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.07 02:40:35" (2/3) ... [2022-07-22 02:40:36,124 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@10197a48 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 22.07 02:40:36, skipping insertion in model container [2022-07-22 02:40:36,124 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-22 02:40:36,125 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.07 02:40:36" (3/3) ... [2022-07-22 02:40:36,126 INFO L354 chiAutomizerObserver]: Analyzing ICFG fibo_5-2.c [2022-07-22 02:40:36,208 INFO L255 stractBuchiCegarLoop]: Interprodecural is true [2022-07-22 02:40:36,223 INFO L256 stractBuchiCegarLoop]: Hoare is false [2022-07-22 02:40:36,223 INFO L257 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2022-07-22 02:40:36,223 INFO L258 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2022-07-22 02:40:36,224 INFO L259 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2022-07-22 02:40:36,224 INFO L260 stractBuchiCegarLoop]: Difference is false [2022-07-22 02:40:36,224 INFO L261 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2022-07-22 02:40:36,224 INFO L265 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2022-07-22 02:40:36,228 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-22 02:40:36,243 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:36,244 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-22 02:40:36,244 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-22 02:40:36,249 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2022-07-22 02:40:36,251 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-22 02:40:36,251 INFO L287 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2022-07-22 02:40:36,252 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-22 02:40:36,255 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:36,255 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-22 02:40:36,256 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-22 02:40:36,256 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2022-07-22 02:40:36,256 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-22 02:40:36,262 INFO L752 eck$LassoCheckResult]: Stem: 3#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(11, 2);call #Ultimate.allocInit(12, 3); 12#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 5#L27true call main_#t~ret6#1 := fibo(main_~x~0#1);< 6#fiboENTRYtrue [2022-07-22 02:40:36,262 INFO L754 eck$LassoCheckResult]: Loop: 6#fiboENTRYtrue ~n := #in~n; 7#L8true assume !(~n < 1); 9#L10true assume !(1 == ~n); 14#L13true call #t~ret4 := fibo(~n - 1);< 6#fiboENTRYtrue [2022-07-22 02:40:36,269 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:36,270 INFO L85 PathProgramCache]: Analyzing trace with hash 29883, now seen corresponding path program 1 times [2022-07-22 02:40:36,276 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:36,281 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1344496993] [2022-07-22 02:40:36,282 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:36,282 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:36,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:36,353 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 02:40:36,368 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:36,384 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 02:40:36,387 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:36,387 INFO L85 PathProgramCache]: Analyzing trace with hash 1450956, now seen corresponding path program 1 times [2022-07-22 02:40:36,387 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:36,388 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2078715556] [2022-07-22 02:40:36,388 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:36,389 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:36,398 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:36,399 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 02:40:36,404 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:36,406 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 02:40:36,413 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:36,414 INFO L85 PathProgramCache]: Analyzing trace with hash 1828301702, now seen corresponding path program 1 times [2022-07-22 02:40:36,414 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:36,414 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2066623085] [2022-07-22 02:40:36,415 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:36,415 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:36,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:36,434 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 02:40:36,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:36,447 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 02:40:36,548 INFO L210 LassoAnalysis]: Preferences: [2022-07-22 02:40:36,549 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-22 02:40:36,549 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-22 02:40:36,550 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-22 02:40:36,550 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-22 02:40:36,550 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:36,550 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-22 02:40:36,550 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-22 02:40:36,550 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2022-07-22 02:40:36,551 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-22 02:40:36,551 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-22 02:40:36,561 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:36,566 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:36,569 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:36,573 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:36,579 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:36,613 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-22 02:40:36,614 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-22 02:40:36,615 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:36,616 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:36,632 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) [2022-07-22 02:40:36,682 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 [2022-07-22 02:40:36,683 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:36,683 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:36,707 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-22 02:40:36,708 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-22 02:40:36,748 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:36,749 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:36,749 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:36,750 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) [2022-07-22 02:40:36,756 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:36,756 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:36,765 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 [2022-07-22 02:40:36,775 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-22 02:40:36,776 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-22 02:40:36,810 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 [2022-07-22 02:40:36,811 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:36,811 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:36,817 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) [2022-07-22 02:40:36,819 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 [2022-07-22 02:40:36,820 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:36,821 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:36,842 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-22 02:40:36,842 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-22 02:40:36,860 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 [2022-07-22 02:40:36,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:36,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:36,867 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) [2022-07-22 02:40:36,874 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 [2022-07-22 02:40:36,875 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:36,875 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:36,901 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 [2022-07-22 02:40:36,902 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:36,902 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:36,903 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) [2022-07-22 02:40:36,904 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 [2022-07-22 02:40:36,918 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-22 02:40:36,918 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:36,972 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-22 02:40:36,976 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2022-07-22 02:40:36,976 INFO L210 LassoAnalysis]: Preferences: [2022-07-22 02:40:36,976 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-22 02:40:36,976 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-22 02:40:36,976 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-22 02:40:36,976 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-22 02:40:36,976 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:36,976 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-22 02:40:36,976 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-22 02:40:36,976 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2022-07-22 02:40:36,976 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-22 02:40:36,977 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-22 02:40:36,977 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:36,981 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:36,984 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:36,987 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:36,993 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:37,030 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-22 02:40:37,034 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-22 02:40:37,035 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:37,035 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:37,047 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) [2022-07-22 02:40:37,049 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 [2022-07-22 02:40:37,050 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 [2022-07-22 02:40:37,057 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:37,057 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:37,057 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:37,057 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:37,057 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:37,059 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:37,059 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:37,083 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-22 02:40:37,112 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 [2022-07-22 02:40:37,112 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:37,112 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:37,113 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) [2022-07-22 02:40:37,122 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 [2022-07-22 02:40:37,140 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 [2022-07-22 02:40:37,147 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:37,147 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:37,147 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:37,147 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:37,147 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:37,148 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:37,148 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:37,163 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-22 02:40:37,192 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 [2022-07-22 02:40:37,193 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:37,193 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:37,197 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) [2022-07-22 02:40:37,198 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 [2022-07-22 02:40:37,200 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-22 02:40:37,206 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:37,206 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:37,206 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:37,206 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:37,207 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:37,208 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:37,208 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:37,212 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-22 02:40:37,247 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 [2022-07-22 02:40:37,248 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:37,248 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:37,249 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) [2022-07-22 02:40:37,251 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 [2022-07-22 02:40:37,252 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 [2022-07-22 02:40:37,259 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:37,259 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:37,259 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:37,259 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:37,259 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:37,261 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:37,261 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:37,268 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-22 02:40:37,286 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-22 02:40:37,286 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-22 02:40:37,287 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:37,287 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:37,288 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) [2022-07-22 02:40:37,291 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 [2022-07-22 02:40:37,291 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-22 02:40:37,291 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-22 02:40:37,291 INFO L513 LassoAnalysis]: Proved termination. [2022-07-22 02:40:37,292 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2022-07-22 02:40:37,311 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:37,313 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-22 02:40:37,329 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:37,343 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:37,345 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-22 02:40:37,345 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:37,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:37,360 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-22 02:40:37,360 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:37,388 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 02:40:37,409 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 [2022-07-22 02:40:37,410 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-22 02:40:37,485 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:37,488 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 48 states and 60 transitions. Complement of second has 12 states. [2022-07-22 02:40:37,490 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 [2022-07-22 02:40:37,494 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-22 02:40:37,494 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 11 transitions. [2022-07-22 02:40:37,495 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 4 letters. [2022-07-22 02:40:37,496 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:37,496 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 7 letters. Loop has 4 letters. [2022-07-22 02:40:37,496 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:37,497 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 8 letters. [2022-07-22 02:40:37,497 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:37,497 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 48 states and 60 transitions. [2022-07-22 02:40:37,500 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:37,518 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 48 states to 25 states and 34 transitions. [2022-07-22 02:40:37,518 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2022-07-22 02:40:37,519 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 18 [2022-07-22 02:40:37,519 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 34 transitions. [2022-07-22 02:40:37,519 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-22 02:40:37,519 INFO L369 hiAutomatonCegarLoop]: Abstraction has 25 states and 34 transitions. [2022-07-22 02:40:37,531 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 34 transitions. [2022-07-22 02:40:37,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 20. [2022-07-22 02:40:37,542 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-07-22 02:40:37,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2022-07-22 02:40:37,543 INFO L392 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2022-07-22 02:40:37,543 INFO L374 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2022-07-22 02:40:37,544 INFO L287 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2022-07-22 02:40:37,544 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2022-07-22 02:40:37,544 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:37,544 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-22 02:40:37,544 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-22 02:40:37,545 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 02:40:37,545 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 02:40:37,545 INFO L752 eck$LassoCheckResult]: Stem: 122#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(11, 2);call #Ultimate.allocInit(12, 3); 123#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 128#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 132#fiboENTRY ~n := #in~n; 133#L8 assume !(~n < 1); 138#L10 assume !(1 == ~n); 127#L13 call #t~ret4 := fibo(~n - 1);< 129#fiboENTRY ~n := #in~n; 134#L8 assume ~n < 1;#res := 0; 135#fiboFINAL assume true; 136#fiboEXIT >#33#return; 125#L13-1 [2022-07-22 02:40:37,546 INFO L754 eck$LassoCheckResult]: Loop: 125#L13-1 call #t~ret5 := fibo(~n - 2);< 126#fiboENTRY ~n := #in~n; 141#L8 assume !(~n < 1); 140#L10 assume !(1 == ~n); 124#L13 call #t~ret4 := fibo(~n - 1);< 126#fiboENTRY ~n := #in~n; 141#L8 assume ~n < 1;#res := 0; 131#fiboFINAL assume true; 139#fiboEXIT >#33#return; 125#L13-1 [2022-07-22 02:40:37,546 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:37,546 INFO L85 PathProgramCache]: Analyzing trace with hash -1181449843, now seen corresponding path program 1 times [2022-07-22 02:40:37,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:37,546 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [501111576] [2022-07-22 02:40:37,546 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:37,546 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:37,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:37,580 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-22 02:40:37,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:37,606 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-22 02:40:37,606 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 02:40:37,606 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [501111576] [2022-07-22 02:40:37,607 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [501111576] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 02:40:37,607 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 02:40:37,607 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-22 02:40:37,607 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [159877505] [2022-07-22 02:40:37,607 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 02:40:37,609 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-22 02:40:37,609 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:37,609 INFO L85 PathProgramCache]: Analyzing trace with hash 246097683, now seen corresponding path program 1 times [2022-07-22 02:40:37,609 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:37,609 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [598600089] [2022-07-22 02:40:37,609 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:37,609 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:37,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:37,626 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-22 02:40:37,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:37,640 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-22 02:40:37,640 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 02:40:37,640 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [598600089] [2022-07-22 02:40:37,640 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [598600089] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-22 02:40:37,640 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-22 02:40:37,640 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-22 02:40:37,640 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2121940662] [2022-07-22 02:40:37,641 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-22 02:40:37,641 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-22 02:40:37,641 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 02:40:37,642 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-07-22 02:40:37,643 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-07-22 02:40:37,644 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-22 02:40:37,686 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 02:40:37,686 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2022-07-22 02:40:37,686 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-22 02:40:37,687 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2022-07-22 02:40:37,688 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:37,689 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2022-07-22 02:40:37,689 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2022-07-22 02:40:37,689 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2022-07-22 02:40:37,690 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2022-07-22 02:40:37,690 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-22 02:40:37,690 INFO L369 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-22 02:40:37,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2022-07-22 02:40:37,691 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2022-07-22 02:40:37,692 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2022-07-22 02:40:37,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2022-07-22 02:40:37,692 INFO L392 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-22 02:40:37,692 INFO L374 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-22 02:40:37,693 INFO L287 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2022-07-22 02:40:37,693 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2022-07-22 02:40:37,693 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:37,693 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-22 02:40:37,693 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-22 02:40:37,694 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 02:40:37,694 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2022-07-22 02:40:37,694 INFO L752 eck$LassoCheckResult]: Stem: 195#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(11, 2);call #Ultimate.allocInit(12, 3); 196#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 201#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 205#fiboENTRY ~n := #in~n; 207#L8 assume !(~n < 1); 211#L10 assume !(1 == ~n); 200#L13 call #t~ret4 := fibo(~n - 1);< 202#fiboENTRY ~n := #in~n; 208#L8 assume !(~n < 1); 210#L10 assume 1 == ~n;#res := 1; 212#fiboFINAL assume true; 214#fiboEXIT >#33#return; 198#L13-1 [2022-07-22 02:40:37,694 INFO L754 eck$LassoCheckResult]: Loop: 198#L13-1 call #t~ret5 := fibo(~n - 2);< 199#fiboENTRY ~n := #in~n; 217#L8 assume !(~n < 1); 215#L10 assume !(1 == ~n); 197#L13 call #t~ret4 := fibo(~n - 1);< 199#fiboENTRY ~n := #in~n; 217#L8 assume !(~n < 1); 215#L10 assume 1 == ~n;#res := 1; 216#fiboFINAL assume true; 213#fiboEXIT >#33#return; 198#L13-1 [2022-07-22 02:40:37,694 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:37,694 INFO L85 PathProgramCache]: Analyzing trace with hash 2029785426, now seen corresponding path program 1 times [2022-07-22 02:40:37,694 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:37,695 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [121029863] [2022-07-22 02:40:37,695 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:37,695 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:37,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:37,717 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-22 02:40:37,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:37,732 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 02:40:37,732 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 02:40:37,732 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [121029863] [2022-07-22 02:40:37,732 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [121029863] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 02:40:37,732 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1927534793] [2022-07-22 02:40:37,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:37,733 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 02:40:37,733 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:37,734 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) [2022-07-22 02:40:37,780 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:37,780 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-22 02:40:37,781 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:37,784 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-07-22 02:40:37,827 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 02:40:37,827 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 02:40:37,918 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 02:40:37,919 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1927534793] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 02:40:37,919 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-22 02:40:37,919 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2022-07-22 02:40:37,919 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [788015254] [2022-07-22 02:40:37,919 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-22 02:40:37,920 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-22 02:40:37,920 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:37,920 INFO L85 PathProgramCache]: Analyzing trace with hash -960881524, now seen corresponding path program 1 times [2022-07-22 02:40:37,920 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:37,920 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1919882476] [2022-07-22 02:40:37,920 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:37,920 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:37,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:37,924 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 02:40:37,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:37,928 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 02:40:38,002 INFO L210 LassoAnalysis]: Preferences: [2022-07-22 02:40:38,002 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-22 02:40:38,002 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-22 02:40:38,002 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-22 02:40:38,002 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-22 02:40:38,002 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:38,002 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-22 02:40:38,002 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-22 02:40:38,003 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2022-07-22 02:40:38,003 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-22 02:40:38,003 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-22 02:40:38,003 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:38,005 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:38,007 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:38,011 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:38,036 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-22 02:40:38,037 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-22 02:40:38,037 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:38,037 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:38,038 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) [2022-07-22 02:40:38,054 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:38,054 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:38,063 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 [2022-07-22 02:40:38,072 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-22 02:40:38,072 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-22 02:40:38,088 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:38,089 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:38,089 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:38,090 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) [2022-07-22 02:40:38,091 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 [2022-07-22 02:40:38,092 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:38,092 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:38,100 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-22 02:40:38,101 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=1} Honda state: {fibo_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-22 02:40:38,119 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 [2022-07-22 02:40:38,120 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:38,120 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:38,121 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) [2022-07-22 02:40:38,125 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 [2022-07-22 02:40:38,125 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:38,125 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:38,156 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 [2022-07-22 02:40:38,156 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:38,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:38,158 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) [2022-07-22 02:40:38,158 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 [2022-07-22 02:40:38,163 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-22 02:40:38,163 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:38,992 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-22 02:40:38,998 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2022-07-22 02:40:38,999 INFO L210 LassoAnalysis]: Preferences: [2022-07-22 02:40:38,999 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-22 02:40:38,999 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-22 02:40:38,999 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-22 02:40:38,999 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-22 02:40:38,999 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:38,999 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-22 02:40:38,999 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-22 02:40:38,999 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2022-07-22 02:40:38,999 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-22 02:40:38,999 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-22 02:40:39,000 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:39,004 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:39,007 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:39,015 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:39,054 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-22 02:40:39,055 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-22 02:40:39,055 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:39,055 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:39,056 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) [2022-07-22 02:40:39,059 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 [2022-07-22 02:40:39,060 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-22 02:40:39,066 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:39,066 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:39,066 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:39,066 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:39,067 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:39,068 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:39,068 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:39,083 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-22 02:40:39,103 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 [2022-07-22 02:40:39,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:39,104 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:39,105 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) [2022-07-22 02:40:39,106 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 [2022-07-22 02:40:39,108 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 [2022-07-22 02:40:39,115 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:39,115 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:39,115 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:39,116 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:39,116 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:39,116 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:39,116 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:39,131 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-22 02:40:39,150 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:39,150 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:39,150 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:39,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) [2022-07-22 02:40:39,153 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 [2022-07-22 02:40:39,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 [2022-07-22 02:40:39,161 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:39,161 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:39,162 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:39,162 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:39,162 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:39,164 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:39,164 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:39,178 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-22 02:40:39,181 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-22 02:40:39,181 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-22 02:40:39,181 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:39,182 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:39,183 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) [2022-07-22 02:40:39,189 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-22 02:40:39,189 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-22 02:40:39,189 INFO L513 LassoAnalysis]: Proved termination. [2022-07-22 02:40:39,189 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2022-07-22 02:40:39,204 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 [2022-07-22 02:40:39,208 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 [2022-07-22 02:40:39,210 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-22 02:40:39,232 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:39,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:39,260 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-22 02:40:39,261 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:39,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:39,361 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-22 02:40:39,362 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:39,415 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 02:40:39,416 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2022-07-22 02:40:39,416 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-22 02:40:39,522 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:39,580 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 135 states and 183 transitions. Complement of second has 36 states. [2022-07-22 02:40:39,580 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 9 states 2 stem states 6 non-accepting loop states 1 accepting loop states [2022-07-22 02:40:39,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-22 02:40:39,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 37 transitions. [2022-07-22 02:40:39,582 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 10 letters. [2022-07-22 02:40:39,582 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:39,582 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 22 letters. Loop has 10 letters. [2022-07-22 02:40:39,582 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:39,582 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 20 letters. [2022-07-22 02:40:39,583 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:39,583 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2022-07-22 02:40:39,588 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-22 02:40:39,591 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 108 states and 152 transitions. [2022-07-22 02:40:39,591 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 64 [2022-07-22 02:40:39,592 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 69 [2022-07-22 02:40:39,592 INFO L73 IsDeterministic]: Start isDeterministic. Operand 108 states and 152 transitions. [2022-07-22 02:40:39,592 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-22 02:40:39,592 INFO L369 hiAutomatonCegarLoop]: Abstraction has 108 states and 152 transitions. [2022-07-22 02:40:39,592 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states and 152 transitions. [2022-07-22 02:40:39,610 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 94. [2022-07-22 02:40:39,610 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 64 states have internal predecessors, (71), 21 states have call successors, (22), 11 states have call predecessors, (22), 15 states have return successors, (33), 18 states have call predecessors, (33), 19 states have call successors, (33) [2022-07-22 02:40:39,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 126 transitions. [2022-07-22 02:40:39,611 INFO L392 hiAutomatonCegarLoop]: Abstraction has 94 states and 126 transitions. [2022-07-22 02:40:39,612 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 02:40:39,612 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-22 02:40:39,612 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-07-22 02:40:39,612 INFO L87 Difference]: Start difference. First operand 94 states and 126 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-22 02:40:39,709 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 02:40:39,709 INFO L93 Difference]: Finished difference Result 123 states and 165 transitions. [2022-07-22 02:40:39,710 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-22 02:40:39,710 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 123 states and 165 transitions. [2022-07-22 02:40:39,713 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-22 02:40:39,715 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 123 states to 118 states and 160 transitions. [2022-07-22 02:40:39,715 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 77 [2022-07-22 02:40:39,716 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 77 [2022-07-22 02:40:39,716 INFO L73 IsDeterministic]: Start isDeterministic. Operand 118 states and 160 transitions. [2022-07-22 02:40:39,716 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-22 02:40:39,716 INFO L369 hiAutomatonCegarLoop]: Abstraction has 118 states and 160 transitions. [2022-07-22 02:40:39,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states and 160 transitions. [2022-07-22 02:40:39,722 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 106. [2022-07-22 02:40:39,723 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.196969696969697) internal successors, (79), 72 states have internal predecessors, (79), 24 states have call successors, (25), 13 states have call predecessors, (25), 16 states have return successors, (37), 20 states have call predecessors, (37), 22 states have call successors, (37) [2022-07-22 02:40:39,723 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 141 transitions. [2022-07-22 02:40:39,724 INFO L392 hiAutomatonCegarLoop]: Abstraction has 106 states and 141 transitions. [2022-07-22 02:40:39,724 INFO L374 stractBuchiCegarLoop]: Abstraction has 106 states and 141 transitions. [2022-07-22 02:40:39,724 INFO L287 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2022-07-22 02:40:39,724 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 141 transitions. [2022-07-22 02:40:39,725 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-22 02:40:39,725 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-22 02:40:39,725 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-22 02:40:39,726 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 02:40:39,726 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 5, 3, 3, 3, 3, 2, 2, 2, 1] [2022-07-22 02:40:39,726 INFO L752 eck$LassoCheckResult]: Stem: 789#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(11, 2);call #Ultimate.allocInit(12, 3); 790#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 804#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 806#fiboENTRY ~n := #in~n; 854#L8 assume !(~n < 1); 853#L10 assume !(1 == ~n); 803#L13 call #t~ret4 := fibo(~n - 1);< 805#fiboENTRY ~n := #in~n; 815#L8 assume !(~n < 1); 820#L10 assume !(1 == ~n); 826#L13 call #t~ret4 := fibo(~n - 1);< 847#fiboENTRY ~n := #in~n; 851#L8 assume !(~n < 1); 849#L10 assume !(1 == ~n); 843#L13 call #t~ret4 := fibo(~n - 1);< 847#fiboENTRY ~n := #in~n; 851#L8 assume !(~n < 1); 849#L10 assume !(1 == ~n); 843#L13 call #t~ret4 := fibo(~n - 1);< 847#fiboENTRY ~n := #in~n; 852#L8 assume !(~n < 1); 850#L10 assume 1 == ~n;#res := 1; 848#fiboFINAL assume true; 846#fiboEXIT >#33#return; 792#L13-1 call #t~ret5 := fibo(~n - 2);< 844#fiboENTRY ~n := #in~n; 892#L8 assume ~n < 1;#res := 0; 891#fiboFINAL assume true; 890#fiboEXIT >#35#return; 889#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 887#fiboFINAL assume true; 879#fiboEXIT >#33#return; 824#L13-1 [2022-07-22 02:40:39,727 INFO L754 eck$LassoCheckResult]: Loop: 824#L13-1 call #t~ret5 := fibo(~n - 2);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume !(1 == ~n); 822#L13 call #t~ret4 := fibo(~n - 1);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume !(1 == ~n); 822#L13 call #t~ret4 := fibo(~n - 1);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume 1 == ~n;#res := 1; 825#fiboFINAL assume true; 876#fiboEXIT >#33#return; 824#L13-1 call #t~ret5 := fibo(~n - 2);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume !(1 == ~n); 822#L13 call #t~ret4 := fibo(~n - 1);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume 1 == ~n;#res := 1; 825#fiboFINAL assume true; 876#fiboEXIT >#33#return; 824#L13-1 call #t~ret5 := fibo(~n - 2);< 802#fiboENTRY ~n := #in~n; 884#L8 assume ~n < 1;#res := 0; 885#fiboFINAL assume true; 883#fiboEXIT >#35#return; 878#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 886#fiboFINAL assume true; 880#fiboEXIT >#35#return; 878#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 886#fiboFINAL assume true; 880#fiboEXIT >#33#return; 824#L13-1 [2022-07-22 02:40:39,727 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:39,727 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 1 times [2022-07-22 02:40:39,727 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:39,727 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [576398000] [2022-07-22 02:40:39,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:39,727 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:39,736 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:39,736 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 02:40:39,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:39,748 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 02:40:39,749 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:39,749 INFO L85 PathProgramCache]: Analyzing trace with hash 1616897917, now seen corresponding path program 1 times [2022-07-22 02:40:39,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:39,749 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [347717023] [2022-07-22 02:40:39,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:39,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:39,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:39,763 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-22 02:40:39,768 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:39,776 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 02:40:39,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:39,787 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-22 02:40:39,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:39,816 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 02:40:39,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:39,820 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-22 02:40:39,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:39,823 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 26 proven. 13 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-07-22 02:40:39,823 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 02:40:39,823 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [347717023] [2022-07-22 02:40:39,824 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [347717023] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 02:40:39,824 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1219473415] [2022-07-22 02:40:39,824 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:39,824 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 02:40:39,824 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:39,851 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 02:40:39,852 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2022-07-22 02:40:39,878 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:39,879 INFO L263 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-22 02:40:39,880 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:39,906 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 25 proven. 15 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2022-07-22 02:40:39,906 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 02:40:40,003 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 25 proven. 15 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2022-07-22 02:40:40,004 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1219473415] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 02:40:40,004 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-22 02:40:40,004 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2022-07-22 02:40:40,004 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1416711259] [2022-07-22 02:40:40,004 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-22 02:40:40,004 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-22 02:40:40,004 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 02:40:40,005 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-07-22 02:40:40,005 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2022-07-22 02:40:40,005 INFO L87 Difference]: Start difference. First operand 106 states and 141 transitions. cyclomatic complexity: 40 Second operand has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 4 states have call successors, (7), 1 states have call predecessors, (7), 4 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2022-07-22 02:40:40,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 02:40:40,073 INFO L93 Difference]: Finished difference Result 60 states and 77 transitions. [2022-07-22 02:40:40,073 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-22 02:40:40,074 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 60 states and 77 transitions. [2022-07-22 02:40:40,075 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:40,076 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 60 states to 54 states and 70 transitions. [2022-07-22 02:40:40,076 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2022-07-22 02:40:40,076 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2022-07-22 02:40:40,076 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2022-07-22 02:40:40,076 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-22 02:40:40,076 INFO L369 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2022-07-22 02:40:40,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2022-07-22 02:40:40,078 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-07-22 02:40:40,079 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 37 states have internal predecessors, (38), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (21), 9 states have call predecessors, (21), 9 states have call successors, (21) [2022-07-22 02:40:40,079 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2022-07-22 02:40:40,079 INFO L392 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2022-07-22 02:40:40,079 INFO L374 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2022-07-22 02:40:40,079 INFO L287 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2022-07-22 02:40:40,079 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2022-07-22 02:40:40,080 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:40,080 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-22 02:40:40,080 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-22 02:40:40,081 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 02:40:40,081 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 1] [2022-07-22 02:40:40,081 INFO L752 eck$LassoCheckResult]: Stem: 1241#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(11, 2);call #Ultimate.allocInit(12, 3); 1242#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 1254#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1255#fiboENTRY ~n := #in~n; 1273#L8 assume !(~n < 1); 1272#L10 assume !(1 == ~n); 1247#L13 call #t~ret4 := fibo(~n - 1);< 1259#fiboENTRY ~n := #in~n; 1260#L8 assume !(~n < 1); 1266#L10 assume !(1 == ~n); 1246#L13 call #t~ret4 := fibo(~n - 1);< 1248#fiboENTRY ~n := #in~n; 1271#L8 assume !(~n < 1); 1289#L10 assume !(1 == ~n); 1263#L13 call #t~ret4 := fibo(~n - 1);< 1248#fiboENTRY ~n := #in~n; 1271#L8 assume !(~n < 1); 1289#L10 assume !(1 == ~n); 1263#L13 call #t~ret4 := fibo(~n - 1);< 1248#fiboENTRY ~n := #in~n; 1270#L8 assume !(~n < 1); 1267#L10 assume 1 == ~n;#res := 1; 1268#fiboFINAL assume true; 1262#fiboEXIT >#33#return; 1264#L13-1 call #t~ret5 := fibo(~n - 2);< 1288#fiboENTRY ~n := #in~n; 1294#L8 assume ~n < 1;#res := 0; 1293#fiboFINAL assume true; 1287#fiboEXIT >#35#return; 1285#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1283#fiboFINAL assume true; 1280#fiboEXIT >#33#return; 1252#L13-1 [2022-07-22 02:40:40,081 INFO L754 eck$LassoCheckResult]: Loop: 1252#L13-1 call #t~ret5 := fibo(~n - 2);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume !(~n < 1); 1275#L10 assume !(1 == ~n); 1251#L13 call #t~ret4 := fibo(~n - 1);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume !(~n < 1); 1275#L10 assume !(1 == ~n); 1251#L13 call #t~ret4 := fibo(~n - 1);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume !(~n < 1); 1275#L10 assume !(1 == ~n); 1251#L13 call #t~ret4 := fibo(~n - 1);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume !(~n < 1); 1275#L10 assume 1 == ~n;#res := 1; 1290#fiboFINAL assume true; 1291#fiboEXIT >#33#return; 1257#L13-1 call #t~ret5 := fibo(~n - 2);< 1256#fiboENTRY ~n := #in~n; 1258#L8 assume ~n < 1;#res := 0; 1265#fiboFINAL assume true; 1286#fiboEXIT >#35#return; 1249#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1253#fiboFINAL assume true; 1261#fiboEXIT >#33#return; 1252#L13-1 call #t~ret5 := fibo(~n - 2);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume ~n < 1;#res := 0; 1265#fiboFINAL assume true; 1286#fiboEXIT >#35#return; 1278#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1284#fiboFINAL assume true; 1281#fiboEXIT >#33#return; 1252#L13-1 [2022-07-22 02:40:40,081 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:40,081 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 2 times [2022-07-22 02:40:40,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:40,082 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [638470279] [2022-07-22 02:40:40,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:40,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:40,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:40,089 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 02:40:40,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:40,120 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 02:40:40,121 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:40,121 INFO L85 PathProgramCache]: Analyzing trace with hash -176759904, now seen corresponding path program 2 times [2022-07-22 02:40:40,121 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:40,121 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [946239309] [2022-07-22 02:40:40,121 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:40,121 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:40,126 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,131 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-22 02:40:40,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,143 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 02:40:40,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,181 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 02:40:40,183 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,185 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-22 02:40:40,186 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,187 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2022-07-22 02:40:40,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,195 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 29 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-07-22 02:40:40,195 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 02:40:40,195 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [946239309] [2022-07-22 02:40:40,196 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [946239309] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 02:40:40,196 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1209206790] [2022-07-22 02:40:40,196 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-22 02:40:40,196 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 02:40:40,196 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:40,212 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 02:40:40,240 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2022-07-22 02:40:40,264 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-22 02:40:40,264 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-22 02:40:40,264 INFO L263 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-22 02:40:40,266 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:40,308 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 12 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2022-07-22 02:40:40,308 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 02:40:40,506 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 13 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-07-22 02:40:40,506 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1209206790] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 02:40:40,506 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-22 02:40:40,506 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 14 [2022-07-22 02:40:40,506 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [332360954] [2022-07-22 02:40:40,506 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-22 02:40:40,507 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-22 02:40:40,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 02:40:40,507 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-22 02:40:40,508 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2022-07-22 02:40:40,508 INFO L87 Difference]: Start difference. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 14 states, 12 states have (on average 2.5) internal successors, (30), 13 states have internal predecessors, (30), 6 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (8), 4 states have call predecessors, (8), 6 states have call successors, (8) [2022-07-22 02:40:40,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 02:40:40,567 INFO L93 Difference]: Finished difference Result 54 states and 67 transitions. [2022-07-22 02:40:40,568 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-22 02:40:40,568 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 54 states and 67 transitions. [2022-07-22 02:40:40,569 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:40,569 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 54 states to 54 states and 67 transitions. [2022-07-22 02:40:40,569 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2022-07-22 02:40:40,569 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2022-07-22 02:40:40,570 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 67 transitions. [2022-07-22 02:40:40,570 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-22 02:40:40,570 INFO L369 hiAutomatonCegarLoop]: Abstraction has 54 states and 67 transitions. [2022-07-22 02:40:40,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 67 transitions. [2022-07-22 02:40:40,572 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-07-22 02:40:40,572 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0571428571428572) internal successors, (37), 37 states have internal predecessors, (37), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (19), 9 states have call predecessors, (19), 9 states have call successors, (19) [2022-07-22 02:40:40,572 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 67 transitions. [2022-07-22 02:40:40,572 INFO L392 hiAutomatonCegarLoop]: Abstraction has 54 states and 67 transitions. [2022-07-22 02:40:40,572 INFO L374 stractBuchiCegarLoop]: Abstraction has 54 states and 67 transitions. [2022-07-22 02:40:40,572 INFO L287 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2022-07-22 02:40:40,572 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 67 transitions. [2022-07-22 02:40:40,573 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-22 02:40:40,573 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-22 02:40:40,573 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-22 02:40:40,574 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 02:40:40,574 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2022-07-22 02:40:40,574 INFO L752 eck$LassoCheckResult]: Stem: 1628#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(11, 2);call #Ultimate.allocInit(12, 3); 1629#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 1641#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1642#fiboENTRY ~n := #in~n; 1661#L8 assume !(~n < 1); 1660#L10 assume !(1 == ~n); 1634#L13 call #t~ret4 := fibo(~n - 1);< 1646#fiboENTRY ~n := #in~n; 1647#L8 assume !(~n < 1); 1652#L10 assume !(1 == ~n); 1633#L13 call #t~ret4 := fibo(~n - 1);< 1635#fiboENTRY ~n := #in~n; 1659#L8 assume !(~n < 1); 1678#L10 assume !(1 == ~n); 1651#L13 call #t~ret4 := fibo(~n - 1);< 1635#fiboENTRY ~n := #in~n; 1659#L8 assume !(~n < 1); 1678#L10 assume !(1 == ~n); 1651#L13 call #t~ret4 := fibo(~n - 1);< 1635#fiboENTRY ~n := #in~n; 1658#L8 assume !(~n < 1); 1653#L10 assume 1 == ~n;#res := 1; 1654#fiboFINAL assume true; 1650#fiboEXIT >#33#return; 1644#L13-1 call #t~ret5 := fibo(~n - 2);< 1643#fiboENTRY ~n := #in~n; 1645#L8 assume ~n < 1;#res := 0; 1648#fiboFINAL assume true; 1649#fiboEXIT >#35#return; 1673#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1670#fiboFINAL assume true; 1667#fiboEXIT >#33#return; 1637#L13-1 [2022-07-22 02:40:40,574 INFO L754 eck$LassoCheckResult]: Loop: 1637#L13-1 call #t~ret5 := fibo(~n - 2);< 1632#fiboENTRY ~n := #in~n; 1677#L8 assume !(~n < 1); 1676#L10 assume !(1 == ~n); 1639#L13 call #t~ret4 := fibo(~n - 1);< 1632#fiboENTRY ~n := #in~n; 1677#L8 assume !(~n < 1); 1676#L10 assume !(1 == ~n); 1639#L13 call #t~ret4 := fibo(~n - 1);< 1632#fiboENTRY ~n := #in~n; 1677#L8 assume !(~n < 1); 1676#L10 assume 1 == ~n;#res := 1; 1675#fiboFINAL assume true; 1674#fiboEXIT >#33#return; 1655#L13-1 call #t~ret5 := fibo(~n - 2);< 1656#fiboENTRY ~n := #in~n; 1681#L8 assume ~n < 1;#res := 0; 1680#fiboFINAL assume true; 1679#fiboEXIT >#35#return; 1636#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1640#fiboFINAL assume true; 1664#fiboEXIT >#33#return; 1637#L13-1 [2022-07-22 02:40:40,574 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:40,574 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 3 times [2022-07-22 02:40:40,574 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:40,574 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1455519737] [2022-07-22 02:40:40,574 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:40,574 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:40,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:40,580 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 02:40:40,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:40,586 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 02:40:40,586 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:40,586 INFO L85 PathProgramCache]: Analyzing trace with hash 780094678, now seen corresponding path program 3 times [2022-07-22 02:40:40,586 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:40,586 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [555296036] [2022-07-22 02:40:40,586 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:40,586 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:40,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:40,589 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 02:40:40,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:40,592 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 02:40:40,593 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:40,593 INFO L85 PathProgramCache]: Analyzing trace with hash 1975410011, now seen corresponding path program 4 times [2022-07-22 02:40:40,593 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:40,593 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [677341372] [2022-07-22 02:40:40,593 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:40,593 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:40,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,661 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2022-07-22 02:40:40,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,665 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 02:40:40,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,666 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-22 02:40:40,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,673 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2022-07-22 02:40:40,677 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,679 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 02:40:40,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,691 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-22 02:40:40,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:40,693 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 34 proven. 64 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-07-22 02:40:40,693 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 02:40:40,693 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [677341372] [2022-07-22 02:40:40,693 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [677341372] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 02:40:40,693 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1933498998] [2022-07-22 02:40:40,693 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-22 02:40:40,693 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 02:40:40,693 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:40,725 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) [2022-07-22 02:40:40,726 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2022-07-22 02:40:40,757 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-22 02:40:40,758 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-22 02:40:40,758 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-22 02:40:40,760 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:40,810 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 52 proven. 67 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-22 02:40:40,811 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 02:40:40,894 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 52 proven. 67 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-22 02:40:40,894 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1933498998] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 02:40:40,894 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-22 02:40:40,894 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12] total 15 [2022-07-22 02:40:40,894 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [804245589] [2022-07-22 02:40:40,894 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-22 02:40:41,076 INFO L210 LassoAnalysis]: Preferences: [2022-07-22 02:40:41,076 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-22 02:40:41,076 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-22 02:40:41,076 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-22 02:40:41,076 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-22 02:40:41,076 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:41,076 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-22 02:40:41,076 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-22 02:40:41,076 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration6_Loop [2022-07-22 02:40:41,076 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-22 02:40:41,076 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-22 02:40:41,077 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:41,093 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:41,095 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:41,096 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:41,137 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-22 02:40:41,137 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-22 02:40:41,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:41,137 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:41,152 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) [2022-07-22 02:40:41,158 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:41,158 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:41,158 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 [2022-07-22 02:40:41,187 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:41,187 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:41,188 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:41,189 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) [2022-07-22 02:40:41,190 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 [2022-07-22 02:40:41,192 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-22 02:40:41,192 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:42,208 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-22 02:40:42,212 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 [2022-07-22 02:40:42,213 INFO L210 LassoAnalysis]: Preferences: [2022-07-22 02:40:42,213 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-22 02:40:42,213 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-22 02:40:42,213 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-22 02:40:42,213 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-22 02:40:42,213 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:42,213 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-22 02:40:42,213 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-22 02:40:42,213 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration6_Loop [2022-07-22 02:40:42,213 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-22 02:40:42,213 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-22 02:40:42,214 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:42,220 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:42,221 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:42,222 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:42,254 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-22 02:40:42,255 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-22 02:40:42,255 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:42,255 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:42,256 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) [2022-07-22 02:40:42,272 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 [2022-07-22 02:40:42,273 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 [2022-07-22 02:40:42,278 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:42,279 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:42,279 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:42,279 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:42,279 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:42,279 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:42,279 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:42,290 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-22 02:40:42,306 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 [2022-07-22 02:40:42,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:42,307 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:42,308 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) [2022-07-22 02:40:42,308 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 [2022-07-22 02:40:42,310 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 [2022-07-22 02:40:42,315 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:42,315 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:42,316 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:42,316 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:42,316 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:42,316 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:42,316 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:42,317 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-22 02:40:42,334 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2022-07-22 02:40:42,334 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:42,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:42,336 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) [2022-07-22 02:40:42,337 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 [2022-07-22 02:40:42,338 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 [2022-07-22 02:40:42,344 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:42,344 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:42,344 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:42,345 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:42,345 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:42,345 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:42,345 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:42,360 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-22 02:40:42,376 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2022-07-22 02:40:42,376 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:42,376 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:42,377 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) [2022-07-22 02:40:42,382 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 [2022-07-22 02:40:42,384 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 [2022-07-22 02:40:42,390 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:42,390 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:42,390 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:42,390 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:42,390 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:42,394 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:42,395 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:42,416 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-22 02:40:42,419 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-22 02:40:42,419 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-22 02:40:42,420 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:42,420 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:42,452 INFO L229 MonitoredProcess]: Starting monitored process 30 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) [2022-07-22 02:40:42,453 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2022-07-22 02:40:42,454 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-22 02:40:42,454 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-22 02:40:42,454 INFO L513 LassoAnalysis]: Proved termination. [2022-07-22 02:40:42,454 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2022-07-22 02:40:42,470 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 [2022-07-22 02:40:42,470 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-22 02:40:42,485 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:42,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:42,540 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-22 02:40:42,541 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:42,720 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:42,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:42,756 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-22 02:40:42,757 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:42,846 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-22 02:40:42,847 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 [2022-07-22 02:40:42,847 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-22 02:40:42,917 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 74 transitions. Complement of second has 11 states. [2022-07-22 02:40:42,918 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 [2022-07-22 02:40:42,918 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-22 02:40:42,918 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2022-07-22 02:40:42,919 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2022-07-22 02:40:42,919 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:42,919 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-22 02:40:42,936 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:42,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:42,985 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-22 02:40:42,986 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:43,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:43,210 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-22 02:40:43,211 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:43,292 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-22 02:40:43,293 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 [2022-07-22 02:40:43,293 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-22 02:40:43,374 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 74 transitions. Complement of second has 11 states. [2022-07-22 02:40:43,374 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 [2022-07-22 02:40:43,377 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-22 02:40:43,377 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2022-07-22 02:40:43,377 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2022-07-22 02:40:43,378 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:43,378 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-22 02:40:43,384 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:43,408 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:43,420 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-22 02:40:43,423 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:43,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:43,554 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-22 02:40:43,555 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:43,623 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-22 02:40:43,623 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 [2022-07-22 02:40:43,624 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-22 02:40:43,795 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 321 states and 401 transitions. Complement of second has 122 states. [2022-07-22 02:40:43,795 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 [2022-07-22 02:40:43,796 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-22 02:40:43,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 46 transitions. [2022-07-22 02:40:43,796 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 22 letters. [2022-07-22 02:40:43,799 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:43,799 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 54 letters. Loop has 22 letters. [2022-07-22 02:40:43,801 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:43,801 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 44 letters. [2022-07-22 02:40:43,802 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:43,803 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 321 states and 401 transitions. [2022-07-22 02:40:43,809 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2022-07-22 02:40:43,816 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 321 states to 203 states and 261 transitions. [2022-07-22 02:40:43,816 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2022-07-22 02:40:43,817 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 90 [2022-07-22 02:40:43,817 INFO L73 IsDeterministic]: Start isDeterministic. Operand 203 states and 261 transitions. [2022-07-22 02:40:43,817 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-22 02:40:43,818 INFO L369 hiAutomatonCegarLoop]: Abstraction has 203 states and 261 transitions. [2022-07-22 02:40:43,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states and 261 transitions. [2022-07-22 02:40:43,836 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 175. [2022-07-22 02:40:43,837 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 175 states, 109 states have (on average 1.1376146788990826) internal successors, (124), 116 states have internal predecessors, (124), 39 states have call successors, (39), 24 states have call predecessors, (39), 27 states have return successors, (49), 34 states have call predecessors, (49), 34 states have call successors, (49) [2022-07-22 02:40:43,838 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 212 transitions. [2022-07-22 02:40:43,838 INFO L392 hiAutomatonCegarLoop]: Abstraction has 175 states and 212 transitions. [2022-07-22 02:40:43,839 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 02:40:43,839 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-07-22 02:40:43,839 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-07-22 02:40:43,839 INFO L87 Difference]: Start difference. First operand 175 states and 212 transitions. Second operand has 15 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 11 states have internal predecessors, (30), 8 states have call successors, (11), 5 states have call predecessors, (11), 2 states have return successors, (7), 4 states have call predecessors, (7), 5 states have call successors, (7) [2022-07-22 02:40:44,011 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 02:40:44,012 INFO L93 Difference]: Finished difference Result 124 states and 140 transitions. [2022-07-22 02:40:44,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-07-22 02:40:44,012 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 124 states and 140 transitions. [2022-07-22 02:40:44,013 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2022-07-22 02:40:44,016 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 124 states to 105 states and 117 transitions. [2022-07-22 02:40:44,016 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2022-07-22 02:40:44,016 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 64 [2022-07-22 02:40:44,016 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 117 transitions. [2022-07-22 02:40:44,017 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-22 02:40:44,017 INFO L369 hiAutomatonCegarLoop]: Abstraction has 105 states and 117 transitions. [2022-07-22 02:40:44,017 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 117 transitions. [2022-07-22 02:40:44,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 96. [2022-07-22 02:40:44,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 63 states have (on average 1.0793650793650793) internal successors, (68), 66 states have internal predecessors, (68), 19 states have call successors, (19), 14 states have call predecessors, (19), 14 states have return successors, (21), 15 states have call predecessors, (21), 15 states have call successors, (21) [2022-07-22 02:40:44,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 108 transitions. [2022-07-22 02:40:44,022 INFO L392 hiAutomatonCegarLoop]: Abstraction has 96 states and 108 transitions. [2022-07-22 02:40:44,022 INFO L374 stractBuchiCegarLoop]: Abstraction has 96 states and 108 transitions. [2022-07-22 02:40:44,022 INFO L287 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2022-07-22 02:40:44,022 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 96 states and 108 transitions. [2022-07-22 02:40:44,023 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2022-07-22 02:40:44,023 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-22 02:40:44,023 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-22 02:40:44,026 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 6, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2022-07-22 02:40:44,026 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-22 02:40:44,027 INFO L752 eck$LassoCheckResult]: Stem: 3515#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(11, 2);call #Ultimate.allocInit(12, 3); 3516#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 3531#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 3532#fiboENTRY ~n := #in~n; 3571#L8 assume !(~n < 1); 3570#L10 assume !(1 == ~n); 3545#L13 call #t~ret4 := fibo(~n - 1);< 3569#fiboENTRY ~n := #in~n; 3568#L8 assume !(~n < 1); 3567#L10 assume !(1 == ~n); 3522#L13 call #t~ret4 := fibo(~n - 1);< 3523#fiboENTRY ~n := #in~n; 3577#L8 assume !(~n < 1); 3552#L10 assume !(1 == ~n); 3521#L13 call #t~ret4 := fibo(~n - 1);< 3523#fiboENTRY ~n := #in~n; 3578#L8 assume !(~n < 1); 3588#L10 assume 1 == ~n;#res := 1; 3586#fiboFINAL assume true; 3583#fiboEXIT >#33#return; 3584#L13-1 call #t~ret5 := fibo(~n - 2);< 3600#fiboENTRY ~n := #in~n; 3602#L8 assume ~n < 1;#res := 0; 3601#fiboFINAL assume true; 3599#fiboEXIT >#35#return; 3598#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3597#fiboFINAL assume true; 3566#fiboEXIT >#33#return; 3525#L13-1 call #t~ret5 := fibo(~n - 2);< 3565#fiboENTRY ~n := #in~n; 3564#L8 assume !(~n < 1); 3563#L10 assume !(1 == ~n); 3518#L13 call #t~ret4 := fibo(~n - 1);< 3596#fiboENTRY ~n := #in~n; 3606#L8 assume !(~n < 1); 3605#L10 assume !(1 == ~n); 3517#L13 [2022-07-22 02:40:44,028 INFO L754 eck$LassoCheckResult]: Loop: 3517#L13 call #t~ret4 := fibo(~n - 1);< 3520#fiboENTRY ~n := #in~n; 3610#L8 assume !(~n < 1); 3551#L10 assume !(1 == ~n); 3517#L13 [2022-07-22 02:40:44,028 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:44,028 INFO L85 PathProgramCache]: Analyzing trace with hash 2096320921, now seen corresponding path program 5 times [2022-07-22 02:40:44,028 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:44,028 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1120023482] [2022-07-22 02:40:44,028 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:44,029 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:44,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:44,066 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2022-07-22 02:40:44,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:44,100 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-22 02:40:44,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:44,111 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-22 02:40:44,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:44,116 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 34 proven. 28 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-07-22 02:40:44,116 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-22 02:40:44,117 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1120023482] [2022-07-22 02:40:44,117 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1120023482] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-22 02:40:44,117 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1087614396] [2022-07-22 02:40:44,117 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-22 02:40:44,117 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-22 02:40:44,117 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:44,136 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-22 02:40:44,166 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Waiting until timeout for monitored process [2022-07-22 02:40:44,168 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2022-07-22 02:40:44,168 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-22 02:40:44,168 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-22 02:40:44,169 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:44,218 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 44 proven. 8 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-07-22 02:40:44,219 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-22 02:40:44,335 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 44 proven. 9 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2022-07-22 02:40:44,335 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1087614396] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-22 02:40:44,336 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-22 02:40:44,336 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 10] total 18 [2022-07-22 02:40:44,336 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1699054644] [2022-07-22 02:40:44,336 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-22 02:40:44,337 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-22 02:40:44,338 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:44,338 INFO L85 PathProgramCache]: Analyzing trace with hash 1893846, now seen corresponding path program 2 times [2022-07-22 02:40:44,338 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-22 02:40:44,338 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [156868485] [2022-07-22 02:40:44,338 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-22 02:40:44,338 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-22 02:40:44,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:44,341 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-22 02:40:44,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-22 02:40:44,342 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-22 02:40:44,372 INFO L210 LassoAnalysis]: Preferences: [2022-07-22 02:40:44,372 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-22 02:40:44,372 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-22 02:40:44,372 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-22 02:40:44,372 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-22 02:40:44,372 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:44,372 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-22 02:40:44,373 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-22 02:40:44,373 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration7_Loop [2022-07-22 02:40:44,373 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-22 02:40:44,373 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-22 02:40:44,374 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:44,375 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:44,376 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:44,377 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:44,405 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-22 02:40:44,405 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-22 02:40:44,405 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:44,405 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:44,406 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) [2022-07-22 02:40:44,407 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 [2022-07-22 02:40:44,408 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:44,409 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:44,429 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-22 02:40:44,430 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-22 02:40:44,445 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 [2022-07-22 02:40:44,445 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:44,446 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:44,447 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) [2022-07-22 02:40:44,447 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 [2022-07-22 02:40:44,449 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:44,449 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:44,455 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-22 02:40:44,455 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-22 02:40:44,471 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 [2022-07-22 02:40:44,471 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:44,472 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:44,473 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) [2022-07-22 02:40:44,474 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 [2022-07-22 02:40:44,475 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:44,475 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:44,496 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-22 02:40:44,496 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=0} Honda state: {fibo_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-22 02:40:44,512 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2022-07-22 02:40:44,512 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:44,513 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:44,514 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) [2022-07-22 02:40:44,514 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 [2022-07-22 02:40:44,516 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-22 02:40:44,516 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:44,555 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 [2022-07-22 02:40:44,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:44,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:44,557 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) [2022-07-22 02:40:44,558 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 [2022-07-22 02:40:44,560 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-22 02:40:44,560 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-22 02:40:46,312 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-22 02:40:46,317 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 [2022-07-22 02:40:46,318 INFO L210 LassoAnalysis]: Preferences: [2022-07-22 02:40:46,318 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-22 02:40:46,318 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-22 02:40:46,318 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-22 02:40:46,318 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-22 02:40:46,318 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:46,318 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-22 02:40:46,318 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-22 02:40:46,318 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration7_Loop [2022-07-22 02:40:46,318 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-22 02:40:46,318 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-22 02:40:46,319 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:46,331 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:46,338 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:46,339 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-22 02:40:46,368 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-22 02:40:46,368 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-22 02:40:46,368 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:46,368 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:46,369 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) [2022-07-22 02:40:46,370 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 [2022-07-22 02:40:46,372 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 [2022-07-22 02:40:46,377 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:46,377 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:46,377 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:46,377 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:46,377 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:46,378 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:46,378 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:46,393 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-22 02:40:46,410 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 [2022-07-22 02:40:46,411 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:46,411 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:46,412 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) [2022-07-22 02:40:46,413 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 [2022-07-22 02:40:46,414 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 [2022-07-22 02:40:46,419 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-22 02:40:46,419 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-22 02:40:46,420 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-22 02:40:46,420 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-22 02:40:46,420 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-22 02:40:46,421 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-22 02:40:46,421 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-22 02:40:46,443 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-22 02:40:46,446 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-22 02:40:46,446 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-22 02:40:46,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-22 02:40:46,446 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-22 02:40:46,448 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) [2022-07-22 02:40:46,452 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 [2022-07-22 02:40:46,452 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-22 02:40:46,452 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-22 02:40:46,452 INFO L513 LassoAnalysis]: Proved termination. [2022-07-22 02:40:46,453 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2022-07-22 02:40:46,479 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 [2022-07-22 02:40:46,480 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-22 02:40:46,488 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:46,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:46,534 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-22 02:40:46,535 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:46,646 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:46,647 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-22 02:40:46,647 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:46,670 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 02:40:46,671 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2022-07-22 02:40:46,671 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-22 02:40:46,700 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 105 states and 118 transitions. Complement of second has 18 states. [2022-07-22 02:40:46,700 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2022-07-22 02:40:46,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-22 02:40:46,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2022-07-22 02:40:46,701 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 36 letters. Loop has 4 letters. [2022-07-22 02:40:46,702 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:46,702 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-22 02:40:46,707 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:46,752 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 [2022-07-22 02:40:46,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:46,758 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-22 02:40:46,759 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:46,879 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:46,880 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-22 02:40:46,881 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:46,900 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 02:40:46,902 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2022-07-22 02:40:46,902 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-22 02:40:46,951 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 111 states and 124 transitions. Complement of second has 17 states. [2022-07-22 02:40:46,952 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2022-07-22 02:40:46,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-22 02:40:46,952 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 16 transitions. [2022-07-22 02:40:46,953 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 16 transitions. Stem has 36 letters. Loop has 4 letters. [2022-07-22 02:40:46,953 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:46,953 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-22 02:40:46,960 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-22 02:40:46,988 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:46,989 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-22 02:40:46,990 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:47,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-22 02:40:47,124 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-22 02:40:47,125 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-22 02:40:47,142 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-22 02:40:47,143 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 4 loop predicates [2022-07-22 02:40:47,143 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-22 02:40:47,183 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 131 states and 150 transitions. Complement of second has 27 states. [2022-07-22 02:40:47,184 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 [2022-07-22 02:40:47,184 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-22 02:40:47,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 22 transitions. [2022-07-22 02:40:47,185 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 4 letters. [2022-07-22 02:40:47,185 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:47,185 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 40 letters. Loop has 4 letters. [2022-07-22 02:40:47,185 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:47,185 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 8 letters. [2022-07-22 02:40:47,186 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-22 02:40:47,186 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 131 states and 150 transitions. [2022-07-22 02:40:47,188 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-22 02:40:47,188 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 131 states to 0 states and 0 transitions. [2022-07-22 02:40:47,188 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2022-07-22 02:40:47,188 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2022-07-22 02:40:47,188 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2022-07-22 02:40:47,188 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2022-07-22 02:40:47,188 INFO L369 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-22 02:40:47,188 INFO L392 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-22 02:40:47,188 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-22 02:40:47,189 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-07-22 02:40:47,189 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=245, Unknown=0, NotChecked=0, Total=306 [2022-07-22 02:40:47,189 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 18 states, 15 states have (on average 2.533333333333333) internal successors, (38), 14 states have internal predecessors, (38), 10 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-07-22 02:40:47,189 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-22 02:40:47,189 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-07-22 02:40:47,189 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-22 02:40:47,190 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2022-07-22 02:40:47,190 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-22 02:40:47,190 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2022-07-22 02:40:47,190 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2022-07-22 02:40:47,190 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2022-07-22 02:40:47,190 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2022-07-22 02:40:47,190 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2022-07-22 02:40:47,190 INFO L369 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-22 02:40:47,190 INFO L392 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-22 02:40:47,190 INFO L374 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-22 02:40:47,191 INFO L287 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2022-07-22 02:40:47,191 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2022-07-22 02:40:47,191 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-22 02:40:47,191 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2022-07-22 02:40:47,197 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 22.07 02:40:47 BoogieIcfgContainer [2022-07-22 02:40:47,197 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2022-07-22 02:40:47,198 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2022-07-22 02:40:47,198 INFO L271 PluginConnector]: Initializing Witness Printer... [2022-07-22 02:40:47,198 INFO L275 PluginConnector]: Witness Printer initialized [2022-07-22 02:40:47,198 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.07 02:40:36" (3/4) ... [2022-07-22 02:40:47,200 INFO L140 WitnessPrinter]: No result that supports witness generation found [2022-07-22 02:40:47,200 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2022-07-22 02:40:47,201 INFO L158 Benchmark]: Toolchain (without parser) took 11601.01ms. Allocated memory was 50.3MB in the beginning and 107.0MB in the end (delta: 56.6MB). Free memory was 26.9MB in the beginning and 68.5MB in the end (delta: -41.6MB). Peak memory consumption was 13.7MB. Max. memory is 16.1GB. [2022-07-22 02:40:47,201 INFO L158 Benchmark]: CDTParser took 0.16ms. Allocated memory is still 50.3MB. Free memory was 31.6MB in the beginning and 31.5MB in the end (delta: 60.1kB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-22 02:40:47,202 INFO L158 Benchmark]: CACSL2BoogieTranslator took 211.76ms. Allocated memory was 50.3MB in the beginning and 60.8MB in the end (delta: 10.5MB). Free memory was 26.7MB in the beginning and 44.0MB in the end (delta: -17.3MB). Peak memory consumption was 12.0MB. Max. memory is 16.1GB. [2022-07-22 02:40:47,202 INFO L158 Benchmark]: Boogie Procedure Inliner took 48.49ms. Allocated memory is still 60.8MB. Free memory was 44.0MB in the beginning and 42.5MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-22 02:40:47,202 INFO L158 Benchmark]: Boogie Preprocessor took 16.36ms. Allocated memory is still 60.8MB. Free memory was 42.5MB in the beginning and 41.7MB in the end (delta: 864.7kB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-22 02:40:47,202 INFO L158 Benchmark]: RCFGBuilder took 233.84ms. Allocated memory is still 60.8MB. Free memory was 41.7MB in the beginning and 33.4MB in the end (delta: 8.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2022-07-22 02:40:47,203 INFO L158 Benchmark]: BuchiAutomizer took 11077.59ms. Allocated memory was 60.8MB in the beginning and 107.0MB in the end (delta: 46.1MB). Free memory was 33.2MB in the beginning and 68.5MB in the end (delta: -35.3MB). Peak memory consumption was 10.1MB. Max. memory is 16.1GB. [2022-07-22 02:40:47,204 INFO L158 Benchmark]: Witness Printer took 2.64ms. Allocated memory is still 107.0MB. Free memory is still 68.5MB. There was no memory consumed. Max. memory is 16.1GB. [2022-07-22 02:40:47,205 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.16ms. Allocated memory is still 50.3MB. Free memory was 31.6MB in the beginning and 31.5MB in the end (delta: 60.1kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 211.76ms. Allocated memory was 50.3MB in the beginning and 60.8MB in the end (delta: 10.5MB). Free memory was 26.7MB in the beginning and 44.0MB in the end (delta: -17.3MB). Peak memory consumption was 12.0MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 48.49ms. Allocated memory is still 60.8MB. Free memory was 44.0MB in the beginning and 42.5MB in the end (delta: 1.4MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 16.36ms. Allocated memory is still 60.8MB. Free memory was 42.5MB in the beginning and 41.7MB in the end (delta: 864.7kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 233.84ms. Allocated memory is still 60.8MB. Free memory was 41.7MB in the beginning and 33.4MB in the end (delta: 8.3MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 11077.59ms. Allocated memory was 60.8MB in the beginning and 107.0MB in the end (delta: 46.1MB). Free memory was 33.2MB in the beginning and 68.5MB in the end (delta: -35.3MB). Peak memory consumption was 10.1MB. Max. memory is 16.1GB. * Witness Printer took 2.64ms. Allocated memory is still 107.0MB. Free memory is still 68.5MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (6 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 9 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function n and consists of 6 locations. 6 modules have a trivial ranking function, the largest among these consists of 18 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 11.0s and 8 iterations. TraceHistogramMax:7. Analysis of lassos took 7.7s. Construction of modules took 0.3s. Büchi inclusion checks took 2.6s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 8. Automata minimization 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 68 StatesRemovedByMinimization, 5 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 374 SdHoareTripleChecker+Valid, 0.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 358 mSDsluCounter, 366 SdHoareTripleChecker+Invalid, 0.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 212 mSDsCounter, 203 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 724 IncrementalHoareTripleChecker+Invalid, 927 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 203 mSolverCounterUnsat, 154 mSDtfsCounter, 724 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI2 SFLT1 conc0 concLT1 SILN0 SILU0 SILI1 SILT2 lasso0 LassoPreprocessingBenchmarks: Lassos: inital19 mio100 ax100 hnf100 lsp92 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq182 hnf93 smp74 dnf100 smp100 tf109 neg96 sie108 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 49ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 8 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 4.1s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2022-07-22 02:40:47,235 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:47,452 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:47,651 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:47,851 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:48,052 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-07-22 02:40:48,251 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