./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursive-simple/fibo_5-1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version f4b24e32 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerTermination.xml -i ../sv-benchmarks/c/recursive-simple/fibo_5-1.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 2199d5dae92fc703178378f6dd7dec10a5f129181c51bc9a88c002f6d4f76a67 --- Real Ultimate output --- This is Ultimate 0.2.2-?-f4b24e3 [2022-07-14 16:00:56,535 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-07-14 16:00:56,537 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-07-14 16:00:56,564 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-07-14 16:00:56,565 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-07-14 16:00:56,567 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-07-14 16:00:56,570 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-07-14 16:00:56,574 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-07-14 16:00:56,575 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-07-14 16:00:56,578 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-07-14 16:00:56,579 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-07-14 16:00:56,581 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-07-14 16:00:56,581 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-07-14 16:00:56,582 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-07-14 16:00:56,583 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-07-14 16:00:56,584 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-07-14 16:00:56,585 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-07-14 16:00:56,586 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-07-14 16:00:56,588 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-07-14 16:00:56,592 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-07-14 16:00:56,594 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-07-14 16:00:56,595 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-07-14 16:00:56,595 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-07-14 16:00:56,596 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-07-14 16:00:56,597 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-07-14 16:00:56,602 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-07-14 16:00:56,602 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-07-14 16:00:56,602 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-07-14 16:00:56,603 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-07-14 16:00:56,604 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-07-14 16:00:56,605 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-07-14 16:00:56,605 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-07-14 16:00:56,606 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-07-14 16:00:56,607 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-07-14 16:00:56,607 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-07-14 16:00:56,607 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-07-14 16:00:56,608 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-07-14 16:00:56,608 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-07-14 16:00:56,608 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-07-14 16:00:56,608 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-07-14 16:00:56,609 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-07-14 16:00:56,610 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-07-14 16:00:56,611 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2022-07-14 16:00:56,636 INFO L113 SettingsManager]: Loading preferences was successful [2022-07-14 16:00:56,637 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-07-14 16:00:56,637 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2022-07-14 16:00:56,637 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2022-07-14 16:00:56,638 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-07-14 16:00:56,639 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-07-14 16:00:56,639 INFO L138 SettingsManager]: * Use SBE=true [2022-07-14 16:00:56,639 INFO L136 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2022-07-14 16:00:56,639 INFO L138 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2022-07-14 16:00:56,640 INFO L138 SettingsManager]: * Use old map elimination=false [2022-07-14 16:00:56,640 INFO L138 SettingsManager]: * Use external solver (rank synthesis)=false [2022-07-14 16:00:56,640 INFO L138 SettingsManager]: * Use only trivial implications for array writes=true [2022-07-14 16:00:56,640 INFO L138 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2022-07-14 16:00:56,640 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-07-14 16:00:56,640 INFO L138 SettingsManager]: * sizeof long=4 [2022-07-14 16:00:56,641 INFO L138 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2022-07-14 16:00:56,641 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-07-14 16:00:56,642 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-07-14 16:00:56,642 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-07-14 16:00:56,642 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2022-07-14 16:00:56,642 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2022-07-14 16:00:56,642 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2022-07-14 16:00:56,642 INFO L138 SettingsManager]: * sizeof long double=12 [2022-07-14 16:00:56,642 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-07-14 16:00:56,642 INFO L138 SettingsManager]: * Assume nondeterminstic values are in range=false [2022-07-14 16:00:56,643 INFO L138 SettingsManager]: * Use constant arrays=true [2022-07-14 16:00:56,643 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2022-07-14 16:00:56,643 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-07-14 16:00:56,643 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-07-14 16:00:56,643 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-07-14 16:00:56,643 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-07-14 16:00:56,644 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-07-14 16:00:56,644 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 -> 2199d5dae92fc703178378f6dd7dec10a5f129181c51bc9a88c002f6d4f76a67 [2022-07-14 16:00:56,831 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-07-14 16:00:56,845 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-07-14 16:00:56,847 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-07-14 16:00:56,848 INFO L271 PluginConnector]: Initializing CDTParser... [2022-07-14 16:00:56,848 INFO L275 PluginConnector]: CDTParser initialized [2022-07-14 16:00:56,849 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursive-simple/fibo_5-1.c [2022-07-14 16:00:56,913 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/60db342d5/e2843993118948bb85826bf374b4141b/FLAGf70a9bfc0 [2022-07-14 16:00:57,202 INFO L306 CDTParser]: Found 1 translation units. [2022-07-14 16:00:57,203 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-1.c [2022-07-14 16:00:57,207 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/60db342d5/e2843993118948bb85826bf374b4141b/FLAGf70a9bfc0 [2022-07-14 16:00:57,637 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/60db342d5/e2843993118948bb85826bf374b4141b [2022-07-14 16:00:57,639 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-07-14 16:00:57,640 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2022-07-14 16:00:57,643 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-07-14 16:00:57,643 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-07-14 16:00:57,646 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-07-14 16:00:57,646 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,647 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4b61bc57 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57, skipping insertion in model container [2022-07-14 16:00:57,647 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,652 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-07-14 16:00:57,660 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-07-14 16:00:57,781 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-1.c[740,753] [2022-07-14 16:00:57,782 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-14 16:00:57,790 INFO L203 MainTranslator]: Completed pre-run [2022-07-14 16:00:57,800 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursive-simple/fibo_5-1.c[740,753] [2022-07-14 16:00:57,802 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-07-14 16:00:57,812 INFO L208 MainTranslator]: Completed translation [2022-07-14 16:00:57,813 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57 WrapperNode [2022-07-14 16:00:57,814 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-07-14 16:00:57,815 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2022-07-14 16:00:57,815 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2022-07-14 16:00:57,815 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2022-07-14 16:00:57,820 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,824 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,836 INFO L137 Inliner]: procedures = 13, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2022-07-14 16:00:57,836 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2022-07-14 16:00:57,837 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-07-14 16:00:57,837 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-07-14 16:00:57,837 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-07-14 16:00:57,842 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,842 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,842 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,843 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,844 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,845 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,846 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,846 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-07-14 16:00:57,847 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-07-14 16:00:57,847 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-07-14 16:00:57,847 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-07-14 16:00:57,848 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (1/1) ... [2022-07-14 16:00:57,853 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:57,859 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:57,869 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-14 16:00:57,871 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-14 16:00:57,893 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-07-14 16:00:57,894 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-07-14 16:00:57,894 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-07-14 16:00:57,894 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-07-14 16:00:57,894 INFO L130 BoogieDeclarations]: Found specification of procedure fibo [2022-07-14 16:00:57,894 INFO L138 BoogieDeclarations]: Found implementation of procedure fibo [2022-07-14 16:00:57,931 INFO L234 CfgBuilder]: Building ICFG [2022-07-14 16:00:57,932 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-07-14 16:00:58,032 INFO L275 CfgBuilder]: Performing block encoding [2022-07-14 16:00:58,043 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-07-14 16:00:58,043 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2022-07-14 16:00:58,044 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.07 04:00:58 BoogieIcfgContainer [2022-07-14 16:00:58,045 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-07-14 16:00:58,046 INFO L113 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2022-07-14 16:00:58,047 INFO L271 PluginConnector]: Initializing BuchiAutomizer... [2022-07-14 16:00:58,049 INFO L275 PluginConnector]: BuchiAutomizer initialized [2022-07-14 16:00:58,049 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-14 16:00:58,050 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 14.07 04:00:57" (1/3) ... [2022-07-14 16:00:58,051 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1e98cb1a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 14.07 04:00:58, skipping insertion in model container [2022-07-14 16:00:58,051 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-14 16:00:58,051 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.07 04:00:57" (2/3) ... [2022-07-14 16:00:58,052 INFO L205 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@1e98cb1a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 14.07 04:00:58, skipping insertion in model container [2022-07-14 16:00:58,052 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2022-07-14 16:00:58,052 INFO L185 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.07 04:00:58" (3/3) ... [2022-07-14 16:00:58,053 INFO L354 chiAutomizerObserver]: Analyzing ICFG fibo_5-1.c [2022-07-14 16:00:58,136 INFO L255 stractBuchiCegarLoop]: Interprodecural is true [2022-07-14 16:00:58,136 INFO L256 stractBuchiCegarLoop]: Hoare is false [2022-07-14 16:00:58,136 INFO L257 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2022-07-14 16:00:58,136 INFO L258 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2022-07-14 16:00:58,136 INFO L259 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2022-07-14 16:00:58,137 INFO L260 stractBuchiCegarLoop]: Difference is false [2022-07-14 16:00:58,137 INFO L261 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2022-07-14 16:00:58,138 INFO L265 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2022-07-14 16:00:58,153 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-14 16:00:58,170 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:00:58,172 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-14 16:00:58,172 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-14 16:00:58,177 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2022-07-14 16:00:58,182 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-14 16:00:58,183 INFO L287 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2022-07-14 16:00:58,183 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-07-14 16:00:58,185 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:00:58,185 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-14 16:00:58,186 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-14 16:00:58,186 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2022-07-14 16:00:58,186 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-14 16:00:58,192 INFO L752 eck$LassoCheckResult]: Stem: 3#ULTIMATE.startENTRYtrue assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 12#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 5#L27true call main_#t~ret6#1 := fibo(main_~x~0#1);< 6#fiboENTRYtrue [2022-07-14 16:00:58,193 INFO L754 eck$LassoCheckResult]: Loop: 6#fiboENTRYtrue ~n := #in~n; 7#L8true assume !(~n < 1); 9#L10true assume !(1 == ~n); 14#L13true call #t~ret4 := fibo(~n - 1);< 6#fiboENTRYtrue [2022-07-14 16:00:58,201 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:00:58,201 INFO L85 PathProgramCache]: Analyzing trace with hash 29883, now seen corresponding path program 1 times [2022-07-14 16:00:58,207 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:00:58,208 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [646781708] [2022-07-14 16:00:58,208 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:00:58,209 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:00:58,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:00:58,283 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-14 16:00:58,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:00:58,313 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-14 16:00:58,315 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:00:58,315 INFO L85 PathProgramCache]: Analyzing trace with hash 1450956, now seen corresponding path program 1 times [2022-07-14 16:00:58,315 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:00:58,315 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1186923198] [2022-07-14 16:00:58,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:00:58,316 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:00:58,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:00:58,320 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-14 16:00:58,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:00:58,323 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-14 16:00:58,324 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:00:58,325 INFO L85 PathProgramCache]: Analyzing trace with hash 1828301702, now seen corresponding path program 1 times [2022-07-14 16:00:58,325 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:00:58,325 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1561613317] [2022-07-14 16:00:58,325 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:00:58,325 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:00:58,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:00:58,333 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-14 16:00:58,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:00:58,341 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-14 16:00:58,413 INFO L210 LassoAnalysis]: Preferences: [2022-07-14 16:00:58,414 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-14 16:00:58,414 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-14 16:00:58,414 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-14 16:00:58,414 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-14 16:00:58,415 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,415 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-14 16:00:58,415 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-14 16:00:58,415 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration1_Loop [2022-07-14 16:00:58,415 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-14 16:00:58,416 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-14 16:00:58,426 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-14 16:00:58,431 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-14 16:00:58,434 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-14 16:00:58,439 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-14 16:00:58,446 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-14 16:00:58,481 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-14 16:00:58,482 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-14 16:00:58,483 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,483 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,485 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-14 16:00:58,486 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-14 16:00:58,487 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:00:58,487 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:00:58,504 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-14 16:00:58,504 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-14 16:00:58,520 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2022-07-14 16:00:58,520 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,521 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,522 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-14 16:00:58,523 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-14 16:00:58,526 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:00:58,526 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:00:58,547 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-14 16:00:58,548 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-14 16:00:58,564 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-14 16:00:58,564 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,564 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,566 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-14 16:00:58,570 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-14 16:00:58,571 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:00:58,571 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:00:58,591 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-14 16:00:58,591 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_~n=0} Honda state: {fibo_~n=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-14 16:00:58,607 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2022-07-14 16:00:58,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,607 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,608 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-14 16:00:58,610 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-14 16:00:58,611 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:00:58,611 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:00:58,635 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-14 16:00:58,635 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,636 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,637 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-14 16:00:58,637 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-14 16:00:58,640 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-14 16:00:58,640 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:00:58,692 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-14 16:00:58,695 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Ended with exit code 0 [2022-07-14 16:00:58,695 INFO L210 LassoAnalysis]: Preferences: [2022-07-14 16:00:58,695 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-14 16:00:58,695 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-14 16:00:58,695 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-14 16:00:58,695 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-14 16:00:58,695 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,695 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-14 16:00:58,695 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-14 16:00:58,695 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration1_Loop [2022-07-14 16:00:58,695 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-14 16:00:58,695 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-14 16:00:58,696 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-14 16:00:58,701 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-14 16:00:58,703 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-14 16:00:58,705 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-14 16:00:58,710 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-14 16:00:58,759 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-14 16:00:58,770 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-14 16:00:58,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,773 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-14 16:00:58,777 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-14 16:00:58,778 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-14 16:00:58,784 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:00:58,784 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:00:58,784 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:00:58,784 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:00:58,785 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:00:58,786 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:00:58,786 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:00:58,804 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-14 16:00:58,822 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-14 16:00:58,823 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,823 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,824 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-14 16:00:58,826 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-14 16:00:58,828 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-14 16:00:58,833 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:00:58,833 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:00:58,833 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:00:58,834 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:00:58,834 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:00:58,835 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:00:58,835 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:00:58,851 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-14 16:00:58,867 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-14 16:00:58,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,869 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,870 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-14 16:00:58,871 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-14 16:00:58,873 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2022-07-14 16:00:58,878 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:00:58,878 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:00:58,879 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:00:58,879 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:00:58,879 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:00:58,879 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:00:58,879 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:00:58,880 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-14 16:00:58,902 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-14 16:00:58,902 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,902 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,904 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-14 16:00:58,908 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-14 16:00:58,909 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-14 16:00:58,916 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:00:58,916 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:00:58,916 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:00:58,916 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:00:58,916 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:00:58,921 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:00:58,921 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:00:58,926 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-14 16:00:58,931 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-14 16:00:58,931 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-14 16:00:58,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:58,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:58,944 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-14 16:00:58,944 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-14 16:00:58,984 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-14 16:00:58,984 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-14 16:00:58,984 INFO L513 LassoAnalysis]: Proved termination. [2022-07-14 16:00:58,984 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_#in~n) = 1*fibo_#in~n Supporting invariants [] [2022-07-14 16:00:59,001 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2022-07-14 16:00:59,003 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-14 16:00:59,019 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:00:59,040 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:00:59,042 INFO L263 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 4 conjunts are in the unsatisfiable core [2022-07-14 16:00:59,042 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:00:59,056 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:00:59,057 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-14 16:00:59,058 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:00:59,104 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-14 16:00:59,131 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-14 16:00:59,132 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-07-14 16:00:59,214 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 18 states, 13 states have (on average 1.2307692307692308) internal successors, (16), 13 states have internal predecessors, (16), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3). Second operand has 4 states, 4 states have (on average 1.25) internal successors, (5), 3 states have internal predecessors, (5), 2 states have call successors, (2), 1 states have call predecessors, (2), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 48 states and 60 transitions. Complement of second has 12 states. [2022-07-14 16:00:59,219 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-14 16:00:59,223 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-14 16:00:59,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4 states to 4 states and 11 transitions. [2022-07-14 16:00:59,226 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 4 letters. [2022-07-14 16:00:59,227 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:00:59,227 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 7 letters. Loop has 4 letters. [2022-07-14 16:00:59,227 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:00:59,227 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 4 states and 11 transitions. Stem has 3 letters. Loop has 8 letters. [2022-07-14 16:00:59,227 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:00:59,228 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 48 states and 60 transitions. [2022-07-14 16:00:59,231 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:00:59,235 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 48 states to 25 states and 34 transitions. [2022-07-14 16:00:59,236 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 17 [2022-07-14 16:00:59,236 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 18 [2022-07-14 16:00:59,236 INFO L73 IsDeterministic]: Start isDeterministic. Operand 25 states and 34 transitions. [2022-07-14 16:00:59,237 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-14 16:00:59,237 INFO L369 hiAutomatonCegarLoop]: Abstraction has 25 states and 34 transitions. [2022-07-14 16:00:59,247 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states and 34 transitions. [2022-07-14 16:00:59,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 20. [2022-07-14 16:00:59,255 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-14 16:00:59,256 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 26 transitions. [2022-07-14 16:00:59,257 INFO L392 hiAutomatonCegarLoop]: Abstraction has 20 states and 26 transitions. [2022-07-14 16:00:59,257 INFO L374 stractBuchiCegarLoop]: Abstraction has 20 states and 26 transitions. [2022-07-14 16:00:59,257 INFO L287 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2022-07-14 16:00:59,257 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 20 states and 26 transitions. [2022-07-14 16:00:59,258 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:00:59,258 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-14 16:00:59,258 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-14 16:00:59,259 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-14 16:00:59,259 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 1, 1, 1, 1, 1, 1, 1] [2022-07-14 16:00:59,259 INFO L752 eck$LassoCheckResult]: Stem: 122#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 123#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 128#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 132#fiboENTRY ~n := #in~n; 133#L8 assume !(~n < 1); 138#L10 assume !(1 == ~n); 127#L13 call #t~ret4 := fibo(~n - 1);< 129#fiboENTRY ~n := #in~n; 134#L8 assume ~n < 1;#res := 0; 135#fiboFINAL assume true; 136#fiboEXIT >#33#return; 125#L13-1 [2022-07-14 16:00:59,259 INFO L754 eck$LassoCheckResult]: Loop: 125#L13-1 call #t~ret5 := fibo(~n - 2);< 126#fiboENTRY ~n := #in~n; 141#L8 assume !(~n < 1); 140#L10 assume !(1 == ~n); 124#L13 call #t~ret4 := fibo(~n - 1);< 126#fiboENTRY ~n := #in~n; 141#L8 assume ~n < 1;#res := 0; 131#fiboFINAL assume true; 139#fiboEXIT >#33#return; 125#L13-1 [2022-07-14 16:00:59,260 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:00:59,260 INFO L85 PathProgramCache]: Analyzing trace with hash -1181449843, now seen corresponding path program 1 times [2022-07-14 16:00:59,260 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:00:59,260 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [143211687] [2022-07-14 16:00:59,260 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:00:59,261 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:00:59,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:00:59,296 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-14 16:00:59,301 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:00:59,318 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-14 16:00:59,318 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-14 16:00:59,319 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [143211687] [2022-07-14 16:00:59,319 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [143211687] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-14 16:00:59,319 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-14 16:00:59,319 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-14 16:00:59,320 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [767479386] [2022-07-14 16:00:59,320 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-14 16:00:59,322 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-14 16:00:59,322 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:00:59,322 INFO L85 PathProgramCache]: Analyzing trace with hash 246097683, now seen corresponding path program 1 times [2022-07-14 16:00:59,322 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:00:59,322 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [216520381] [2022-07-14 16:00:59,322 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:00:59,323 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:00:59,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:00:59,339 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-14 16:00:59,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:00:59,355 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-14 16:00:59,355 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-14 16:00:59,371 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [216520381] [2022-07-14 16:00:59,371 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [216520381] provided 1 perfect and 0 imperfect interpolant sequences [2022-07-14 16:00:59,371 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-07-14 16:00:59,371 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-07-14 16:00:59,372 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [735669496] [2022-07-14 16:00:59,372 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-07-14 16:00:59,372 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-14 16:00:59,372 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-14 16:00:59,374 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-07-14 16:00:59,374 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-07-14 16:00:59,375 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-14 16:00:59,424 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-14 16:00:59,424 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2022-07-14 16:00:59,424 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-07-14 16:00:59,425 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 26 states and 32 transitions. [2022-07-14 16:00:59,430 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:00:59,433 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 26 states to 24 states and 30 transitions. [2022-07-14 16:00:59,433 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 20 [2022-07-14 16:00:59,433 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 20 [2022-07-14 16:00:59,434 INFO L73 IsDeterministic]: Start isDeterministic. Operand 24 states and 30 transitions. [2022-07-14 16:00:59,434 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-14 16:00:59,435 INFO L369 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-14 16:00:59,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states and 30 transitions. [2022-07-14 16:00:59,436 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2022-07-14 16:00:59,437 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-14 16:00:59,439 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2022-07-14 16:00:59,439 INFO L392 hiAutomatonCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-14 16:00:59,439 INFO L374 stractBuchiCegarLoop]: Abstraction has 24 states and 30 transitions. [2022-07-14 16:00:59,440 INFO L287 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2022-07-14 16:00:59,440 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 24 states and 30 transitions. [2022-07-14 16:00:59,441 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:00:59,443 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-14 16:00:59,443 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-14 16:00:59,444 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-14 16:00:59,444 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1] [2022-07-14 16:00:59,444 INFO L752 eck$LassoCheckResult]: Stem: 195#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 196#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 201#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 205#fiboENTRY ~n := #in~n; 207#L8 assume !(~n < 1); 211#L10 assume !(1 == ~n); 200#L13 call #t~ret4 := fibo(~n - 1);< 202#fiboENTRY ~n := #in~n; 208#L8 assume !(~n < 1); 210#L10 assume 1 == ~n;#res := 1; 212#fiboFINAL assume true; 214#fiboEXIT >#33#return; 198#L13-1 [2022-07-14 16:00:59,445 INFO L754 eck$LassoCheckResult]: Loop: 198#L13-1 call #t~ret5 := fibo(~n - 2);< 199#fiboENTRY ~n := #in~n; 217#L8 assume !(~n < 1); 215#L10 assume !(1 == ~n); 197#L13 call #t~ret4 := fibo(~n - 1);< 199#fiboENTRY ~n := #in~n; 217#L8 assume !(~n < 1); 215#L10 assume 1 == ~n;#res := 1; 216#fiboFINAL assume true; 213#fiboEXIT >#33#return; 198#L13-1 [2022-07-14 16:00:59,445 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:00:59,445 INFO L85 PathProgramCache]: Analyzing trace with hash 2029785426, now seen corresponding path program 1 times [2022-07-14 16:00:59,445 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:00:59,446 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1632500153] [2022-07-14 16:00:59,446 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:00:59,446 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:00:59,453 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:00:59,486 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-07-14 16:00:59,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:00:59,524 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-14 16:00:59,524 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-14 16:00:59,525 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1632500153] [2022-07-14 16:00:59,525 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1632500153] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-14 16:00:59,527 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2057457799] [2022-07-14 16:00:59,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:00:59,528 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-14 16:00:59,529 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:59,530 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-14 16:00:59,537 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-14 16:00:59,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:00:59,569 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-14 16:00:59,570 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:00:59,594 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-14 16:00:59,594 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-14 16:00:59,666 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-14 16:00:59,672 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2057457799] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-14 16:00:59,672 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-14 16:00:59,672 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 11 [2022-07-14 16:00:59,673 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1870605162] [2022-07-14 16:00:59,673 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-14 16:00:59,673 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-14 16:00:59,673 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:00:59,673 INFO L85 PathProgramCache]: Analyzing trace with hash -960881524, now seen corresponding path program 1 times [2022-07-14 16:00:59,674 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:00:59,674 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1027762314] [2022-07-14 16:00:59,674 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:00:59,674 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:00:59,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:00:59,679 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-14 16:00:59,681 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:00:59,682 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-14 16:00:59,758 INFO L210 LassoAnalysis]: Preferences: [2022-07-14 16:00:59,758 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-14 16:00:59,758 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-14 16:00:59,758 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-14 16:00:59,758 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-14 16:00:59,758 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:59,758 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-14 16:00:59,759 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-14 16:00:59,759 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration3_Loop [2022-07-14 16:00:59,759 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-14 16:00:59,759 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-14 16:00:59,759 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-14 16:00:59,761 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-14 16:00:59,763 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-14 16:00:59,768 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-14 16:00:59,794 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-14 16:00:59,794 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-14 16:00:59,794 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:59,794 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:59,796 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-14 16:00:59,797 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-14 16:00:59,798 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:00:59,798 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:00:59,820 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-14 16:00:59,820 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-14 16:00:59,836 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-14 16:00:59,836 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:59,837 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:59,838 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-14 16:00:59,839 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-14 16:00:59,840 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:00:59,840 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:00:59,847 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-14 16:00:59,847 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=1} Honda state: {fibo_#t~ret4=1} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-14 16:00:59,877 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-14 16:00:59,878 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:59,878 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:59,879 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-14 16:00:59,880 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-14 16:00:59,883 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:00:59,883 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:00:59,938 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-14 16:00:59,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:00:59,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:00:59,939 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-14 16:00:59,947 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-14 16:00:59,948 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-14 16:00:59,948 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:01:00,754 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-14 16:01:00,758 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-14 16:01:00,758 INFO L210 LassoAnalysis]: Preferences: [2022-07-14 16:01:00,758 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-14 16:01:00,758 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-14 16:01:00,758 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-14 16:01:00,759 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-14 16:01:00,759 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:00,759 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-14 16:01:00,759 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-14 16:01:00,759 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration3_Loop [2022-07-14 16:01:00,759 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-14 16:01:00,759 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-14 16:01:00,760 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-14 16:01:00,778 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-14 16:01:00,780 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-14 16:01:00,785 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-14 16:01:00,812 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-14 16:01:00,813 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-14 16:01:00,813 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:00,813 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:00,816 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-14 16:01:00,817 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-14 16:01:00,818 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-14 16:01:00,825 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:01:00,825 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:01:00,825 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:01:00,825 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:01:00,825 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:01:00,826 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:01:00,826 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:01:00,834 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-14 16:01:00,850 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2022-07-14 16:01:00,850 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:00,850 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:00,851 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-14 16:01:00,852 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-14 16:01:00,853 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-14 16:01:00,860 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:01:00,860 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:01:00,860 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:01:00,860 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:01:00,861 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:01:00,861 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:01:00,861 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:01:00,864 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-14 16:01:00,884 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-14 16:01:00,885 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:00,885 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:00,889 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-14 16:01:00,890 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-14 16:01:00,891 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-14 16:01:00,897 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:01:00,897 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:01:00,898 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:01:00,898 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:01:00,898 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:01:00,899 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:01:00,899 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:01:00,914 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-14 16:01:00,933 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-14 16:01:00,933 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-14 16:01:00,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:00,933 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:00,934 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-14 16:01:00,946 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-14 16:01:00,947 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-14 16:01:00,947 INFO L513 LassoAnalysis]: Proved termination. [2022-07-14 16:01:00,947 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2022-07-14 16:01:00,966 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-14 16:01:00,966 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-14 16:01:00,967 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-14 16:01:00,969 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-14 16:01:00,987 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:01,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,017 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-14 16:01:01,019 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:01,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,077 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 11 conjunts are in the unsatisfiable core [2022-07-14 16:01:01,078 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:01,129 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-14 16:01:01,130 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-14 16:01:01,130 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-14 16:01:01,297 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-14 16:01:01,298 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-14 16:01:01,300 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-14 16:01:01,301 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 37 transitions. [2022-07-14 16:01:01,301 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 10 letters. [2022-07-14 16:01:01,302 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:01,304 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 22 letters. Loop has 10 letters. [2022-07-14 16:01:01,304 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:01,304 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 37 transitions. Stem has 12 letters. Loop has 20 letters. [2022-07-14 16:01:01,306 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:01,306 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 135 states and 183 transitions. [2022-07-14 16:01:01,313 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-14 16:01:01,318 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 135 states to 108 states and 152 transitions. [2022-07-14 16:01:01,318 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 64 [2022-07-14 16:01:01,319 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 69 [2022-07-14 16:01:01,319 INFO L73 IsDeterministic]: Start isDeterministic. Operand 108 states and 152 transitions. [2022-07-14 16:01:01,319 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-14 16:01:01,319 INFO L369 hiAutomatonCegarLoop]: Abstraction has 108 states and 152 transitions. [2022-07-14 16:01:01,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states and 152 transitions. [2022-07-14 16:01:01,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 94. [2022-07-14 16:01:01,345 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-14 16:01:01,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 126 transitions. [2022-07-14 16:01:01,348 INFO L392 hiAutomatonCegarLoop]: Abstraction has 94 states and 126 transitions. [2022-07-14 16:01:01,348 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-14 16:01:01,349 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-07-14 16:01:01,349 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-07-14 16:01:01,350 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-14 16:01:01,444 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-14 16:01:01,444 INFO L93 Difference]: Finished difference Result 123 states and 165 transitions. [2022-07-14 16:01:01,444 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-07-14 16:01:01,445 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 123 states and 165 transitions. [2022-07-14 16:01:01,451 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-14 16:01:01,457 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 123 states to 118 states and 160 transitions. [2022-07-14 16:01:01,458 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 77 [2022-07-14 16:01:01,458 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 77 [2022-07-14 16:01:01,458 INFO L73 IsDeterministic]: Start isDeterministic. Operand 118 states and 160 transitions. [2022-07-14 16:01:01,459 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-14 16:01:01,459 INFO L369 hiAutomatonCegarLoop]: Abstraction has 118 states and 160 transitions. [2022-07-14 16:01:01,459 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states and 160 transitions. [2022-07-14 16:01:01,472 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 106. [2022-07-14 16:01:01,472 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-14 16:01:01,473 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 141 transitions. [2022-07-14 16:01:01,473 INFO L392 hiAutomatonCegarLoop]: Abstraction has 106 states and 141 transitions. [2022-07-14 16:01:01,473 INFO L374 stractBuchiCegarLoop]: Abstraction has 106 states and 141 transitions. [2022-07-14 16:01:01,473 INFO L287 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2022-07-14 16:01:01,473 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 106 states and 141 transitions. [2022-07-14 16:01:01,474 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 10 [2022-07-14 16:01:01,474 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-14 16:01:01,474 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-14 16:01:01,475 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-14 16:01:01,475 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 5, 3, 3, 3, 3, 2, 2, 2, 1] [2022-07-14 16:01:01,475 INFO L752 eck$LassoCheckResult]: Stem: 789#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 790#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 804#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 806#fiboENTRY ~n := #in~n; 854#L8 assume !(~n < 1); 853#L10 assume !(1 == ~n); 803#L13 call #t~ret4 := fibo(~n - 1);< 805#fiboENTRY ~n := #in~n; 815#L8 assume !(~n < 1); 820#L10 assume !(1 == ~n); 826#L13 call #t~ret4 := fibo(~n - 1);< 847#fiboENTRY ~n := #in~n; 851#L8 assume !(~n < 1); 849#L10 assume !(1 == ~n); 843#L13 call #t~ret4 := fibo(~n - 1);< 847#fiboENTRY ~n := #in~n; 851#L8 assume !(~n < 1); 849#L10 assume !(1 == ~n); 843#L13 call #t~ret4 := fibo(~n - 1);< 847#fiboENTRY ~n := #in~n; 852#L8 assume !(~n < 1); 850#L10 assume 1 == ~n;#res := 1; 848#fiboFINAL assume true; 846#fiboEXIT >#33#return; 792#L13-1 call #t~ret5 := fibo(~n - 2);< 844#fiboENTRY ~n := #in~n; 892#L8 assume ~n < 1;#res := 0; 891#fiboFINAL assume true; 890#fiboEXIT >#35#return; 889#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 887#fiboFINAL assume true; 879#fiboEXIT >#33#return; 824#L13-1 [2022-07-14 16:01:01,475 INFO L754 eck$LassoCheckResult]: Loop: 824#L13-1 call #t~ret5 := fibo(~n - 2);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume !(1 == ~n); 822#L13 call #t~ret4 := fibo(~n - 1);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume !(1 == ~n); 822#L13 call #t~ret4 := fibo(~n - 1);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume 1 == ~n;#res := 1; 825#fiboFINAL assume true; 876#fiboEXIT >#33#return; 824#L13-1 call #t~ret5 := fibo(~n - 2);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume !(1 == ~n); 822#L13 call #t~ret4 := fibo(~n - 1);< 802#fiboENTRY ~n := #in~n; 884#L8 assume !(~n < 1); 821#L10 assume 1 == ~n;#res := 1; 825#fiboFINAL assume true; 876#fiboEXIT >#33#return; 824#L13-1 call #t~ret5 := fibo(~n - 2);< 802#fiboENTRY ~n := #in~n; 884#L8 assume ~n < 1;#res := 0; 885#fiboFINAL assume true; 883#fiboEXIT >#35#return; 878#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 886#fiboFINAL assume true; 880#fiboEXIT >#35#return; 878#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 886#fiboFINAL assume true; 880#fiboEXIT >#33#return; 824#L13-1 [2022-07-14 16:01:01,476 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:01,476 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 1 times [2022-07-14 16:01:01,476 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:01:01,476 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1249542801] [2022-07-14 16:01:01,476 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:01,476 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:01:01,486 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:01,486 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-14 16:01:01,494 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:01,498 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-14 16:01:01,498 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:01,499 INFO L85 PathProgramCache]: Analyzing trace with hash 1616897917, now seen corresponding path program 1 times [2022-07-14 16:01:01,499 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:01:01,499 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [522406391] [2022-07-14 16:01:01,499 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:01,499 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:01:01,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,513 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-14 16:01:01,526 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,540 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-14 16:01:01,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,553 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-14 16:01:01,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,580 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-14 16:01:01,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,584 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-14 16:01:01,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,588 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 26 proven. 13 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-07-14 16:01:01,588 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-14 16:01:01,588 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [522406391] [2022-07-14 16:01:01,588 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [522406391] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-14 16:01:01,588 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1947507425] [2022-07-14 16:01:01,588 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:01,589 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-14 16:01:01,589 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:01,600 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-14 16:01:01,601 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2022-07-14 16:01:01,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,629 INFO L263 TraceCheckSpWp]: Trace formula consists of 76 conjuncts, 6 conjunts are in the unsatisfiable core [2022-07-14 16:01:01,630 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:01,672 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 25 proven. 15 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2022-07-14 16:01:01,672 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-14 16:01:01,797 INFO L134 CoverageAnalysis]: Checked inductivity of 67 backedges. 25 proven. 15 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2022-07-14 16:01:01,797 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1947507425] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-14 16:01:01,798 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-14 16:01:01,798 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2022-07-14 16:01:01,798 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [527192727] [2022-07-14 16:01:01,798 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-14 16:01:01,798 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-14 16:01:01,798 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-14 16:01:01,799 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-07-14 16:01:01,799 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2022-07-14 16:01:01,800 INFO L87 Difference]: Start difference. First operand 106 states and 141 transitions. cyclomatic complexity: 40 Second operand has 11 states, 10 states have (on average 2.7) internal successors, (27), 10 states have internal predecessors, (27), 4 states have call successors, (7), 1 states have call predecessors, (7), 4 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2022-07-14 16:01:01,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-14 16:01:01,869 INFO L93 Difference]: Finished difference Result 60 states and 77 transitions. [2022-07-14 16:01:01,870 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-14 16:01:01,870 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 60 states and 77 transitions. [2022-07-14 16:01:01,871 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:01:01,871 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 60 states to 54 states and 70 transitions. [2022-07-14 16:01:01,871 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2022-07-14 16:01:01,872 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2022-07-14 16:01:01,872 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 70 transitions. [2022-07-14 16:01:01,872 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-14 16:01:01,872 INFO L369 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2022-07-14 16:01:01,872 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 70 transitions. [2022-07-14 16:01:01,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-07-14 16:01:01,874 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0857142857142856) internal successors, (38), 37 states have internal predecessors, (38), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (21), 9 states have call predecessors, (21), 9 states have call successors, (21) [2022-07-14 16:01:01,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 70 transitions. [2022-07-14 16:01:01,874 INFO L392 hiAutomatonCegarLoop]: Abstraction has 54 states and 70 transitions. [2022-07-14 16:01:01,875 INFO L374 stractBuchiCegarLoop]: Abstraction has 54 states and 70 transitions. [2022-07-14 16:01:01,875 INFO L287 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2022-07-14 16:01:01,875 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 70 transitions. [2022-07-14 16:01:01,875 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:01:01,875 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-14 16:01:01,875 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-14 16:01:01,876 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-14 16:01:01,876 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [6, 5, 4, 3, 3, 3, 3, 2, 2, 2, 1] [2022-07-14 16:01:01,876 INFO L752 eck$LassoCheckResult]: Stem: 1241#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 1242#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 1254#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1255#fiboENTRY ~n := #in~n; 1273#L8 assume !(~n < 1); 1272#L10 assume !(1 == ~n); 1247#L13 call #t~ret4 := fibo(~n - 1);< 1259#fiboENTRY ~n := #in~n; 1260#L8 assume !(~n < 1); 1266#L10 assume !(1 == ~n); 1246#L13 call #t~ret4 := fibo(~n - 1);< 1248#fiboENTRY ~n := #in~n; 1271#L8 assume !(~n < 1); 1289#L10 assume !(1 == ~n); 1263#L13 call #t~ret4 := fibo(~n - 1);< 1248#fiboENTRY ~n := #in~n; 1271#L8 assume !(~n < 1); 1289#L10 assume !(1 == ~n); 1263#L13 call #t~ret4 := fibo(~n - 1);< 1248#fiboENTRY ~n := #in~n; 1270#L8 assume !(~n < 1); 1267#L10 assume 1 == ~n;#res := 1; 1268#fiboFINAL assume true; 1262#fiboEXIT >#33#return; 1264#L13-1 call #t~ret5 := fibo(~n - 2);< 1288#fiboENTRY ~n := #in~n; 1294#L8 assume ~n < 1;#res := 0; 1293#fiboFINAL assume true; 1287#fiboEXIT >#35#return; 1285#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1283#fiboFINAL assume true; 1280#fiboEXIT >#33#return; 1252#L13-1 [2022-07-14 16:01:01,876 INFO L754 eck$LassoCheckResult]: Loop: 1252#L13-1 call #t~ret5 := fibo(~n - 2);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume !(~n < 1); 1275#L10 assume !(1 == ~n); 1251#L13 call #t~ret4 := fibo(~n - 1);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume !(~n < 1); 1275#L10 assume !(1 == ~n); 1251#L13 call #t~ret4 := fibo(~n - 1);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume !(~n < 1); 1275#L10 assume !(1 == ~n); 1251#L13 call #t~ret4 := fibo(~n - 1);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume !(~n < 1); 1275#L10 assume 1 == ~n;#res := 1; 1290#fiboFINAL assume true; 1291#fiboEXIT >#33#return; 1257#L13-1 call #t~ret5 := fibo(~n - 2);< 1256#fiboENTRY ~n := #in~n; 1258#L8 assume ~n < 1;#res := 0; 1265#fiboFINAL assume true; 1286#fiboEXIT >#35#return; 1249#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1253#fiboFINAL assume true; 1261#fiboEXIT >#33#return; 1252#L13-1 call #t~ret5 := fibo(~n - 2);< 1245#fiboENTRY ~n := #in~n; 1274#L8 assume ~n < 1;#res := 0; 1265#fiboFINAL assume true; 1286#fiboEXIT >#35#return; 1278#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1284#fiboFINAL assume true; 1281#fiboEXIT >#33#return; 1252#L13-1 [2022-07-14 16:01:01,877 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:01,877 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 2 times [2022-07-14 16:01:01,877 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:01:01,877 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [530832325] [2022-07-14 16:01:01,877 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:01,877 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:01:01,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:01,916 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-14 16:01:01,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:01,930 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-14 16:01:01,934 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-14 16:01:01,934 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:01,934 INFO L85 PathProgramCache]: Analyzing trace with hash -176759904, now seen corresponding path program 2 times [2022-07-14 16:01:01,934 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:01:01,934 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1858731772] [2022-07-14 16:01:01,934 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:01,935 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:01:01,940 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,945 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 4 [2022-07-14 16:01:01,950 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:01,968 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-14 16:01:01,971 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,000 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-14 16:01:02,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,003 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-14 16:01:02,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,006 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 21 [2022-07-14 16:01:02,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,019 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 29 proven. 6 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-07-14 16:01:02,019 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-14 16:01:02,020 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1858731772] [2022-07-14 16:01:02,020 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1858731772] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-14 16:01:02,020 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [426480791] [2022-07-14 16:01:02,020 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-07-14 16:01:02,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-14 16:01:02,020 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:02,031 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-14 16:01:02,033 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2022-07-14 16:01:02,061 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-07-14 16:01:02,062 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-14 16:01:02,062 INFO L263 TraceCheckSpWp]: Trace formula consists of 74 conjuncts, 8 conjunts are in the unsatisfiable core [2022-07-14 16:01:02,065 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:02,104 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 12 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2022-07-14 16:01:02,104 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-14 16:01:02,270 INFO L134 CoverageAnalysis]: Checked inductivity of 63 backedges. 30 proven. 13 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-07-14 16:01:02,270 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [426480791] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-14 16:01:02,270 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-14 16:01:02,270 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 9] total 14 [2022-07-14 16:01:02,271 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2078832284] [2022-07-14 16:01:02,271 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-14 16:01:02,271 INFO L769 eck$LassoCheckResult]: loop already infeasible [2022-07-14 16:01:02,271 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-14 16:01:02,271 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-07-14 16:01:02,271 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2022-07-14 16:01:02,272 INFO L87 Difference]: Start difference. First operand 54 states and 70 transitions. cyclomatic complexity: 18 Second operand has 14 states, 12 states have (on average 2.5) internal successors, (30), 13 states have internal predecessors, (30), 6 states have call successors, (8), 1 states have call predecessors, (8), 5 states have return successors, (8), 4 states have call predecessors, (8), 6 states have call successors, (8) [2022-07-14 16:01:02,321 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-14 16:01:02,321 INFO L93 Difference]: Finished difference Result 54 states and 67 transitions. [2022-07-14 16:01:02,321 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-07-14 16:01:02,322 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 54 states and 67 transitions. [2022-07-14 16:01:02,322 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:01:02,323 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 54 states to 54 states and 67 transitions. [2022-07-14 16:01:02,323 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 43 [2022-07-14 16:01:02,323 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 43 [2022-07-14 16:01:02,323 INFO L73 IsDeterministic]: Start isDeterministic. Operand 54 states and 67 transitions. [2022-07-14 16:01:02,323 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-14 16:01:02,323 INFO L369 hiAutomatonCegarLoop]: Abstraction has 54 states and 67 transitions. [2022-07-14 16:01:02,323 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states and 67 transitions. [2022-07-14 16:01:02,325 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 54. [2022-07-14 16:01:02,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.0571428571428572) internal successors, (37), 37 states have internal predecessors, (37), 11 states have call successors, (11), 7 states have call predecessors, (11), 8 states have return successors, (19), 9 states have call predecessors, (19), 9 states have call successors, (19) [2022-07-14 16:01:02,325 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 67 transitions. [2022-07-14 16:01:02,325 INFO L392 hiAutomatonCegarLoop]: Abstraction has 54 states and 67 transitions. [2022-07-14 16:01:02,326 INFO L374 stractBuchiCegarLoop]: Abstraction has 54 states and 67 transitions. [2022-07-14 16:01:02,326 INFO L287 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2022-07-14 16:01:02,326 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 54 states and 67 transitions. [2022-07-14 16:01:02,326 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 5 [2022-07-14 16:01:02,326 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-14 16:01:02,326 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-14 16:01:02,327 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [6, 5, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2022-07-14 16:01:02,327 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1] [2022-07-14 16:01:02,327 INFO L752 eck$LassoCheckResult]: Stem: 1628#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 1629#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 1641#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 1642#fiboENTRY ~n := #in~n; 1661#L8 assume !(~n < 1); 1660#L10 assume !(1 == ~n); 1634#L13 call #t~ret4 := fibo(~n - 1);< 1646#fiboENTRY ~n := #in~n; 1647#L8 assume !(~n < 1); 1652#L10 assume !(1 == ~n); 1633#L13 call #t~ret4 := fibo(~n - 1);< 1635#fiboENTRY ~n := #in~n; 1659#L8 assume !(~n < 1); 1678#L10 assume !(1 == ~n); 1651#L13 call #t~ret4 := fibo(~n - 1);< 1635#fiboENTRY ~n := #in~n; 1659#L8 assume !(~n < 1); 1678#L10 assume !(1 == ~n); 1651#L13 call #t~ret4 := fibo(~n - 1);< 1635#fiboENTRY ~n := #in~n; 1658#L8 assume !(~n < 1); 1653#L10 assume 1 == ~n;#res := 1; 1654#fiboFINAL assume true; 1650#fiboEXIT >#33#return; 1644#L13-1 call #t~ret5 := fibo(~n - 2);< 1643#fiboENTRY ~n := #in~n; 1645#L8 assume ~n < 1;#res := 0; 1648#fiboFINAL assume true; 1649#fiboEXIT >#35#return; 1673#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1670#fiboFINAL assume true; 1667#fiboEXIT >#33#return; 1637#L13-1 [2022-07-14 16:01:02,327 INFO L754 eck$LassoCheckResult]: Loop: 1637#L13-1 call #t~ret5 := fibo(~n - 2);< 1632#fiboENTRY ~n := #in~n; 1677#L8 assume !(~n < 1); 1676#L10 assume !(1 == ~n); 1639#L13 call #t~ret4 := fibo(~n - 1);< 1632#fiboENTRY ~n := #in~n; 1677#L8 assume !(~n < 1); 1676#L10 assume !(1 == ~n); 1639#L13 call #t~ret4 := fibo(~n - 1);< 1632#fiboENTRY ~n := #in~n; 1677#L8 assume !(~n < 1); 1676#L10 assume 1 == ~n;#res := 1; 1675#fiboFINAL assume true; 1674#fiboEXIT >#33#return; 1655#L13-1 call #t~ret5 := fibo(~n - 2);< 1656#fiboENTRY ~n := #in~n; 1681#L8 assume ~n < 1;#res := 0; 1680#fiboFINAL assume true; 1679#fiboEXIT >#35#return; 1636#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 1640#fiboFINAL assume true; 1664#fiboEXIT >#33#return; 1637#L13-1 [2022-07-14 16:01:02,327 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:02,327 INFO L85 PathProgramCache]: Analyzing trace with hash -1730264506, now seen corresponding path program 3 times [2022-07-14 16:01:02,327 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:01:02,328 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1241531748] [2022-07-14 16:01:02,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:02,328 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:01:02,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:02,336 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-14 16:01:02,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:02,343 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-14 16:01:02,343 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:02,343 INFO L85 PathProgramCache]: Analyzing trace with hash 780094678, now seen corresponding path program 3 times [2022-07-14 16:01:02,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:01:02,343 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1151152163] [2022-07-14 16:01:02,344 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:02,344 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:01:02,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:02,347 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-14 16:01:02,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:02,351 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-14 16:01:02,351 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:02,351 INFO L85 PathProgramCache]: Analyzing trace with hash 1975410011, now seen corresponding path program 4 times [2022-07-14 16:01:02,351 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:01:02,352 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1028885188] [2022-07-14 16:01:02,352 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:02,352 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:01:02,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,430 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2022-07-14 16:01:02,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,435 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-14 16:01:02,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,438 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-14 16:01:02,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,440 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2022-07-14 16:01:02,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,444 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-14 16:01:02,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,446 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-14 16:01:02,447 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:02,448 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 34 proven. 64 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-07-14 16:01:02,448 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-14 16:01:02,448 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1028885188] [2022-07-14 16:01:02,448 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1028885188] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-14 16:01:02,448 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [92974462] [2022-07-14 16:01:02,448 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-07-14 16:01:02,449 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-14 16:01:02,449 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:02,450 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-14 16:01:02,451 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-14 16:01:02,481 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-07-14 16:01:02,481 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-14 16:01:02,482 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 12 conjunts are in the unsatisfiable core [2022-07-14 16:01:02,483 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:02,525 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 52 proven. 67 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-14 16:01:02,525 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-14 16:01:02,608 INFO L134 CoverageAnalysis]: Checked inductivity of 167 backedges. 52 proven. 67 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-07-14 16:01:02,608 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [92974462] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-14 16:01:02,608 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-14 16:01:02,608 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12] total 15 [2022-07-14 16:01:02,609 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1939284027] [2022-07-14 16:01:02,609 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-14 16:01:02,796 INFO L210 LassoAnalysis]: Preferences: [2022-07-14 16:01:02,796 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-14 16:01:02,796 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-14 16:01:02,796 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-14 16:01:02,796 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-14 16:01:02,796 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:02,796 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-14 16:01:02,796 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-14 16:01:02,796 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration6_Loop [2022-07-14 16:01:02,796 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-14 16:01:02,796 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-14 16:01:02,797 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-14 16:01:02,804 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-14 16:01:02,805 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-14 16:01:02,806 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-14 16:01:02,843 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-14 16:01:02,844 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-14 16:01:02,844 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:02,844 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:02,845 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-14 16:01:02,846 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-14 16:01:02,847 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:01:02,847 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:01:02,874 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Ended with exit code 0 [2022-07-14 16:01:02,874 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:02,874 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:02,875 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-14 16:01:02,876 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-14 16:01:02,877 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-14 16:01:02,877 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:01:03,844 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-14 16:01:03,849 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2022-07-14 16:01:03,849 INFO L210 LassoAnalysis]: Preferences: [2022-07-14 16:01:03,849 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-14 16:01:03,849 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-14 16:01:03,849 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-14 16:01:03,849 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-14 16:01:03,849 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:03,849 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-14 16:01:03,849 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-14 16:01:03,849 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration6_Loop [2022-07-14 16:01:03,849 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-14 16:01:03,849 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-14 16:01:03,850 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-14 16:01:03,852 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-14 16:01:03,854 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-14 16:01:03,856 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-14 16:01:03,899 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-14 16:01:03,900 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-14 16:01:03,900 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:03,900 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:03,901 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-14 16:01:03,902 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-14 16:01:03,904 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-14 16:01:03,909 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:01:03,909 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:01:03,909 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:01:03,909 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:01:03,909 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:01:03,910 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:01:03,910 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:01:03,923 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-14 16:01:03,938 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-14 16:01:03,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:03,938 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:03,939 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-14 16:01:03,940 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-14 16:01:03,941 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-14 16:01:03,946 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:01:03,946 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:01:03,947 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:01:03,947 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:01:03,947 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:01:03,947 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:01:03,947 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:01:03,948 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-14 16:01:03,963 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2022-07-14 16:01:03,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:03,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:03,965 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-14 16:01:03,965 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-14 16:01:03,967 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-14 16:01:03,972 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:01:03,972 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:01:03,972 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:01:03,972 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:01:03,972 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:01:03,973 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:01:03,973 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:01:03,974 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-14 16:01:03,989 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Ended with exit code 0 [2022-07-14 16:01:03,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:03,989 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:03,990 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-14 16:01:03,992 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-14 16:01:03,992 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-14 16:01:03,998 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:01:03,998 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:01:03,998 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:01:03,998 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:01:03,998 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:01:03,999 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:01:03,999 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:01:04,007 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-14 16:01:04,010 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-14 16:01:04,010 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-14 16:01:04,010 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:04,010 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:04,011 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-14 16:01:04,024 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-14 16:01:04,024 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-14 16:01:04,024 INFO L513 LassoAnalysis]: Proved termination. [2022-07-14 16:01:04,024 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2022-07-14 16:01:04,038 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2022-07-14 16:01:04,039 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-14 16:01:04,040 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-14 16:01:04,047 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:04,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:04,091 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-14 16:01:04,092 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:04,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:04,286 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-14 16:01:04,287 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:04,377 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-14 16:01:04,377 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2022-07-14 16:01:04,378 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-14 16:01:04,447 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 74 transitions. Complement of second has 11 states. [2022-07-14 16:01:04,448 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-14 16:01:04,449 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-14 16:01:04,450 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2022-07-14 16:01:04,450 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2022-07-14 16:01:04,450 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:04,450 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-14 16:01:04,456 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:04,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:04,494 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-14 16:01:04,495 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:04,500 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2022-07-14 16:01:04,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:04,651 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-14 16:01:04,652 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:04,736 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-14 16:01:04,737 INFO L152 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 7 loop predicates [2022-07-14 16:01:04,738 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-14 16:01:04,816 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 61 states and 74 transitions. Complement of second has 11 states. [2022-07-14 16:01:04,817 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-14 16:01:04,819 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-14 16:01:04,820 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 17 transitions. [2022-07-14 16:01:04,820 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 17 transitions. Stem has 32 letters. Loop has 22 letters. [2022-07-14 16:01:04,820 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:04,820 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-14 16:01:04,828 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:04,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:04,862 INFO L263 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 14 conjunts are in the unsatisfiable core [2022-07-14 16:01:04,864 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:05,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:05,017 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 17 conjunts are in the unsatisfiable core [2022-07-14 16:01:05,018 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:05,092 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 4 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-07-14 16:01:05,093 INFO L152 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 7 loop predicates [2022-07-14 16:01:05,093 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15 Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-14 16:01:05,253 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 54 states and 67 transitions. cyclomatic complexity: 15. Second operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) Result 321 states and 401 transitions. Complement of second has 122 states. [2022-07-14 16:01:05,254 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 10 states 2 stem states 7 non-accepting loop states 1 accepting loop states [2022-07-14 16:01:05,254 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 3.25) internal successors, (26), 7 states have internal predecessors, (26), 6 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (6), 3 states have call predecessors, (6), 5 states have call successors, (6) [2022-07-14 16:01:05,255 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 46 transitions. [2022-07-14 16:01:05,255 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 22 letters. [2022-07-14 16:01:05,256 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:05,256 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 54 letters. Loop has 22 letters. [2022-07-14 16:01:05,256 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:05,256 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 10 states and 46 transitions. Stem has 32 letters. Loop has 44 letters. [2022-07-14 16:01:05,257 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:05,258 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 321 states and 401 transitions. [2022-07-14 16:01:05,261 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 14 [2022-07-14 16:01:05,263 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 321 states to 203 states and 261 transitions. [2022-07-14 16:01:05,263 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2022-07-14 16:01:05,263 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 90 [2022-07-14 16:01:05,263 INFO L73 IsDeterministic]: Start isDeterministic. Operand 203 states and 261 transitions. [2022-07-14 16:01:05,264 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-14 16:01:05,264 INFO L369 hiAutomatonCegarLoop]: Abstraction has 203 states and 261 transitions. [2022-07-14 16:01:05,264 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states and 261 transitions. [2022-07-14 16:01:05,269 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 175. [2022-07-14 16:01:05,270 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 175 states, 109 states have (on average 1.1376146788990826) internal successors, (124), 116 states have internal predecessors, (124), 39 states have call successors, (39), 24 states have call predecessors, (39), 27 states have return successors, (49), 34 states have call predecessors, (49), 34 states have call successors, (49) [2022-07-14 16:01:05,271 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 212 transitions. [2022-07-14 16:01:05,271 INFO L392 hiAutomatonCegarLoop]: Abstraction has 175 states and 212 transitions. [2022-07-14 16:01:05,271 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-14 16:01:05,272 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-07-14 16:01:05,272 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-07-14 16:01:05,272 INFO L87 Difference]: Start difference. First operand 175 states and 212 transitions. Second operand has 15 states, 13 states have (on average 2.3076923076923075) internal successors, (30), 11 states have internal predecessors, (30), 8 states have call successors, (11), 5 states have call predecessors, (11), 2 states have return successors, (7), 4 states have call predecessors, (7), 5 states have call successors, (7) [2022-07-14 16:01:05,436 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-14 16:01:05,436 INFO L93 Difference]: Finished difference Result 124 states and 140 transitions. [2022-07-14 16:01:05,437 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-07-14 16:01:05,437 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 124 states and 140 transitions. [2022-07-14 16:01:05,438 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2022-07-14 16:01:05,439 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 124 states to 105 states and 117 transitions. [2022-07-14 16:01:05,439 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 51 [2022-07-14 16:01:05,439 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 64 [2022-07-14 16:01:05,439 INFO L73 IsDeterministic]: Start isDeterministic. Operand 105 states and 117 transitions. [2022-07-14 16:01:05,439 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2022-07-14 16:01:05,439 INFO L369 hiAutomatonCegarLoop]: Abstraction has 105 states and 117 transitions. [2022-07-14 16:01:05,440 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states and 117 transitions. [2022-07-14 16:01:05,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 96. [2022-07-14 16:01:05,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 63 states have (on average 1.0793650793650793) internal successors, (68), 66 states have internal predecessors, (68), 19 states have call successors, (19), 14 states have call predecessors, (19), 14 states have return successors, (21), 15 states have call predecessors, (21), 15 states have call successors, (21) [2022-07-14 16:01:05,443 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 108 transitions. [2022-07-14 16:01:05,443 INFO L392 hiAutomatonCegarLoop]: Abstraction has 96 states and 108 transitions. [2022-07-14 16:01:05,443 INFO L374 stractBuchiCegarLoop]: Abstraction has 96 states and 108 transitions. [2022-07-14 16:01:05,443 INFO L287 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2022-07-14 16:01:05,443 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 96 states and 108 transitions. [2022-07-14 16:01:05,444 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2022-07-14 16:01:05,444 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2022-07-14 16:01:05,444 INFO L119 BuchiIsEmpty]: Starting construction of run [2022-07-14 16:01:05,445 INFO L179 hiAutomatonCegarLoop]: Counterexample stem histogram [7, 6, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2022-07-14 16:01:05,446 INFO L180 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2022-07-14 16:01:05,446 INFO L752 eck$LassoCheckResult]: Stem: 3515#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;#NULL.base, #NULL.offset := 0, 0;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int(48, 1, 0, 1);call write~init~int(0, 1, 1, 1);call #Ultimate.allocInit(11, 2);call #Ultimate.allocInit(12, 3); 3516#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~ret6#1, main_~x~0#1, main_~result~0#1;main_~x~0#1 := 5; 3531#L27 call main_#t~ret6#1 := fibo(main_~x~0#1);< 3532#fiboENTRY ~n := #in~n; 3571#L8 assume !(~n < 1); 3570#L10 assume !(1 == ~n); 3545#L13 call #t~ret4 := fibo(~n - 1);< 3569#fiboENTRY ~n := #in~n; 3568#L8 assume !(~n < 1); 3567#L10 assume !(1 == ~n); 3522#L13 call #t~ret4 := fibo(~n - 1);< 3523#fiboENTRY ~n := #in~n; 3577#L8 assume !(~n < 1); 3552#L10 assume !(1 == ~n); 3521#L13 call #t~ret4 := fibo(~n - 1);< 3523#fiboENTRY ~n := #in~n; 3578#L8 assume !(~n < 1); 3588#L10 assume 1 == ~n;#res := 1; 3586#fiboFINAL assume true; 3583#fiboEXIT >#33#return; 3584#L13-1 call #t~ret5 := fibo(~n - 2);< 3600#fiboENTRY ~n := #in~n; 3602#L8 assume ~n < 1;#res := 0; 3601#fiboFINAL assume true; 3599#fiboEXIT >#35#return; 3598#L13-2 #res := #t~ret4 + #t~ret5;havoc #t~ret4;havoc #t~ret5; 3597#fiboFINAL assume true; 3566#fiboEXIT >#33#return; 3525#L13-1 call #t~ret5 := fibo(~n - 2);< 3565#fiboENTRY ~n := #in~n; 3564#L8 assume !(~n < 1); 3563#L10 assume !(1 == ~n); 3518#L13 call #t~ret4 := fibo(~n - 1);< 3596#fiboENTRY ~n := #in~n; 3606#L8 assume !(~n < 1); 3605#L10 assume !(1 == ~n); 3517#L13 [2022-07-14 16:01:05,447 INFO L754 eck$LassoCheckResult]: Loop: 3517#L13 call #t~ret4 := fibo(~n - 1);< 3520#fiboENTRY ~n := #in~n; 3610#L8 assume !(~n < 1); 3551#L10 assume !(1 == ~n); 3517#L13 [2022-07-14 16:01:05,447 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:05,447 INFO L85 PathProgramCache]: Analyzing trace with hash 2096320921, now seen corresponding path program 5 times [2022-07-14 16:01:05,447 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:01:05,448 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [130602267] [2022-07-14 16:01:05,448 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:05,448 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:01:05,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:05,482 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2022-07-14 16:01:05,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:05,512 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2022-07-14 16:01:05,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:05,523 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2022-07-14 16:01:05,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:05,530 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 34 proven. 28 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2022-07-14 16:01:05,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-07-14 16:01:05,530 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [130602267] [2022-07-14 16:01:05,531 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [130602267] provided 0 perfect and 1 imperfect interpolant sequences [2022-07-14 16:01:05,531 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [537253251] [2022-07-14 16:01:05,531 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-07-14 16:01:05,531 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-07-14 16:01:05,531 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:05,532 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-07-14 16:01:05,533 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Waiting until timeout for monitored process [2022-07-14 16:01:05,560 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2022-07-14 16:01:05,561 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-07-14 16:01:05,561 INFO L263 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 9 conjunts are in the unsatisfiable core [2022-07-14 16:01:05,562 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:05,622 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 44 proven. 8 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-07-14 16:01:05,622 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-07-14 16:01:05,716 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 44 proven. 9 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2022-07-14 16:01:05,716 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [537253251] provided 0 perfect and 2 imperfect interpolant sequences [2022-07-14 16:01:05,716 INFO L184 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2022-07-14 16:01:05,716 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9, 10] total 18 [2022-07-14 16:01:05,717 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1975622874] [2022-07-14 16:01:05,717 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2022-07-14 16:01:05,717 INFO L757 eck$LassoCheckResult]: stem already infeasible [2022-07-14 16:01:05,717 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:05,717 INFO L85 PathProgramCache]: Analyzing trace with hash 1893846, now seen corresponding path program 2 times [2022-07-14 16:01:05,718 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-07-14 16:01:05,718 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [426047993] [2022-07-14 16:01:05,718 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-07-14 16:01:05,718 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-07-14 16:01:05,720 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:05,720 INFO L352 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2022-07-14 16:01:05,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2022-07-14 16:01:05,721 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2022-07-14 16:01:05,774 INFO L210 LassoAnalysis]: Preferences: [2022-07-14 16:01:05,774 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-14 16:01:05,774 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-14 16:01:05,775 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-14 16:01:05,775 INFO L129 ssoRankerPreferences]: Use exernal solver: true [2022-07-14 16:01:05,775 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:05,775 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-14 16:01:05,775 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-14 16:01:05,775 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration7_Loop [2022-07-14 16:01:05,775 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-14 16:01:05,775 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-14 16:01:05,776 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-14 16:01:05,777 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-14 16:01:05,779 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-14 16:01:05,780 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-14 16:01:05,809 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-14 16:01:05,810 INFO L404 LassoAnalysis]: Checking for nontermination... [2022-07-14 16:01:05,810 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:05,810 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:05,811 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-14 16:01:05,831 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:01:05,832 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:01:05,840 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-14 16:01:05,847 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-14 16:01:05,847 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#res=0} Honda state: {fibo_#res=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-14 16:01:05,864 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-14 16:01:05,864 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:05,864 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:05,865 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-14 16:01:05,866 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-14 16:01:05,867 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:01:05,867 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:01:05,899 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-14 16:01:05,899 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret5=0} Honda state: {fibo_#t~ret5=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-14 16:01:05,918 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-14 16:01:05,918 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:05,919 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:05,920 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-14 16:01:05,921 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-14 16:01:05,922 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:01:05,922 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:01:05,947 INFO L437 LassoAnalysis]: Proved nontermination for one component. [2022-07-14 16:01:05,947 INFO L440 LassoAnalysis]: Non-Termination argument consisting of: Initial state: {fibo_#t~ret4=0} Honda state: {fibo_#t~ret4=0} Generalized eigenvectors: [] Lambdas: [] Nus: [] [2022-07-14 16:01:05,965 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-14 16:01:05,966 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:05,966 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:05,967 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-14 16:01:05,968 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-14 16:01:05,969 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 0 Nilpotent components: true [2022-07-14 16:01:05,969 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:01:06,000 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Ended with exit code 0 [2022-07-14 16:01:06,001 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:06,001 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:06,003 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-14 16:01:06,004 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-14 16:01:06,005 INFO L148 nArgumentSynthesizer]: Nontermination analysis: NONLINEAR Allow bounded executions: true Number of generalized eigenvectors: 3 Nilpotent components: true [2022-07-14 16:01:06,005 INFO L160 nArgumentSynthesizer]: Using integer mode. [2022-07-14 16:01:07,727 INFO L444 LassoAnalysis]: Proving nontermination failed: No geometric nontermination argument exists. [2022-07-14 16:01:07,731 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-14 16:01:07,731 INFO L210 LassoAnalysis]: Preferences: [2022-07-14 16:01:07,731 INFO L126 ssoRankerPreferences]: Compute integeral hull: false [2022-07-14 16:01:07,731 INFO L127 ssoRankerPreferences]: Enable LassoPartitioneer: true [2022-07-14 16:01:07,731 INFO L128 ssoRankerPreferences]: Term annotations enabled: false [2022-07-14 16:01:07,731 INFO L129 ssoRankerPreferences]: Use exernal solver: false [2022-07-14 16:01:07,731 INFO L130 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:07,732 INFO L131 ssoRankerPreferences]: Dump SMT script to file: false [2022-07-14 16:01:07,732 INFO L132 ssoRankerPreferences]: Path of dumped script: [2022-07-14 16:01:07,732 INFO L133 ssoRankerPreferences]: Filename of dumped script: fibo_5-1.c_Iteration7_Loop [2022-07-14 16:01:07,732 INFO L134 ssoRankerPreferences]: MapElimAlgo: Frank [2022-07-14 16:01:07,732 INFO L276 LassoAnalysis]: Starting lasso preprocessing... [2022-07-14 16:01:07,732 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-14 16:01:07,734 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-14 16:01:07,740 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-14 16:01:07,750 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-14 16:01:07,774 INFO L294 LassoAnalysis]: Preprocessing complete. [2022-07-14 16:01:07,774 INFO L490 LassoAnalysis]: Using template 'affine'. [2022-07-14 16:01:07,775 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:07,775 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:07,776 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2022-07-14 16:01:07,777 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2022-07-14 16:01:07,778 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-14 16:01:07,783 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:01:07,783 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:01:07,783 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:01:07,783 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:01:07,783 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:01:07,784 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:01:07,784 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:01:07,807 INFO L527 LassoAnalysis]: Proving termination failed for this template and these settings. [2022-07-14 16:01:07,824 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2022-07-14 16:01:07,825 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:07,825 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:07,826 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-14 16:01:07,827 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-14 16:01:07,828 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-14 16:01:07,833 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2022-07-14 16:01:07,834 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2022-07-14 16:01:07,834 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2022-07-14 16:01:07,834 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2022-07-14 16:01:07,834 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2022-07-14 16:01:07,834 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2022-07-14 16:01:07,834 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2022-07-14 16:01:07,836 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2022-07-14 16:01:07,839 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2022-07-14 16:01:07,839 INFO L444 ModelExtractionUtils]: 1 out of 4 variables were initially zero. Simplification set additionally 1 variables to zero. [2022-07-14 16:01:07,839 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2022-07-14 16:01:07,839 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-07-14 16:01:07,840 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-14 16:01:07,842 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-14 16:01:07,842 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2022-07-14 16:01:07,842 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2022-07-14 16:01:07,842 INFO L513 LassoAnalysis]: Proved termination. [2022-07-14 16:01:07,842 INFO L515 LassoAnalysis]: Termination argument consisting of: Ranking function f(fibo_~n) = 1*fibo_~n Supporting invariants [] [2022-07-14 16:01:07,859 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2022-07-14 16:01:07,860 INFO L293 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2022-07-14 16:01:07,869 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:07,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:07,916 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-14 16:01:07,917 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:08,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:08,045 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-14 16:01:08,045 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:08,073 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-14 16:01:08,074 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-14 16:01:08,074 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-14 16:01:08,110 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 105 states and 118 transitions. Complement of second has 18 states. [2022-07-14 16:01:08,110 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-14 16:01:08,111 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-14 16:01:08,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 13 transitions. [2022-07-14 16:01:08,111 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 13 transitions. Stem has 36 letters. Loop has 4 letters. [2022-07-14 16:01:08,111 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:08,111 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-14 16:01:08,118 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:08,152 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:08,153 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-14 16:01:08,154 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:08,257 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-14 16:01:08,292 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:08,292 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-14 16:01:08,293 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:08,311 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-14 16:01:08,312 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-14 16:01:08,312 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-14 16:01:08,363 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 111 states and 124 transitions. Complement of second has 17 states. [2022-07-14 16:01:08,364 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-14 16:01:08,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-14 16:01:08,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 16 transitions. [2022-07-14 16:01:08,364 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 16 transitions. Stem has 36 letters. Loop has 4 letters. [2022-07-14 16:01:08,365 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:08,365 INFO L577 RefineBuchi]: Bad chosen interpolant automaton: word not accepted [2022-07-14 16:01:08,372 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-07-14 16:01:08,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:08,402 INFO L263 TraceCheckSpWp]: Trace formula consists of 294 conjuncts, 16 conjunts are in the unsatisfiable core [2022-07-14 16:01:08,403 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:08,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-07-14 16:01:08,522 INFO L263 TraceCheckSpWp]: Trace formula consists of 38 conjuncts, 7 conjunts are in the unsatisfiable core [2022-07-14 16:01:08,523 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-07-14 16:01:08,540 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-14 16:01:08,541 INFO L152 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2022-07-14 16:01:08,541 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15 Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-14 16:01:08,580 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 96 states and 108 transitions. cyclomatic complexity: 15. Second operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Result 131 states and 150 transitions. Complement of second has 27 states. [2022-07-14 16:01:08,581 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-14 16:01:08,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.2) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-07-14 16:01:08,581 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 22 transitions. [2022-07-14 16:01:08,582 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 4 letters. [2022-07-14 16:01:08,582 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:08,582 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 40 letters. Loop has 4 letters. [2022-07-14 16:01:08,582 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:08,582 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 22 transitions. Stem has 36 letters. Loop has 8 letters. [2022-07-14 16:01:08,583 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2022-07-14 16:01:08,583 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 131 states and 150 transitions. [2022-07-14 16:01:08,584 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-14 16:01:08,584 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 131 states to 0 states and 0 transitions. [2022-07-14 16:01:08,584 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2022-07-14 16:01:08,584 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2022-07-14 16:01:08,584 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2022-07-14 16:01:08,584 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2022-07-14 16:01:08,584 INFO L369 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-14 16:01:08,584 INFO L392 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-14 16:01:08,585 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-07-14 16:01:08,585 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2022-07-14 16:01:08,585 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=245, Unknown=0, NotChecked=0, Total=306 [2022-07-14 16:01:08,585 INFO L87 Difference]: Start difference. First operand 0 states and 0 transitions. Second operand has 18 states, 15 states have (on average 2.533333333333333) internal successors, (38), 14 states have internal predecessors, (38), 10 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-07-14 16:01:08,585 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-07-14 16:01:08,585 INFO L93 Difference]: Finished difference Result 0 states and 0 transitions. [2022-07-14 16:01:08,586 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2022-07-14 16:01:08,586 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 0 states and 0 transitions. [2022-07-14 16:01:08,586 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-14 16:01:08,586 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 0 states to 0 states and 0 transitions. [2022-07-14 16:01:08,586 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2022-07-14 16:01:08,586 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2022-07-14 16:01:08,586 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2022-07-14 16:01:08,586 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2022-07-14 16:01:08,586 INFO L369 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-14 16:01:08,587 INFO L392 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-14 16:01:08,587 INFO L374 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-07-14 16:01:08,587 INFO L287 stractBuchiCegarLoop]: ======== Iteration 8 ============ [2022-07-14 16:01:08,587 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2022-07-14 16:01:08,587 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2022-07-14 16:01:08,587 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2022-07-14 16:01:08,592 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 14.07 04:01:08 BoogieIcfgContainer [2022-07-14 16:01:08,592 INFO L132 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2022-07-14 16:01:08,592 INFO L113 PluginConnector]: ------------------------Witness Printer---------------------------- [2022-07-14 16:01:08,592 INFO L271 PluginConnector]: Initializing Witness Printer... [2022-07-14 16:01:08,593 INFO L275 PluginConnector]: Witness Printer initialized [2022-07-14 16:01:08,593 INFO L185 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.07 04:00:58" (3/4) ... [2022-07-14 16:01:08,595 INFO L140 WitnessPrinter]: No result that supports witness generation found [2022-07-14 16:01:08,595 INFO L132 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2022-07-14 16:01:08,595 INFO L158 Benchmark]: Toolchain (without parser) took 10954.92ms. Allocated memory was 107.0MB in the beginning and 136.3MB in the end (delta: 29.4MB). Free memory was 66.3MB in the beginning and 54.7MB in the end (delta: 11.6MB). Peak memory consumption was 41.4MB. Max. memory is 16.1GB. [2022-07-14 16:01:08,595 INFO L158 Benchmark]: CDTParser took 0.14ms. Allocated memory is still 107.0MB. Free memory was 82.7MB in the beginning and 82.6MB in the end (delta: 90.9kB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-14 16:01:08,596 INFO L158 Benchmark]: CACSL2BoogieTranslator took 170.94ms. Allocated memory is still 107.0MB. Free memory was 66.1MB in the beginning and 81.7MB in the end (delta: -15.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2022-07-14 16:01:08,596 INFO L158 Benchmark]: Boogie Procedure Inliner took 21.71ms. Allocated memory is still 107.0MB. Free memory was 81.7MB in the beginning and 80.1MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2022-07-14 16:01:08,596 INFO L158 Benchmark]: Boogie Preprocessor took 9.66ms. Allocated memory is still 107.0MB. Free memory was 80.1MB in the beginning and 79.2MB in the end (delta: 872.1kB). There was no memory consumed. Max. memory is 16.1GB. [2022-07-14 16:01:08,596 INFO L158 Benchmark]: RCFGBuilder took 198.33ms. Allocated memory is still 107.0MB. Free memory was 79.2MB in the beginning and 70.9MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2022-07-14 16:01:08,596 INFO L158 Benchmark]: BuchiAutomizer took 10545.94ms. Allocated memory was 107.0MB in the beginning and 136.3MB in the end (delta: 29.4MB). Free memory was 70.9MB in the beginning and 54.7MB in the end (delta: 16.2MB). Peak memory consumption was 47.9MB. Max. memory is 16.1GB. [2022-07-14 16:01:08,597 INFO L158 Benchmark]: Witness Printer took 2.42ms. Allocated memory is still 136.3MB. Free memory is still 54.7MB. There was no memory consumed. Max. memory is 16.1GB. [2022-07-14 16:01:08,598 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.14ms. Allocated memory is still 107.0MB. Free memory was 82.7MB in the beginning and 82.6MB in the end (delta: 90.9kB). There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 170.94ms. Allocated memory is still 107.0MB. Free memory was 66.1MB in the beginning and 81.7MB in the end (delta: -15.5MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 21.71ms. Allocated memory is still 107.0MB. Free memory was 81.7MB in the beginning and 80.1MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 9.66ms. Allocated memory is still 107.0MB. Free memory was 80.1MB in the beginning and 79.2MB in the end (delta: 872.1kB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 198.33ms. Allocated memory is still 107.0MB. Free memory was 79.2MB in the beginning and 70.9MB in the end (delta: 8.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * BuchiAutomizer took 10545.94ms. Allocated memory was 107.0MB in the beginning and 136.3MB in the end (delta: 29.4MB). Free memory was 70.9MB in the beginning and 54.7MB in the end (delta: 16.2MB). Peak memory consumption was 47.9MB. Max. memory is 16.1GB. * Witness Printer took 2.42ms. Allocated memory is still 136.3MB. Free memory is still 54.7MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 10 terminating modules (6 trivial, 2 deterministic, 2 nondeterministic). One deterministic module has affine ranking function \old(n) and consists of 4 locations. One deterministic module has affine ranking function n and consists of 9 locations. One nondeterministic module has affine ranking function n and consists of 10 locations. One nondeterministic module has affine ranking function n and consists of 6 locations. 6 modules have a trivial ranking function, the largest among these consists of 18 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 10.4s and 8 iterations. TraceHistogramMax:7. Analysis of lassos took 7.3s. Construction of modules took 0.3s. Büchi inclusion checks took 2.5s. Highest rank in rank-based complementation 3. Minimization of det autom 2. Minimization of nondet autom 8. Automata minimization 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 68 StatesRemovedByMinimization, 5 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [2, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 8/26 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 374 SdHoareTripleChecker+Valid, 0.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 358 mSDsluCounter, 366 SdHoareTripleChecker+Invalid, 0.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 212 mSDsCounter, 203 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 724 IncrementalHoareTripleChecker+Invalid, 927 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 203 mSolverCounterUnsat, 154 mSDtfsCounter, 724 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI2 SFLT1 conc0 concLT1 SILN0 SILU0 SILI1 SILT2 lasso0 LassoPreprocessingBenchmarks: Lassos: inital19 mio100 ax100 hnf100 lsp92 ukn100 mio100 lsp100 div100 bol100 ite100 ukn100 eq182 hnf93 smp74 dnf100 smp100 tf109 neg96 sie108 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 32ms VariablesStem: 0 VariablesLoop: 0 DisjunctsStem: 1 DisjunctsLoop: 1 SupportingInvariants: 0 MotzkinApplications: 2 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 8 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 4 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 3.9s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2022-07-14 16:01:08,622 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (31)] Forceful destruction successful, exit code 0 [2022-07-14 16:01:08,838 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-14 16:01:09,037 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Ended with exit code 0 [2022-07-14 16:01:09,232 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Ended with exit code 0 [2022-07-14 16:01:09,434 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-07-14 16:01:09,633 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE