./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 c3fed411 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-tmp.no-commuhash-c3fed41 [2021-12-19 19:14:04,734 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-19 19:14:04,736 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-19 19:14:04,766 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-19 19:14:04,773 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-19 19:14:04,776 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-19 19:14:04,777 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-19 19:14:04,782 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-19 19:14:04,783 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-19 19:14:04,786 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-19 19:14:04,787 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-19 19:14:04,788 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-19 19:14:04,788 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-19 19:14:04,790 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-19 19:14:04,791 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-19 19:14:04,793 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-19 19:14:04,793 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-19 19:14:04,794 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-19 19:14:04,797 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-19 19:14:04,799 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-19 19:14:04,801 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-19 19:14:04,801 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-19 19:14:04,802 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-19 19:14:04,803 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-19 19:14:04,808 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-19 19:14:04,810 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-19 19:14:04,810 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-19 19:14:04,811 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-19 19:14:04,812 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-19 19:14:04,812 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-19 19:14:04,813 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-19 19:14:04,813 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-19 19:14:04,814 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-19 19:14:04,815 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-19 19:14:04,816 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-19 19:14:04,816 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-19 19:14:04,816 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-19 19:14:04,817 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-19 19:14:04,817 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-19 19:14:04,817 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-19 19:14:04,818 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-19 19:14:04,819 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2021-12-19 19:14:04,845 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-19 19:14:04,845 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-19 19:14:04,845 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-19 19:14:04,846 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-19 19:14:04,846 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-19 19:14:04,847 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-19 19:14:04,847 INFO L138 SettingsManager]: * Use SBE=true [2021-12-19 19:14:04,847 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2021-12-19 19:14:04,847 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2021-12-19 19:14:04,847 INFO L138 SettingsManager]: * Use old map elimination=false [2021-12-19 19:14:04,848 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2021-12-19 19:14:04,848 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2021-12-19 19:14:04,848 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2021-12-19 19:14:04,848 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-19 19:14:04,848 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-19 19:14:04,849 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-19 19:14:04,849 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-19 19:14:04,849 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-19 19:14:04,849 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-19 19:14:04,849 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2021-12-19 19:14:04,849 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2021-12-19 19:14:04,849 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2021-12-19 19:14:04,849 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-19 19:14:04,850 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-19 19:14:04,851 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2021-12-19 19:14:04,851 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-19 19:14:04,851 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2021-12-19 19:14:04,851 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-19 19:14:04,851 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-19 19:14:04,851 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-19 19:14:04,852 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-19 19:14:04,852 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-19 19:14:04,853 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2021-12-19 19:14:04,853 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 [2021-12-19 19:14:05,010 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-19 19:14:05,033 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-19 19:14:05,035 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-19 19:14:05,036 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-19 19:14:05,037 INFO L275 PluginConnector]: CDTParser initialized [2021-12-19 19:14:05,037 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 [2021-12-19 19:14:05,074 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e1ce81c9f/682e1b5bedf4498381584094e80e4c5c/FLAGde40078d7 [2021-12-19 19:14:05,397 INFO L306 CDTParser]: Found 1 translation units. [2021-12-19 19:14:05,398 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-2.c [2021-12-19 19:14:05,402 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e1ce81c9f/682e1b5bedf4498381584094e80e4c5c/FLAGde40078d7 [2021-12-19 19:14:05,410 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e1ce81c9f/682e1b5bedf4498381584094e80e4c5c [2021-12-19 19:14:05,412 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-19 19:14:05,413 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-19 19:14:05,414 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-19 19:14:05,414 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-19 19:14:05,416 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-19 19:14:05,416 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,417 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@515028b0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05, skipping insertion in model container [2021-12-19 19:14:05,417 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,421 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-19 19:14:05,428 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-19 19:14:05,564 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] [2021-12-19 19:14:05,564 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-19 19:14:05,588 INFO L203 MainTranslator]: Completed pre-run [2021-12-19 19:14:05,597 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] [2021-12-19 19:14:05,599 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-19 19:14:05,618 INFO L208 MainTranslator]: Completed translation [2021-12-19 19:14:05,618 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05 WrapperNode [2021-12-19 19:14:05,618 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-19 19:14:05,619 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-19 19:14:05,619 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-19 19:14:05,620 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-19 19:14:05,624 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,628 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,639 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2021-12-19 19:14:05,639 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-19 19:14:05,639 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-19 19:14:05,640 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-19 19:14:05,640 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-19 19:14:05,644 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,645 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,646 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,646 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,647 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,648 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,649 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,649 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-19 19:14:05,650 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-19 19:14:05,650 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-19 19:14:05,650 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-19 19:14:05,651 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (1/1) ... [2021-12-19 19:14:05,656 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:05,662 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:05,675 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:05,677 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2021-12-19 19:14:05,713 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-19 19:14:05,713 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-19 19:14:05,713 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-19 19:14:05,713 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-19 19:14:05,713 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2021-12-19 19:14:05,713 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2021-12-19 19:14:05,752 INFO L236 CfgBuilder]: Building ICFG [2021-12-19 19:14:05,753 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-19 19:14:05,841 INFO L277 CfgBuilder]: Performing block encoding [2021-12-19 19:14:05,846 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-19 19:14:05,847 INFO L301 CfgBuilder]: Removed 0 assume(true) statements. [2021-12-19 19:14:05,848 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.12 07:14:05 BoogieIcfgContainer [2021-12-19 19:14:05,848 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-19 19:14:05,849 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2021-12-19 19:14:05,849 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2021-12-19 19:14:05,851 INFO L275 PluginConnector]: BuchiAutomizer initialized [2021-12-19 19:14:05,851 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-19 19:14:05,852 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 19.12 07:14:05" (1/3) ... [2021-12-19 19:14:05,852 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@77d1d528 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.12 07:14:05, skipping insertion in model container [2021-12-19 19:14:05,853 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-19 19:14:05,853 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.12 07:14:05" (2/3) ... [2021-12-19 19:14:05,853 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@77d1d528 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.12 07:14:05, skipping insertion in model container [2021-12-19 19:14:05,853 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-19 19:14:05,853 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.12 07:14:05" (3/3) ... [2021-12-19 19:14:05,854 INFO L388 chiAutomizerObserver]: Analyzing ICFG fibo_5-2.c [2021-12-19 19:14:05,920 INFO L359 BuchiCegarLoop]: Interprodecural is true [2021-12-19 19:14:05,921 INFO L360 BuchiCegarLoop]: Hoare is false [2021-12-19 19:14:05,921 INFO L361 BuchiCegarLoop]: Compute interpolants for ForwardPredicates [2021-12-19 19:14:05,921 INFO L362 BuchiCegarLoop]: Backedges is STRAIGHT_LINE [2021-12-19 19:14:05,921 INFO L363 BuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-12-19 19:14:05,921 INFO L364 BuchiCegarLoop]: Difference is false [2021-12-19 19:14:05,921 INFO L365 BuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-12-19 19:14:05,921 INFO L368 BuchiCegarLoop]: ======== Iteration 0==of CEGAR loop == BuchiCegarLoop======== [2021-12-19 19:14:05,930 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) [2021-12-19 19:14:05,942 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:05,942 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-19 19:14:05,943 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-19 19:14:05,946 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1] [2021-12-19 19:14:05,947 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-19 19:14:05,947 INFO L425 BuchiCegarLoop]: ======== Iteration 1============ [2021-12-19 19:14:05,947 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) [2021-12-19 19:14:05,949 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:05,949 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-19 19:14:05,949 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-19 19:14:05,950 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1] [2021-12-19 19:14:05,950 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-19 19:14:05,954 INFO L791 eck$LassoCheckResult]: Stem: 4#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); 13#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; 6#L27true call main_#t~ret6#1 := fibo(main_~x~0#1);< 7#fiboENTRYtrue [2021-12-19 19:14:05,954 INFO L793 eck$LassoCheckResult]: Loop: 7#fiboENTRYtrue ~n := #in~n; 8#L8true assume !(~n < 1); 10#L10true assume !(1 == ~n); 15#L13true call #t~ret4 := fibo(~n - 1);< 7#fiboENTRYtrue [2021-12-19 19:14:05,957 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:05,957 INFO L85 PathProgramCache]: Analyzing trace with hash 29883, now seen corresponding path program 1 times [2021-12-19 19:14:05,963 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:05,963 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1240979352] [2021-12-19 19:14:05,963 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:05,964 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:06,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:06,020 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-19 19:14:06,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:06,048 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-19 19:14:06,052 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:06,052 INFO L85 PathProgramCache]: Analyzing trace with hash 1450956, now seen corresponding path program 1 times [2021-12-19 19:14:06,052 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:06,053 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [775970334] [2021-12-19 19:14:06,054 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:06,054 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:06,062 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:06,062 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-19 19:14:06,072 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:06,075 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-19 19:14:06,076 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:06,076 INFO L85 PathProgramCache]: Analyzing trace with hash 1828301702, now seen corresponding path program 1 times [2021-12-19 19:14:06,076 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:06,077 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [346245727] [2021-12-19 19:14:06,077 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:06,077 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:06,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:06,092 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-19 19:14:06,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:06,109 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-19 19:14:06,204 INFO L210 LassoAnalysis]: Preferences: [2021-12-19 19:14:06,205 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-19 19:14:06,205 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-19 19:14:06,205 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-19 19:14:06,205 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-19 19:14:06,205 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,206 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-19 19:14:06,206 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-19 19:14:06,206 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2021-12-19 19:14:06,206 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-19 19:14:06,206 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-19 19:14:06,216 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,221 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,223 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,226 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,232 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,278 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-19 19:14:06,278 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-19 19:14:06,280 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,280 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,282 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,283 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2021-12-19 19:14:06,285 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:06,285 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:06,305 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-19 19:14:06,305 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-19 19:14:06,324 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:06,324 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,324 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,325 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,326 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2021-12-19 19:14:06,328 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:06,328 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:06,349 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-19 19:14:06,349 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-19 19:14:06,366 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:06,366 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,367 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,368 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,369 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2021-12-19 19:14:06,370 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:06,370 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:06,391 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-19 19:14:06,391 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-19 19:14:06,408 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:06,408 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,408 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,411 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,412 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2021-12-19 19:14:06,413 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:06,413 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:06,442 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:06,443 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,443 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,444 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,445 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2021-12-19 19:14:06,447 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-19 19:14:06,447 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:06,500 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-19 19:14:06,503 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2021-12-19 19:14:06,504 INFO L210 LassoAnalysis]: Preferences: [2021-12-19 19:14:06,504 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-19 19:14:06,504 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-19 19:14:06,504 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-19 19:14:06,504 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-19 19:14:06,504 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,504 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-19 19:14:06,504 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-19 19:14:06,504 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2021-12-19 19:14:06,504 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-19 19:14:06,505 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-19 19:14:06,505 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,507 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,509 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,511 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,516 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:06,561 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-19 19:14:06,565 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-19 19:14:06,566 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,566 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,567 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,568 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2021-12-19 19:14:06,570 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:06,576 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:06,576 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:06,577 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:06,577 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:06,577 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:06,578 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:06,578 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:06,589 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-19 19:14:06,604 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Ended with exit code 0 [2021-12-19 19:14:06,605 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,616 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,617 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2021-12-19 19:14:06,619 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:06,624 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:06,624 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:06,624 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:06,625 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:06,625 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:06,625 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:06,625 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:06,641 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-19 19:14:06,656 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:06,657 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,658 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,659 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2021-12-19 19:14:06,661 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:06,666 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:06,666 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:06,666 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:06,666 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:06,666 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:06,667 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:06,667 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:06,683 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-19 19:14:06,698 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:06,698 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,699 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,704 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,705 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2021-12-19 19:14:06,707 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:06,713 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:06,714 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:06,714 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:06,714 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:06,714 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:06,716 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:06,716 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:06,733 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-19 19:14:06,751 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-19 19:14:06,752 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-19 19:14:06,753 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:06,753 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:06,757 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:06,757 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2021-12-19 19:14:06,758 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-19 19:14:06,758 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-19 19:14:06,758 INFO L513 LassoAnalysis]: Proved termination. [2021-12-19 19:14:06,759 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2021-12-19 19:14:06,777 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:06,779 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-19 19:14:06,791 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:06,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:06,805 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-19 19:14:06,806 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:06,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:06,819 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-19 19:14:06,820 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:06,850 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 19:14:06,869 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2021-12-19 19:14:06,870 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) [2021-12-19 19:14:06,976 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. [2021-12-19 19:14:06,978 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 4 states 1 stem states 2 non-accepting loop states 1 accepting loop states [2021-12-19 19:14:06,981 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) [2021-12-19 19:14:06,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 11 transitions. [2021-12-19 19:14:06,982 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 4 letters. [2021-12-19 19:14:06,983 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:06,983 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 7 letters. Loop has 4 letters. [2021-12-19 19:14:06,983 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:06,984 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 8 letters. [2021-12-19 19:14:06,984 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:06,984 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 48 states and 60 transitions. [2021-12-19 19:14:06,987 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:06,990 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 48 states to 25 states and 34 transitions. [2021-12-19 19:14:06,996 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2021-12-19 19:14:06,996 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 18 [2021-12-19 19:14:06,996 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 34 transitions. [2021-12-19 19:14:06,997 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-19 19:14:06,997 INFO L681 BuchiCegarLoop]: Abstraction has 25 states and 34 transitions. [2021-12-19 19:14:07,006 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 34 transitions. [2021-12-19 19:14:07,017 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 20. [2021-12-19 19:14:07,017 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) [2021-12-19 19:14:07,023 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2021-12-19 19:14:07,024 INFO L704 BuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2021-12-19 19:14:07,024 INFO L587 BuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2021-12-19 19:14:07,024 INFO L425 BuchiCegarLoop]: ======== Iteration 2============ [2021-12-19 19:14:07,024 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2021-12-19 19:14:07,035 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:07,035 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-19 19:14:07,035 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-19 19:14:07,036 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-19 19:14:07,036 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2021-12-19 19:14:07,037 INFO L791 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 [2021-12-19 19:14:07,037 INFO L793 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 [2021-12-19 19:14:07,037 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:07,037 INFO L85 PathProgramCache]: Analyzing trace with hash -1181449843, now seen corresponding path program 1 times [2021-12-19 19:14:07,037 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:07,038 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [146665017] [2021-12-19 19:14:07,038 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:07,038 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:07,057 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:07,097 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-19 19:14:07,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:07,139 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-19 19:14:07,139 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 19:14:07,140 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [146665017] [2021-12-19 19:14:07,140 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [146665017] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 19:14:07,140 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 19:14:07,140 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-19 19:14:07,141 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [581817241] [2021-12-19 19:14:07,141 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 19:14:07,142 INFO L796 eck$LassoCheckResult]: stem already infeasible [2021-12-19 19:14:07,143 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:07,143 INFO L85 PathProgramCache]: Analyzing trace with hash 246097683, now seen corresponding path program 1 times [2021-12-19 19:14:07,143 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:07,143 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2097923972] [2021-12-19 19:14:07,143 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:07,143 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:07,147 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:07,158 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-19 19:14:07,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:07,176 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-19 19:14:07,176 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 19:14:07,176 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2097923972] [2021-12-19 19:14:07,177 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2097923972] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-19 19:14:07,177 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-19 19:14:07,177 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-19 19:14:07,177 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1166677060] [2021-12-19 19:14:07,177 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-19 19:14:07,177 INFO L808 eck$LassoCheckResult]: loop already infeasible [2021-12-19 19:14:07,178 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 19:14:07,179 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-19 19:14:07,180 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2021-12-19 19:14:07,180 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) [2021-12-19 19:14:07,236 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 19:14:07,236 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2021-12-19 19:14:07,237 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-19 19:14:07,237 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2021-12-19 19:14:07,238 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:07,239 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2021-12-19 19:14:07,239 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2021-12-19 19:14:07,240 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2021-12-19 19:14:07,240 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2021-12-19 19:14:07,240 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-19 19:14:07,240 INFO L681 BuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2021-12-19 19:14:07,240 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2021-12-19 19:14:07,242 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2021-12-19 19:14:07,242 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) [2021-12-19 19:14:07,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2021-12-19 19:14:07,242 INFO L704 BuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2021-12-19 19:14:07,242 INFO L587 BuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2021-12-19 19:14:07,243 INFO L425 BuchiCegarLoop]: ======== Iteration 3============ [2021-12-19 19:14:07,243 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2021-12-19 19:14:07,243 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:07,243 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-19 19:14:07,243 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-19 19:14:07,244 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-19 19:14:07,244 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2021-12-19 19:14:07,244 INFO L791 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 [2021-12-19 19:14:07,244 INFO L793 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 [2021-12-19 19:14:07,245 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:07,245 INFO L85 PathProgramCache]: Analyzing trace with hash 2029785426, now seen corresponding path program 1 times [2021-12-19 19:14:07,245 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:07,245 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1216589456] [2021-12-19 19:14:07,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:07,245 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:07,250 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:07,267 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-19 19:14:07,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:07,281 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 19:14:07,281 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 19:14:07,281 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1216589456] [2021-12-19 19:14:07,282 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1216589456] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-19 19:14:07,282 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1371574100] [2021-12-19 19:14:07,282 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:07,282 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 19:14:07,282 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:07,283 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-19 19:14:07,284 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-12-19 19:14:07,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:07,306 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-19 19:14:07,306 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:07,336 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 19:14:07,336 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-19 19:14:07,425 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 19:14:07,426 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1371574100] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-19 19:14:07,426 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-19 19:14:07,426 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2021-12-19 19:14:07,426 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [5722547] [2021-12-19 19:14:07,427 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-19 19:14:07,427 INFO L796 eck$LassoCheckResult]: stem already infeasible [2021-12-19 19:14:07,427 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:07,427 INFO L85 PathProgramCache]: Analyzing trace with hash -960881524, now seen corresponding path program 1 times [2021-12-19 19:14:07,427 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:07,428 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1988885461] [2021-12-19 19:14:07,428 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:07,428 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:07,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:07,434 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-19 19:14:07,434 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:07,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:07,437 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-19 19:14:07,520 INFO L210 LassoAnalysis]: Preferences: [2021-12-19 19:14:07,520 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-19 19:14:07,520 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-19 19:14:07,520 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-19 19:14:07,520 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-19 19:14:07,520 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:07,521 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-19 19:14:07,521 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-19 19:14:07,521 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2021-12-19 19:14:07,521 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-19 19:14:07,521 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-19 19:14:07,522 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:07,523 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:07,528 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:07,529 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:07,554 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-19 19:14:07,554 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-19 19:14:07,554 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:07,554 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:07,555 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:07,556 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2021-12-19 19:14:07,558 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:07,558 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:07,579 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-19 19:14:07,579 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-19 19:14:07,596 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:07,596 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:07,596 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:07,597 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:07,598 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2021-12-19 19:14:07,599 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:07,599 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:07,636 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:07,637 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:07,637 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:07,638 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:07,639 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2021-12-19 19:14:07,640 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-19 19:14:07,640 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:08,387 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-19 19:14:08,392 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:08,392 INFO L210 LassoAnalysis]: Preferences: [2021-12-19 19:14:08,392 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-19 19:14:08,392 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-19 19:14:08,392 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-19 19:14:08,392 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-19 19:14:08,392 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:08,392 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-19 19:14:08,392 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-19 19:14:08,392 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2021-12-19 19:14:08,392 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-19 19:14:08,392 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-19 19:14:08,393 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:08,407 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:08,409 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:08,415 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:08,456 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-19 19:14:08,456 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-19 19:14:08,456 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:08,457 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:08,472 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:08,473 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2021-12-19 19:14:08,474 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:08,479 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:08,479 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:08,479 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:08,479 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:08,479 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:08,481 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:08,481 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:08,495 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-19 19:14:08,511 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:08,512 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:08,512 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:08,515 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:08,556 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:08,556 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2021-12-19 19:14:08,561 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:08,561 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:08,562 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:08,562 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:08,562 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:08,562 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:08,562 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:08,587 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-19 19:14:08,602 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:08,602 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:08,602 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:08,603 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:08,604 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2021-12-19 19:14:08,606 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:08,612 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:08,612 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:08,612 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:08,612 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:08,612 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:08,636 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:08,637 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:08,639 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-19 19:14:08,663 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-19 19:14:08,663 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-19 19:14:08,663 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:08,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:08,691 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:08,694 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-19 19:14:08,694 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-19 19:14:08,694 INFO L513 LassoAnalysis]: Proved termination. [2021-12-19 19:14:08,695 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2021-12-19 19:14:08,708 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2021-12-19 19:14:08,710 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:08,710 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-19 19:14:08,719 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:08,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:08,734 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-19 19:14:08,735 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:08,862 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:08,862 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2021-12-19 19:14:08,863 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:08,943 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 19:14:08,944 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 [2021-12-19 19:14:08,944 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) [2021-12-19 19:14:09,069 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. [2021-12-19 19:14:09,069 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 [2021-12-19 19:14:09,070 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) [2021-12-19 19:14:09,070 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 37 transitions. [2021-12-19 19:14:09,070 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 10 letters. [2021-12-19 19:14:09,070 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:09,071 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 22 letters. Loop has 10 letters. [2021-12-19 19:14:09,071 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:09,071 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 20 letters. [2021-12-19 19:14:09,071 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:09,071 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2021-12-19 19:14:09,075 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2021-12-19 19:14:09,077 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 108 states and 152 transitions. [2021-12-19 19:14:09,077 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 64 [2021-12-19 19:14:09,078 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 69 [2021-12-19 19:14:09,078 INFO L73 IsDeterministic]: Start isDeterministic. Operand 108 states and 152 transitions. [2021-12-19 19:14:09,078 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-19 19:14:09,078 INFO L681 BuchiCegarLoop]: Abstraction has 108 states and 152 transitions. [2021-12-19 19:14:09,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states and 152 transitions. [2021-12-19 19:14:09,095 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 94. [2021-12-19 19:14:09,096 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) [2021-12-19 19:14:09,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 126 transitions. [2021-12-19 19:14:09,097 INFO L704 BuchiCegarLoop]: Abstraction has 94 states and 126 transitions. [2021-12-19 19:14:09,097 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 19:14:09,097 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-12-19 19:14:09,097 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2021-12-19 19:14:09,097 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) [2021-12-19 19:14:09,200 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 19:14:09,200 INFO L93 Difference]: Finished difference Result 123 states and 165 transitions. [2021-12-19 19:14:09,201 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-19 19:14:09,201 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 123 states and 165 transitions. [2021-12-19 19:14:09,204 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2021-12-19 19:14:09,205 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 123 states to 118 states and 160 transitions. [2021-12-19 19:14:09,205 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 77 [2021-12-19 19:14:09,206 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 77 [2021-12-19 19:14:09,206 INFO L73 IsDeterministic]: Start isDeterministic. Operand 118 states and 160 transitions. [2021-12-19 19:14:09,206 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-19 19:14:09,206 INFO L681 BuchiCegarLoop]: Abstraction has 118 states and 160 transitions. [2021-12-19 19:14:09,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states and 160 transitions. [2021-12-19 19:14:09,211 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 106. [2021-12-19 19:14:09,212 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) [2021-12-19 19:14:09,220 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 141 transitions. [2021-12-19 19:14:09,220 INFO L704 BuchiCegarLoop]: Abstraction has 106 states and 141 transitions. [2021-12-19 19:14:09,220 INFO L587 BuchiCegarLoop]: Abstraction has 106 states and 141 transitions. [2021-12-19 19:14:09,220 INFO L425 BuchiCegarLoop]: ======== Iteration 4============ [2021-12-19 19:14:09,220 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 141 transitions. [2021-12-19 19:14:09,221 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2021-12-19 19:14:09,221 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-19 19:14:09,221 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-19 19:14:09,222 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-19 19:14:09,222 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [6, 5, 5, 3, 3, 3, 3, 2, 2, 2, 1] [2021-12-19 19:14:09,223 INFO L791 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 [2021-12-19 19:14:09,223 INFO L793 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 [2021-12-19 19:14:09,223 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:09,223 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 1 times [2021-12-19 19:14:09,223 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:09,223 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [521446728] [2021-12-19 19:14:09,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:09,223 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:09,245 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:09,245 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-19 19:14:09,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:09,255 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-19 19:14:09,255 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:09,255 INFO L85 PathProgramCache]: Analyzing trace with hash 1616897917, now seen corresponding path program 1 times [2021-12-19 19:14:09,255 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:09,255 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [538370305] [2021-12-19 19:14:09,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:09,255 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:09,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,267 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-19 19:14:09,271 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,280 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-19 19:14:09,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,289 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-19 19:14:09,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,320 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-19 19:14:09,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,324 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-19 19:14:09,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,328 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 26 proven. 13 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-19 19:14:09,328 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 19:14:09,328 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [538370305] [2021-12-19 19:14:09,328 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [538370305] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-19 19:14:09,328 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1400509502] [2021-12-19 19:14:09,330 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:09,341 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 19:14:09,341 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:09,341 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:09,342 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-19 19:14:09,343 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2021-12-19 19:14:09,364 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,365 INFO L263 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-19 19:14:09,366 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:09,429 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 25 proven. 15 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-12-19 19:14:09,429 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-19 19:14:09,566 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 25 proven. 15 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-12-19 19:14:09,567 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1400509502] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-19 19:14:09,567 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-19 19:14:09,567 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2021-12-19 19:14:09,567 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2114974051] [2021-12-19 19:14:09,567 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-19 19:14:09,567 INFO L808 eck$LassoCheckResult]: loop already infeasible [2021-12-19 19:14:09,567 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 19:14:09,568 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-12-19 19:14:09,568 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2021-12-19 19:14:09,568 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) [2021-12-19 19:14:09,633 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 19:14:09,633 INFO L93 Difference]: Finished difference Result 60 states and 77 transitions. [2021-12-19 19:14:09,634 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-19 19:14:09,634 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 60 states and 77 transitions. [2021-12-19 19:14:09,635 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:09,636 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 60 states to 54 states and 70 transitions. [2021-12-19 19:14:09,636 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2021-12-19 19:14:09,636 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2021-12-19 19:14:09,636 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2021-12-19 19:14:09,636 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-19 19:14:09,636 INFO L681 BuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2021-12-19 19:14:09,636 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2021-12-19 19:14:09,638 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2021-12-19 19:14:09,639 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) [2021-12-19 19:14:09,639 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2021-12-19 19:14:09,639 INFO L704 BuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2021-12-19 19:14:09,639 INFO L587 BuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2021-12-19 19:14:09,639 INFO L425 BuchiCegarLoop]: ======== Iteration 5============ [2021-12-19 19:14:09,639 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2021-12-19 19:14:09,640 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:09,640 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-19 19:14:09,640 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-19 19:14:09,641 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-19 19:14:09,641 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 1] [2021-12-19 19:14:09,641 INFO L791 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 [2021-12-19 19:14:09,641 INFO L793 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 [2021-12-19 19:14:09,641 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:09,641 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 2 times [2021-12-19 19:14:09,641 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:09,641 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [288152760] [2021-12-19 19:14:09,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:09,641 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:09,648 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:09,648 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-19 19:14:09,653 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:09,660 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-19 19:14:09,662 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:09,662 INFO L85 PathProgramCache]: Analyzing trace with hash -176759904, now seen corresponding path program 2 times [2021-12-19 19:14:09,662 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:09,663 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [934732158] [2021-12-19 19:14:09,663 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:09,663 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:09,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,681 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-19 19:14:09,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,701 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-19 19:14:09,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,732 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-19 19:14:09,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,744 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-19 19:14:09,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,749 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2021-12-19 19:14:09,751 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:09,762 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 29 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-19 19:14:09,762 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 19:14:09,762 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [934732158] [2021-12-19 19:14:09,762 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [934732158] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-19 19:14:09,763 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2031956536] [2021-12-19 19:14:09,763 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-19 19:14:09,763 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 19:14:09,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:09,771 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) [2021-12-19 19:14:09,772 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2021-12-19 19:14:09,795 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-19 19:14:09,795 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-19 19:14:09,796 INFO L263 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 8 conjunts are in the unsatisfiable core [2021-12-19 19:14:09,796 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:09,874 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 12 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2021-12-19 19:14:09,874 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-19 19:14:10,093 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 13 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2021-12-19 19:14:10,094 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2031956536] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-19 19:14:10,094 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-19 19:14:10,094 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 14 [2021-12-19 19:14:10,094 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [317163150] [2021-12-19 19:14:10,094 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-19 19:14:10,095 INFO L808 eck$LassoCheckResult]: loop already infeasible [2021-12-19 19:14:10,095 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 19:14:10,095 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-19 19:14:10,095 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2021-12-19 19:14:10,096 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) [2021-12-19 19:14:10,146 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 19:14:10,146 INFO L93 Difference]: Finished difference Result 54 states and 67 transitions. [2021-12-19 19:14:10,146 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-19 19:14:10,147 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 54 states and 67 transitions. [2021-12-19 19:14:10,148 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:10,149 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 54 states to 54 states and 67 transitions. [2021-12-19 19:14:10,149 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2021-12-19 19:14:10,149 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2021-12-19 19:14:10,150 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 67 transitions. [2021-12-19 19:14:10,150 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-19 19:14:10,150 INFO L681 BuchiCegarLoop]: Abstraction has 54 states and 67 transitions. [2021-12-19 19:14:10,150 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 67 transitions. [2021-12-19 19:14:10,152 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2021-12-19 19:14:10,152 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) [2021-12-19 19:14:10,152 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 67 transitions. [2021-12-19 19:14:10,153 INFO L704 BuchiCegarLoop]: Abstraction has 54 states and 67 transitions. [2021-12-19 19:14:10,153 INFO L587 BuchiCegarLoop]: Abstraction has 54 states and 67 transitions. [2021-12-19 19:14:10,153 INFO L425 BuchiCegarLoop]: ======== Iteration 6============ [2021-12-19 19:14:10,153 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 67 transitions. [2021-12-19 19:14:10,153 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-19 19:14:10,153 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-19 19:14:10,154 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-19 19:14:10,154 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-19 19:14:10,154 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2021-12-19 19:14:10,155 INFO L791 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 [2021-12-19 19:14:10,155 INFO L793 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 [2021-12-19 19:14:10,155 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:10,155 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 3 times [2021-12-19 19:14:10,155 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:10,155 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [657076163] [2021-12-19 19:14:10,155 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:10,156 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:10,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:10,161 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-19 19:14:10,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:10,166 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-19 19:14:10,166 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:10,167 INFO L85 PathProgramCache]: Analyzing trace with hash 780094678, now seen corresponding path program 3 times [2021-12-19 19:14:10,167 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:10,167 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1115285910] [2021-12-19 19:14:10,167 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:10,167 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:10,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:10,170 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-19 19:14:10,172 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:10,173 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-19 19:14:10,174 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:10,174 INFO L85 PathProgramCache]: Analyzing trace with hash 1975410011, now seen corresponding path program 4 times [2021-12-19 19:14:10,174 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:10,174 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [643100869] [2021-12-19 19:14:10,174 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:10,174 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:10,180 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:10,231 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2021-12-19 19:14:10,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:10,237 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-19 19:14:10,237 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:10,239 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-19 19:14:10,240 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:10,241 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2021-12-19 19:14:10,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:10,245 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-19 19:14:10,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:10,248 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-19 19:14:10,248 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:10,250 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 34 proven. 64 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2021-12-19 19:14:10,250 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 19:14:10,250 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [643100869] [2021-12-19 19:14:10,250 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [643100869] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-19 19:14:10,250 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1479753632] [2021-12-19 19:14:10,250 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-19 19:14:10,251 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 19:14:10,251 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:10,263 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) [2021-12-19 19:14:10,302 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2021-12-19 19:14:10,304 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-19 19:14:10,305 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-19 19:14:10,305 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-19 19:14:10,306 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:10,391 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 52 proven. 67 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-12-19 19:14:10,391 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-19 19:14:10,503 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 52 proven. 67 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-12-19 19:14:10,503 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1479753632] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-19 19:14:10,503 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-19 19:14:10,503 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12] total 15 [2021-12-19 19:14:10,504 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1687810445] [2021-12-19 19:14:10,504 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-19 19:14:10,659 INFO L210 LassoAnalysis]: Preferences: [2021-12-19 19:14:10,659 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-19 19:14:10,659 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-19 19:14:10,659 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-19 19:14:10,660 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-19 19:14:10,660 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:10,660 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-19 19:14:10,660 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-19 19:14:10,660 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration6_Loop [2021-12-19 19:14:10,660 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-19 19:14:10,660 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-19 19:14:10,661 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:10,663 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:10,664 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:10,666 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:10,694 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-19 19:14:10,695 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-19 19:14:10,695 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:10,695 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:10,702 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:10,703 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2021-12-19 19:14:10,704 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:10,704 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:10,710 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-19 19:14:10,710 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-19 19:14:10,725 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Ended with exit code 0 [2021-12-19 19:14:10,725 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:10,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:10,726 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:10,727 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2021-12-19 19:14:10,729 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:10,729 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:10,749 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-19 19:14:10,750 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-19 19:14:10,764 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:10,765 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:10,765 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:10,765 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:10,766 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2021-12-19 19:14:10,768 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:10,768 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:10,795 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-19 19:14:10,795 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=1} Honda state: {fibo_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-19 19:14:10,810 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:10,811 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:10,811 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:10,812 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:10,813 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2021-12-19 19:14:10,814 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:10,814 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:10,856 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 [2021-12-19 19:14:10,857 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:10,857 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:10,864 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:10,864 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2021-12-19 19:14:10,865 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-19 19:14:10,865 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:11,517 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-19 19:14:11,520 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:11,521 INFO L210 LassoAnalysis]: Preferences: [2021-12-19 19:14:11,521 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-19 19:14:11,521 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-19 19:14:11,521 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-19 19:14:11,521 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-19 19:14:11,521 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:11,521 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-19 19:14:11,521 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-19 19:14:11,521 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration6_Loop [2021-12-19 19:14:11,521 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-19 19:14:11,521 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-19 19:14:11,521 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:11,523 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:11,529 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:11,530 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:11,557 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-19 19:14:11,557 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-19 19:14:11,558 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:11,558 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:11,571 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:11,572 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2021-12-19 19:14:11,588 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:11,593 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:11,593 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:11,594 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:11,594 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:11,594 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:11,594 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:11,594 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:11,605 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-19 19:14:11,620 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2021-12-19 19:14:11,621 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:11,621 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:11,621 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:11,625 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2021-12-19 19:14:11,626 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:11,631 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:11,631 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:11,631 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:11,631 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:11,631 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:11,632 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:11,632 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:11,633 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-19 19:14:11,647 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:11,648 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:11,648 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:11,649 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) [2021-12-19 19:14:11,653 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 [2021-12-19 19:14:11,654 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:11,659 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:11,659 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:11,659 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:11,659 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:11,659 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:11,660 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:11,660 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:11,661 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-19 19:14:11,675 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Ended with exit code 0 [2021-12-19 19:14:11,676 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:11,676 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:11,676 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:11,677 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2021-12-19 19:14:11,679 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:11,683 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:11,684 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:11,684 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:11,684 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:11,684 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:11,685 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:11,685 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:11,700 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-19 19:14:11,702 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2021-12-19 19:14:11,702 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2021-12-19 19:14:11,702 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:11,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:11,703 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:11,704 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2021-12-19 19:14:11,705 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-19 19:14:11,705 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-19 19:14:11,705 INFO L513 LassoAnalysis]: Proved termination. [2021-12-19 19:14:11,705 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2021-12-19 19:14:11,722 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:11,722 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-19 19:14:11,734 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:11,767 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:11,768 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-19 19:14:11,769 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:11,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:11,985 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-19 19:14:11,986 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:12,041 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:12,109 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-19 19:14:12,109 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2021-12-19 19:14:12,109 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) [2021-12-19 19:14:12,173 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. [2021-12-19 19:14:12,174 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2021-12-19 19:14:12,174 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) [2021-12-19 19:14:12,174 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2021-12-19 19:14:12,174 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2021-12-19 19:14:12,175 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:12,175 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-19 19:14:12,182 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:12,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:12,213 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-19 19:14:12,214 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:12,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:12,404 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-19 19:14:12,405 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:12,495 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-19 19:14:12,496 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2021-12-19 19:14:12,496 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) [2021-12-19 19:14:12,552 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. [2021-12-19 19:14:12,554 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2021-12-19 19:14:12,554 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) [2021-12-19 19:14:12,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2021-12-19 19:14:12,555 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2021-12-19 19:14:12,555 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:12,555 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-19 19:14:12,561 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:12,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:12,586 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-19 19:14:12,586 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:12,798 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:12,799 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-19 19:14:12,799 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:12,901 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-19 19:14:12,902 INFO L152 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2021-12-19 19:14:12,902 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) [2021-12-19 19:14:13,073 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. [2021-12-19 19:14:13,074 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2021-12-19 19:14:13,074 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) [2021-12-19 19:14:13,075 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 46 transitions. [2021-12-19 19:14:13,075 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 22 letters. [2021-12-19 19:14:13,075 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:13,075 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 54 letters. Loop has 22 letters. [2021-12-19 19:14:13,076 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:13,076 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 44 letters. [2021-12-19 19:14:13,077 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:13,077 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 321 states and 401 transitions. [2021-12-19 19:14:13,080 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-19 19:14:13,082 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 321 states to 203 states and 261 transitions. [2021-12-19 19:14:13,082 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2021-12-19 19:14:13,082 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 90 [2021-12-19 19:14:13,083 INFO L73 IsDeterministic]: Start isDeterministic. Operand 203 states and 261 transitions. [2021-12-19 19:14:13,083 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-19 19:14:13,083 INFO L681 BuchiCegarLoop]: Abstraction has 203 states and 261 transitions. [2021-12-19 19:14:13,083 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states and 261 transitions. [2021-12-19 19:14:13,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 175. [2021-12-19 19:14:13,089 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) [2021-12-19 19:14:13,090 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 212 transitions. [2021-12-19 19:14:13,090 INFO L704 BuchiCegarLoop]: Abstraction has 175 states and 212 transitions. [2021-12-19 19:14:13,090 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 19:14:13,091 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-12-19 19:14:13,091 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2021-12-19 19:14:13,091 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) [2021-12-19 19:14:13,247 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 19:14:13,248 INFO L93 Difference]: Finished difference Result 124 states and 140 transitions. [2021-12-19 19:14:13,249 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2021-12-19 19:14:13,249 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 124 states and 140 transitions. [2021-12-19 19:14:13,250 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2021-12-19 19:14:13,251 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 124 states to 105 states and 117 transitions. [2021-12-19 19:14:13,251 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2021-12-19 19:14:13,251 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 64 [2021-12-19 19:14:13,251 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 117 transitions. [2021-12-19 19:14:13,251 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-19 19:14:13,251 INFO L681 BuchiCegarLoop]: Abstraction has 105 states and 117 transitions. [2021-12-19 19:14:13,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 117 transitions. [2021-12-19 19:14:13,253 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 96. [2021-12-19 19:14:13,254 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) [2021-12-19 19:14:13,254 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 108 transitions. [2021-12-19 19:14:13,254 INFO L704 BuchiCegarLoop]: Abstraction has 96 states and 108 transitions. [2021-12-19 19:14:13,254 INFO L587 BuchiCegarLoop]: Abstraction has 96 states and 108 transitions. [2021-12-19 19:14:13,254 INFO L425 BuchiCegarLoop]: ======== Iteration 7============ [2021-12-19 19:14:13,254 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 96 states and 108 transitions. [2021-12-19 19:14:13,255 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2021-12-19 19:14:13,255 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-19 19:14:13,255 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-19 19:14:13,255 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [7, 6, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2021-12-19 19:14:13,255 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-19 19:14:13,255 INFO L791 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 [2021-12-19 19:14:13,255 INFO L793 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 [2021-12-19 19:14:13,256 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:13,256 INFO L85 PathProgramCache]: Analyzing trace with hash 2096320921, now seen corresponding path program 5 times [2021-12-19 19:14:13,256 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:13,256 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1115791743] [2021-12-19 19:14:13,256 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:13,256 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:13,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:13,281 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2021-12-19 19:14:13,282 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:13,301 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-19 19:14:13,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:13,311 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-19 19:14:13,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:13,315 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 34 proven. 28 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-19 19:14:13,315 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-19 19:14:13,315 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1115791743] [2021-12-19 19:14:13,315 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1115791743] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-19 19:14:13,315 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1205110340] [2021-12-19 19:14:13,315 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-19 19:14:13,316 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-19 19:14:13,316 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:13,331 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-19 19:14:13,377 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (33)] Waiting until timeout for monitored process [2021-12-19 19:14:13,396 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2021-12-19 19:14:13,396 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-19 19:14:13,396 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-19 19:14:13,397 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:13,482 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 44 proven. 8 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2021-12-19 19:14:13,482 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-19 19:14:13,607 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 44 proven. 9 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2021-12-19 19:14:13,607 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1205110340] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-19 19:14:13,607 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-19 19:14:13,607 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 10] total 18 [2021-12-19 19:14:13,607 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [125872692] [2021-12-19 19:14:13,608 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-19 19:14:13,608 INFO L796 eck$LassoCheckResult]: stem already infeasible [2021-12-19 19:14:13,608 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:13,608 INFO L85 PathProgramCache]: Analyzing trace with hash 1893846, now seen corresponding path program 2 times [2021-12-19 19:14:13,608 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-19 19:14:13,608 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [189495280] [2021-12-19 19:14:13,608 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-19 19:14:13,608 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-19 19:14:13,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:13,610 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-19 19:14:13,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-19 19:14:13,611 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-19 19:14:13,641 INFO L210 LassoAnalysis]: Preferences: [2021-12-19 19:14:13,641 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-19 19:14:13,641 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-19 19:14:13,641 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-19 19:14:13,641 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-19 19:14:13,641 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:13,641 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-19 19:14:13,641 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-19 19:14:13,642 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration7_Loop [2021-12-19 19:14:13,642 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-19 19:14:13,642 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-19 19:14:13,642 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:13,643 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:13,644 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:13,649 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:13,672 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-19 19:14:13,672 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-19 19:14:13,672 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:13,672 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:13,673 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:13,673 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2021-12-19 19:14:13,675 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:13,675 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:13,681 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-19 19:14:13,681 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-19 19:14:13,696 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2021-12-19 19:14:13,697 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:13,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:13,697 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:13,698 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2021-12-19 19:14:13,699 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:13,699 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:13,720 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-19 19:14:13,720 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-19 19:14:13,735 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:13,735 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:13,735 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:13,737 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:13,738 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2021-12-19 19:14:13,739 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-19 19:14:13,739 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:13,764 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Ended with exit code 0 [2021-12-19 19:14:13,764 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:13,764 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:13,767 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:13,769 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2021-12-19 19:14:13,769 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-19 19:14:13,769 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-19 19:14:16,303 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-19 19:14:16,307 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:16,307 INFO L210 LassoAnalysis]: Preferences: [2021-12-19 19:14:16,307 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-19 19:14:16,307 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-19 19:14:16,307 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-19 19:14:16,307 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-19 19:14:16,307 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:16,307 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-19 19:14:16,307 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-19 19:14:16,307 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration7_Loop [2021-12-19 19:14:16,308 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-19 19:14:16,308 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-19 19:14:16,308 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:16,309 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:16,315 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:16,316 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-19 19:14:16,341 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-19 19:14:16,341 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-19 19:14:16,341 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:16,341 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:16,342 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:16,343 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2021-12-19 19:14:16,344 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:16,349 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:16,349 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:16,349 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:16,349 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:16,349 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:16,350 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:16,350 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:16,375 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-19 19:14:16,395 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:16,396 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:16,396 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:16,410 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:16,411 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2021-12-19 19:14:16,412 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2021-12-19 19:14:16,418 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-19 19:14:16,418 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-19 19:14:16,418 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-19 19:14:16,418 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-19 19:14:16,418 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-19 19:14:16,419 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-19 19:14:16,419 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-19 19:14:16,430 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-19 19:14:16,431 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2021-12-19 19:14:16,431 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2021-12-19 19:14:16,431 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-19 19:14:16,431 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-19 19:14:16,432 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2021-12-19 19:14:16,434 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2021-12-19 19:14:16,435 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-19 19:14:16,435 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-19 19:14:16,435 INFO L513 LassoAnalysis]: Proved termination. [2021-12-19 19:14:16,435 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2021-12-19 19:14:16,449 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:16,450 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-19 19:14:16,457 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:16,504 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:16,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:16,511 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-19 19:14:16,512 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:16,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:16,745 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-19 19:14:16,745 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:16,772 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 19:14:16,773 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 [2021-12-19 19:14:16,773 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) [2021-12-19 19:14:16,827 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. [2021-12-19 19:14:16,827 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2021-12-19 19:14:16,828 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) [2021-12-19 19:14:16,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2021-12-19 19:14:16,828 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 36 letters. Loop has 4 letters. [2021-12-19 19:14:16,828 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:16,828 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-19 19:14:16,834 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:16,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:16,864 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-19 19:14:16,865 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:17,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:17,077 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-19 19:14:17,077 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:17,102 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 19:14:17,102 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 [2021-12-19 19:14:17,102 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) [2021-12-19 19:14:17,166 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. [2021-12-19 19:14:17,166 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 [2021-12-19 19:14:17,167 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) [2021-12-19 19:14:17,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 16 transitions. [2021-12-19 19:14:17,167 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 16 transitions. Stem has 36 letters. Loop has 4 letters. [2021-12-19 19:14:17,167 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:17,167 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-19 19:14:17,184 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-19 19:14:17,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:17,215 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-19 19:14:17,216 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:17,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-19 19:14:17,415 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-19 19:14:17,415 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-19 19:14:17,452 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-19 19:14:17,452 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 [2021-12-19 19:14:17,453 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) [2021-12-19 19:14:17,501 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. [2021-12-19 19:14:17,502 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2021-12-19 19:14:17,503 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) [2021-12-19 19:14:17,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 22 transitions. [2021-12-19 19:14:17,503 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 4 letters. [2021-12-19 19:14:17,503 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:17,504 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 40 letters. Loop has 4 letters. [2021-12-19 19:14:17,504 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:17,504 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 8 letters. [2021-12-19 19:14:17,504 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-19 19:14:17,504 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 131 states and 150 transitions. [2021-12-19 19:14:17,505 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-19 19:14:17,505 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 131 states to 0 states and 0 transitions. [2021-12-19 19:14:17,505 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2021-12-19 19:14:17,506 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2021-12-19 19:14:17,506 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2021-12-19 19:14:17,506 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2021-12-19 19:14:17,506 INFO L681 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-19 19:14:17,506 INFO L704 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-19 19:14:17,506 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-19 19:14:17,506 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-12-19 19:14:17,506 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=245, Unknown=0, NotChecked=0, Total=306 [2021-12-19 19:14:17,507 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) [2021-12-19 19:14:17,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-19 19:14:17,507 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2021-12-19 19:14:17,507 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-19 19:14:17,507 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2021-12-19 19:14:17,507 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-19 19:14:17,507 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2021-12-19 19:14:17,507 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2021-12-19 19:14:17,507 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2021-12-19 19:14:17,507 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2021-12-19 19:14:17,508 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2021-12-19 19:14:17,508 INFO L681 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-19 19:14:17,508 INFO L704 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-19 19:14:17,508 INFO L587 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-19 19:14:17,508 INFO L425 BuchiCegarLoop]: ======== Iteration 8============ [2021-12-19 19:14:17,508 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2021-12-19 19:14:17,508 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-19 19:14:17,508 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2021-12-19 19:14:17,513 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 19.12 07:14:17 BoogieIcfgContainer [2021-12-19 19:14:17,513 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2021-12-19 19:14:17,513 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2021-12-19 19:14:17,513 INFO L271 PluginConnector]: Initializing Witness Printer... [2021-12-19 19:14:17,513 INFO L275 PluginConnector]: Witness Printer initialized [2021-12-19 19:14:17,514 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.12 07:14:05" (3/4) ... [2021-12-19 19:14:17,515 INFO L140 WitnessPrinter]: No result that supports witness generation found [2021-12-19 19:14:17,515 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2021-12-19 19:14:17,516 INFO L158 Benchmark]: Toolchain (without parser) took 12102.93ms. Allocated memory was 115.3MB in the beginning and 195.0MB in the end (delta: 79.7MB). Free memory was 93.4MB in the beginning and 158.7MB in the end (delta: -65.4MB). Peak memory consumption was 14.8MB. Max. memory is 16.1GB. [2021-12-19 19:14:17,516 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 90.2MB. Free memory is still 52.1MB. There was no memory consumed. Max. memory is 16.1GB. [2021-12-19 19:14:17,516 INFO L158 Benchmark]: CACSL2BoogieTranslator took 205.01ms. Allocated memory is still 115.3MB. Free memory was 92.9MB in the beginning and 91.5MB in the end (delta: 1.5MB). Peak memory consumption was 10.8MB. Max. memory is 16.1GB. [2021-12-19 19:14:17,516 INFO L158 Benchmark]: Boogie Procedure Inliner took 19.60ms. Allocated memory is still 115.3MB. Free memory was 91.5MB in the beginning and 89.8MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2021-12-19 19:14:17,516 INFO L158 Benchmark]: Boogie Preprocessor took 10.14ms. Allocated memory is still 115.3MB. Free memory was 89.8MB in the beginning and 88.8MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-19 19:14:17,517 INFO L158 Benchmark]: RCFGBuilder took 198.23ms. Allocated memory is still 115.3MB. Free memory was 88.8MB in the beginning and 80.4MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-12-19 19:14:17,517 INFO L158 Benchmark]: BuchiAutomizer took 11663.92ms. Allocated memory was 115.3MB in the beginning and 195.0MB in the end (delta: 79.7MB). Free memory was 80.4MB in the beginning and 159.8MB in the end (delta: -79.4MB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-19 19:14:17,517 INFO L158 Benchmark]: Witness Printer took 2.29ms. Allocated memory is still 195.0MB. Free memory is still 158.7MB. There was no memory consumed. Max. memory is 16.1GB. [2021-12-19 19:14:17,518 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.13ms. Allocated memory is still 90.2MB. Free memory is still 52.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 205.01ms. Allocated memory is still 115.3MB. Free memory was 92.9MB in the beginning and 91.5MB in the end (delta: 1.5MB). Peak memory consumption was 10.8MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 19.60ms. Allocated memory is still 115.3MB. Free memory was 91.5MB in the beginning and 89.8MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 10.14ms. Allocated memory is still 115.3MB. Free memory was 89.8MB in the beginning and 88.8MB in the end (delta: 1.0MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 198.23ms. Allocated memory is still 115.3MB. Free memory was 88.8MB in the beginning and 80.4MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 11663.92ms. Allocated memory was 115.3MB in the beginning and 195.0MB in the end (delta: 79.7MB). Free memory was 80.4MB in the beginning and 159.8MB in the end (delta: -79.4MB). There was no memory consumed. Max. memory is 16.1GB. * Witness Printer took 2.29ms. Allocated memory is still 195.0MB. Free memory is still 158.7MB. 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.6s and 8 iterations. TraceHistogramMax:7. Analysis of lassos took 8.0s. Construction of modules took 0.4s. Büchi inclusion checks took 3.0s. 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 106 states and ocurred in iteration 3. Nontrivial modules had stage [2, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 374 SdHoareTripleChecker+Valid, 0.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 358 mSDsluCounter, 381 SdHoareTripleChecker+Invalid, 0.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 220 mSDsCounter, 203 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 709 IncrementalHoareTripleChecker+Invalid, 912 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 203 mSolverCounterUnsat, 161 mSDtfsCounter, 709 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI2 SFLT1 conc0 concLT1 SILN0 SILU0 SILI1 SILT2 lasso0 LassoPreprocessingBenchmarks: Lassos: inital16 mio100 ax100 hnf96 lsp90 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq192 hnf91 smp86 dnf100 smp100 tf109 neg97 sie105 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 24ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 4.3s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2021-12-19 19:14:17,557 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (33)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:17,755 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:17,957 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2021-12-19 19:14:18,157 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:18,358 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2021-12-19 19:14:18,559 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE