./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 6c24879c 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-?-6c24879 [2022-07-13 04:20:36,122 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-13 04:20:36,125 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-13 04:20:36,168 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-13 04:20:36,169 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-13 04:20:36,170 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-13 04:20:36,173 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-13 04:20:36,175 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-13 04:20:36,177 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-13 04:20:36,181 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-13 04:20:36,182 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-13 04:20:36,184 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-13 04:20:36,184 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-13 04:20:36,186 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-13 04:20:36,187 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-13 04:20:36,189 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-13 04:20:36,190 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-13 04:20:36,192 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-13 04:20:36,193 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-13 04:20:36,199 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-13 04:20:36,201 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-13 04:20:36,201 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-13 04:20:36,202 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-13 04:20:36,203 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-13 04:20:36,204 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-13 04:20:36,211 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-13 04:20:36,211 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-13 04:20:36,211 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-13 04:20:36,212 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-13 04:20:36,213 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-13 04:20:36,214 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-13 04:20:36,214 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-13 04:20:36,215 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-13 04:20:36,216 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-13 04:20:36,216 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-13 04:20:36,217 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-13 04:20:36,217 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-13 04:20:36,218 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-13 04:20:36,218 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-13 04:20:36,219 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-13 04:20:36,220 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-13 04:20:36,222 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-13 04:20:36,223 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2022-07-13 04:20:36,251 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-13 04:20:36,251 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-13 04:20:36,251 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-13 04:20:36,251 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-13 04:20:36,252 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-13 04:20:36,252 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-13 04:20:36,252 INFO L138 SettingsManager]: * Use SBE=true [2022-07-13 04:20:36,252 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2022-07-13 04:20:36,253 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2022-07-13 04:20:36,253 INFO L138 SettingsManager]: * Use old map elimination=false [2022-07-13 04:20:36,253 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2022-07-13 04:20:36,253 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2022-07-13 04:20:36,253 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2022-07-13 04:20:36,253 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-13 04:20:36,253 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-13 04:20:36,253 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2022-07-13 04:20:36,253 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-13 04:20:36,254 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-13 04:20:36,254 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-13 04:20:36,254 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2022-07-13 04:20:36,254 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2022-07-13 04:20:36,254 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2022-07-13 04:20:36,254 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-13 04:20:36,254 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-13 04:20:36,254 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2022-07-13 04:20:36,254 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-13 04:20:36,255 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2022-07-13 04:20:36,255 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-13 04:20:36,255 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-13 04:20:36,255 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-13 04:20:36,255 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-13 04:20:36,256 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-07-13 04:20:36,256 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-13 04:20:36,495 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-13 04:20:36,516 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-13 04:20:36,519 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-13 04:20:36,520 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-13 04:20:36,520 INFO L275 PluginConnector]: CDTParser initialized [2022-07-13 04:20:36,521 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-13 04:20:36,581 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8a7e8b1a3/73d8c36e9fcc427cb6949e4d8cc97299/FLAGd7bec7f48 [2022-07-13 04:20:36,996 INFO L306 CDTParser]: Found 1 translation units. [2022-07-13 04:20:36,997 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-2.c [2022-07-13 04:20:37,003 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8a7e8b1a3/73d8c36e9fcc427cb6949e4d8cc97299/FLAGd7bec7f48 [2022-07-13 04:20:37,022 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8a7e8b1a3/73d8c36e9fcc427cb6949e4d8cc97299 [2022-07-13 04:20:37,025 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-13 04:20:37,026 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-13 04:20:37,029 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-13 04:20:37,029 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-13 04:20:37,032 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-13 04:20:37,033 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,034 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6c719566 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37, skipping insertion in model container [2022-07-13 04:20:37,034 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,041 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-13 04:20:37,053 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-13 04:20:37,248 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-13 04:20:37,249 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-13 04:20:37,259 INFO L203 MainTranslator]: Completed pre-run [2022-07-13 04:20:37,271 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-13 04:20:37,273 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-13 04:20:37,288 INFO L208 MainTranslator]: Completed translation [2022-07-13 04:20:37,289 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37 WrapperNode [2022-07-13 04:20:37,289 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-13 04:20:37,290 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-13 04:20:37,290 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-13 04:20:37,290 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-13 04:20:37,296 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,302 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,317 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2022-07-13 04:20:37,317 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-13 04:20:37,318 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-13 04:20:37,318 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-13 04:20:37,318 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-13 04:20:37,325 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,325 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,327 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,327 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,330 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,331 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,336 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,338 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-13 04:20:37,339 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-13 04:20:37,340 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-13 04:20:37,340 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-13 04:20:37,341 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (1/1) ... [2022-07-13 04:20:37,347 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:37,356 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:37,373 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-13 04:20:37,384 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-13 04:20:37,417 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-13 04:20:37,417 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-13 04:20:37,418 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-13 04:20:37,418 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-13 04:20:37,418 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2022-07-13 04:20:37,418 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2022-07-13 04:20:37,473 INFO L234 CfgBuilder]: Building ICFG [2022-07-13 04:20:37,475 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-13 04:20:37,586 INFO L275 CfgBuilder]: Performing block encoding [2022-07-13 04:20:37,593 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-13 04:20:37,593 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2022-07-13 04:20:37,595 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.07 04:20:37 BoogieIcfgContainer [2022-07-13 04:20:37,595 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-13 04:20:37,596 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2022-07-13 04:20:37,596 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2022-07-13 04:20:37,599 INFO L275 PluginConnector]: BuchiAutomizer initialized [2022-07-13 04:20:37,600 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-13 04:20:37,600 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 13.07 04:20:37" (1/3) ... [2022-07-13 04:20:37,601 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@35d11898 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.07 04:20:37, skipping insertion in model container [2022-07-13 04:20:37,601 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-13 04:20:37,602 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 13.07 04:20:37" (2/3) ... [2022-07-13 04:20:37,602 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@35d11898 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 13.07 04:20:37, skipping insertion in model container [2022-07-13 04:20:37,602 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-13 04:20:37,603 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.07 04:20:37" (3/3) ... [2022-07-13 04:20:37,605 INFO L354 chiAutomizerObserver]: Analyzing ICFG fibo_5-2.c [2022-07-13 04:20:37,652 INFO L255 stractBuchiCegarLoop]: Interprodecural is true [2022-07-13 04:20:37,652 INFO L256 stractBuchiCegarLoop]: Hoare is false [2022-07-13 04:20:37,652 INFO L257 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2022-07-13 04:20:37,652 INFO L258 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2022-07-13 04:20:37,652 INFO L259 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2022-07-13 04:20:37,653 INFO L260 stractBuchiCegarLoop]: Difference is false [2022-07-13 04:20:37,653 INFO L261 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2022-07-13 04:20:37,653 INFO L265 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2022-07-13 04:20:37,656 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-13 04:20:37,673 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:37,673 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-13 04:20:37,673 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-13 04:20:37,679 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2022-07-13 04:20:37,679 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-13 04:20:37,679 INFO L287 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2022-07-13 04:20:37,680 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-13 04:20:37,682 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:37,682 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-13 04:20:37,683 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-13 04:20:37,683 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2022-07-13 04:20:37,683 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-13 04:20:37,689 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-13 04:20:37,689 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-13 04:20:37,694 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:37,694 INFO L85 PathProgramCache]: Analyzing trace with hash 29883, now seen corresponding path program 1 times [2022-07-13 04:20:37,702 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:37,702 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1634410866] [2022-07-13 04:20:37,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:37,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:37,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:37,792 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-13 04:20:37,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:37,841 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-13 04:20:37,845 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:37,845 INFO L85 PathProgramCache]: Analyzing trace with hash 1450956, now seen corresponding path program 1 times [2022-07-13 04:20:37,846 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:37,847 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1627949960] [2022-07-13 04:20:37,847 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:37,847 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:37,868 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:37,869 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-13 04:20:37,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:37,880 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-13 04:20:37,882 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:37,883 INFO L85 PathProgramCache]: Analyzing trace with hash 1828301702, now seen corresponding path program 1 times [2022-07-13 04:20:37,883 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:37,884 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1340884662] [2022-07-13 04:20:37,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:37,884 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:37,901 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:37,901 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-13 04:20:37,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:37,912 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-13 04:20:38,009 INFO L210 LassoAnalysis]: Preferences: [2022-07-13 04:20:38,009 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-13 04:20:38,009 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-13 04:20:38,009 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-13 04:20:38,010 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-13 04:20:38,010 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,010 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-13 04:20:38,010 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-13 04:20:38,010 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2022-07-13 04:20:38,010 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-13 04:20:38,010 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-13 04:20:38,024 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-13 04:20:38,029 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-13 04:20:38,033 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-13 04:20:38,038 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-13 04:20:38,048 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-13 04:20:38,102 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-13 04:20:38,103 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-13 04:20:38,104 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,105 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,107 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-13 04:20:38,111 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-13 04:20:38,112 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:38,112 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:38,126 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-13 04:20:38,126 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-13 04:20:38,143 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-13 04:20:38,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,145 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-13 04:20:38,146 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-13 04:20:38,147 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:38,147 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:38,155 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-13 04:20:38,155 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-13 04:20:38,174 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2022-07-13 04:20:38,174 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,175 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,176 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-13 04:20:38,180 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:38,180 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:38,189 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-13 04:20:38,193 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-13 04:20:38,193 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-13 04:20:38,208 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2022-07-13 04:20:38,209 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,209 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,210 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-13 04:20:38,212 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-13 04:20:38,213 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:38,213 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:38,240 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-13 04:20:38,241 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,241 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,242 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-13 04:20:38,242 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-13 04:20:38,246 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-13 04:20:38,246 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:38,298 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-13 04:20:38,301 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-13 04:20:38,301 INFO L210 LassoAnalysis]: Preferences: [2022-07-13 04:20:38,301 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-13 04:20:38,302 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-13 04:20:38,302 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-13 04:20:38,302 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-13 04:20:38,302 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,302 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-13 04:20:38,302 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-13 04:20:38,302 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2022-07-13 04:20:38,302 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-13 04:20:38,302 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-13 04:20:38,304 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-13 04:20:38,306 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-13 04:20:38,309 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-13 04:20:38,311 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-13 04:20:38,318 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-13 04:20:38,361 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-13 04:20:38,365 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-13 04:20:38,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,368 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-13 04:20:38,369 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-13 04:20:38,370 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-13 04:20:38,376 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:38,376 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:38,377 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:38,377 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:38,377 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:38,378 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:38,378 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:38,380 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-13 04:20:38,397 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-13 04:20:38,398 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,399 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-13 04:20:38,400 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-13 04:20:38,401 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-13 04:20:38,407 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:38,407 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:38,407 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:38,407 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:38,407 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:38,408 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:38,408 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:38,420 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-13 04:20:38,436 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-13 04:20:38,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,438 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-13 04:20:38,439 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-13 04:20:38,440 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-13 04:20:38,446 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:38,446 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:38,446 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:38,446 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:38,446 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:38,447 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:38,447 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:38,448 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-13 04:20:38,463 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-13 04:20:38,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,465 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-13 04:20:38,466 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-13 04:20:38,467 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-13 04:20:38,473 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:38,473 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:38,473 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:38,473 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:38,473 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:38,474 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:38,474 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:38,479 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-13 04:20:38,483 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-13 04:20:38,483 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-13 04:20:38,484 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:38,484 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:38,528 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-13 04:20:38,529 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-13 04:20:38,530 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-13 04:20:38,531 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-13 04:20:38,531 INFO L513 LassoAnalysis]: Proved termination. [2022-07-13 04:20:38,531 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2022-07-13 04:20:38,547 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2022-07-13 04:20:38,549 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-13 04:20:38,576 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:38,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:38,607 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-13 04:20:38,609 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:38,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:38,633 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-13 04:20:38,634 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:38,682 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-13 04:20:38,714 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-13 04:20:38,715 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-13 04:20:38,817 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-13 04:20:38,819 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-13 04:20:38,829 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-13 04:20:38,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 11 transitions. [2022-07-13 04:20:38,832 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 4 letters. [2022-07-13 04:20:38,834 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:38,834 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 7 letters. Loop has 4 letters. [2022-07-13 04:20:38,834 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:38,834 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 8 letters. [2022-07-13 04:20:38,835 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:38,836 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 48 states and 60 transitions. [2022-07-13 04:20:38,845 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:38,856 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 48 states to 25 states and 34 transitions. [2022-07-13 04:20:38,857 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2022-07-13 04:20:38,857 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 18 [2022-07-13 04:20:38,858 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 34 transitions. [2022-07-13 04:20:38,858 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-13 04:20:38,858 INFO L369 hiAutomatonCegarLoop]: Abstraction has 25 states and 34 transitions. [2022-07-13 04:20:38,869 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 34 transitions. [2022-07-13 04:20:38,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 20. [2022-07-13 04:20:38,879 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-13 04:20:38,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2022-07-13 04:20:38,880 INFO L392 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2022-07-13 04:20:38,880 INFO L374 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2022-07-13 04:20:38,881 INFO L287 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2022-07-13 04:20:38,881 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2022-07-13 04:20:38,881 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:38,881 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-13 04:20:38,882 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-13 04:20:38,882 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 04:20:38,883 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 04:20:38,883 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-13 04:20:38,883 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-13 04:20:38,884 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:38,884 INFO L85 PathProgramCache]: Analyzing trace with hash -1181449843, now seen corresponding path program 1 times [2022-07-13 04:20:38,884 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:38,884 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1277951644] [2022-07-13 04:20:38,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:38,885 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:38,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:38,942 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-13 04:20:38,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:38,966 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-13 04:20:38,966 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 04:20:38,966 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1277951644] [2022-07-13 04:20:38,967 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1277951644] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-13 04:20:38,967 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-13 04:20:38,967 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-13 04:20:38,967 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [227368837] [2022-07-13 04:20:38,968 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-13 04:20:38,970 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-13 04:20:38,970 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:38,970 INFO L85 PathProgramCache]: Analyzing trace with hash 246097683, now seen corresponding path program 1 times [2022-07-13 04:20:38,971 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:38,971 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1485405140] [2022-07-13 04:20:38,971 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:38,971 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:38,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:38,991 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-13 04:20:38,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:39,007 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-13 04:20:39,008 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 04:20:39,008 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1485405140] [2022-07-13 04:20:39,008 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1485405140] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-13 04:20:39,008 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-13 04:20:39,008 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-13 04:20:39,008 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [390584503] [2022-07-13 04:20:39,009 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-13 04:20:39,009 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-13 04:20:39,009 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 04:20:39,011 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-07-13 04:20:39,011 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-07-13 04:20:39,012 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-13 04:20:39,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 04:20:39,072 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2022-07-13 04:20:39,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-13 04:20:39,073 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2022-07-13 04:20:39,077 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:39,084 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2022-07-13 04:20:39,084 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2022-07-13 04:20:39,085 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2022-07-13 04:20:39,085 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2022-07-13 04:20:39,086 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-13 04:20:39,086 INFO L369 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-13 04:20:39,086 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2022-07-13 04:20:39,090 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2022-07-13 04:20:39,091 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-13 04:20:39,093 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2022-07-13 04:20:39,093 INFO L392 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-13 04:20:39,093 INFO L374 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-13 04:20:39,093 INFO L287 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2022-07-13 04:20:39,094 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2022-07-13 04:20:39,095 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:39,096 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-13 04:20:39,096 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-13 04:20:39,096 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 04:20:39,097 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2022-07-13 04:20:39,097 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-13 04:20:39,097 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-13 04:20:39,098 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:39,098 INFO L85 PathProgramCache]: Analyzing trace with hash 2029785426, now seen corresponding path program 1 times [2022-07-13 04:20:39,098 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:39,098 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2107558544] [2022-07-13 04:20:39,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:39,098 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:39,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:39,160 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-13 04:20:39,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:39,192 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-13 04:20:39,192 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 04:20:39,193 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2107558544] [2022-07-13 04:20:39,193 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2107558544] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 04:20:39,193 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1683935202] [2022-07-13 04:20:39,193 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:39,194 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 04:20:39,194 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:39,195 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-13 04:20:39,196 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-13 04:20:39,223 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:39,224 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-13 04:20:39,225 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:39,262 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-13 04:20:39,262 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 04:20:39,351 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-13 04:20:39,351 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1683935202] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 04:20:39,351 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 04:20:39,352 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2022-07-13 04:20:39,352 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [890367289] [2022-07-13 04:20:39,352 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 04:20:39,352 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-13 04:20:39,353 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:39,353 INFO L85 PathProgramCache]: Analyzing trace with hash -960881524, now seen corresponding path program 1 times [2022-07-13 04:20:39,353 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:39,353 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [682535816] [2022-07-13 04:20:39,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:39,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:39,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:39,359 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-13 04:20:39,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:39,363 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-13 04:20:39,491 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-13 04:20:39,505 INFO L210 LassoAnalysis]: Preferences: [2022-07-13 04:20:39,506 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-13 04:20:39,506 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-13 04:20:39,506 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-13 04:20:39,506 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-13 04:20:39,506 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:39,506 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-13 04:20:39,506 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-13 04:20:39,506 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2022-07-13 04:20:39,506 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-13 04:20:39,506 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-13 04:20:39,507 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-13 04:20:39,519 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-13 04:20:39,522 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-13 04:20:39,529 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-13 04:20:39,567 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-13 04:20:39,567 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-13 04:20:39,567 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:39,567 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:39,568 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-13 04:20:39,570 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-13 04:20:39,571 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:39,571 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:39,592 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-13 04:20:39,592 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-13 04:20:39,615 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-13 04:20:39,616 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:39,616 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:39,617 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-13 04:20:39,626 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:39,626 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:39,635 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-13 04:20:39,651 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-13 04:20:39,652 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-13 04:20:39,676 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-13 04:20:39,677 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:39,677 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:39,678 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-13 04:20:39,679 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-13 04:20:39,680 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:39,681 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:39,740 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-13 04:20:39,740 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:39,740 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:39,742 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-13 04:20:39,748 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-13 04:20:39,748 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:39,750 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-13 04:20:40,554 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-13 04:20:40,558 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2022-07-13 04:20:40,558 INFO L210 LassoAnalysis]: Preferences: [2022-07-13 04:20:40,558 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-13 04:20:40,558 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-13 04:20:40,558 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-13 04:20:40,558 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-13 04:20:40,558 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:40,558 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-13 04:20:40,558 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-13 04:20:40,558 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2022-07-13 04:20:40,558 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-13 04:20:40,559 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-13 04:20:40,559 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-13 04:20:40,568 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-13 04:20:40,570 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-13 04:20:40,575 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-13 04:20:40,612 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-13 04:20:40,613 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-13 04:20:40,613 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:40,613 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:40,614 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-13 04:20:40,625 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-13 04:20:40,632 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:40,632 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:40,632 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:40,633 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:40,633 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:40,634 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:40,634 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:40,638 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-13 04:20:40,647 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-13 04:20:40,664 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-13 04:20:40,664 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:40,664 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:40,665 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-13 04:20:40,666 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-13 04:20:40,667 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-13 04:20:40,673 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:40,673 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:40,674 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:40,674 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:40,674 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:40,675 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:40,675 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:40,676 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-13 04:20:40,692 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-13 04:20:40,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:40,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:40,693 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-13 04:20:40,694 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-13 04:20:40,695 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-13 04:20:40,700 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:40,701 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:40,701 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:40,701 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:40,701 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:40,702 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:40,702 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:40,717 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-13 04:20:40,721 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-13 04:20:40,721 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-13 04:20:40,721 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:40,721 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:40,723 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-13 04:20:40,727 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-13 04:20:40,728 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-13 04:20:40,728 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-13 04:20:40,728 INFO L513 LassoAnalysis]: Proved termination. [2022-07-13 04:20:40,728 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2022-07-13 04:20:40,743 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-13 04:20:40,744 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-13 04:20:40,761 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:40,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:40,780 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-13 04:20:40,781 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:40,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:40,844 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-13 04:20:40,846 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:40,905 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-13 04:20:40,906 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-13 04:20:40,907 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-13 04:20:41,067 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-13 04:20:41,068 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-13 04:20:41,069 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-13 04:20:41,069 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 37 transitions. [2022-07-13 04:20:41,069 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 10 letters. [2022-07-13 04:20:41,070 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:41,070 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 22 letters. Loop has 10 letters. [2022-07-13 04:20:41,070 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:41,071 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 20 letters. [2022-07-13 04:20:41,071 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:41,072 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2022-07-13 04:20:41,076 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-13 04:20:41,080 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 108 states and 152 transitions. [2022-07-13 04:20:41,080 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 64 [2022-07-13 04:20:41,080 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 69 [2022-07-13 04:20:41,081 INFO L73 IsDeterministic]: Start isDeterministic. Operand 108 states and 152 transitions. [2022-07-13 04:20:41,081 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-13 04:20:41,081 INFO L369 hiAutomatonCegarLoop]: Abstraction has 108 states and 152 transitions. [2022-07-13 04:20:41,081 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states and 152 transitions. [2022-07-13 04:20:41,090 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 94. [2022-07-13 04:20:41,091 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-13 04:20:41,092 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 126 transitions. [2022-07-13 04:20:41,092 INFO L392 hiAutomatonCegarLoop]: Abstraction has 94 states and 126 transitions. [2022-07-13 04:20:41,092 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 04:20:41,093 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-13 04:20:41,093 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-07-13 04:20:41,093 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-13 04:20:41,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 04:20:41,196 INFO L93 Difference]: Finished difference Result 123 states and 165 transitions. [2022-07-13 04:20:41,199 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-13 04:20:41,200 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 123 states and 165 transitions. [2022-07-13 04:20:41,203 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-13 04:20:41,206 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 123 states to 118 states and 160 transitions. [2022-07-13 04:20:41,206 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 77 [2022-07-13 04:20:41,206 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 77 [2022-07-13 04:20:41,206 INFO L73 IsDeterministic]: Start isDeterministic. Operand 118 states and 160 transitions. [2022-07-13 04:20:41,207 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-13 04:20:41,207 INFO L369 hiAutomatonCegarLoop]: Abstraction has 118 states and 160 transitions. [2022-07-13 04:20:41,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states and 160 transitions. [2022-07-13 04:20:41,216 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 106. [2022-07-13 04:20:41,216 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-13 04:20:41,218 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 141 transitions. [2022-07-13 04:20:41,218 INFO L392 hiAutomatonCegarLoop]: Abstraction has 106 states and 141 transitions. [2022-07-13 04:20:41,218 INFO L374 stractBuchiCegarLoop]: Abstraction has 106 states and 141 transitions. [2022-07-13 04:20:41,218 INFO L287 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2022-07-13 04:20:41,218 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 141 transitions. [2022-07-13 04:20:41,220 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-13 04:20:41,220 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-13 04:20:41,220 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-13 04:20:41,222 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 04:20:41,222 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 5, 3, 3, 3, 3, 2, 2, 2, 1] [2022-07-13 04:20:41,222 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-13 04:20:41,222 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-13 04:20:41,223 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:41,223 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 1 times [2022-07-13 04:20:41,223 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:41,223 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [59277207] [2022-07-13 04:20:41,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:41,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:41,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:41,236 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-13 04:20:41,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:41,250 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-13 04:20:41,251 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:41,251 INFO L85 PathProgramCache]: Analyzing trace with hash 1616897917, now seen corresponding path program 1 times [2022-07-13 04:20:41,251 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:41,252 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [839427262] [2022-07-13 04:20:41,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:41,252 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:41,265 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,273 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-13 04:20:41,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,310 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-13 04:20:41,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,329 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-13 04:20:41,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,393 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-13 04:20:41,409 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-13 04:20:41,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,414 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-13 04:20:41,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,418 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-13 04:20:41,418 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 04:20:41,418 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [839427262] [2022-07-13 04:20:41,418 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [839427262] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 04:20:41,419 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1620678121] [2022-07-13 04:20:41,419 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:41,419 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 04:20:41,421 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:41,436 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-13 04:20:41,465 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-13 04:20:41,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,472 INFO L263 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-13 04:20:41,474 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:41,504 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-13 04:20:41,505 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 04:20:41,640 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-13 04:20:41,641 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1620678121] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 04:20:41,641 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 04:20:41,641 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2022-07-13 04:20:41,642 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [967720743] [2022-07-13 04:20:41,642 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 04:20:41,642 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-13 04:20:41,642 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 04:20:41,643 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-07-13 04:20:41,643 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2022-07-13 04:20:41,643 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-13 04:20:41,732 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 04:20:41,733 INFO L93 Difference]: Finished difference Result 60 states and 77 transitions. [2022-07-13 04:20:41,733 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-13 04:20:41,736 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 60 states and 77 transitions. [2022-07-13 04:20:41,740 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:41,743 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 60 states to 54 states and 70 transitions. [2022-07-13 04:20:41,744 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2022-07-13 04:20:41,744 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2022-07-13 04:20:41,744 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2022-07-13 04:20:41,744 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-13 04:20:41,744 INFO L369 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2022-07-13 04:20:41,744 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2022-07-13 04:20:41,756 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-07-13 04:20:41,756 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-13 04:20:41,757 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2022-07-13 04:20:41,757 INFO L392 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2022-07-13 04:20:41,757 INFO L374 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2022-07-13 04:20:41,757 INFO L287 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2022-07-13 04:20:41,757 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2022-07-13 04:20:41,758 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:41,758 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-13 04:20:41,759 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-13 04:20:41,760 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 04:20:41,760 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 1] [2022-07-13 04:20:41,760 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-13 04:20:41,760 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-13 04:20:41,761 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:41,761 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 2 times [2022-07-13 04:20:41,761 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:41,761 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [19287052] [2022-07-13 04:20:41,761 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:41,761 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:41,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:41,772 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-13 04:20:41,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:41,782 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-13 04:20:41,782 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:41,782 INFO L85 PathProgramCache]: Analyzing trace with hash -176759904, now seen corresponding path program 2 times [2022-07-13 04:20:41,783 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:41,783 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1316135861] [2022-07-13 04:20:41,783 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:41,783 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:41,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,796 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-13 04:20:41,801 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,810 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-13 04:20:41,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,841 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-13 04:20:41,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,846 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-13 04:20:41,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,850 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2022-07-13 04:20:41,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:41,860 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-13 04:20:41,860 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 04:20:41,860 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1316135861] [2022-07-13 04:20:41,861 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1316135861] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 04:20:41,861 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [450796217] [2022-07-13 04:20:41,861 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-13 04:20:41,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 04:20:41,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:41,863 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-13 04:20:41,897 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-13 04:20:41,904 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-13 04:20:41,905 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 04:20:41,905 INFO L263 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-13 04:20:41,907 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:41,955 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-13 04:20:41,956 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 04:20:42,173 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-13 04:20:42,173 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [450796217] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 04:20:42,173 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 04:20:42,174 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 14 [2022-07-13 04:20:42,174 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2123597894] [2022-07-13 04:20:42,174 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 04:20:42,174 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-13 04:20:42,175 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 04:20:42,175 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-13 04:20:42,175 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2022-07-13 04:20:42,176 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-13 04:20:42,245 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 04:20:42,245 INFO L93 Difference]: Finished difference Result 54 states and 67 transitions. [2022-07-13 04:20:42,246 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-13 04:20:42,247 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 54 states and 67 transitions. [2022-07-13 04:20:42,248 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:42,249 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 54 states to 54 states and 67 transitions. [2022-07-13 04:20:42,249 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2022-07-13 04:20:42,249 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2022-07-13 04:20:42,249 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 67 transitions. [2022-07-13 04:20:42,249 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-13 04:20:42,249 INFO L369 hiAutomatonCegarLoop]: Abstraction has 54 states and 67 transitions. [2022-07-13 04:20:42,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 67 transitions. [2022-07-13 04:20:42,252 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-07-13 04:20:42,253 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-13 04:20:42,253 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 67 transitions. [2022-07-13 04:20:42,253 INFO L392 hiAutomatonCegarLoop]: Abstraction has 54 states and 67 transitions. [2022-07-13 04:20:42,253 INFO L374 stractBuchiCegarLoop]: Abstraction has 54 states and 67 transitions. [2022-07-13 04:20:42,254 INFO L287 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2022-07-13 04:20:42,254 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 67 transitions. [2022-07-13 04:20:42,254 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-13 04:20:42,255 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-13 04:20:42,255 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-13 04:20:42,256 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 04:20:42,256 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2022-07-13 04:20:42,256 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-13 04:20:42,256 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-13 04:20:42,257 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:42,257 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 3 times [2022-07-13 04:20:42,257 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:42,257 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [961214184] [2022-07-13 04:20:42,257 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:42,258 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:42,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:42,266 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-13 04:20:42,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:42,283 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-13 04:20:42,285 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:42,286 INFO L85 PathProgramCache]: Analyzing trace with hash 780094678, now seen corresponding path program 3 times [2022-07-13 04:20:42,286 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:42,288 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [463584897] [2022-07-13 04:20:42,288 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:42,289 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:42,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:42,309 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-13 04:20:42,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:42,315 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-13 04:20:42,316 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:42,316 INFO L85 PathProgramCache]: Analyzing trace with hash 1975410011, now seen corresponding path program 4 times [2022-07-13 04:20:42,316 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:42,316 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [799134330] [2022-07-13 04:20:42,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:42,317 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:42,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:42,421 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2022-07-13 04:20:42,424 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:42,427 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-13 04:20:42,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:42,430 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-13 04:20:42,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:42,433 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2022-07-13 04:20:42,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:42,438 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-13 04:20:42,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:42,440 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-13 04:20:42,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:42,443 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-13 04:20:42,443 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 04:20:42,443 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [799134330] [2022-07-13 04:20:42,444 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [799134330] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 04:20:42,444 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [284298234] [2022-07-13 04:20:42,444 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-13 04:20:42,444 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 04:20:42,444 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:42,447 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-13 04:20:42,476 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-13 04:20:42,490 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-13 04:20:42,491 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 04:20:42,491 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-13 04:20:42,496 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:42,557 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-13 04:20:42,557 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 04:20:42,657 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-13 04:20:42,658 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [284298234] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 04:20:42,658 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 04:20:42,658 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12] total 15 [2022-07-13 04:20:42,660 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [567501828] [2022-07-13 04:20:42,660 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 04:20:42,876 INFO L210 LassoAnalysis]: Preferences: [2022-07-13 04:20:42,876 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-13 04:20:42,876 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-13 04:20:42,876 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-13 04:20:42,876 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-13 04:20:42,876 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:42,876 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-13 04:20:42,876 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-13 04:20:42,876 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration6_Loop [2022-07-13 04:20:42,876 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-13 04:20:42,876 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-13 04:20:42,877 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-13 04:20:42,885 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-13 04:20:42,887 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-13 04:20:42,889 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-13 04:20:42,937 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-13 04:20:42,937 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-13 04:20:42,937 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:42,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:42,943 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-13 04:20:42,948 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:42,948 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:42,961 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-13 04:20:42,993 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-13 04:20:42,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:42,993 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:42,995 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-13 04:20:43,000 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-13 04:20:43,000 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:43,005 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-13 04:20:43,999 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-13 04:20:44,002 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-13 04:20:44,003 INFO L210 LassoAnalysis]: Preferences: [2022-07-13 04:20:44,003 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-13 04:20:44,003 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-13 04:20:44,003 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-13 04:20:44,003 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-13 04:20:44,004 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:44,004 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-13 04:20:44,004 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-13 04:20:44,004 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration6_Loop [2022-07-13 04:20:44,004 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-13 04:20:44,004 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-13 04:20:44,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-13 04:20:44,006 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-13 04:20:44,008 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-13 04:20:44,009 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-13 04:20:44,070 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-13 04:20:44,070 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-13 04:20:44,070 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:44,070 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:44,072 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-13 04:20:44,080 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-13 04:20:44,087 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:44,087 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:44,087 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:44,088 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:44,088 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:44,089 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:44,089 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:44,092 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-13 04:20:44,097 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-13 04:20:44,113 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2022-07-13 04:20:44,113 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:44,114 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:44,115 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-13 04:20:44,115 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-13 04:20:44,116 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-13 04:20:44,122 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:44,122 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:44,123 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:44,123 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:44,123 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:44,123 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:44,123 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:44,134 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-13 04:20:44,157 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2022-07-13 04:20:44,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:44,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:44,159 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-13 04:20:44,163 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-13 04:20:44,167 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-13 04:20:44,169 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:44,169 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:44,169 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:44,170 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:44,170 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:44,170 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:44,170 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:44,171 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-13 04:20:44,188 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2022-07-13 04:20:44,188 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:44,189 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:44,190 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-13 04:20:44,190 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-13 04:20:44,193 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-13 04:20:44,198 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:44,198 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:44,199 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:44,199 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:44,199 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:44,203 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:44,203 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:44,212 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-13 04:20:44,215 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-13 04:20:44,215 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-13 04:20:44,215 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:44,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:44,219 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-13 04:20:44,220 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-13 04:20:44,220 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-13 04:20:44,220 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-13 04:20:44,221 INFO L513 LassoAnalysis]: Proved termination. [2022-07-13 04:20:44,221 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2022-07-13 04:20:44,235 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2022-07-13 04:20:44,236 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-13 04:20:44,260 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:44,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:44,298 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-13 04:20:44,299 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:44,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:44,471 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-13 04:20:44,472 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:44,561 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-13 04:20:44,600 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-13 04:20:44,601 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-13 04:20:44,601 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-13 04:20:44,675 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-13 04:20:44,675 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-13 04:20:44,678 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-13 04:20:44,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2022-07-13 04:20:44,678 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2022-07-13 04:20:44,679 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:44,679 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-13 04:20:44,686 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:44,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:44,719 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-13 04:20:44,722 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:44,898 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:44,899 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-13 04:20:44,901 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:44,990 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-13 04:20:44,991 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-13 04:20:44,992 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-13 04:20:45,070 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-13 04:20:45,071 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-13 04:20:45,072 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-13 04:20:45,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2022-07-13 04:20:45,073 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2022-07-13 04:20:45,073 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:45,073 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-13 04:20:45,085 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:45,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:45,115 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-13 04:20:45,117 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:45,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:45,270 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-13 04:20:45,271 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:45,361 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-13 04:20:45,361 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-13 04:20:45,362 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-13 04:20:45,567 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-13 04:20:45,575 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-13 04:20:45,576 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-13 04:20:45,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 46 transitions. [2022-07-13 04:20:45,578 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 22 letters. [2022-07-13 04:20:45,580 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:45,580 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 54 letters. Loop has 22 letters. [2022-07-13 04:20:45,581 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:45,581 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 44 letters. [2022-07-13 04:20:45,582 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:45,582 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 321 states and 401 transitions. [2022-07-13 04:20:45,589 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2022-07-13 04:20:45,595 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 321 states to 203 states and 261 transitions. [2022-07-13 04:20:45,595 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2022-07-13 04:20:45,596 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 90 [2022-07-13 04:20:45,596 INFO L73 IsDeterministic]: Start isDeterministic. Operand 203 states and 261 transitions. [2022-07-13 04:20:45,596 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-13 04:20:45,596 INFO L369 hiAutomatonCegarLoop]: Abstraction has 203 states and 261 transitions. [2022-07-13 04:20:45,597 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states and 261 transitions. [2022-07-13 04:20:45,615 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 175. [2022-07-13 04:20:45,615 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-13 04:20:45,617 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 212 transitions. [2022-07-13 04:20:45,618 INFO L392 hiAutomatonCegarLoop]: Abstraction has 175 states and 212 transitions. [2022-07-13 04:20:45,618 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 04:20:45,618 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-07-13 04:20:45,618 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-07-13 04:20:45,619 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-13 04:20:45,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 04:20:45,826 INFO L93 Difference]: Finished difference Result 124 states and 140 transitions. [2022-07-13 04:20:45,828 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-07-13 04:20:45,829 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 124 states and 140 transitions. [2022-07-13 04:20:45,830 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2022-07-13 04:20:45,831 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 124 states to 105 states and 117 transitions. [2022-07-13 04:20:45,831 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2022-07-13 04:20:45,831 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 64 [2022-07-13 04:20:45,831 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 117 transitions. [2022-07-13 04:20:45,831 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-13 04:20:45,832 INFO L369 hiAutomatonCegarLoop]: Abstraction has 105 states and 117 transitions. [2022-07-13 04:20:45,832 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 117 transitions. [2022-07-13 04:20:45,834 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 96. [2022-07-13 04:20:45,834 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-13 04:20:45,834 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 108 transitions. [2022-07-13 04:20:45,835 INFO L392 hiAutomatonCegarLoop]: Abstraction has 96 states and 108 transitions. [2022-07-13 04:20:45,835 INFO L374 stractBuchiCegarLoop]: Abstraction has 96 states and 108 transitions. [2022-07-13 04:20:45,835 INFO L287 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2022-07-13 04:20:45,835 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 96 states and 108 transitions. [2022-07-13 04:20:45,836 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2022-07-13 04:20:45,836 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-13 04:20:45,836 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-13 04:20:45,837 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 6, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2022-07-13 04:20:45,837 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-13 04:20:45,837 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-13 04:20:45,837 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-13 04:20:45,838 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:45,838 INFO L85 PathProgramCache]: Analyzing trace with hash 2096320921, now seen corresponding path program 5 times [2022-07-13 04:20:45,838 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:45,838 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1997758508] [2022-07-13 04:20:45,838 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:45,838 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:45,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:45,881 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2022-07-13 04:20:45,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:45,919 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-13 04:20:45,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:45,931 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-13 04:20:45,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:45,934 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-13 04:20:45,934 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-13 04:20:45,934 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1997758508] [2022-07-13 04:20:45,935 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1997758508] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-13 04:20:45,935 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1889405245] [2022-07-13 04:20:45,935 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-13 04:20:45,935 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-13 04:20:45,935 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:45,936 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-13 04:20:45,937 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-13 04:20:45,964 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2022-07-13 04:20:45,964 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-13 04:20:45,965 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-13 04:20:45,966 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:46,035 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-13 04:20:46,035 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-13 04:20:46,172 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-13 04:20:46,173 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1889405245] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-13 04:20:46,173 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-13 04:20:46,173 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 10] total 18 [2022-07-13 04:20:46,174 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1979117489] [2022-07-13 04:20:46,174 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-13 04:20:46,175 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-13 04:20:46,175 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:46,175 INFO L85 PathProgramCache]: Analyzing trace with hash 1893846, now seen corresponding path program 2 times [2022-07-13 04:20:46,175 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-13 04:20:46,175 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1199168478] [2022-07-13 04:20:46,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-13 04:20:46,176 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-13 04:20:46,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:46,179 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-13 04:20:46,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-13 04:20:46,181 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-13 04:20:46,226 INFO L210 LassoAnalysis]: Preferences: [2022-07-13 04:20:46,226 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-13 04:20:46,226 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-13 04:20:46,226 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-13 04:20:46,226 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-13 04:20:46,226 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:46,226 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-13 04:20:46,226 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-13 04:20:46,227 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration7_Loop [2022-07-13 04:20:46,227 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-13 04:20:46,227 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-13 04:20:46,228 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-13 04:20:46,230 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-13 04:20:46,232 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-13 04:20:46,234 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-13 04:20:46,273 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-13 04:20:46,273 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-13 04:20:46,273 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:46,273 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:46,275 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-13 04:20:46,276 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-13 04:20:46,278 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:46,278 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:46,298 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-13 04:20:46,299 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-13 04:20:46,324 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-13 04:20:46,324 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:46,324 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:46,326 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-13 04:20:46,327 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-13 04:20:46,328 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:46,328 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:46,351 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-13 04:20:46,352 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-13 04:20:46,376 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-13 04:20:46,377 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:46,377 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:46,378 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-13 04:20:46,383 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:46,384 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:46,392 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-13 04:20:46,404 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-13 04:20:46,404 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-13 04:20:46,429 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2022-07-13 04:20:46,430 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:46,430 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:46,431 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-13 04:20:46,434 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-13 04:20:46,434 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:46,451 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-13 04:20:46,481 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-13 04:20:46,482 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:46,482 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:46,484 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-13 04:20:46,486 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-13 04:20:46,486 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-13 04:20:46,506 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-13 04:20:48,181 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-13 04:20:48,184 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Ended with exit code 0 [2022-07-13 04:20:48,185 INFO L210 LassoAnalysis]: Preferences: [2022-07-13 04:20:48,185 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-13 04:20:48,185 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-13 04:20:48,185 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-13 04:20:48,185 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-13 04:20:48,185 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:48,185 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-13 04:20:48,185 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-13 04:20:48,185 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration7_Loop [2022-07-13 04:20:48,185 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-13 04:20:48,185 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-13 04:20:48,186 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-13 04:20:48,192 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-13 04:20:48,200 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-13 04:20:48,202 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-13 04:20:48,232 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-13 04:20:48,232 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-13 04:20:48,232 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:48,232 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:48,234 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-13 04:20:48,236 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-13 04:20:48,241 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-13 04:20:48,251 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:48,251 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:48,251 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:48,251 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:48,252 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:48,252 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:48,252 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:48,261 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-13 04:20:48,279 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Ended with exit code 0 [2022-07-13 04:20:48,279 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:48,279 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:48,280 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-13 04:20:48,281 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-13 04:20:48,282 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-13 04:20:48,288 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-13 04:20:48,288 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-13 04:20:48,288 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-13 04:20:48,288 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-13 04:20:48,288 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-13 04:20:48,289 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-13 04:20:48,289 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-13 04:20:48,291 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-13 04:20:48,293 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-13 04:20:48,293 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-13 04:20:48,293 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-13 04:20:48,293 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-13 04:20:48,294 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-13 04:20:48,295 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-13 04:20:48,296 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-13 04:20:48,296 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-13 04:20:48,296 INFO L513 LassoAnalysis]: Proved termination. [2022-07-13 04:20:48,296 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2022-07-13 04:20:48,311 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-13 04:20:48,311 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-13 04:20:48,319 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:48,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:48,363 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-13 04:20:48,365 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:48,514 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-13 04:20:48,550 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:48,550 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-13 04:20:48,551 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:48,577 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-13 04:20:48,578 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-13 04:20:48,578 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-13 04:20:48,619 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-13 04:20:48,619 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-13 04:20:48,620 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-13 04:20:48,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2022-07-13 04:20:48,620 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 36 letters. Loop has 4 letters. [2022-07-13 04:20:48,620 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:48,620 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-13 04:20:48,628 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:48,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:48,666 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-13 04:20:48,667 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:48,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:48,806 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-13 04:20:48,807 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:48,831 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-13 04:20:48,832 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-13 04:20:48,832 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-13 04:20:48,893 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-13 04:20:48,893 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-13 04:20:48,894 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-13 04:20:48,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 16 transitions. [2022-07-13 04:20:48,894 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 16 transitions. Stem has 36 letters. Loop has 4 letters. [2022-07-13 04:20:48,894 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:48,895 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-13 04:20:48,903 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-13 04:20:48,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:48,942 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-13 04:20:48,943 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:49,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-13 04:20:49,091 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-13 04:20:49,091 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-13 04:20:49,121 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-13 04:20:49,122 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-13 04:20:49,122 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-13 04:20:49,172 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-13 04:20:49,175 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-13 04:20:49,175 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-13 04:20:49,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 22 transitions. [2022-07-13 04:20:49,175 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 4 letters. [2022-07-13 04:20:49,176 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:49,176 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 40 letters. Loop has 4 letters. [2022-07-13 04:20:49,176 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:49,176 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 8 letters. [2022-07-13 04:20:49,176 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-13 04:20:49,176 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 131 states and 150 transitions. [2022-07-13 04:20:49,178 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-13 04:20:49,178 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 131 states to 0 states and 0 transitions. [2022-07-13 04:20:49,178 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2022-07-13 04:20:49,178 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2022-07-13 04:20:49,178 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2022-07-13 04:20:49,178 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2022-07-13 04:20:49,178 INFO L369 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-13 04:20:49,178 INFO L392 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-13 04:20:49,178 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-13 04:20:49,179 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-07-13 04:20:49,179 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=245, Unknown=0, NotChecked=0, Total=306 [2022-07-13 04:20:49,180 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-13 04:20:49,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-13 04:20:49,180 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-07-13 04:20:49,180 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-13 04:20:49,181 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2022-07-13 04:20:49,181 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-13 04:20:49,181 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2022-07-13 04:20:49,181 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2022-07-13 04:20:49,181 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2022-07-13 04:20:49,181 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2022-07-13 04:20:49,181 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2022-07-13 04:20:49,182 INFO L369 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-13 04:20:49,182 INFO L392 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-13 04:20:49,182 INFO L374 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-13 04:20:49,182 INFO L287 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2022-07-13 04:20:49,182 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2022-07-13 04:20:49,182 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-13 04:20:49,182 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2022-07-13 04:20:49,188 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 13.07 04:20:49 BoogieIcfgContainer [2022-07-13 04:20:49,188 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2022-07-13 04:20:49,189 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2022-07-13 04:20:49,189 INFO L271 PluginConnector]: Initializing Witness Printer... [2022-07-13 04:20:49,189 INFO L275 PluginConnector]: Witness Printer initialized [2022-07-13 04:20:49,189 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 13.07 04:20:37" (3/4) ... [2022-07-13 04:20:49,191 INFO L140 WitnessPrinter]: No result that supports witness generation found [2022-07-13 04:20:49,191 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2022-07-13 04:20:49,192 INFO L158 Benchmark]: Toolchain (without parser) took 12165.55ms. Allocated memory was 107.0MB in the beginning and 176.2MB in the end (delta: 69.2MB). Free memory was 78.1MB in the beginning and 60.6MB in the end (delta: 17.5MB). Peak memory consumption was 87.3MB. Max. memory is 16.1GB. [2022-07-13 04:20:49,192 INFO L158 Benchmark]: CDTParser took 0.17ms. Allocated memory is still 107.0MB. Free memory was 65.9MB in the beginning and 65.8MB in the end (delta: 84.1kB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-13 04:20:49,193 INFO L158 Benchmark]: CACSL2BoogieTranslator took 259.98ms. Allocated memory was 107.0MB in the beginning and 146.8MB in the end (delta: 39.8MB). Free memory was 77.8MB in the beginning and 121.9MB in the end (delta: -44.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2022-07-13 04:20:49,193 INFO L158 Benchmark]: Boogie Procedure Inliner took 27.60ms. Allocated memory is still 146.8MB. Free memory was 121.9MB in the beginning and 120.5MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2022-07-13 04:20:49,193 INFO L158 Benchmark]: Boogie Preprocessor took 19.72ms. Allocated memory is still 146.8MB. Free memory was 120.5MB in the beginning and 119.7MB in the end (delta: 772.5kB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-13 04:20:49,194 INFO L158 Benchmark]: RCFGBuilder took 255.78ms. Allocated memory is still 146.8MB. Free memory was 119.7MB in the beginning and 111.2MB in the end (delta: 8.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2022-07-13 04:20:49,194 INFO L158 Benchmark]: BuchiAutomizer took 11592.17ms. Allocated memory was 146.8MB in the beginning and 176.2MB in the end (delta: 29.4MB). Free memory was 110.8MB in the beginning and 60.6MB in the end (delta: 50.2MB). Peak memory consumption was 82.7MB. Max. memory is 16.1GB. [2022-07-13 04:20:49,196 INFO L158 Benchmark]: Witness Printer took 2.79ms. Allocated memory is still 176.2MB. Free memory is still 60.6MB. There was no memory consumed. Max. memory is 16.1GB. [2022-07-13 04:20:49,197 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.17ms. Allocated memory is still 107.0MB. Free memory was 65.9MB in the beginning and 65.8MB in the end (delta: 84.1kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 259.98ms. Allocated memory was 107.0MB in the beginning and 146.8MB in the end (delta: 39.8MB). Free memory was 77.8MB in the beginning and 121.9MB in the end (delta: -44.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 27.60ms. Allocated memory is still 146.8MB. Free memory was 121.9MB in the beginning and 120.5MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 19.72ms. Allocated memory is still 146.8MB. Free memory was 120.5MB in the beginning and 119.7MB in the end (delta: 772.5kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 255.78ms. Allocated memory is still 146.8MB. Free memory was 119.7MB in the beginning and 111.2MB in the end (delta: 8.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 11592.17ms. Allocated memory was 146.8MB in the beginning and 176.2MB in the end (delta: 29.4MB). Free memory was 110.8MB in the beginning and 60.6MB in the end (delta: 50.2MB). Peak memory consumption was 82.7MB. Max. memory is 16.1GB. * Witness Printer took 2.79ms. Allocated memory is still 176.2MB. Free memory is still 60.6MB. 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.5s and 8 iterations. TraceHistogramMax:7. Analysis of lassos took 7.9s. Construction of modules took 0.4s. Büchi inclusion checks took 2.8s. 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.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 358 mSDsluCounter, 366 SdHoareTripleChecker+Invalid, 0.5s 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: 14ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 8 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 3.9s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2022-07-13 04:20:49,226 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-13 04:20:49,429 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-13 04:20:49,629 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Ended with exit code 0 [2022-07-13 04:20:49,829 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2022-07-13 04:20:50,030 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-07-13 04:20:50,230 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE