./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive/Fibonacci02.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 791161d1 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/Fibonacci02.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 b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 --- Real Ultimate output --- This is Ultimate 0.2.2-?-791161d [2022-07-23 15:28:22,933 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-23 15:28:22,935 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-23 15:28:22,984 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-23 15:28:22,984 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-23 15:28:22,985 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-23 15:28:22,987 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-23 15:28:22,989 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-23 15:28:22,991 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-23 15:28:22,995 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-23 15:28:22,995 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-23 15:28:22,997 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-23 15:28:22,998 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-23 15:28:22,999 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-23 15:28:23,000 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-23 15:28:23,003 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-23 15:28:23,004 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-23 15:28:23,005 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-23 15:28:23,006 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-23 15:28:23,011 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-23 15:28:23,013 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-23 15:28:23,014 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-23 15:28:23,015 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-23 15:28:23,016 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-23 15:28:23,017 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-23 15:28:23,023 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-23 15:28:23,024 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-23 15:28:23,024 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-23 15:28:23,026 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-23 15:28:23,026 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-23 15:28:23,027 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-23 15:28:23,027 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-23 15:28:23,029 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-23 15:28:23,029 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-23 15:28:23,031 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-23 15:28:23,031 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-23 15:28:23,032 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-23 15:28:23,032 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-23 15:28:23,032 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-23 15:28:23,033 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-23 15:28:23,033 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-23 15:28:23,035 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-23 15:28:23,036 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2022-07-23 15:28:23,064 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-23 15:28:23,065 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-23 15:28:23,065 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-23 15:28:23,065 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-23 15:28:23,067 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-23 15:28:23,067 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-23 15:28:23,068 INFO L138 SettingsManager]: * Use SBE=true [2022-07-23 15:28:23,068 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2022-07-23 15:28:23,068 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2022-07-23 15:28:23,069 INFO L138 SettingsManager]: * Use old map elimination=false [2022-07-23 15:28:23,069 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2022-07-23 15:28:23,069 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2022-07-23 15:28:23,069 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2022-07-23 15:28:23,069 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-23 15:28:23,070 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-23 15:28:23,070 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2022-07-23 15:28:23,071 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-23 15:28:23,071 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-23 15:28:23,071 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-23 15:28:23,072 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2022-07-23 15:28:23,072 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2022-07-23 15:28:23,072 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2022-07-23 15:28:23,072 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-23 15:28:23,072 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-23 15:28:23,073 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2022-07-23 15:28:23,073 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-23 15:28:23,073 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2022-07-23 15:28:23,073 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-23 15:28:23,073 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-23 15:28:23,074 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-23 15:28:23,074 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-23 15:28:23,075 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-07-23 15:28:23,075 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 -> b7261cadd839cd02322bb28945f92ad1bd2170c0a65dd385996b5ff81cbb1de7 [2022-07-23 15:28:23,319 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-23 15:28:23,341 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-23 15:28:23,344 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-23 15:28:23,345 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-23 15:28:23,345 INFO L275 PluginConnector]: CDTParser initialized [2022-07-23 15:28:23,346 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive/Fibonacci02.c [2022-07-23 15:28:23,404 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/96afcdbcb/66afab8afbf94c13af326a1b9fd53e49/FLAG2aa441149 [2022-07-23 15:28:23,829 INFO L306 CDTParser]: Found 1 translation units. [2022-07-23 15:28:23,829 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive/Fibonacci02.c [2022-07-23 15:28:23,835 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/96afcdbcb/66afab8afbf94c13af326a1b9fd53e49/FLAG2aa441149 [2022-07-23 15:28:24,231 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/96afcdbcb/66afab8afbf94c13af326a1b9fd53e49 [2022-07-23 15:28:24,234 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-23 15:28:24,235 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-23 15:28:24,240 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-23 15:28:24,240 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-23 15:28:24,243 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-23 15:28:24,243 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,244 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5b0c9d58 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24, skipping insertion in model container [2022-07-23 15:28:24,244 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,250 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-23 15:28:24,260 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-23 15:28:24,402 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/Fibonacci02.c[715,728] [2022-07-23 15:28:24,402 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-23 15:28:24,410 INFO L203 MainTranslator]: Completed pre-run [2022-07-23 15:28:24,421 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/Fibonacci02.c[715,728] [2022-07-23 15:28:24,421 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-23 15:28:24,432 INFO L208 MainTranslator]: Completed translation [2022-07-23 15:28:24,432 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24 WrapperNode [2022-07-23 15:28:24,433 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-23 15:28:24,434 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-23 15:28:24,434 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-23 15:28:24,434 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-23 15:28:24,440 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,446 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,460 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2022-07-23 15:28:24,460 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-23 15:28:24,462 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-23 15:28:24,462 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-23 15:28:24,462 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-23 15:28:24,468 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,468 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,469 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,469 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,471 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,473 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,479 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,481 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-23 15:28:24,482 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-23 15:28:24,483 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-23 15:28:24,483 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-23 15:28:24,484 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (1/1) ... [2022-07-23 15:28:24,489 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:24,496 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:24,508 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:24,521 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2022-07-23 15:28:24,545 INFO L130 BoogieDeclarations]: Found specification of procedure fibonacci [2022-07-23 15:28:24,546 INFO L138 BoogieDeclarations]: Found implementation of procedure fibonacci [2022-07-23 15:28:24,546 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-23 15:28:24,546 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-23 15:28:24,546 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-23 15:28:24,546 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-23 15:28:24,602 INFO L234 CfgBuilder]: Building ICFG [2022-07-23 15:28:24,604 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-23 15:28:24,710 INFO L275 CfgBuilder]: Performing block encoding [2022-07-23 15:28:24,716 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-23 15:28:24,717 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2022-07-23 15:28:24,719 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.07 03:28:24 BoogieIcfgContainer [2022-07-23 15:28:24,719 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-23 15:28:24,720 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2022-07-23 15:28:24,721 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2022-07-23 15:28:24,723 INFO L275 PluginConnector]: BuchiAutomizer initialized [2022-07-23 15:28:24,724 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-23 15:28:24,724 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 23.07 03:28:24" (1/3) ... [2022-07-23 15:28:24,725 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@568d7d55 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 23.07 03:28:24, skipping insertion in model container [2022-07-23 15:28:24,725 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-23 15:28:24,726 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.07 03:28:24" (2/3) ... [2022-07-23 15:28:24,726 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@568d7d55 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 23.07 03:28:24, skipping insertion in model container [2022-07-23 15:28:24,726 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-23 15:28:24,726 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.07 03:28:24" (3/3) ... [2022-07-23 15:28:24,728 INFO L354 chiAutomizerObserver]: Analyzing ICFG Fibonacci02.c [2022-07-23 15:28:24,790 INFO L255 stractBuchiCegarLoop]: Interprodecural is true [2022-07-23 15:28:24,791 INFO L256 stractBuchiCegarLoop]: Hoare is false [2022-07-23 15:28:24,791 INFO L257 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2022-07-23 15:28:24,791 INFO L258 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2022-07-23 15:28:24,791 INFO L259 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2022-07-23 15:28:24,791 INFO L260 stractBuchiCegarLoop]: Difference is false [2022-07-23 15:28:24,791 INFO L261 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2022-07-23 15:28:24,791 INFO L265 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2022-07-23 15:28:24,795 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 17 states, 12 states have (on average 1.25) internal successors, (15), 12 states have internal predecessors, (15), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-23 15:28:24,811 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-23 15:28:24,812 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-23 15:28:24,812 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-23 15:28:24,835 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2022-07-23 15:28:24,836 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-23 15:28:24,836 INFO L287 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2022-07-23 15:28:24,836 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 17 states, 12 states have (on average 1.25) internal successors, (15), 12 states have internal predecessors, (15), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-23 15:28:24,838 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-23 15:28:24,839 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-23 15:28:24,839 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-23 15:28:24,839 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2022-07-23 15:28:24,840 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-23 15:28:24,846 INFO L752 eck$LassoCheckResult]: Stem: 6#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(14, 2);call #Ultimate.allocInit(12, 3); 14#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 := 9; 10#L29true call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 4#fibonacciENTRYtrue [2022-07-23 15:28:24,847 INFO L754 eck$LassoCheckResult]: Loop: 4#fibonacciENTRYtrue ~n := #in~n; 5#L17true assume !(~n < 1); 17#L19true assume !(1 == ~n); 16#L22true call #t~ret4 := fibonacci(~n - 1);< 4#fibonacciENTRYtrue [2022-07-23 15:28:24,861 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:24,862 INFO L85 PathProgramCache]: Analyzing trace with hash 42781, now seen corresponding path program 1 times [2022-07-23 15:28:24,869 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:24,871 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [16623659] [2022-07-23 15:28:24,871 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:24,872 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:24,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:24,966 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-23 15:28:24,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:25,006 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-23 15:28:25,009 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:25,010 INFO L85 PathProgramCache]: Analyzing trace with hash 927641, now seen corresponding path program 1 times [2022-07-23 15:28:25,010 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:25,011 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1577671184] [2022-07-23 15:28:25,011 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:25,012 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:25,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:25,024 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-23 15:28:25,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:25,033 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-23 15:28:25,035 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:25,035 INFO L85 PathProgramCache]: Analyzing trace with hash 854450357, now seen corresponding path program 1 times [2022-07-23 15:28:25,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:25,036 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2058126561] [2022-07-23 15:28:25,036 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:25,036 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:25,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:25,060 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-23 15:28:25,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:25,084 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-23 15:28:25,211 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:25,211 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:25,212 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:25,212 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:25,212 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-23 15:28:25,213 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,213 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:25,213 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:25,213 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2022-07-23 15:28:25,213 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:25,214 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:25,227 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,237 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,240 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,245 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,254 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,315 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:25,316 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-23 15:28:25,319 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,320 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,335 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,343 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:25,344 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:25,354 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2022-07-23 15:28:25,362 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:25,363 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:25,389 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:25,390 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,390 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,391 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,398 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:25,398 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:25,407 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2022-07-23 15:28:25,419 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:25,420 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:25,446 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:25,446 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,447 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,449 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,451 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2022-07-23 15:28:25,452 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:25,452 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:25,474 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:25,474 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:25,500 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:25,500 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,501 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,502 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,510 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:25,510 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:25,519 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2022-07-23 15:28:25,555 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:25,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,557 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,560 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2022-07-23 15:28:25,561 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-23 15:28:25,561 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:25,622 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-23 15:28:25,625 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 [2022-07-23 15:28:25,626 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:25,626 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:25,626 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:25,626 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:25,626 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-23 15:28:25,626 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,626 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:25,626 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:25,626 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration1_Loop [2022-07-23 15:28:25,627 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:25,627 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:25,628 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,631 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,636 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,638 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,645 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:25,686 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:25,690 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-23 15:28:25,692 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,692 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,693 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,700 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:25,709 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:25,709 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:25,710 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:25,710 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:25,710 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:25,712 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:25,713 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:25,714 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2022-07-23 15:28:25,719 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:25,741 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:25,742 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,742 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,743 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,744 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2022-07-23 15:28:25,749 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:25,757 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:25,757 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:25,757 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:25,757 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:25,758 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:25,758 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:25,759 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:25,771 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:25,792 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:25,792 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,792 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,793 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,794 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2022-07-23 15:28:25,796 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:25,803 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:25,804 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:25,804 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:25,804 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:25,804 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:25,805 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:25,805 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:25,811 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:25,829 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:25,831 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,831 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,832 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,832 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2022-07-23 15:28:25,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 [2022-07-23 15:28:25,841 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:25,841 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:25,842 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:25,842 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:25,842 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:25,843 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:25,843 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:25,856 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-23 15:28:25,863 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-23 15:28:25,864 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-23 15:28:25,865 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:25,865 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:25,866 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:25,867 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2022-07-23 15:28:25,868 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-23 15:28:25,868 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-23 15:28:25,868 INFO L513 LassoAnalysis]: Proved termination. [2022-07-23 15:28:25,868 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2022-07-23 15:28:25,884 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:25,887 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-23 15:28:25,915 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:25,942 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:25,945 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-23 15:28:25,947 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:25,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:25,988 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-23 15:28:25,989 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:26,048 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:26,075 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 3 loop predicates [2022-07-23 15:28:26,077 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 17 states, 12 states have (on average 1.25) internal successors, (15), 12 states have internal predecessors, (15), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-23 15:28:26,161 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 17 states, 12 states have (on average 1.25) internal successors, (15), 12 states have internal predecessors, (15), 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 47 states and 59 transitions. Complement of second has 12 states. [2022-07-23 15:28:26,162 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 4 states 1 stem states 2 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:26,167 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-23 15:28:26,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 11 transitions. [2022-07-23 15:28:26,169 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 4 letters. [2022-07-23 15:28:26,170 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:26,170 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 7 letters. Loop has 4 letters. [2022-07-23 15:28:26,170 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:26,170 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 8 letters. [2022-07-23 15:28:26,171 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:26,171 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 47 states and 59 transitions. [2022-07-23 15:28:26,175 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-23 15:28:26,180 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 47 states to 25 states and 34 transitions. [2022-07-23 15:28:26,180 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2022-07-23 15:28:26,181 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 18 [2022-07-23 15:28:26,181 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 34 transitions. [2022-07-23 15:28:26,181 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-23 15:28:26,181 INFO L369 hiAutomatonCegarLoop]: Abstraction has 25 states and 34 transitions. [2022-07-23 15:28:26,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 34 transitions. [2022-07-23 15:28:26,203 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 20. [2022-07-23 15:28:26,203 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 14 states have (on average 1.2857142857142858) internal successors, (18), 14 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-07-23 15:28:26,204 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2022-07-23 15:28:26,205 INFO L392 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2022-07-23 15:28:26,205 INFO L374 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2022-07-23 15:28:26,205 INFO L287 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2022-07-23 15:28:26,205 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2022-07-23 15:28:26,206 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-23 15:28:26,206 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-23 15:28:26,206 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-23 15:28:26,207 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-23 15:28:26,207 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2022-07-23 15:28:26,208 INFO L752 eck$LassoCheckResult]: Stem: 132#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(14, 2);call #Ultimate.allocInit(12, 3); 133#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 := 9; 122#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 131#fibonacciENTRY ~n := #in~n; 128#L17 assume !(~n < 1); 129#L19 assume !(1 == ~n); 121#L22 call #t~ret4 := fibonacci(~n - 1);< 130#fibonacciENTRY ~n := #in~n; 125#L17 assume ~n < 1;#res := 0; 126#fibonacciFINAL assume true; 134#fibonacciEXIT >#29#return; 120#L22-1 [2022-07-23 15:28:26,208 INFO L754 eck$LassoCheckResult]: Loop: 120#L22-1 call #t~ret5 := fibonacci(~n - 2);< 124#fibonacciENTRY ~n := #in~n; 139#L17 assume !(~n < 1); 138#L19 assume !(1 == ~n); 123#L22 call #t~ret4 := fibonacci(~n - 1);< 124#fibonacciENTRY ~n := #in~n; 139#L17 assume ~n < 1;#res := 0; 136#fibonacciFINAL assume true; 137#fibonacciEXIT >#29#return; 120#L22-1 [2022-07-23 15:28:26,208 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:26,208 INFO L85 PathProgramCache]: Analyzing trace with hash 1391758089, now seen corresponding path program 1 times [2022-07-23 15:28:26,209 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:26,209 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [621051540] [2022-07-23 15:28:26,209 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:26,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:26,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:26,249 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-23 15:28:26,254 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:26,273 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-23 15:28:26,274 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-23 15:28:26,274 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [621051540] [2022-07-23 15:28:26,274 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [621051540] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-23 15:28:26,275 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-23 15:28:26,275 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-23 15:28:26,275 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [388379414] [2022-07-23 15:28:26,276 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-23 15:28:26,277 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-23 15:28:26,278 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:26,278 INFO L85 PathProgramCache]: Analyzing trace with hash 924369961, now seen corresponding path program 1 times [2022-07-23 15:28:26,278 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:26,279 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [141491914] [2022-07-23 15:28:26,279 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:26,279 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:26,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:26,299 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-23 15:28:26,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:26,346 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2022-07-23 15:28:26,347 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-23 15:28:26,347 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [141491914] [2022-07-23 15:28:26,347 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [141491914] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-23 15:28:26,347 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-23 15:28:26,348 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-23 15:28:26,348 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [327482091] [2022-07-23 15:28:26,348 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-23 15:28:26,348 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-23 15:28:26,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-23 15:28:26,351 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-07-23 15:28:26,352 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-07-23 15:28:26,353 INFO L87 Difference]: Start difference. First operand 20 states and 26 transitions. cyclomatic complexity: 8 Second operand has 6 states, 4 states have (on average 1.5) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:26,358 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:26,429 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-23 15:28:26,429 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2022-07-23 15:28:26,430 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-23 15:28:26,431 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2022-07-23 15:28:26,436 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-23 15:28:26,440 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2022-07-23 15:28:26,440 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2022-07-23 15:28:26,441 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2022-07-23 15:28:26,441 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2022-07-23 15:28:26,442 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-23 15:28:26,442 INFO L369 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-23 15:28:26,442 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2022-07-23 15:28:26,446 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2022-07-23 15:28:26,446 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 24 states, 16 states have (on average 1.1875) internal successors, (19), 18 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 4 states have return successors, (7), 2 states have call predecessors, (7), 3 states have call successors, (7) [2022-07-23 15:28:26,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2022-07-23 15:28:26,451 INFO L392 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-23 15:28:26,451 INFO L374 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-23 15:28:26,451 INFO L287 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2022-07-23 15:28:26,452 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2022-07-23 15:28:26,454 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-23 15:28:26,455 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-23 15:28:26,455 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-23 15:28:26,456 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-23 15:28:26,456 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2022-07-23 15:28:26,456 INFO L752 eck$LassoCheckResult]: Stem: 204#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(14, 2);call #Ultimate.allocInit(12, 3); 205#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 := 9; 194#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 208#fibonacciENTRY ~n := #in~n; 200#L17 assume !(~n < 1); 203#L19 assume !(1 == ~n); 195#L22 call #t~ret4 := fibonacci(~n - 1);< 199#fibonacciENTRY ~n := #in~n; 201#L17 assume !(~n < 1); 202#L19 assume 1 == ~n;#res := 1; 216#fibonacciFINAL assume true; 215#fibonacciEXIT >#29#return; 193#L22-1 [2022-07-23 15:28:26,456 INFO L754 eck$LassoCheckResult]: Loop: 193#L22-1 call #t~ret5 := fibonacci(~n - 2);< 197#fibonacciENTRY ~n := #in~n; 198#L17 assume !(~n < 1); 210#L19 assume !(1 == ~n); 196#L22 call #t~ret4 := fibonacci(~n - 1);< 197#fibonacciENTRY ~n := #in~n; 198#L17 assume !(~n < 1); 210#L19 assume 1 == ~n;#res := 1; 211#fibonacciFINAL assume true; 213#fibonacciEXIT >#29#return; 193#L22-1 [2022-07-23 15:28:26,457 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:26,457 INFO L85 PathProgramCache]: Analyzing trace with hash 194852287, now seen corresponding path program 1 times [2022-07-23 15:28:26,457 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:26,457 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1440198014] [2022-07-23 15:28:26,458 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:26,458 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:26,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:26,509 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-23 15:28:26,517 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:26,543 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:26,544 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-23 15:28:26,545 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1440198014] [2022-07-23 15:28:26,545 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1440198014] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-23 15:28:26,551 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [811040763] [2022-07-23 15:28:26,552 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:26,552 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-23 15:28:26,552 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:26,553 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-23 15:28:26,583 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-07-23 15:28:26,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:26,591 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-23 15:28:26,593 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:26,639 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:26,640 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-23 15:28:26,753 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:26,754 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [811040763] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-23 15:28:26,754 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-23 15:28:26,754 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2022-07-23 15:28:26,754 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [999059113] [2022-07-23 15:28:26,754 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-23 15:28:26,755 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-23 15:28:26,755 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:26,755 INFO L85 PathProgramCache]: Analyzing trace with hash -1409277793, now seen corresponding path program 1 times [2022-07-23 15:28:26,756 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:26,756 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1907769942] [2022-07-23 15:28:26,756 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:26,756 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:26,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:26,771 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-23 15:28:26,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:26,786 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-23 15:28:26,902 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:26,903 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:26,903 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:26,903 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:26,903 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-23 15:28:26,903 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:26,903 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:26,903 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:26,904 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2022-07-23 15:28:26,904 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:26,904 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:26,905 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:26,907 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:26,908 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:26,911 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:26,946 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:26,946 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-23 15:28:26,946 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:26,947 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:26,948 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:26,949 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2022-07-23 15:28:26,951 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:26,951 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:26,973 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:26,973 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:26,998 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:26,999 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:26,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:27,000 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:27,001 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2022-07-23 15:28:27,003 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:27,003 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:27,024 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:27,024 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:27,055 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:27,055 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:27,056 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:27,057 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:27,058 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2022-07-23 15:28:27,059 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:27,059 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:27,070 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:27,070 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=1} Honda state: {fibonacci_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:27,088 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2022-07-23 15:28:27,089 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:27,089 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:27,090 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:27,090 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2022-07-23 15:28:27,091 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:27,092 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:27,119 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:27,120 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:27,120 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:27,120 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:27,124 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2022-07-23 15:28:27,125 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-23 15:28:27,125 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:27,476 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-23 15:28:27,486 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:27,487 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:27,487 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:27,487 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:27,487 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:27,487 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-23 15:28:27,487 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:27,487 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:27,487 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:27,487 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration3_Loop [2022-07-23 15:28:27,487 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:27,488 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:27,488 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:27,491 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:27,493 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:27,496 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:27,541 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:27,541 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-23 15:28:27,541 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:27,541 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:27,542 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:27,552 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2022-07-23 15:28:27,552 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:27,560 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:27,561 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:27,561 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:27,561 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:27,561 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:27,562 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:27,562 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:27,575 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:27,602 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:27,602 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:27,602 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:27,603 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:27,609 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2022-07-23 15:28:27,609 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:27,618 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:27,618 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:27,618 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:27,619 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:27,619 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:27,619 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:27,619 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:27,635 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:27,662 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:27,662 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:27,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:27,664 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:27,665 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2022-07-23 15:28:27,666 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:27,681 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:27,681 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:27,681 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:27,681 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:27,681 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:27,682 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:27,682 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:27,696 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:27,722 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:27,723 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:27,723 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:27,724 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:27,732 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:27,740 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:27,740 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:27,740 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:27,740 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:27,740 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:27,746 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:27,746 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:27,749 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2022-07-23 15:28:27,753 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-23 15:28:27,761 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-23 15:28:27,761 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-23 15:28:27,761 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:27,761 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:27,804 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:27,806 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2022-07-23 15:28:27,807 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-23 15:28:27,807 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-23 15:28:27,807 INFO L513 LassoAnalysis]: Proved termination. [2022-07-23 15:28:27,807 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2022-07-23 15:28:27,823 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:27,824 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-23 15:28:27,865 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:27,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:27,896 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-23 15:28:27,897 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:28,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:28,024 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-23 15:28:28,025 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:28,099 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:28,100 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2022-07-23 15:28:28,100 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-23 15:28:28,216 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:28,320 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 24 states and 30 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Result 135 states and 183 transitions. Complement of second has 36 states. [2022-07-23 15:28:28,320 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 9 states 2 stem states 6 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:28,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-23 15:28:28,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 37 transitions. [2022-07-23 15:28:28,323 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 10 letters. [2022-07-23 15:28:28,324 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:28,324 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 22 letters. Loop has 10 letters. [2022-07-23 15:28:28,324 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:28,324 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 20 letters. [2022-07-23 15:28:28,327 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:28,327 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2022-07-23 15:28:28,336 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-23 15:28:28,342 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 108 states and 152 transitions. [2022-07-23 15:28:28,342 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 64 [2022-07-23 15:28:28,343 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 69 [2022-07-23 15:28:28,343 INFO L73 IsDeterministic]: Start isDeterministic. Operand 108 states and 152 transitions. [2022-07-23 15:28:28,343 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-23 15:28:28,343 INFO L369 hiAutomatonCegarLoop]: Abstraction has 108 states and 152 transitions. [2022-07-23 15:28:28,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states and 152 transitions. [2022-07-23 15:28:28,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 94. [2022-07-23 15:28:28,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 58 states have (on average 1.2241379310344827) internal successors, (71), 64 states have internal predecessors, (71), 21 states have call successors, (22), 11 states have call predecessors, (22), 15 states have return successors, (33), 18 states have call predecessors, (33), 19 states have call successors, (33) [2022-07-23 15:28:28,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 126 transitions. [2022-07-23 15:28:28,369 INFO L392 hiAutomatonCegarLoop]: Abstraction has 94 states and 126 transitions. [2022-07-23 15:28:28,369 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-23 15:28:28,370 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-23 15:28:28,372 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-07-23 15:28:28,372 INFO L87 Difference]: Start difference. First operand 94 states and 126 transitions. Second operand has 12 states, 9 states have (on average 2.111111111111111) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-07-23 15:28:28,504 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-23 15:28:28,504 INFO L93 Difference]: Finished difference Result 123 states and 165 transitions. [2022-07-23 15:28:28,505 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-23 15:28:28,505 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 123 states and 165 transitions. [2022-07-23 15:28:28,513 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-23 15:28:28,521 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 123 states to 118 states and 160 transitions. [2022-07-23 15:28:28,522 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 77 [2022-07-23 15:28:28,522 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 77 [2022-07-23 15:28:28,522 INFO L73 IsDeterministic]: Start isDeterministic. Operand 118 states and 160 transitions. [2022-07-23 15:28:28,523 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-23 15:28:28,523 INFO L369 hiAutomatonCegarLoop]: Abstraction has 118 states and 160 transitions. [2022-07-23 15:28:28,524 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states and 160 transitions. [2022-07-23 15:28:28,537 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 106. [2022-07-23 15:28:28,538 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 66 states have (on average 1.196969696969697) internal successors, (79), 72 states have internal predecessors, (79), 24 states have call successors, (25), 13 states have call predecessors, (25), 16 states have return successors, (37), 20 states have call predecessors, (37), 22 states have call successors, (37) [2022-07-23 15:28:28,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 141 transitions. [2022-07-23 15:28:28,539 INFO L392 hiAutomatonCegarLoop]: Abstraction has 106 states and 141 transitions. [2022-07-23 15:28:28,539 INFO L374 stractBuchiCegarLoop]: Abstraction has 106 states and 141 transitions. [2022-07-23 15:28:28,539 INFO L287 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2022-07-23 15:28:28,539 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 141 transitions. [2022-07-23 15:28:28,540 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-23 15:28:28,540 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-23 15:28:28,540 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-23 15:28:28,541 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-23 15:28:28,541 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2022-07-23 15:28:28,541 INFO L752 eck$LassoCheckResult]: Stem: 805#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(14, 2);call #Ultimate.allocInit(12, 3); 806#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 := 9; 788#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 814#fibonacciENTRY ~n := #in~n; 799#L17 assume !(~n < 1); 800#L19 assume !(1 == ~n); 795#L22 call #t~ret4 := fibonacci(~n - 1);< 794#fibonacciENTRY ~n := #in~n; 796#L17 assume !(~n < 1); 852#L19 assume !(1 == ~n); 803#L22 call #t~ret4 := fibonacci(~n - 1);< 804#fibonacciENTRY ~n := #in~n; 850#L17 assume !(~n < 1); 848#L19 assume !(1 == ~n); 843#L22 call #t~ret4 := fibonacci(~n - 1);< 804#fibonacciENTRY ~n := #in~n; 850#L17 assume !(~n < 1); 848#L19 assume !(1 == ~n); 843#L22 call #t~ret4 := fibonacci(~n - 1);< 804#fibonacciENTRY ~n := #in~n; 851#L17 assume !(~n < 1); 849#L19 assume 1 == ~n;#res := 1; 847#fibonacciFINAL assume true; 846#fibonacciEXIT >#29#return; 791#L22-1 call #t~ret5 := fibonacci(~n - 2);< 844#fibonacciENTRY ~n := #in~n; 797#L17 assume ~n < 1;#res := 0; 798#fibonacciFINAL assume true; 888#fibonacciEXIT >#31#return; 887#L22-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 885#fibonacciFINAL assume true; 877#fibonacciEXIT >#29#return; 819#L22-1 [2022-07-23 15:28:28,541 INFO L754 eck$LassoCheckResult]: Loop: 819#L22-1 call #t~ret5 := fibonacci(~n - 2);< 802#fibonacciENTRY ~n := #in~n; 882#L17 assume !(~n < 1); 818#L19 assume !(1 == ~n); 821#L22 call #t~ret4 := fibonacci(~n - 1);< 802#fibonacciENTRY ~n := #in~n; 882#L17 assume !(~n < 1); 818#L19 assume 1 == ~n;#res := 1; 822#fibonacciFINAL assume true; 874#fibonacciEXIT >#29#return; 819#L22-1 [2022-07-23 15:28:28,541 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:28,542 INFO L85 PathProgramCache]: Analyzing trace with hash -1460678817, now seen corresponding path program 1 times [2022-07-23 15:28:28,542 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:28,542 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [172091764] [2022-07-23 15:28:28,542 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:28,542 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:28,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:28,616 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2022-07-23 15:28:28,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:28,672 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-23 15:28:28,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:28,696 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-23 15:28:28,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:28,701 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-07-23 15:28:28,701 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-23 15:28:28,701 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [172091764] [2022-07-23 15:28:28,702 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [172091764] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-23 15:28:28,702 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2136240513] [2022-07-23 15:28:28,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:28,702 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-23 15:28:28,702 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:28,703 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-23 15:28:28,730 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Waiting until timeout for monitored process [2022-07-23 15:28:28,746 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:28,747 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-23 15:28:28,749 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:28,806 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 45 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-07-23 15:28:28,806 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-23 15:28:29,028 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 47 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-07-23 15:28:29,028 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2136240513] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-23 15:28:29,028 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-23 15:28:29,029 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 12] total 22 [2022-07-23 15:28:29,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1877212023] [2022-07-23 15:28:29,029 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-23 15:28:29,029 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-23 15:28:29,029 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:29,029 INFO L85 PathProgramCache]: Analyzing trace with hash -1409277793, now seen corresponding path program 2 times [2022-07-23 15:28:29,030 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:29,030 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2038874088] [2022-07-23 15:28:29,030 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:29,030 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:29,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:29,033 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-23 15:28:29,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:29,036 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-23 15:28:29,160 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:29,160 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:29,160 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:29,160 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:29,160 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-23 15:28:29,160 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:29,161 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:29,161 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:29,161 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2022-07-23 15:28:29,161 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:29,161 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:29,162 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:29,168 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:29,170 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:29,173 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:29,209 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:29,210 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-23 15:28:29,210 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:29,210 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:29,211 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:29,220 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:29,221 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:29,221 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2022-07-23 15:28:29,244 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:29,244 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:29,244 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:29,245 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:29,246 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2022-07-23 15:28:29,247 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-23 15:28:29,247 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:29,587 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-23 15:28:29,592 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Ended with exit code 0 [2022-07-23 15:28:29,592 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:29,592 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:29,592 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:29,592 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:29,592 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-23 15:28:29,592 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:29,592 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:29,593 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:29,593 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration4_Loop [2022-07-23 15:28:29,593 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:29,593 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:29,593 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:29,595 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:29,597 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:29,602 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:29,639 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:29,640 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-23 15:28:29,640 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:29,640 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:29,641 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:29,642 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2022-07-23 15:28:29,643 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:29,649 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:29,649 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:29,650 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:29,650 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:29,650 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:29,650 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:29,650 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:29,651 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:29,668 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Ended with exit code 0 [2022-07-23 15:28:29,668 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:29,668 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:29,669 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:29,669 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2022-07-23 15:28:29,671 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:29,677 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:29,677 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:29,677 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:29,677 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:29,677 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:29,678 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:29,678 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:29,688 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:29,703 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Ended with exit code 0 [2022-07-23 15:28:29,704 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:29,704 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:29,705 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:29,706 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2022-07-23 15:28:29,707 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:29,713 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:29,713 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:29,713 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:29,713 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:29,713 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:29,714 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:29,714 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:29,723 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-23 15:28:29,726 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-23 15:28:29,726 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-23 15:28:29,726 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:29,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:29,728 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:29,730 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-23 15:28:29,730 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-23 15:28:29,730 INFO L513 LassoAnalysis]: Proved termination. [2022-07-23 15:28:29,730 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2022-07-23 15:28:29,730 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2022-07-23 15:28:29,746 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:29,747 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-23 15:28:29,755 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:29,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:29,797 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-23 15:28:29,799 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:29,980 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:29,981 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-23 15:28:29,982 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:30,053 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:30,054 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2022-07-23 15:28:30,054 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 106 states and 141 transitions. cyclomatic complexity: 40 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-07-23 15:28:30,247 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 106 states and 141 transitions. cyclomatic complexity: 40. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 175 states and 233 transitions. Complement of second has 33 states. [2022-07-23 15:28:30,248 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 9 states 2 stem states 6 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:30,249 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-07-23 15:28:30,249 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 37 transitions. [2022-07-23 15:28:30,249 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 32 letters. Loop has 10 letters. [2022-07-23 15:28:30,250 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:30,250 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-23 15:28:30,259 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:30,299 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:30,300 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-23 15:28:30,302 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:30,410 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Ended with exit code 0 [2022-07-23 15:28:30,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:30,496 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-23 15:28:30,497 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:30,563 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:30,564 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 6 loop predicates [2022-07-23 15:28:30,564 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 106 states and 141 transitions. cyclomatic complexity: 40 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-07-23 15:28:30,687 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 106 states and 141 transitions. cyclomatic complexity: 40. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 300 states and 403 transitions. Complement of second has 25 states. [2022-07-23 15:28:30,688 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:30,689 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-07-23 15:28:30,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 24 transitions. [2022-07-23 15:28:30,689 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 24 transitions. Stem has 32 letters. Loop has 10 letters. [2022-07-23 15:28:30,689 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:30,689 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-23 15:28:30,697 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:30,737 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:30,738 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-23 15:28:30,740 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:30,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:30,908 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-23 15:28:30,909 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:30,967 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:30,968 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 6 loop predicates [2022-07-23 15:28:30,968 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 106 states and 141 transitions. cyclomatic complexity: 40 Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-07-23 15:28:31,178 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 106 states and 141 transitions. cyclomatic complexity: 40. Second operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) Result 858 states and 1136 transitions. Complement of second has 130 states. [2022-07-23 15:28:31,183 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 9 states 2 stem states 6 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:31,185 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 5 states have internal predecessors, (19), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (4), 2 states have call predecessors, (4), 3 states have call successors, (4) [2022-07-23 15:28:31,186 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 42 transitions. [2022-07-23 15:28:31,186 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 42 transitions. Stem has 32 letters. Loop has 10 letters. [2022-07-23 15:28:31,188 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:31,188 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 42 transitions. Stem has 42 letters. Loop has 10 letters. [2022-07-23 15:28:31,190 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:31,190 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 42 transitions. Stem has 32 letters. Loop has 20 letters. [2022-07-23 15:28:31,190 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:31,191 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 858 states and 1136 transitions. [2022-07-23 15:28:31,206 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 44 [2022-07-23 15:28:31,215 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 858 states to 430 states and 620 transitions. [2022-07-23 15:28:31,215 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 163 [2022-07-23 15:28:31,218 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 188 [2022-07-23 15:28:31,218 INFO L73 IsDeterministic]: Start isDeterministic. Operand 430 states and 620 transitions. [2022-07-23 15:28:31,218 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-23 15:28:31,218 INFO L369 hiAutomatonCegarLoop]: Abstraction has 430 states and 620 transitions. [2022-07-23 15:28:31,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 430 states and 620 transitions. [2022-07-23 15:28:31,240 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 430 to 352. [2022-07-23 15:28:31,241 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 352 states, 221 states have (on average 1.1990950226244343) internal successors, (265), 235 states have internal predecessors, (265), 75 states have call successors, (84), 46 states have call predecessors, (84), 56 states have return successors, (136), 70 states have call predecessors, (136), 71 states have call successors, (136) [2022-07-23 15:28:31,244 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 352 states to 352 states and 485 transitions. [2022-07-23 15:28:31,244 INFO L392 hiAutomatonCegarLoop]: Abstraction has 352 states and 485 transitions. [2022-07-23 15:28:31,244 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-23 15:28:31,245 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-07-23 15:28:31,245 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=100, Invalid=406, Unknown=0, NotChecked=0, Total=506 [2022-07-23 15:28:31,245 INFO L87 Difference]: Start difference. First operand 352 states and 485 transitions. Second operand has 23 states, 19 states have (on average 2.1578947368421053) internal successors, (41), 15 states have internal predecessors, (41), 13 states have call successors, (13), 7 states have call predecessors, (13), 3 states have return successors, (7), 3 states have call predecessors, (7), 7 states have call successors, (7) [2022-07-23 15:28:31,598 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-23 15:28:31,598 INFO L93 Difference]: Finished difference Result 683 states and 994 transitions. [2022-07-23 15:28:31,598 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-07-23 15:28:31,599 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 683 states and 994 transitions. [2022-07-23 15:28:31,608 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2022-07-23 15:28:31,617 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 683 states to 652 states and 949 transitions. [2022-07-23 15:28:31,617 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 282 [2022-07-23 15:28:31,618 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 285 [2022-07-23 15:28:31,618 INFO L73 IsDeterministic]: Start isDeterministic. Operand 652 states and 949 transitions. [2022-07-23 15:28:31,618 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-23 15:28:31,618 INFO L369 hiAutomatonCegarLoop]: Abstraction has 652 states and 949 transitions. [2022-07-23 15:28:31,618 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 652 states and 949 transitions. [2022-07-23 15:28:31,635 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 652 to 622. [2022-07-23 15:28:31,637 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 622 states, 380 states have (on average 1.1631578947368422) internal successors, (442), 400 states have internal predecessors, (442), 151 states have call successors, (165), 76 states have call predecessors, (165), 91 states have return successors, (305), 145 states have call predecessors, (305), 141 states have call successors, (305) [2022-07-23 15:28:31,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 622 states to 622 states and 912 transitions. [2022-07-23 15:28:31,642 INFO L392 hiAutomatonCegarLoop]: Abstraction has 622 states and 912 transitions. [2022-07-23 15:28:31,642 INFO L374 stractBuchiCegarLoop]: Abstraction has 622 states and 912 transitions. [2022-07-23 15:28:31,643 INFO L287 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2022-07-23 15:28:31,643 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 622 states and 912 transitions. [2022-07-23 15:28:31,646 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2022-07-23 15:28:31,647 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-23 15:28:31,647 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-23 15:28:31,648 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [10, 10, 9, 9, 1, 1, 1, 1, 1, 1, 1] [2022-07-23 15:28:31,648 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-23 15:28:31,648 INFO L752 eck$LassoCheckResult]: Stem: 4173#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(14, 2);call #Ultimate.allocInit(12, 3); 4174#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 := 9; 4183#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 4184#fibonacciENTRY ~n := #in~n; 4228#L17 assume !(~n < 1); 4227#L19 assume !(1 == ~n); 4223#L22 call #t~ret4 := fibonacci(~n - 1);< 4226#fibonacciENTRY ~n := #in~n; 4225#L17 assume !(~n < 1); 4224#L19 assume !(1 == ~n); 4219#L22 call #t~ret4 := fibonacci(~n - 1);< 4222#fibonacciENTRY ~n := #in~n; 4221#L17 assume !(~n < 1); 4220#L19 assume !(1 == ~n); 4215#L22 call #t~ret4 := fibonacci(~n - 1);< 4218#fibonacciENTRY ~n := #in~n; 4217#L17 assume !(~n < 1); 4216#L19 assume !(1 == ~n); 4211#L22 call #t~ret4 := fibonacci(~n - 1);< 4214#fibonacciENTRY ~n := #in~n; 4213#L17 assume !(~n < 1); 4212#L19 assume !(1 == ~n); 4208#L22 call #t~ret4 := fibonacci(~n - 1);< 4210#fibonacciENTRY ~n := #in~n; 4209#L17 assume !(~n < 1); 4207#L19 assume !(1 == ~n); 4203#L22 call #t~ret4 := fibonacci(~n - 1);< 4202#fibonacciENTRY ~n := #in~n; 4205#L17 assume !(~n < 1); 4579#L19 assume !(1 == ~n); 4204#L22 call #t~ret4 := fibonacci(~n - 1);< 4202#fibonacciENTRY ~n := #in~n; 4206#L17 assume !(~n < 1); 4609#L19 assume 1 == ~n;#res := 1; 4608#fibonacciFINAL assume true; 4605#fibonacciEXIT >#29#return; 4384#L22-1 call #t~ret5 := fibonacci(~n - 2);< 4386#fibonacciENTRY ~n := #in~n; 4684#L17 assume !(~n < 1); 4618#L19 assume !(1 == ~n); 4619#L22 call #t~ret4 := fibonacci(~n - 1);< 4630#fibonacciENTRY ~n := #in~n; 4681#L17 assume !(~n < 1); 4634#L19 assume !(1 == ~n); 4635#L22 call #t~ret4 := fibonacci(~n - 1);< 4650#fibonacciENTRY [2022-07-23 15:28:31,648 INFO L754 eck$LassoCheckResult]: Loop: 4650#fibonacciENTRY ~n := #in~n; 4665#L17 assume !(~n < 1); 4662#L19 assume !(1 == ~n); 4647#L22 call #t~ret4 := fibonacci(~n - 1);< 4650#fibonacciENTRY [2022-07-23 15:28:31,649 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:31,649 INFO L85 PathProgramCache]: Analyzing trace with hash -1413084929, now seen corresponding path program 1 times [2022-07-23 15:28:31,649 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:31,649 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [222043438] [2022-07-23 15:28:31,649 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:31,649 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:31,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:31,802 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2022-07-23 15:28:31,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:31,838 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-23 15:28:31,838 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-23 15:28:31,838 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [222043438] [2022-07-23 15:28:31,838 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [222043438] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-23 15:28:31,838 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [69898188] [2022-07-23 15:28:31,838 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:31,839 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-23 15:28:31,839 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:31,840 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-23 15:28:31,860 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Waiting until timeout for monitored process [2022-07-23 15:28:31,893 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:31,894 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 18 conjunts are in the unsatisfiable core [2022-07-23 15:28:31,896 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:31,961 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-23 15:28:31,961 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-23 15:28:32,065 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 62 proven. 105 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-23 15:28:32,066 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [69898188] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-23 15:28:32,066 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-23 15:28:32,066 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19, 19] total 21 [2022-07-23 15:28:32,066 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [683056628] [2022-07-23 15:28:32,066 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-23 15:28:32,066 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-23 15:28:32,067 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:32,067 INFO L85 PathProgramCache]: Analyzing trace with hash 927641, now seen corresponding path program 2 times [2022-07-23 15:28:32,067 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:32,067 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1121757700] [2022-07-23 15:28:32,067 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:32,067 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:32,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:32,069 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-23 15:28:32,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:32,071 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-23 15:28:32,101 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:32,102 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:32,102 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:32,102 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:32,102 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-23 15:28:32,102 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:32,102 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:32,102 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:32,102 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2022-07-23 15:28:32,102 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:32,102 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:32,102 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,104 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,109 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,110 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,112 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,139 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:32,139 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-23 15:28:32,139 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:32,139 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:32,140 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) [2022-07-23 15:28:32,142 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 [2022-07-23 15:28:32,143 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:32,143 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:32,164 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:32,164 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_~n=0} Honda state: {fibonacci_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:32,189 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 [2022-07-23 15:28:32,189 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:32,189 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:32,190 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:32,191 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2022-07-23 15:28:32,192 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:32,192 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:32,240 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:32,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:32,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:32,241 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:32,243 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2022-07-23 15:28:32,244 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-23 15:28:32,244 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:32,295 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-23 15:28:32,303 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:32,303 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:32,303 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:32,304 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:32,304 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:32,304 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-23 15:28:32,304 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:32,304 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:32,304 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:32,304 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration5_Loop [2022-07-23 15:28:32,304 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:32,304 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:32,305 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,307 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,313 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,315 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,317 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:32,355 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:32,355 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-23 15:28:32,356 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:32,356 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:32,360 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:32,361 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2022-07-23 15:28:32,362 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:32,370 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:32,370 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:32,370 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:32,371 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:32,371 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:32,371 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:32,371 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:32,373 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:32,389 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:32,390 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:32,390 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:32,390 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:32,393 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:32,394 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2022-07-23 15:28:32,399 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:32,399 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:32,399 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:32,399 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:32,399 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:32,400 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:32,400 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:32,401 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-23 15:28:32,403 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2022-07-23 15:28:32,403 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2022-07-23 15:28:32,404 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:32,404 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:32,405 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:32,406 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2022-07-23 15:28:32,407 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-23 15:28:32,407 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-23 15:28:32,408 INFO L513 LassoAnalysis]: Proved termination. [2022-07-23 15:28:32,408 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_#in~n) = 1*fibonacci_#in~n Supporting invariants [] [2022-07-23 15:28:32,424 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:32,424 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-23 15:28:32,433 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:32,497 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:32,500 INFO L263 TraceCheckSpWp]: Trace formula consists of 425 conjuncts, 24 conjunts are in the unsatisfiable core [2022-07-23 15:28:32,502 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:32,609 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:32,610 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-23 15:28:32,611 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:32,634 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:32,634 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2022-07-23 15:28:32,635 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 622 states and 912 transitions. cyclomatic complexity: 300 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:32,699 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 622 states and 912 transitions. cyclomatic complexity: 300. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 644 states and 934 transitions. Complement of second has 13 states. [2022-07-23 15:28:32,700 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:32,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:32,701 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 13 transitions. [2022-07-23 15:28:32,701 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2022-07-23 15:28:32,701 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:32,701 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-23 15:28:32,711 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:32,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:32,773 INFO L263 TraceCheckSpWp]: Trace formula consists of 425 conjuncts, 24 conjunts are in the unsatisfiable core [2022-07-23 15:28:32,775 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:32,867 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:32,920 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:32,921 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-23 15:28:32,922 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:32,948 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:32,949 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2022-07-23 15:28:32,949 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 622 states and 912 transitions. cyclomatic complexity: 300 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:33,008 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 622 states and 912 transitions. cyclomatic complexity: 300. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 644 states and 934 transitions. Complement of second has 13 states. [2022-07-23 15:28:33,009 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:33,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:33,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 13 transitions. [2022-07-23 15:28:33,011 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 13 transitions. Stem has 45 letters. Loop has 4 letters. [2022-07-23 15:28:33,011 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:33,011 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-23 15:28:33,020 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:33,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:33,082 INFO L263 TraceCheckSpWp]: Trace formula consists of 425 conjuncts, 24 conjunts are in the unsatisfiable core [2022-07-23 15:28:33,083 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:33,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:33,195 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-23 15:28:33,196 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:33,219 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:33,221 INFO L152 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2022-07-23 15:28:33,222 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 622 states and 912 transitions. cyclomatic complexity: 300 Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:33,302 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 622 states and 912 transitions. cyclomatic complexity: 300. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 839 states and 1152 transitions. Complement of second has 14 states. [2022-07-23 15:28:33,302 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 5 states 2 stem states 2 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:33,303 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:33,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 21 transitions. [2022-07-23 15:28:33,303 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 21 transitions. Stem has 45 letters. Loop has 4 letters. [2022-07-23 15:28:33,304 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:33,304 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 21 transitions. Stem has 49 letters. Loop has 4 letters. [2022-07-23 15:28:33,305 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:33,305 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 5 states and 21 transitions. Stem has 45 letters. Loop has 8 letters. [2022-07-23 15:28:33,307 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:33,307 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 839 states and 1152 transitions. [2022-07-23 15:28:33,316 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2022-07-23 15:28:33,324 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 839 states to 684 states and 985 transitions. [2022-07-23 15:28:33,324 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 241 [2022-07-23 15:28:33,325 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 250 [2022-07-23 15:28:33,325 INFO L73 IsDeterministic]: Start isDeterministic. Operand 684 states and 985 transitions. [2022-07-23 15:28:33,325 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-23 15:28:33,326 INFO L369 hiAutomatonCegarLoop]: Abstraction has 684 states and 985 transitions. [2022-07-23 15:28:33,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 684 states and 985 transitions. [2022-07-23 15:28:33,343 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 684 to 654. [2022-07-23 15:28:33,344 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 654 states, 407 states have (on average 1.1523341523341524) internal successors, (469), 432 states have internal predecessors, (469), 151 states have call successors, (165), 76 states have call predecessors, (165), 96 states have return successors, (315), 145 states have call predecessors, (315), 141 states have call successors, (315) [2022-07-23 15:28:33,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 654 states to 654 states and 949 transitions. [2022-07-23 15:28:33,349 INFO L392 hiAutomatonCegarLoop]: Abstraction has 654 states and 949 transitions. [2022-07-23 15:28:33,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-23 15:28:33,349 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-07-23 15:28:33,349 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=92, Invalid=328, Unknown=0, NotChecked=0, Total=420 [2022-07-23 15:28:33,349 INFO L87 Difference]: Start difference. First operand 654 states and 949 transitions. Second operand has 21 states, 20 states have (on average 1.8) internal successors, (36), 14 states have internal predecessors, (36), 9 states have call successors, (10), 9 states have call predecessors, (10), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:33,655 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-23 15:28:33,656 INFO L93 Difference]: Finished difference Result 799 states and 1195 transitions. [2022-07-23 15:28:33,656 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-07-23 15:28:33,657 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 799 states and 1195 transitions. [2022-07-23 15:28:33,668 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2022-07-23 15:28:33,680 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 799 states to 778 states and 1163 transitions. [2022-07-23 15:28:33,680 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 289 [2022-07-23 15:28:33,681 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 292 [2022-07-23 15:28:33,681 INFO L73 IsDeterministic]: Start isDeterministic. Operand 778 states and 1163 transitions. [2022-07-23 15:28:33,681 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-23 15:28:33,681 INFO L369 hiAutomatonCegarLoop]: Abstraction has 778 states and 1163 transitions. [2022-07-23 15:28:33,682 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 778 states and 1163 transitions. [2022-07-23 15:28:33,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 778 to 710. [2022-07-23 15:28:33,702 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 710 states, 441 states have (on average 1.145124716553288) internal successors, (505), 470 states have internal predecessors, (505), 169 states have call successors, (185), 86 states have call predecessors, (185), 100 states have return successors, (341), 153 states have call predecessors, (341), 159 states have call successors, (341) [2022-07-23 15:28:33,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 710 states to 710 states and 1031 transitions. [2022-07-23 15:28:33,707 INFO L392 hiAutomatonCegarLoop]: Abstraction has 710 states and 1031 transitions. [2022-07-23 15:28:33,707 INFO L374 stractBuchiCegarLoop]: Abstraction has 710 states and 1031 transitions. [2022-07-23 15:28:33,707 INFO L287 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2022-07-23 15:28:33,707 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 710 states and 1031 transitions. [2022-07-23 15:28:33,711 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2022-07-23 15:28:33,712 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-23 15:28:33,712 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-23 15:28:33,715 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [12, 12, 11, 10, 1, 1, 1, 1, 1, 1, 1] [2022-07-23 15:28:33,715 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-23 15:28:33,716 INFO L752 eck$LassoCheckResult]: Stem: 9192#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(14, 2);call #Ultimate.allocInit(12, 3); 9193#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 := 9; 9202#L29 call main_#t~ret6#1 := fibonacci(main_~x~0#1);< 9203#fibonacciENTRY ~n := #in~n; 9312#L17 assume !(~n < 1); 9308#L19 assume !(1 == ~n); 9278#L22 call #t~ret4 := fibonacci(~n - 1);< 9295#fibonacciENTRY ~n := #in~n; 9660#L17 assume !(~n < 1); 9659#L19 assume !(1 == ~n); 9281#L22 call #t~ret4 := fibonacci(~n - 1);< 9282#fibonacciENTRY ~n := #in~n; 9372#L17 assume !(~n < 1); 9370#L19 assume !(1 == ~n); 9316#L22 call #t~ret4 := fibonacci(~n - 1);< 9318#fibonacciENTRY ~n := #in~n; 9618#L17 assume !(~n < 1); 9617#L19 assume !(1 == ~n); 9365#L22 call #t~ret4 := fibonacci(~n - 1);< 9367#fibonacciENTRY ~n := #in~n; 9620#L17 assume !(~n < 1); 9619#L19 assume !(1 == ~n); 9325#L22 call #t~ret4 := fibonacci(~n - 1);< 9369#fibonacciENTRY ~n := #in~n; 9459#L17 assume !(~n < 1); 9450#L19 assume !(1 == ~n); 9441#L22 call #t~ret4 := fibonacci(~n - 1);< 9446#fibonacciENTRY ~n := #in~n; 9544#L17 assume !(~n < 1); 9543#L19 assume !(1 == ~n); 9383#L22 call #t~ret4 := fibonacci(~n - 1);< 9489#fibonacciENTRY ~n := #in~n; 9553#L17 assume !(~n < 1); 9490#L19 assume !(1 == ~n); 9380#L22 call #t~ret4 := fibonacci(~n - 1);< 9489#fibonacciENTRY ~n := #in~n; 9556#L17 assume !(~n < 1); 9750#L19 assume 1 == ~n;#res := 1; 9749#fibonacciFINAL assume true; 9747#fibonacciEXIT >#29#return; 9743#L22-1 call #t~ret5 := fibonacci(~n - 2);< 9744#fibonacciENTRY ~n := #in~n; 9869#L17 assume !(~n < 1); 9764#L19 assume !(1 == ~n); 9766#L22 call #t~ret4 := fibonacci(~n - 1);< 9804#fibonacciENTRY ~n := #in~n; 9851#L17 assume !(~n < 1); 9849#L19 assume !(1 == ~n); 9208#L22 call #t~ret4 := fibonacci(~n - 1);< 9217#fibonacciENTRY ~n := #in~n; 9218#L17 assume !(~n < 1); 9861#L19 assume !(1 == ~n); 9209#L22 [2022-07-23 15:28:33,716 INFO L754 eck$LassoCheckResult]: Loop: 9209#L22 call #t~ret4 := fibonacci(~n - 1);< 9217#fibonacciENTRY ~n := #in~n; 9218#L17 assume !(~n < 1); 9861#L19 assume !(1 == ~n); 9209#L22 [2022-07-23 15:28:33,716 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:33,716 INFO L85 PathProgramCache]: Analyzing trace with hash 1648910477, now seen corresponding path program 2 times [2022-07-23 15:28:33,717 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:33,717 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1840715539] [2022-07-23 15:28:33,717 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:33,717 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:33,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:33,919 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2022-07-23 15:28:33,921 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:33,923 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-23 15:28:33,923 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-23 15:28:33,923 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1840715539] [2022-07-23 15:28:33,923 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1840715539] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-23 15:28:33,923 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1215122054] [2022-07-23 15:28:33,923 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-23 15:28:33,924 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-23 15:28:33,924 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:33,928 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-23 15:28:33,929 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (37)] Waiting until timeout for monitored process [2022-07-23 15:28:33,968 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-23 15:28:33,968 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-23 15:28:33,969 INFO L263 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 20 conjunts are in the unsatisfiable core [2022-07-23 15:28:33,971 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:34,037 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-23 15:28:34,037 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-23 15:28:34,105 INFO L134 CoverageAnalysis]: Checked inductivity of 243 backedges. 213 proven. 24 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-07-23 15:28:34,105 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1215122054] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-23 15:28:34,105 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-23 15:28:34,105 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 21 [2022-07-23 15:28:34,106 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [916662847] [2022-07-23 15:28:34,106 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-23 15:28:34,106 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-23 15:28:34,107 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:34,107 INFO L85 PathProgramCache]: Analyzing trace with hash 1757801, now seen corresponding path program 3 times [2022-07-23 15:28:34,107 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-23 15:28:34,107 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1453033525] [2022-07-23 15:28:34,107 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-23 15:28:34,107 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-23 15:28:34,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:34,112 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-23 15:28:34,117 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-23 15:28:34,118 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-23 15:28:34,158 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:34,158 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:34,159 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:34,159 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:34,159 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-23 15:28:34,159 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:34,159 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:34,159 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:34,159 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2022-07-23 15:28:34,159 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:34,159 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:34,160 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:34,162 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:34,163 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:34,165 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:34,207 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:34,208 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-23 15:28:34,208 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:34,208 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:34,209 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:34,210 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2022-07-23 15:28:34,211 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:34,211 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:34,218 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:34,218 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret4=0} Honda state: {fibonacci_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:34,234 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 [2022-07-23 15:28:34,235 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:34,235 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:34,235 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:34,236 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2022-07-23 15:28:34,238 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:34,238 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:34,248 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:34,248 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#t~ret5=0} Honda state: {fibonacci_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:34,264 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:34,264 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:34,264 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:34,265 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) [2022-07-23 15:28:34,266 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 [2022-07-23 15:28:34,268 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:34,268 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:34,275 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-23 15:28:34,275 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibonacci_#res=0} Honda state: {fibonacci_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-23 15:28:34,291 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:34,291 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:34,291 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:34,292 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:34,293 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2022-07-23 15:28:34,294 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-23 15:28:34,294 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:34,325 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:34,326 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:34,326 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:34,327 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:34,327 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2022-07-23 15:28:34,329 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-23 15:28:34,329 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-23 15:28:38,869 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-23 15:28:38,874 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:38,875 INFO L210 LassoAnalysis]: Preferences: [2022-07-23 15:28:38,875 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-23 15:28:38,875 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-23 15:28:38,875 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-23 15:28:38,875 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-23 15:28:38,875 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:38,875 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-23 15:28:38,875 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-23 15:28:38,875 INFO L133 ssoRankerPreferences]: Filename of dumped script: Fibonacci02.c_Iteration6_Loop [2022-07-23 15:28:38,875 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-23 15:28:38,875 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-23 15:28:38,876 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:38,877 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:38,879 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:38,892 INFO L141 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA XnfConversionTechnique=BOTTOM_UP_WITH_LOCAL_SIMPLIFICATION AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2022-07-23 15:28:38,924 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-23 15:28:38,924 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-23 15:28:38,924 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:38,924 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:38,925 INFO L229 MonitoredProcess]: Starting monitored process 43 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:38,934 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:38,939 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2022-07-23 15:28:38,940 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:38,941 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:38,941 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:38,941 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:38,941 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:38,941 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:38,941 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:38,942 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:38,957 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:38,958 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:38,958 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:38,959 INFO L229 MonitoredProcess]: Starting monitored process 44 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:38,959 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Waiting until timeout for monitored process [2022-07-23 15:28:38,961 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:38,966 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:38,966 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:38,967 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:38,967 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:38,967 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:38,967 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:38,967 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:38,968 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-23 15:28:38,984 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:38,984 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:38,984 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:38,985 INFO L229 MonitoredProcess]: Starting monitored process 45 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:38,985 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Waiting until timeout for monitored process [2022-07-23 15:28:38,987 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-23 15:28:38,993 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-23 15:28:38,993 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-23 15:28:38,993 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-23 15:28:38,993 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-23 15:28:38,993 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-23 15:28:38,994 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-23 15:28:38,994 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-23 15:28:39,018 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-23 15:28:39,021 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-23 15:28:39,021 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-23 15:28:39,022 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-23 15:28:39,022 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-23 15:28:39,024 INFO L229 MonitoredProcess]: Starting monitored process 46 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-23 15:28:39,024 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Waiting until timeout for monitored process [2022-07-23 15:28:39,025 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-23 15:28:39,025 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-23 15:28:39,025 INFO L513 LassoAnalysis]: Proved termination. [2022-07-23 15:28:39,025 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibonacci_~n) = 1*fibonacci_~n Supporting invariants [] [2022-07-23 15:28:39,041 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:39,042 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-23 15:28:39,054 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:39,104 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Ended with exit code 0 [2022-07-23 15:28:39,130 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:39,132 INFO L263 TraceCheckSpWp]: Trace formula consists of 465 conjuncts, 26 conjunts are in the unsatisfiable core [2022-07-23 15:28:39,134 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:39,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:39,241 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-23 15:28:39,242 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:39,271 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:39,272 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2022-07-23 15:28:39,272 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 710 states and 1031 transitions. cyclomatic complexity: 331 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:39,326 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 710 states and 1031 transitions. cyclomatic complexity: 331. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 734 states and 1056 transitions. Complement of second has 18 states. [2022-07-23 15:28:39,327 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:39,327 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:39,328 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2022-07-23 15:28:39,328 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 52 letters. Loop has 4 letters. [2022-07-23 15:28:39,328 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:39,328 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-23 15:28:39,337 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-23 15:28:39,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:39,402 INFO L263 TraceCheckSpWp]: Trace formula consists of 465 conjuncts, 26 conjunts are in the unsatisfiable core [2022-07-23 15:28:39,404 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:39,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-23 15:28:39,507 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-23 15:28:39,508 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-23 15:28:39,533 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-07-23 15:28:39,533 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2022-07-23 15:28:39,533 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 710 states and 1031 transitions. cyclomatic complexity: 331 Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:39,612 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 710 states and 1031 transitions. cyclomatic complexity: 331. Second operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 964 states and 1378 transitions. Complement of second has 22 states. [2022-07-23 15:28:39,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2022-07-23 15:28:39,613 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 2.6) internal successors, (13), 5 states have internal predecessors, (13), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:39,614 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 16 transitions. [2022-07-23 15:28:39,614 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 16 transitions. Stem has 52 letters. Loop has 4 letters. [2022-07-23 15:28:39,615 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:39,615 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 16 transitions. Stem has 56 letters. Loop has 4 letters. [2022-07-23 15:28:39,615 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:39,615 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 16 transitions. Stem has 52 letters. Loop has 8 letters. [2022-07-23 15:28:39,615 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-23 15:28:39,616 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 964 states and 1378 transitions. [2022-07-23 15:28:39,630 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 54 [2022-07-23 15:28:39,646 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 964 states to 888 states and 1297 transitions. [2022-07-23 15:28:39,646 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 290 [2022-07-23 15:28:39,646 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 318 [2022-07-23 15:28:39,647 INFO L73 IsDeterministic]: Start isDeterministic. Operand 888 states and 1297 transitions. [2022-07-23 15:28:39,650 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-23 15:28:39,650 INFO L369 hiAutomatonCegarLoop]: Abstraction has 888 states and 1297 transitions. [2022-07-23 15:28:39,650 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 888 states and 1297 transitions. [2022-07-23 15:28:39,686 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 888 to 875. [2022-07-23 15:28:39,687 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 875 states, 551 states have (on average 1.1306715063520871) internal successors, (623), 588 states have internal predecessors, (623), 202 states have call successors, (236), 113 states have call predecessors, (236), 122 states have return successors, (421), 173 states have call predecessors, (421), 192 states have call successors, (421) [2022-07-23 15:28:39,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 875 states to 875 states and 1280 transitions. [2022-07-23 15:28:39,692 INFO L392 hiAutomatonCegarLoop]: Abstraction has 875 states and 1280 transitions. [2022-07-23 15:28:39,692 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-23 15:28:39,693 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-07-23 15:28:39,693 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=309, Unknown=0, NotChecked=0, Total=420 [2022-07-23 15:28:39,693 INFO L87 Difference]: Start difference. First operand 875 states and 1280 transitions. Second operand has 21 states, 20 states have (on average 1.75) internal successors, (35), 12 states have internal predecessors, (35), 10 states have call successors, (11), 11 states have call predecessors, (11), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-07-23 15:28:39,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-23 15:28:39,975 INFO L93 Difference]: Finished difference Result 475 states and 560 transitions. [2022-07-23 15:28:39,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-07-23 15:28:39,976 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 475 states and 560 transitions. [2022-07-23 15:28:39,979 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-23 15:28:39,979 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 475 states to 0 states and 0 transitions. [2022-07-23 15:28:39,979 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2022-07-23 15:28:39,979 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2022-07-23 15:28:39,980 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2022-07-23 15:28:39,980 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2022-07-23 15:28:39,980 INFO L369 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-23 15:28:39,980 INFO L392 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-23 15:28:39,980 INFO L374 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-23 15:28:39,980 INFO L287 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2022-07-23 15:28:39,980 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2022-07-23 15:28:39,980 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-23 15:28:39,980 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2022-07-23 15:28:39,986 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 23.07 03:28:39 BoogieIcfgContainer [2022-07-23 15:28:39,986 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2022-07-23 15:28:39,987 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2022-07-23 15:28:39,987 INFO L271 PluginConnector]: Initializing Witness Printer... [2022-07-23 15:28:39,987 INFO L275 PluginConnector]: Witness Printer initialized [2022-07-23 15:28:39,987 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.07 03:28:24" (3/4) ... [2022-07-23 15:28:39,990 INFO L140 WitnessPrinter]: No result that supports witness generation found [2022-07-23 15:28:39,990 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2022-07-23 15:28:39,990 INFO L158 Benchmark]: Toolchain (without parser) took 15755.28ms. Allocated memory was 107.0MB in the beginning and 134.2MB in the end (delta: 27.3MB). Free memory was 75.9MB in the beginning and 76.7MB in the end (delta: -785.4kB). Peak memory consumption was 26.3MB. Max. memory is 16.1GB. [2022-07-23 15:28:39,991 INFO L158 Benchmark]: CDTParser took 0.18ms. Allocated memory is still 107.0MB. Free memory is still 61.1MB. There was no memory consumed. Max. memory is 16.1GB. [2022-07-23 15:28:39,991 INFO L158 Benchmark]: CACSL2BoogieTranslator took 193.46ms. Allocated memory is still 107.0MB. Free memory was 75.9MB in the beginning and 83.2MB in the end (delta: -7.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2022-07-23 15:28:39,991 INFO L158 Benchmark]: Boogie Procedure Inliner took 26.89ms. Allocated memory is still 107.0MB. Free memory was 83.2MB in the beginning and 81.6MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2022-07-23 15:28:39,992 INFO L158 Benchmark]: Boogie Preprocessor took 19.05ms. Allocated memory is still 107.0MB. Free memory was 81.6MB in the beginning and 80.9MB in the end (delta: 733.0kB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-23 15:28:39,992 INFO L158 Benchmark]: RCFGBuilder took 237.22ms. Allocated memory is still 107.0MB. Free memory was 80.9MB in the beginning and 72.5MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2022-07-23 15:28:39,992 INFO L158 Benchmark]: BuchiAutomizer took 15265.82ms. Allocated memory was 107.0MB in the beginning and 134.2MB in the end (delta: 27.3MB). Free memory was 72.5MB in the beginning and 76.7MB in the end (delta: -4.2MB). Peak memory consumption was 25.2MB. Max. memory is 16.1GB. [2022-07-23 15:28:39,992 INFO L158 Benchmark]: Witness Printer took 3.06ms. Allocated memory is still 134.2MB. Free memory is still 76.7MB. There was no memory consumed. Max. memory is 16.1GB. [2022-07-23 15:28:39,994 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.18ms. Allocated memory is still 107.0MB. Free memory is still 61.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 193.46ms. Allocated memory is still 107.0MB. Free memory was 75.9MB in the beginning and 83.2MB in the end (delta: -7.3MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 26.89ms. Allocated memory is still 107.0MB. Free memory was 83.2MB in the beginning and 81.6MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 19.05ms. Allocated memory is still 107.0MB. Free memory was 81.6MB in the beginning and 80.9MB in the end (delta: 733.0kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 237.22ms. Allocated memory is still 107.0MB. Free memory was 80.9MB in the beginning and 72.5MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 15265.82ms. Allocated memory was 107.0MB in the beginning and 134.2MB in the end (delta: 27.3MB). Free memory was 72.5MB in the beginning and 76.7MB in the end (delta: -4.2MB). Peak memory consumption was 25.2MB. Max. memory is 16.1GB. * Witness Printer took 3.06ms. Allocated memory is still 134.2MB. Free memory is still 76.7MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (5 trivial, 3 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 deterministic module has affine ranking function n and consists of 7 locations. One nondeterministic module has affine ranking function n and consists of 9 locations. One nondeterministic module has affine ranking function \old(n) and consists of 5 locations. 5 modules have a trivial ranking function, the largest among these consists of 23 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 15.2s and 7 iterations. TraceHistogramMax:12. Analysis of lassos took 9.8s. Construction of modules took 0.9s. Büchi inclusion checks took 3.8s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 9. Automata minimization 0.2s AutomataMinimizationTime, 9 MinimizatonAttempts, 250 StatesRemovedByMinimization, 8 NontrivialMinimizations. Non-live state removal took 0.1s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 1, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 0/6 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 595 SdHoareTripleChecker+Valid, 1.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 570 mSDsluCounter, 595 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 382 mSDsCounter, 433 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1422 IncrementalHoareTripleChecker+Invalid, 1855 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 433 mSolverCounterUnsat, 213 mSDtfsCounter, 1422 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT1 conc0 concLT0 SILN0 SILU0 SILI1 SILT4 lasso0 LassoPreprocessingBenchmarks: Lassos: inital16 mio100 ax100 hnf100 lsp92 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq185 hnf93 smp79 dnf100 smp100 tf109 neg96 sie106 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 27ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 10 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 5 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 5.7s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2022-07-23 15:28:40,026 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (37)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:40,232 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (30)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:40,432 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (23)] Ended with exit code 0 [2022-07-23 15:28:40,631 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-07-23 15:28:40,833 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE