./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-16 10:03:08,026 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-16 10:03:08,028 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-16 10:03:08,093 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-16 10:03:08,094 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-16 10:03:08,097 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-16 10:03:08,099 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-16 10:03:08,103 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-16 10:03:08,105 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-16 10:03:08,110 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-16 10:03:08,110 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-16 10:03:08,112 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-16 10:03:08,112 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-16 10:03:08,114 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-16 10:03:08,115 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-16 10:03:08,119 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-16 10:03:08,120 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-16 10:03:08,120 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-16 10:03:08,124 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-16 10:03:08,128 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-16 10:03:08,129 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-16 10:03:08,130 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-16 10:03:08,131 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-16 10:03:08,132 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-16 10:03:08,137 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-16 10:03:08,138 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-16 10:03:08,138 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-16 10:03:08,139 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-16 10:03:08,140 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-16 10:03:08,140 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-16 10:03:08,141 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-16 10:03:08,141 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-16 10:03:08,142 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-16 10:03:08,143 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-16 10:03:08,144 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-16 10:03:08,144 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-16 10:03:08,145 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-16 10:03:08,145 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-16 10:03:08,145 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-16 10:03:08,146 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-16 10:03:08,146 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-16 10:03:08,147 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2021-12-16 10:03:08,171 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-16 10:03:08,171 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-16 10:03:08,171 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-16 10:03:08,172 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-16 10:03:08,173 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-16 10:03:08,173 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-16 10:03:08,173 INFO L138 SettingsManager]: * Use SBE=true [2021-12-16 10:03:08,173 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2021-12-16 10:03:08,173 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2021-12-16 10:03:08,174 INFO L138 SettingsManager]: * Use old map elimination=false [2021-12-16 10:03:08,174 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2021-12-16 10:03:08,175 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2021-12-16 10:03:08,175 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2021-12-16 10:03:08,175 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-16 10:03:08,175 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-16 10:03:08,175 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2021-12-16 10:03:08,175 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-16 10:03:08,176 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-16 10:03:08,176 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-16 10:03:08,176 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2021-12-16 10:03:08,176 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2021-12-16 10:03:08,176 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2021-12-16 10:03:08,176 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-16 10:03:08,177 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-16 10:03:08,178 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2021-12-16 10:03:08,178 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-16 10:03:08,178 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2021-12-16 10:03:08,179 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-16 10:03:08,179 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-16 10:03:08,179 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-16 10:03:08,179 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-16 10:03:08,179 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-16 10:03:08,180 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2021-12-16 10:03:08,180 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-16 10:03:08,338 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-16 10:03:08,360 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-16 10:03:08,373 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-16 10:03:08,374 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-16 10:03:08,374 INFO L275 PluginConnector]: CDTParser initialized [2021-12-16 10:03:08,375 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-16 10:03:08,417 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/944d9989a/9dee8bbef5b94cb481bc294dbf004e81/FLAGb16ed1358 [2021-12-16 10:03:08,771 INFO L306 CDTParser]: Found 1 translation units. [2021-12-16 10:03:08,771 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-2.c [2021-12-16 10:03:08,775 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/944d9989a/9dee8bbef5b94cb481bc294dbf004e81/FLAGb16ed1358 [2021-12-16 10:03:08,783 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/944d9989a/9dee8bbef5b94cb481bc294dbf004e81 [2021-12-16 10:03:08,785 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-16 10:03:08,786 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-16 10:03:08,787 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-16 10:03:08,787 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-16 10:03:08,789 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-16 10:03:08,789 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,790 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@36eb3a38 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08, skipping insertion in model container [2021-12-16 10:03:08,790 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,804 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-16 10:03:08,812 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-16 10:03:08,920 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-16 10:03:08,922 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-16 10:03:08,928 INFO L203 MainTranslator]: Completed pre-run [2021-12-16 10:03:08,937 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-16 10:03:08,938 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-16 10:03:08,947 INFO L208 MainTranslator]: Completed translation [2021-12-16 10:03:08,948 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08 WrapperNode [2021-12-16 10:03:08,948 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-16 10:03:08,949 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-16 10:03:08,949 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-16 10:03:08,949 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-16 10:03:08,954 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,958 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,967 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2021-12-16 10:03:08,967 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-16 10:03:08,968 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-16 10:03:08,968 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-16 10:03:08,968 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-16 10:03:08,973 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,974 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,974 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,974 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,976 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,977 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,978 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,978 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-16 10:03:08,979 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-16 10:03:08,979 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-16 10:03:08,979 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-16 10:03:08,980 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (1/1) ... [2021-12-16 10:03:08,985 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:08,991 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:09,000 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-16 10:03:09,010 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-16 10:03:09,035 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-16 10:03:09,041 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-16 10:03:09,041 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-16 10:03:09,042 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-16 10:03:09,042 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2021-12-16 10:03:09,042 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2021-12-16 10:03:09,080 INFO L236 CfgBuilder]: Building ICFG [2021-12-16 10:03:09,081 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-16 10:03:09,141 INFO L277 CfgBuilder]: Performing block encoding [2021-12-16 10:03:09,145 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-16 10:03:09,146 INFO L301 CfgBuilder]: Removed 0 assume(true) statements. [2021-12-16 10:03:09,147 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.12 10:03:09 BoogieIcfgContainer [2021-12-16 10:03:09,147 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-16 10:03:09,148 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2021-12-16 10:03:09,148 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2021-12-16 10:03:09,150 INFO L275 PluginConnector]: BuchiAutomizer initialized [2021-12-16 10:03:09,151 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-16 10:03:09,151 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 16.12 10:03:08" (1/3) ... [2021-12-16 10:03:09,151 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1e2134bd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 16.12 10:03:09, skipping insertion in model container [2021-12-16 10:03:09,152 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-16 10:03:09,152 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 16.12 10:03:08" (2/3) ... [2021-12-16 10:03:09,152 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1e2134bd and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 16.12 10:03:09, skipping insertion in model container [2021-12-16 10:03:09,152 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2021-12-16 10:03:09,152 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.12 10:03:09" (3/3) ... [2021-12-16 10:03:09,153 INFO L388 chiAutomizerObserver]: Analyzing ICFG fibo_5-2.c [2021-12-16 10:03:09,181 INFO L359 BuchiCegarLoop]: Interprodecural is true [2021-12-16 10:03:09,181 INFO L360 BuchiCegarLoop]: Hoare is false [2021-12-16 10:03:09,181 INFO L361 BuchiCegarLoop]: Compute interpolants for ForwardPredicates [2021-12-16 10:03:09,181 INFO L362 BuchiCegarLoop]: Backedges is STRAIGHT_LINE [2021-12-16 10:03:09,181 INFO L363 BuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-12-16 10:03:09,181 INFO L364 BuchiCegarLoop]: Difference is false [2021-12-16 10:03:09,182 INFO L365 BuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-12-16 10:03:09,182 INFO L368 BuchiCegarLoop]: ======== Iteration 0==of CEGAR loop == BuchiCegarLoop======== [2021-12-16 10:03:09,191 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-16 10:03:09,204 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:09,204 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-16 10:03:09,204 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-16 10:03:09,208 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1] [2021-12-16 10:03:09,209 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-16 10:03:09,209 INFO L425 BuchiCegarLoop]: ======== Iteration 1============ [2021-12-16 10:03:09,209 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-16 10:03:09,210 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:09,210 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-16 10:03:09,211 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-16 10:03:09,211 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [1, 1, 1] [2021-12-16 10:03:09,211 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-16 10:03:09,215 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-16 10:03:09,216 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-16 10:03:09,219 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:09,220 INFO L85 PathProgramCache]: Analyzing trace with hash 29883, now seen corresponding path program 1 times [2021-12-16 10:03:09,225 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:09,226 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1694541403] [2021-12-16 10:03:09,226 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:09,227 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:09,280 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:09,280 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-16 10:03:09,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:09,317 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-16 10:03:09,323 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:09,323 INFO L85 PathProgramCache]: Analyzing trace with hash 1450956, now seen corresponding path program 1 times [2021-12-16 10:03:09,323 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:09,324 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [224034001] [2021-12-16 10:03:09,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:09,325 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:09,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:09,334 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-16 10:03:09,338 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:09,341 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-16 10:03:09,342 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:09,343 INFO L85 PathProgramCache]: Analyzing trace with hash 1828301702, now seen corresponding path program 1 times [2021-12-16 10:03:09,343 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:09,343 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1323125212] [2021-12-16 10:03:09,343 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:09,344 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:09,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:09,363 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-16 10:03:09,373 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:09,379 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-16 10:03:09,511 INFO L210 LassoAnalysis]: Preferences: [2021-12-16 10:03:09,512 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-16 10:03:09,512 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-16 10:03:09,512 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-16 10:03:09,512 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-16 10:03:09,512 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:09,512 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-16 10:03:09,512 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-16 10:03:09,512 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2021-12-16 10:03:09,513 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-16 10:03:09,513 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-16 10:03:09,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-16 10:03:09,544 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-16 10:03:09,546 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-16 10:03:09,548 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-16 10:03:09,555 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-16 10:03:09,596 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-16 10:03:09,597 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-16 10:03:09,598 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:09,599 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:09,621 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-16 10:03:09,640 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-16 10:03:09,641 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:09,641 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:09,664 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-16 10:03:09,664 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-16 10:03:09,682 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-16 10:03:09,683 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:09,683 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:09,684 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-16 10:03:09,686 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-16 10:03:09,687 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:09,687 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:09,709 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-16 10:03:09,709 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-16 10:03:09,727 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-16 10:03:09,727 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:09,728 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:09,729 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-16 10:03:09,731 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-16 10:03:09,732 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:09,732 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:09,754 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-16 10:03:09,754 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-16 10:03:09,771 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-16 10:03:09,772 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:09,772 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:09,773 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-16 10:03:09,775 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-16 10:03:09,776 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:09,776 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:09,814 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-16 10:03:09,815 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:09,815 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:09,816 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-16 10:03:09,825 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-16 10:03:09,827 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-16 10:03:09,827 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:09,881 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-16 10:03:09,900 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2021-12-16 10:03:09,900 INFO L210 LassoAnalysis]: Preferences: [2021-12-16 10:03:09,900 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-16 10:03:09,900 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-16 10:03:09,901 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-16 10:03:09,901 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-16 10:03:09,901 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:09,901 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-16 10:03:09,901 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-16 10:03:09,901 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration1_Loop [2021-12-16 10:03:09,901 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-16 10:03:09,901 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-16 10:03:09,902 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-16 10:03:09,906 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-16 10:03:09,909 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-16 10:03:09,911 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-16 10:03:09,917 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-16 10:03:09,962 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-16 10:03:09,965 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-16 10:03:09,966 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:09,966 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:09,967 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-16 10:03:09,987 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-16 10:03:09,988 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-16 10:03:09,994 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:09,995 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:09,995 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:09,995 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:09,995 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:09,996 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:09,997 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:10,004 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-16 10:03:10,018 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-16 10:03:10,019 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:10,019 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:10,020 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-16 10:03:10,022 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-16 10:03:10,026 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-16 10:03:10,028 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:10,037 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:10,037 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:10,037 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:10,037 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:10,038 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:10,038 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:10,047 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-16 10:03:10,062 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-16 10:03:10,066 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:10,066 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:10,067 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-16 10:03:10,068 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-16 10:03:10,070 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-16 10:03:10,075 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:10,076 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:10,076 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:10,076 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:10,076 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:10,076 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:10,077 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:10,081 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-16 10:03:10,096 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-16 10:03:10,097 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:10,097 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:10,098 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-16 10:03:10,099 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-16 10:03:10,100 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-16 10:03:10,106 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:10,106 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:10,106 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:10,106 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:10,106 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:10,107 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:10,112 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:10,128 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-16 10:03:10,131 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-16 10:03:10,131 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-16 10:03:10,132 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:10,132 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:10,148 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-16 10:03:10,149 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-16 10:03:10,171 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-16 10:03:10,172 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-16 10:03:10,172 INFO L513 LassoAnalysis]: Proved termination. [2021-12-16 10:03:10,172 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2021-12-16 10:03:10,187 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-16 10:03:10,189 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-16 10:03:10,202 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:10,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:10,216 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 4 conjunts are in the unsatisfiable core [2021-12-16 10:03:10,217 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:10,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:10,231 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-16 10:03:10,232 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:10,263 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-16 10:03:10,285 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-16 10:03:10,286 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-16 10:03:10,348 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-16 10:03:10,349 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-16 10:03:10,353 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-16 10:03:10,353 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 11 transitions. [2021-12-16 10:03:10,354 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 4 letters. [2021-12-16 10:03:10,355 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:10,355 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 7 letters. Loop has 4 letters. [2021-12-16 10:03:10,356 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:10,356 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 8 letters. [2021-12-16 10:03:10,356 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:10,357 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 48 states and 60 transitions. [2021-12-16 10:03:10,360 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:10,363 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 48 states to 25 states and 34 transitions. [2021-12-16 10:03:10,364 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2021-12-16 10:03:10,364 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 18 [2021-12-16 10:03:10,365 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 34 transitions. [2021-12-16 10:03:10,365 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-16 10:03:10,365 INFO L681 BuchiCegarLoop]: Abstraction has 25 states and 34 transitions. [2021-12-16 10:03:10,376 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 34 transitions. [2021-12-16 10:03:10,384 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 20. [2021-12-16 10:03:10,384 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-16 10:03:10,385 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2021-12-16 10:03:10,386 INFO L704 BuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2021-12-16 10:03:10,386 INFO L587 BuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2021-12-16 10:03:10,386 INFO L425 BuchiCegarLoop]: ======== Iteration 2============ [2021-12-16 10:03:10,386 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2021-12-16 10:03:10,387 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:10,387 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-16 10:03:10,387 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-16 10:03:10,388 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 10:03:10,388 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 10:03:10,388 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-16 10:03:10,389 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-16 10:03:10,389 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:10,389 INFO L85 PathProgramCache]: Analyzing trace with hash -1181449843, now seen corresponding path program 1 times [2021-12-16 10:03:10,389 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:10,390 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1028920052] [2021-12-16 10:03:10,390 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:10,390 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:10,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:10,422 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-16 10:03:10,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:10,443 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-16 10:03:10,443 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 10:03:10,443 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1028920052] [2021-12-16 10:03:10,444 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1028920052] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 10:03:10,444 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 10:03:10,444 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-16 10:03:10,444 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1352210541] [2021-12-16 10:03:10,445 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 10:03:10,446 INFO L796 eck$LassoCheckResult]: stem already infeasible [2021-12-16 10:03:10,446 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:10,447 INFO L85 PathProgramCache]: Analyzing trace with hash 246097683, now seen corresponding path program 1 times [2021-12-16 10:03:10,447 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:10,447 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1338413334] [2021-12-16 10:03:10,447 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:10,447 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:10,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:10,463 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-16 10:03:10,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:10,477 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-16 10:03:10,477 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 10:03:10,478 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1338413334] [2021-12-16 10:03:10,478 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1338413334] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-16 10:03:10,478 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-16 10:03:10,478 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-16 10:03:10,478 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1623776888] [2021-12-16 10:03:10,478 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-16 10:03:10,479 INFO L808 eck$LassoCheckResult]: loop already infeasible [2021-12-16 10:03:10,479 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 10:03:10,480 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-16 10:03:10,481 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2021-12-16 10:03:10,482 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-16 10:03:10,515 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-16 10:03:10,577 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 10:03:10,577 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2021-12-16 10:03:10,577 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-16 10:03:10,578 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2021-12-16 10:03:10,580 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:10,583 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2021-12-16 10:03:10,585 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2021-12-16 10:03:10,585 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2021-12-16 10:03:10,585 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2021-12-16 10:03:10,585 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-16 10:03:10,585 INFO L681 BuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2021-12-16 10:03:10,585 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2021-12-16 10:03:10,587 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2021-12-16 10:03:10,588 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-16 10:03:10,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2021-12-16 10:03:10,590 INFO L704 BuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2021-12-16 10:03:10,590 INFO L587 BuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2021-12-16 10:03:10,590 INFO L425 BuchiCegarLoop]: ======== Iteration 3============ [2021-12-16 10:03:10,590 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2021-12-16 10:03:10,591 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:10,592 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-16 10:03:10,592 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-16 10:03:10,593 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 10:03:10,593 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2021-12-16 10:03:10,593 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-16 10:03:10,593 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-16 10:03:10,594 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:10,594 INFO L85 PathProgramCache]: Analyzing trace with hash 2029785426, now seen corresponding path program 1 times [2021-12-16 10:03:10,594 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:10,594 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1934860359] [2021-12-16 10:03:10,595 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:10,595 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:10,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:10,630 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-16 10:03:10,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:10,651 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-16 10:03:10,652 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 10:03:10,652 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1934860359] [2021-12-16 10:03:10,652 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1934860359] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-16 10:03:10,653 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [785939266] [2021-12-16 10:03:10,653 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:10,653 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 10:03:10,653 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:10,668 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-16 10:03:10,691 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-16 10:03:10,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:10,717 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-16 10:03:10,718 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:10,764 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-16 10:03:10,765 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 10:03:10,832 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-16 10:03:10,833 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [785939266] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 10:03:10,833 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-16 10:03:10,833 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2021-12-16 10:03:10,833 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1291588018] [2021-12-16 10:03:10,833 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-16 10:03:10,834 INFO L796 eck$LassoCheckResult]: stem already infeasible [2021-12-16 10:03:10,834 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:10,834 INFO L85 PathProgramCache]: Analyzing trace with hash -960881524, now seen corresponding path program 1 times [2021-12-16 10:03:10,834 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:10,834 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1891050073] [2021-12-16 10:03:10,834 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:10,835 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:10,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:10,838 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-16 10:03:10,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:10,842 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-16 10:03:10,964 INFO L210 LassoAnalysis]: Preferences: [2021-12-16 10:03:10,964 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-16 10:03:10,964 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-16 10:03:10,964 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-16 10:03:10,965 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-16 10:03:10,965 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:10,965 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-16 10:03:10,965 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-16 10:03:10,967 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2021-12-16 10:03:10,968 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-16 10:03:10,968 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-16 10:03:10,968 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-16 10:03:10,970 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-16 10:03:10,975 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-16 10:03:10,977 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-16 10:03:11,002 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-16 10:03:11,002 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-16 10:03:11,002 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:11,002 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:11,003 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-16 10:03:11,004 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-16 10:03:11,005 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:11,006 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:11,023 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-16 10:03:11,024 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-16 10:03:11,038 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2021-12-16 10:03:11,039 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:11,039 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:11,040 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-16 10:03:11,041 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-16 10:03:11,042 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:11,042 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:11,064 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2021-12-16 10:03:11,065 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:11,065 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:11,065 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-16 10:03:11,067 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-16 10:03:11,068 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-16 10:03:11,068 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:11,827 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-16 10:03:11,830 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-16 10:03:11,830 INFO L210 LassoAnalysis]: Preferences: [2021-12-16 10:03:11,831 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-16 10:03:11,831 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-16 10:03:11,831 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-16 10:03:11,831 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-16 10:03:11,831 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:11,831 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-16 10:03:11,831 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-16 10:03:11,831 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration3_Loop [2021-12-16 10:03:11,831 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-16 10:03:11,831 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-16 10:03:11,832 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-16 10:03:11,834 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-16 10:03:11,836 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-16 10:03:11,841 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-16 10:03:11,869 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-16 10:03:11,869 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-16 10:03:11,870 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:11,870 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:11,871 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-16 10:03:11,872 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-16 10:03:11,873 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-16 10:03:11,878 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:11,878 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:11,878 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:11,878 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:11,878 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:11,879 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:11,879 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:11,895 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-16 10:03:11,921 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2021-12-16 10:03:11,922 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:11,922 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:11,923 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-16 10:03:11,939 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-16 10:03:11,939 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-16 10:03:11,944 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:11,945 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:11,945 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:11,945 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:11,945 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:11,945 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:11,945 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:11,952 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-16 10:03:11,967 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-16 10:03:11,967 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:11,968 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:11,968 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-16 10:03:11,969 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-16 10:03:11,971 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-16 10:03:11,976 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:11,976 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:11,976 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:11,976 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:11,976 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:11,977 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:11,977 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:11,993 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-16 10:03:11,996 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2021-12-16 10:03:11,996 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2021-12-16 10:03:11,996 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:11,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:11,999 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-16 10:03:12,000 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-16 10:03:12,002 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-16 10:03:12,003 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-16 10:03:12,003 INFO L513 LassoAnalysis]: Proved termination. [2021-12-16 10:03:12,003 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2021-12-16 10:03:12,017 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2021-12-16 10:03:12,018 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-16 10:03:12,026 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:12,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:12,042 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-16 10:03:12,043 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:12,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:12,113 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2021-12-16 10:03:12,114 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:12,188 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-16 10:03:12,188 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-16 10:03:12,188 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-16 10:03:12,325 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-16 10:03:12,326 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-16 10:03:12,326 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-16 10:03:12,327 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 37 transitions. [2021-12-16 10:03:12,327 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 10 letters. [2021-12-16 10:03:12,327 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:12,327 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 22 letters. Loop has 10 letters. [2021-12-16 10:03:12,328 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:12,328 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 20 letters. [2021-12-16 10:03:12,328 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:12,328 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2021-12-16 10:03:12,333 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2021-12-16 10:03:12,343 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 108 states and 152 transitions. [2021-12-16 10:03:12,344 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 64 [2021-12-16 10:03:12,345 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 69 [2021-12-16 10:03:12,345 INFO L73 IsDeterministic]: Start isDeterministic. Operand 108 states and 152 transitions. [2021-12-16 10:03:12,345 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-16 10:03:12,345 INFO L681 BuchiCegarLoop]: Abstraction has 108 states and 152 transitions. [2021-12-16 10:03:12,345 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states and 152 transitions. [2021-12-16 10:03:12,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 94. [2021-12-16 10:03:12,376 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-16 10:03:12,379 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 126 transitions. [2021-12-16 10:03:12,380 INFO L704 BuchiCegarLoop]: Abstraction has 94 states and 126 transitions. [2021-12-16 10:03:12,380 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 10:03:12,381 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-12-16 10:03:12,381 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2021-12-16 10:03:12,381 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-16 10:03:12,476 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 10:03:12,476 INFO L93 Difference]: Finished difference Result 123 states and 165 transitions. [2021-12-16 10:03:12,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-16 10:03:12,476 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 123 states and 165 transitions. [2021-12-16 10:03:12,487 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2021-12-16 10:03:12,493 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 123 states to 118 states and 160 transitions. [2021-12-16 10:03:12,493 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 77 [2021-12-16 10:03:12,493 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 77 [2021-12-16 10:03:12,494 INFO L73 IsDeterministic]: Start isDeterministic. Operand 118 states and 160 transitions. [2021-12-16 10:03:12,494 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-16 10:03:12,494 INFO L681 BuchiCegarLoop]: Abstraction has 118 states and 160 transitions. [2021-12-16 10:03:12,495 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states and 160 transitions. [2021-12-16 10:03:12,501 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 106. [2021-12-16 10:03:12,501 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-16 10:03:12,535 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 141 transitions. [2021-12-16 10:03:12,535 INFO L704 BuchiCegarLoop]: Abstraction has 106 states and 141 transitions. [2021-12-16 10:03:12,536 INFO L587 BuchiCegarLoop]: Abstraction has 106 states and 141 transitions. [2021-12-16 10:03:12,536 INFO L425 BuchiCegarLoop]: ======== Iteration 4============ [2021-12-16 10:03:12,536 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 141 transitions. [2021-12-16 10:03:12,539 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2021-12-16 10:03:12,539 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-16 10:03:12,539 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-16 10:03:12,542 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 10:03:12,542 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [6, 5, 5, 3, 3, 3, 3, 2, 2, 2, 1] [2021-12-16 10:03:12,542 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-16 10:03:12,542 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-16 10:03:12,543 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:12,543 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 1 times [2021-12-16 10:03:12,543 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:12,543 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [465927018] [2021-12-16 10:03:12,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:12,544 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:12,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:12,558 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-16 10:03:12,562 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-16 10:03:12,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:12,576 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-16 10:03:12,576 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:12,576 INFO L85 PathProgramCache]: Analyzing trace with hash 1616897917, now seen corresponding path program 1 times [2021-12-16 10:03:12,576 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:12,577 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [550504877] [2021-12-16 10:03:12,577 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:12,577 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:12,600 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:12,607 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-16 10:03:12,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:12,619 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-16 10:03:12,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:12,629 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-16 10:03:12,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:12,648 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-16 10:03:12,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:12,652 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-16 10:03:12,653 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:12,655 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-16 10:03:12,656 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 10:03:12,656 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [550504877] [2021-12-16 10:03:12,656 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [550504877] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-16 10:03:12,656 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [21789461] [2021-12-16 10:03:12,656 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:12,656 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 10:03:12,657 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:12,657 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-16 10:03:12,679 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-16 10:03:12,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:12,705 INFO L263 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 6 conjunts are in the unsatisfiable core [2021-12-16 10:03:12,706 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:12,758 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-16 10:03:12,758 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 10:03:12,910 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-16 10:03:12,911 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [21789461] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 10:03:12,911 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-16 10:03:12,911 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2021-12-16 10:03:12,912 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [573913522] [2021-12-16 10:03:12,912 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-16 10:03:12,912 INFO L808 eck$LassoCheckResult]: loop already infeasible [2021-12-16 10:03:12,913 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 10:03:12,913 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-12-16 10:03:12,913 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2021-12-16 10:03:12,915 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-16 10:03:12,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 10:03:12,980 INFO L93 Difference]: Finished difference Result 60 states and 77 transitions. [2021-12-16 10:03:12,980 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-16 10:03:12,982 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 60 states and 77 transitions. [2021-12-16 10:03:12,983 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:12,984 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 60 states to 54 states and 70 transitions. [2021-12-16 10:03:12,984 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2021-12-16 10:03:12,984 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2021-12-16 10:03:12,984 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2021-12-16 10:03:12,984 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-16 10:03:12,984 INFO L681 BuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2021-12-16 10:03:12,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2021-12-16 10:03:12,997 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2021-12-16 10:03:12,999 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-16 10:03:13,000 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2021-12-16 10:03:13,000 INFO L704 BuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2021-12-16 10:03:13,000 INFO L587 BuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2021-12-16 10:03:13,000 INFO L425 BuchiCegarLoop]: ======== Iteration 5============ [2021-12-16 10:03:13,000 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2021-12-16 10:03:13,001 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:13,001 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-16 10:03:13,001 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-16 10:03:13,002 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 10:03:13,002 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 1] [2021-12-16 10:03:13,002 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-16 10:03:13,003 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-16 10:03:13,003 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:13,005 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 2 times [2021-12-16 10:03:13,006 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:13,006 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1080952130] [2021-12-16 10:03:13,006 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:13,006 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:13,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:13,016 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-16 10:03:13,024 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:13,033 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-16 10:03:13,034 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:13,034 INFO L85 PathProgramCache]: Analyzing trace with hash -176759904, now seen corresponding path program 2 times [2021-12-16 10:03:13,035 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:13,035 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1456408096] [2021-12-16 10:03:13,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:13,035 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:13,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,053 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2021-12-16 10:03:13,059 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,071 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-16 10:03:13,075 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,098 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-16 10:03:13,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,108 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-16 10:03:13,111 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,114 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2021-12-16 10:03:13,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,127 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-16 10:03:13,127 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 10:03:13,127 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1456408096] [2021-12-16 10:03:13,127 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1456408096] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-16 10:03:13,128 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1850638412] [2021-12-16 10:03:13,128 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-16 10:03:13,128 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 10:03:13,128 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:13,142 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-16 10:03:13,143 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-16 10:03:13,166 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-16 10:03:13,166 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-16 10:03:13,167 INFO L263 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 8 conjunts are in the unsatisfiable core [2021-12-16 10:03:13,168 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:13,236 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-16 10:03:13,236 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 10:03:13,451 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-16 10:03:13,452 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1850638412] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 10:03:13,452 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-16 10:03:13,452 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 14 [2021-12-16 10:03:13,452 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [77563885] [2021-12-16 10:03:13,452 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-16 10:03:13,453 INFO L808 eck$LassoCheckResult]: loop already infeasible [2021-12-16 10:03:13,453 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 10:03:13,453 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-16 10:03:13,453 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2021-12-16 10:03:13,454 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-16 10:03:13,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 10:03:13,524 INFO L93 Difference]: Finished difference Result 54 states and 67 transitions. [2021-12-16 10:03:13,524 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2021-12-16 10:03:13,525 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 54 states and 67 transitions. [2021-12-16 10:03:13,525 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:13,526 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 54 states to 54 states and 67 transitions. [2021-12-16 10:03:13,526 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2021-12-16 10:03:13,526 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2021-12-16 10:03:13,526 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 67 transitions. [2021-12-16 10:03:13,526 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-16 10:03:13,526 INFO L681 BuchiCegarLoop]: Abstraction has 54 states and 67 transitions. [2021-12-16 10:03:13,527 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 67 transitions. [2021-12-16 10:03:13,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2021-12-16 10:03:13,528 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-16 10:03:13,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 67 transitions. [2021-12-16 10:03:13,529 INFO L704 BuchiCegarLoop]: Abstraction has 54 states and 67 transitions. [2021-12-16 10:03:13,529 INFO L587 BuchiCegarLoop]: Abstraction has 54 states and 67 transitions. [2021-12-16 10:03:13,529 INFO L425 BuchiCegarLoop]: ======== Iteration 6============ [2021-12-16 10:03:13,529 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 67 transitions. [2021-12-16 10:03:13,530 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2021-12-16 10:03:13,530 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-16 10:03:13,530 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-16 10:03:13,530 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 10:03:13,531 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2021-12-16 10:03:13,531 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-16 10:03:13,531 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-16 10:03:13,531 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:13,531 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 3 times [2021-12-16 10:03:13,531 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:13,532 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [302717984] [2021-12-16 10:03:13,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:13,532 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:13,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:13,536 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-16 10:03:13,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:13,542 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-16 10:03:13,542 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:13,542 INFO L85 PathProgramCache]: Analyzing trace with hash 780094678, now seen corresponding path program 3 times [2021-12-16 10:03:13,542 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:13,542 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [137082930] [2021-12-16 10:03:13,543 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:13,543 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:13,545 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:13,545 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-16 10:03:13,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:13,548 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-16 10:03:13,548 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:13,549 INFO L85 PathProgramCache]: Analyzing trace with hash 1975410011, now seen corresponding path program 4 times [2021-12-16 10:03:13,549 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:13,549 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [750375055] [2021-12-16 10:03:13,549 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:13,549 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:13,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,612 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2021-12-16 10:03:13,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,616 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-16 10:03:13,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,619 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-16 10:03:13,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,621 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2021-12-16 10:03:13,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,624 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-16 10:03:13,625 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,626 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-16 10:03:13,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:13,628 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-16 10:03:13,628 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 10:03:13,628 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [750375055] [2021-12-16 10:03:13,628 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [750375055] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-16 10:03:13,629 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1594910777] [2021-12-16 10:03:13,629 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-16 10:03:13,629 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 10:03:13,629 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:13,667 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-16 10:03:13,678 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-16 10:03:13,705 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-16 10:03:13,705 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-16 10:03:13,706 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 12 conjunts are in the unsatisfiable core [2021-12-16 10:03:13,707 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:13,799 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-16 10:03:13,799 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 10:03:13,906 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-16 10:03:13,907 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1594910777] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 10:03:13,907 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-16 10:03:13,907 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12] total 15 [2021-12-16 10:03:13,907 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [263189202] [2021-12-16 10:03:13,907 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-16 10:03:14,042 INFO L210 LassoAnalysis]: Preferences: [2021-12-16 10:03:14,042 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-16 10:03:14,042 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-16 10:03:14,042 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-16 10:03:14,042 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-16 10:03:14,042 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,042 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-16 10:03:14,042 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-16 10:03:14,042 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration6_Loop [2021-12-16 10:03:14,042 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-16 10:03:14,042 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-16 10:03:14,042 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-16 10:03:14,044 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-16 10:03:14,045 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-16 10:03:14,047 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-16 10:03:14,068 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-16 10:03:14,068 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-16 10:03:14,068 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,068 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,084 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-16 10:03:14,093 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-16 10:03:14,093 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:14,093 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:14,101 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-16 10:03:14,101 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-16 10:03:14,119 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2021-12-16 10:03:14,120 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,120 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,121 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-16 10:03:14,122 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-16 10:03:14,123 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:14,123 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:14,130 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-16 10:03:14,130 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-16 10:03:14,145 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-16 10:03:14,146 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,146 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,147 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-16 10:03:14,148 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-16 10:03:14,149 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:14,149 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:14,156 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-16 10:03:14,157 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-16 10:03:14,172 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-16 10:03:14,173 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,173 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,174 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-16 10:03:14,175 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-16 10:03:14,176 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:14,176 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:14,214 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2021-12-16 10:03:14,214 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,215 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,215 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-16 10:03:14,224 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-16 10:03:14,226 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-16 10:03:14,226 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:14,793 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-16 10:03:14,797 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-16 10:03:14,797 INFO L210 LassoAnalysis]: Preferences: [2021-12-16 10:03:14,797 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-16 10:03:14,797 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-16 10:03:14,797 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-16 10:03:14,797 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-16 10:03:14,797 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,797 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-16 10:03:14,797 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-16 10:03:14,797 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration6_Loop [2021-12-16 10:03:14,797 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-16 10:03:14,797 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-16 10:03:14,798 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-16 10:03:14,800 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-16 10:03:14,801 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-16 10:03:14,803 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-16 10:03:14,830 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-16 10:03:14,830 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-16 10:03:14,830 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,831 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,832 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-16 10:03:14,833 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-16 10:03:14,834 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-16 10:03:14,840 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:14,840 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:14,840 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:14,840 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:14,840 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:14,841 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:14,841 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:14,867 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-16 10:03:14,889 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2021-12-16 10:03:14,889 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,889 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,890 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-16 10:03:14,891 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-16 10:03:14,893 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-16 10:03:14,898 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:14,898 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:14,898 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:14,898 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:14,898 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:14,899 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:14,899 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:14,900 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-16 10:03:14,915 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2021-12-16 10:03:14,916 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,916 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,920 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-16 10:03:14,921 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-16 10:03:14,924 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-16 10:03:14,930 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:14,930 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:14,930 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:14,930 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:14,930 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:14,930 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:14,931 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:14,939 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-16 10:03:14,954 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2021-12-16 10:03:14,955 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,955 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,956 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-16 10:03:14,957 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-16 10:03:14,958 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-16 10:03:14,963 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:14,963 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:14,964 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:14,964 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:14,964 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:14,965 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:14,965 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:14,967 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-16 10:03:14,969 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2021-12-16 10:03:14,969 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2021-12-16 10:03:14,969 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:14,969 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:14,986 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-16 10:03:14,987 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-16 10:03:14,988 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-16 10:03:14,988 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-16 10:03:14,988 INFO L513 LassoAnalysis]: Proved termination. [2021-12-16 10:03:14,988 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2021-12-16 10:03:15,007 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-16 10:03:15,007 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-16 10:03:15,018 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:15,053 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:15,055 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-16 10:03:15,058 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:15,166 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-16 10:03:15,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:15,326 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-16 10:03:15,327 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:15,429 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-16 10:03:15,429 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-16 10:03:15,430 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-16 10:03:15,496 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-16 10:03:15,498 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-16 10:03:15,498 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-16 10:03:15,499 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2021-12-16 10:03:15,499 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2021-12-16 10:03:15,499 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:15,499 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-16 10:03:15,506 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:15,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:15,533 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-16 10:03:15,534 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:15,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:15,734 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-16 10:03:15,735 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:15,829 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-16 10:03:15,830 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-16 10:03:15,830 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-16 10:03:15,889 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-16 10:03:15,891 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-16 10:03:15,891 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-16 10:03:15,891 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2021-12-16 10:03:15,892 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2021-12-16 10:03:15,892 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:15,892 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-16 10:03:15,898 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:15,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:15,926 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-16 10:03:15,927 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:16,119 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:16,120 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2021-12-16 10:03:16,121 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:16,211 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-16 10:03:16,212 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-16 10:03:16,212 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-16 10:03:16,375 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-16 10:03:16,376 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-16 10:03:16,376 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-16 10:03:16,377 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 46 transitions. [2021-12-16 10:03:16,377 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 22 letters. [2021-12-16 10:03:16,377 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:16,378 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 54 letters. Loop has 22 letters. [2021-12-16 10:03:16,378 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:16,378 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 44 letters. [2021-12-16 10:03:16,379 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:16,379 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 321 states and 401 transitions. [2021-12-16 10:03:16,382 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2021-12-16 10:03:16,383 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 321 states to 203 states and 261 transitions. [2021-12-16 10:03:16,383 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2021-12-16 10:03:16,384 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 90 [2021-12-16 10:03:16,384 INFO L73 IsDeterministic]: Start isDeterministic. Operand 203 states and 261 transitions. [2021-12-16 10:03:16,384 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-16 10:03:16,384 INFO L681 BuchiCegarLoop]: Abstraction has 203 states and 261 transitions. [2021-12-16 10:03:16,384 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states and 261 transitions. [2021-12-16 10:03:16,389 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 175. [2021-12-16 10:03:16,389 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-16 10:03:16,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 212 transitions. [2021-12-16 10:03:16,390 INFO L704 BuchiCegarLoop]: Abstraction has 175 states and 212 transitions. [2021-12-16 10:03:16,390 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 10:03:16,391 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2021-12-16 10:03:16,391 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2021-12-16 10:03:16,391 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-16 10:03:16,555 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 10:03:16,555 INFO L93 Difference]: Finished difference Result 124 states and 140 transitions. [2021-12-16 10:03:16,557 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2021-12-16 10:03:16,557 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 124 states and 140 transitions. [2021-12-16 10:03:16,558 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2021-12-16 10:03:16,559 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 124 states to 105 states and 117 transitions. [2021-12-16 10:03:16,559 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2021-12-16 10:03:16,559 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 64 [2021-12-16 10:03:16,559 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 117 transitions. [2021-12-16 10:03:16,559 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2021-12-16 10:03:16,559 INFO L681 BuchiCegarLoop]: Abstraction has 105 states and 117 transitions. [2021-12-16 10:03:16,559 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 117 transitions. [2021-12-16 10:03:16,561 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 96. [2021-12-16 10:03:16,561 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-16 10:03:16,562 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 108 transitions. [2021-12-16 10:03:16,562 INFO L704 BuchiCegarLoop]: Abstraction has 96 states and 108 transitions. [2021-12-16 10:03:16,562 INFO L587 BuchiCegarLoop]: Abstraction has 96 states and 108 transitions. [2021-12-16 10:03:16,562 INFO L425 BuchiCegarLoop]: ======== Iteration 7============ [2021-12-16 10:03:16,562 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 96 states and 108 transitions. [2021-12-16 10:03:16,562 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2021-12-16 10:03:16,563 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2021-12-16 10:03:16,563 INFO L119 BuchiIsEmpty]: Starting construction of run [2021-12-16 10:03:16,563 INFO L842 BuchiCegarLoop]: Counterexample stem histogram [7, 6, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2021-12-16 10:03:16,563 INFO L843 BuchiCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2021-12-16 10:03:16,563 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-16 10:03:16,563 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-16 10:03:16,564 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:16,564 INFO L85 PathProgramCache]: Analyzing trace with hash 2096320921, now seen corresponding path program 5 times [2021-12-16 10:03:16,564 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:16,564 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1975256439] [2021-12-16 10:03:16,564 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:16,564 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:16,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:16,590 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2021-12-16 10:03:16,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:16,612 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-16 10:03:16,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:16,621 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-16 10:03:16,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:16,625 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-16 10:03:16,625 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-16 10:03:16,625 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1975256439] [2021-12-16 10:03:16,625 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1975256439] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-16 10:03:16,625 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1567677364] [2021-12-16 10:03:16,625 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2021-12-16 10:03:16,626 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-16 10:03:16,626 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:16,626 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-16 10:03:16,653 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-16 10:03:16,675 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2021-12-16 10:03:16,676 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-16 10:03:16,676 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-16 10:03:16,677 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:16,755 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-16 10:03:16,755 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-16 10:03:16,883 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-16 10:03:16,883 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1567677364] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-16 10:03:16,884 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-16 10:03:16,884 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 10] total 18 [2021-12-16 10:03:16,884 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [401058883] [2021-12-16 10:03:16,884 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-16 10:03:16,884 INFO L796 eck$LassoCheckResult]: stem already infeasible [2021-12-16 10:03:16,885 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:16,885 INFO L85 PathProgramCache]: Analyzing trace with hash 1893846, now seen corresponding path program 2 times [2021-12-16 10:03:16,885 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-16 10:03:16,885 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [652806059] [2021-12-16 10:03:16,885 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-16 10:03:16,885 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-16 10:03:16,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:16,887 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2021-12-16 10:03:16,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2021-12-16 10:03:16,888 INFO L133 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2021-12-16 10:03:16,936 INFO L210 LassoAnalysis]: Preferences: [2021-12-16 10:03:16,936 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-16 10:03:16,936 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-16 10:03:16,936 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-16 10:03:16,936 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2021-12-16 10:03:16,936 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:16,936 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-16 10:03:16,936 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-16 10:03:16,936 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration7_Loop [2021-12-16 10:03:16,936 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-16 10:03:16,937 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-16 10:03:16,937 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-16 10:03:16,938 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-16 10:03:16,939 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2021-12-16 10:03:16,944 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-16 10:03:16,970 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-16 10:03:16,970 INFO L404 LassoAnalysis]: Checking for nontermination... [2021-12-16 10:03:16,970 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:16,970 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:16,971 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-16 10:03:16,972 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-16 10:03:16,974 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:16,974 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:16,980 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-16 10:03:16,980 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2021-12-16 10:03:16,995 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-16 10:03:16,995 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:16,995 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:16,996 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-16 10:03:16,996 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-16 10:03:16,999 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:16,999 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:17,005 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2021-12-16 10:03:17,005 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-16 10:03:17,022 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-16 10:03:17,022 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:17,022 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:17,023 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-16 10:03:17,023 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-16 10:03:17,024 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2021-12-16 10:03:17,024 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:17,050 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-16 10:03:17,050 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:17,050 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:17,053 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-16 10:03:17,054 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-16 10:03:17,055 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2021-12-16 10:03:17,055 INFO L160 nArgumentSynthesizer]: Using integer mode. [2021-12-16 10:03:19,540 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2021-12-16 10:03:19,546 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-16 10:03:19,546 INFO L210 LassoAnalysis]: Preferences: [2021-12-16 10:03:19,546 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2021-12-16 10:03:19,546 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2021-12-16 10:03:19,546 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2021-12-16 10:03:19,546 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2021-12-16 10:03:19,546 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:19,546 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2021-12-16 10:03:19,546 INFO L132 ssoRankerPreferences]: Path of dumped script: [2021-12-16 10:03:19,546 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-2.c_Iteration7_Loop [2021-12-16 10:03:19,546 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2021-12-16 10:03:19,546 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2021-12-16 10:03:19,547 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-16 10:03:19,554 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-16 10:03:19,560 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-16 10:03:19,562 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-16 10:03:19,586 INFO L294 LassoAnalysis]: Preprocessing complete. [2021-12-16 10:03:19,586 INFO L490 LassoAnalysis]: Using template 'affine'. [2021-12-16 10:03:19,586 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:19,587 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:19,587 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-16 10:03:19,588 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-16 10:03:19,589 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-16 10:03:19,595 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:19,596 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:19,596 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:19,596 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:19,596 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:19,597 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:19,597 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:19,605 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2021-12-16 10:03:19,620 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2021-12-16 10:03:19,620 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:19,620 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:19,621 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-16 10:03:19,622 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-16 10:03:19,624 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-16 10:03:19,629 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2021-12-16 10:03:19,629 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2021-12-16 10:03:19,629 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2021-12-16 10:03:19,629 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2021-12-16 10:03:19,630 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2021-12-16 10:03:19,630 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2021-12-16 10:03:19,630 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2021-12-16 10:03:19,632 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2021-12-16 10:03:19,633 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2021-12-16 10:03:19,633 INFO L444 ModelExtractionUtils]: 2 out of 4 variables were initially zero. Simplification set additionally 0 variables to zero. [2021-12-16 10:03:19,633 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2021-12-16 10:03:19,633 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-16 10:03:19,635 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-16 10:03:19,636 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-16 10:03:19,637 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2021-12-16 10:03:19,637 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2021-12-16 10:03:19,637 INFO L513 LassoAnalysis]: Proved termination. [2021-12-16 10:03:19,637 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2021-12-16 10:03:19,652 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-16 10:03:19,652 INFO L297 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2021-12-16 10:03:19,661 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:19,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:19,698 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-16 10:03:19,698 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:19,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:19,891 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-16 10:03:19,891 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:19,913 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-16 10:03:19,913 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-16 10:03:19,913 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-16 10:03:19,946 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-16 10:03:19,946 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-16 10:03:19,947 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-16 10:03:19,947 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2021-12-16 10:03:19,948 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 36 letters. Loop has 4 letters. [2021-12-16 10:03:19,948 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:19,948 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-16 10:03:19,954 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:19,981 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:19,982 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-16 10:03:19,983 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:20,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:20,152 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-16 10:03:20,153 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:20,176 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-16 10:03:20,178 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-16 10:03:20,178 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-16 10:03:20,226 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-16 10:03:20,226 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-16 10:03:20,227 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-16 10:03:20,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 16 transitions. [2021-12-16 10:03:20,227 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 16 transitions. Stem has 36 letters. Loop has 4 letters. [2021-12-16 10:03:20,227 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:20,227 INFO L634 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2021-12-16 10:03:20,234 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-16 10:03:20,262 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:20,263 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-16 10:03:20,264 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:20,300 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Ended with exit code 0 [2021-12-16 10:03:20,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-16 10:03:20,467 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-16 10:03:20,467 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-16 10:03:20,484 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-16 10:03:20,484 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-16 10:03:20,484 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-16 10:03:20,514 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-16 10:03:20,514 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-16 10:03:20,515 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-16 10:03:20,515 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 22 transitions. [2021-12-16 10:03:20,515 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 4 letters. [2021-12-16 10:03:20,515 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:20,515 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 40 letters. Loop has 4 letters. [2021-12-16 10:03:20,515 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:20,515 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 8 letters. [2021-12-16 10:03:20,516 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2021-12-16 10:03:20,516 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 131 states and 150 transitions. [2021-12-16 10:03:20,517 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-16 10:03:20,517 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 131 states to 0 states and 0 transitions. [2021-12-16 10:03:20,517 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2021-12-16 10:03:20,517 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2021-12-16 10:03:20,517 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2021-12-16 10:03:20,517 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2021-12-16 10:03:20,517 INFO L681 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-16 10:03:20,517 INFO L704 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-16 10:03:20,518 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-16 10:03:20,518 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2021-12-16 10:03:20,518 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=245, Unknown=0, NotChecked=0, Total=306 [2021-12-16 10:03:20,518 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-16 10:03:20,518 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-16 10:03:20,518 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2021-12-16 10:03:20,518 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-16 10:03:20,522 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2021-12-16 10:03:20,522 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-16 10:03:20,522 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2021-12-16 10:03:20,522 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2021-12-16 10:03:20,522 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2021-12-16 10:03:20,522 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2021-12-16 10:03:20,522 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2021-12-16 10:03:20,522 INFO L681 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-16 10:03:20,522 INFO L704 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-16 10:03:20,522 INFO L587 BuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2021-12-16 10:03:20,522 INFO L425 BuchiCegarLoop]: ======== Iteration 8============ [2021-12-16 10:03:20,522 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2021-12-16 10:03:20,522 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2021-12-16 10:03:20,523 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2021-12-16 10:03:20,539 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 16.12 10:03:20 BoogieIcfgContainer [2021-12-16 10:03:20,539 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2021-12-16 10:03:20,539 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2021-12-16 10:03:20,539 INFO L271 PluginConnector]: Initializing Witness Printer... [2021-12-16 10:03:20,539 INFO L275 PluginConnector]: Witness Printer initialized [2021-12-16 10:03:20,540 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 16.12 10:03:09" (3/4) ... [2021-12-16 10:03:20,541 INFO L140 WitnessPrinter]: No result that supports witness generation found [2021-12-16 10:03:20,542 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2021-12-16 10:03:20,542 INFO L158 Benchmark]: Toolchain (without parser) took 11756.23ms. Allocated memory was 117.4MB in the beginning and 182.5MB in the end (delta: 65.0MB). Free memory was 90.5MB in the beginning and 117.0MB in the end (delta: -26.5MB). Peak memory consumption was 37.0MB. Max. memory is 16.1GB. [2021-12-16 10:03:20,542 INFO L158 Benchmark]: CDTParser took 0.15ms. Allocated memory is still 117.4MB. Free memory is still 74.6MB. There was no memory consumed. Max. memory is 16.1GB. [2021-12-16 10:03:20,543 INFO L158 Benchmark]: CACSL2BoogieTranslator took 161.39ms. Allocated memory was 117.4MB in the beginning and 151.0MB in the end (delta: 33.6MB). Free memory was 90.5MB in the beginning and 126.4MB in the end (delta: -35.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2021-12-16 10:03:20,543 INFO L158 Benchmark]: Boogie Procedure Inliner took 18.88ms. Allocated memory is still 151.0MB. Free memory was 126.4MB in the beginning and 124.7MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2021-12-16 10:03:20,543 INFO L158 Benchmark]: Boogie Preprocessor took 10.36ms. Allocated memory is still 151.0MB. Free memory was 124.7MB in the beginning and 124.3MB in the end (delta: 448.4kB). There was no memory consumed. Max. memory is 16.1GB. [2021-12-16 10:03:20,543 INFO L158 Benchmark]: RCFGBuilder took 168.11ms. Allocated memory is still 151.0MB. Free memory was 124.3MB in the beginning and 115.0MB in the end (delta: 9.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2021-12-16 10:03:20,544 INFO L158 Benchmark]: BuchiAutomizer took 11391.21ms. Allocated memory was 151.0MB in the beginning and 182.5MB in the end (delta: 31.5MB). Free memory was 115.0MB in the beginning and 117.0MB in the end (delta: -2.0MB). Peak memory consumption was 30.3MB. Max. memory is 16.1GB. [2021-12-16 10:03:20,545 INFO L158 Benchmark]: Witness Printer took 2.40ms. Allocated memory is still 182.5MB. Free memory is still 117.0MB. There was no memory consumed. Max. memory is 16.1GB. [2021-12-16 10:03:20,546 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.15ms. Allocated memory is still 117.4MB. Free memory is still 74.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 161.39ms. Allocated memory was 117.4MB in the beginning and 151.0MB in the end (delta: 33.6MB). Free memory was 90.5MB in the beginning and 126.4MB in the end (delta: -35.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 18.88ms. Allocated memory is still 151.0MB. Free memory was 126.4MB in the beginning and 124.7MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 10.36ms. Allocated memory is still 151.0MB. Free memory was 124.7MB in the beginning and 124.3MB in the end (delta: 448.4kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 168.11ms. Allocated memory is still 151.0MB. Free memory was 124.3MB in the beginning and 115.0MB in the end (delta: 9.2MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * BuchiAutomizer took 11391.21ms. Allocated memory was 151.0MB in the beginning and 182.5MB in the end (delta: 31.5MB). Free memory was 115.0MB in the beginning and 117.0MB in the end (delta: -2.0MB). Peak memory consumption was 30.3MB. Max. memory is 16.1GB. * Witness Printer took 2.40ms. Allocated memory is still 182.5MB. Free memory is still 117.0MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 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.3s and 8 iterations. TraceHistogramMax:7. Analysis of lassos took 7.8s. Construction of modules took 0.3s. Büchi inclusion checks took 2.8s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 8. Automata minimization 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 68 StatesRemovedByMinimization, 5 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had 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: 37ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 9 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 4.2s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2021-12-16 10:03:20,567 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-16 10:03:20,783 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-16 10:03:20,983 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2021-12-16 10:03:21,183 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-16 10:03:21,383 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-16 10:03:21,585 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