java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default-INT-LIM.epf -i ../../../trunk/examples/svcomp/loop-lit/mcmillan2006_true-unreach-call_true-termination.c.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-63daa26 [2018-11-12 20:41:45,471 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-11-12 20:41:45,473 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-11-12 20:41:45,484 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-11-12 20:41:45,485 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-11-12 20:41:45,486 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-11-12 20:41:45,487 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-11-12 20:41:45,489 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-11-12 20:41:45,490 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-11-12 20:41:45,491 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-11-12 20:41:45,492 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-11-12 20:41:45,493 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-11-12 20:41:45,493 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-11-12 20:41:45,494 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-11-12 20:41:45,496 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-11-12 20:41:45,496 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-11-12 20:41:45,497 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-11-12 20:41:45,499 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-11-12 20:41:45,501 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-11-12 20:41:45,503 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-11-12 20:41:45,504 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-11-12 20:41:45,505 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-11-12 20:41:45,508 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-11-12 20:41:45,508 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-11-12 20:41:45,508 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-11-12 20:41:45,509 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-11-12 20:41:45,510 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-11-12 20:41:45,511 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-11-12 20:41:45,512 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-11-12 20:41:45,514 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-11-12 20:41:45,514 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-11-12 20:41:45,518 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-11-12 20:41:45,518 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-11-12 20:41:45,518 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-11-12 20:41:45,519 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-11-12 20:41:45,520 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-11-12 20:41:45,520 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default-INT-LIM.epf [2018-11-12 20:41:45,549 INFO L110 SettingsManager]: Loading preferences was successful [2018-11-12 20:41:45,550 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-11-12 20:41:45,551 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-11-12 20:41:45,551 INFO L133 SettingsManager]: * User list type=DISABLED [2018-11-12 20:41:45,551 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-11-12 20:41:45,551 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-11-12 20:41:45,551 INFO L133 SettingsManager]: * Maximum recursion depth of evaluation operations=6 [2018-11-12 20:41:45,552 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-11-12 20:41:45,552 INFO L133 SettingsManager]: * Octagon Domain=false [2018-11-12 20:41:45,552 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-11-12 20:41:45,552 INFO L133 SettingsManager]: * Log string format=TERM [2018-11-12 20:41:45,552 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-11-12 20:41:45,553 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-11-12 20:41:45,553 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-11-12 20:41:45,553 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-11-12 20:41:45,554 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-11-12 20:41:45,554 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-11-12 20:41:45,554 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-11-12 20:41:45,554 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-11-12 20:41:45,555 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-11-12 20:41:45,556 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-11-12 20:41:45,556 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-11-12 20:41:45,556 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-11-12 20:41:45,556 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-11-12 20:41:45,556 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-11-12 20:41:45,557 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-12 20:41:45,557 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-11-12 20:41:45,557 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-11-12 20:41:45,557 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-11-12 20:41:45,558 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-11-12 20:41:45,558 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-11-12 20:41:45,558 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-11-12 20:41:45,558 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-11-12 20:41:45,558 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-11-12 20:41:45,559 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-11-12 20:41:45,623 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-11-12 20:41:45,637 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-11-12 20:41:45,642 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-11-12 20:41:45,643 INFO L271 PluginConnector]: Initializing CDTParser... [2018-11-12 20:41:45,643 INFO L276 PluginConnector]: CDTParser initialized [2018-11-12 20:41:45,644 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/loop-lit/mcmillan2006_true-unreach-call_true-termination.c.i [2018-11-12 20:41:45,706 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d0517c3ff/d9bf667df94a4d6db41774feee436285/FLAG9417b023f [2018-11-12 20:41:46,106 INFO L298 CDTParser]: Found 1 translation units. [2018-11-12 20:41:46,106 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loop-lit/mcmillan2006_true-unreach-call_true-termination.c.i [2018-11-12 20:41:46,114 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d0517c3ff/d9bf667df94a4d6db41774feee436285/FLAG9417b023f [2018-11-12 20:41:46,128 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d0517c3ff/d9bf667df94a4d6db41774feee436285 [2018-11-12 20:41:46,141 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-11-12 20:41:46,142 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-11-12 20:41:46,143 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-11-12 20:41:46,143 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-11-12 20:41:46,146 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-11-12 20:41:46,147 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,150 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@46f35d84 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46, skipping insertion in model container [2018-11-12 20:41:46,150 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,161 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-11-12 20:41:46,183 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-11-12 20:41:46,417 INFO L201 PostProcessor]: Analyzing one entry point: main [2018-11-12 20:41:46,430 INFO L189 MainTranslator]: Completed pre-run [2018-11-12 20:41:46,448 INFO L201 PostProcessor]: Analyzing one entry point: main [2018-11-12 20:41:46,465 INFO L193 MainTranslator]: Completed translation [2018-11-12 20:41:46,466 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46 WrapperNode [2018-11-12 20:41:46,466 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-11-12 20:41:46,467 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-11-12 20:41:46,467 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-11-12 20:41:46,467 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-11-12 20:41:46,475 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,483 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,489 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-11-12 20:41:46,489 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-11-12 20:41:46,489 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-11-12 20:41:46,489 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-11-12 20:41:46,498 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,498 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,499 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,499 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,505 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,511 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,512 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... [2018-11-12 20:41:46,515 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-11-12 20:41:46,516 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-11-12 20:41:46,516 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-11-12 20:41:46,516 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-11-12 20:41:46,517 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-11-12 20:41:46,643 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-11-12 20:41:46,644 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-11-12 20:41:46,644 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2018-11-12 20:41:46,644 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-11-12 20:41:46,644 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-11-12 20:41:46,644 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-11-12 20:41:46,644 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-11-12 20:41:46,644 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-11-12 20:41:46,645 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2018-11-12 20:41:46,645 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-11-12 20:41:46,645 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-11-12 20:41:47,005 INFO L278 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-11-12 20:41:47,006 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 08:41:47 BoogieIcfgContainer [2018-11-12 20:41:47,006 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-11-12 20:41:47,007 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-11-12 20:41:47,007 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-11-12 20:41:47,011 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-11-12 20:41:47,011 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 12.11 08:41:46" (1/3) ... [2018-11-12 20:41:47,012 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@443e13a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 08:41:47, skipping insertion in model container [2018-11-12 20:41:47,012 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 12.11 08:41:46" (2/3) ... [2018-11-12 20:41:47,012 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@443e13a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.11 08:41:47, skipping insertion in model container [2018-11-12 20:41:47,013 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.11 08:41:47" (3/3) ... [2018-11-12 20:41:47,015 INFO L112 eAbstractionObserver]: Analyzing ICFG mcmillan2006_true-unreach-call_true-termination.c.i [2018-11-12 20:41:47,025 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-11-12 20:41:47,033 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-11-12 20:41:47,049 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-11-12 20:41:47,080 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-11-12 20:41:47,080 INFO L383 AbstractCegarLoop]: Hoare is true [2018-11-12 20:41:47,080 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-11-12 20:41:47,080 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-11-12 20:41:47,080 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-11-12 20:41:47,081 INFO L387 AbstractCegarLoop]: Difference is false [2018-11-12 20:41:47,081 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-11-12 20:41:47,081 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-11-12 20:41:47,100 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states. [2018-11-12 20:41:47,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-11-12 20:41:47,107 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:41:47,108 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:41:47,110 INFO L423 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:41:47,116 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:41:47,116 INFO L82 PathProgramCache]: Analyzing trace with hash 235483989, now seen corresponding path program 1 times [2018-11-12 20:41:47,119 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:41:47,173 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:47,173 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:41:47,173 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:47,173 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:41:47,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:47,259 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:47,261 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-12 20:41:47,261 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-11-12 20:41:47,261 INFO L256 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-12 20:41:47,266 INFO L459 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-11-12 20:41:47,279 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-11-12 20:41:47,279 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-12 20:41:47,282 INFO L87 Difference]: Start difference. First operand 27 states. Second operand 2 states. [2018-11-12 20:41:47,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:41:47,305 INFO L93 Difference]: Finished difference Result 44 states and 52 transitions. [2018-11-12 20:41:47,305 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-11-12 20:41:47,306 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 15 [2018-11-12 20:41:47,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:41:47,315 INFO L225 Difference]: With dead ends: 44 [2018-11-12 20:41:47,316 INFO L226 Difference]: Without dead ends: 22 [2018-11-12 20:41:47,321 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-11-12 20:41:47,342 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-11-12 20:41:47,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-11-12 20:41:47,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2018-11-12 20:41:47,363 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 23 transitions. [2018-11-12 20:41:47,365 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 23 transitions. Word has length 15 [2018-11-12 20:41:47,365 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:41:47,366 INFO L480 AbstractCegarLoop]: Abstraction has 22 states and 23 transitions. [2018-11-12 20:41:47,366 INFO L481 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-11-12 20:41:47,366 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 23 transitions. [2018-11-12 20:41:47,367 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-11-12 20:41:47,367 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:41:47,367 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:41:47,368 INFO L423 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:41:47,368 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:41:47,368 INFO L82 PathProgramCache]: Analyzing trace with hash 1613839314, now seen corresponding path program 1 times [2018-11-12 20:41:47,368 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:41:47,370 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:47,370 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:41:47,370 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:47,370 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:41:47,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:47,530 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:47,531 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-11-12 20:41:47,531 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-11-12 20:41:47,531 INFO L256 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-11-12 20:41:47,533 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-11-12 20:41:47,533 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-11-12 20:41:47,534 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-11-12 20:41:47,534 INFO L87 Difference]: Start difference. First operand 22 states and 23 transitions. Second operand 5 states. [2018-11-12 20:41:47,669 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:41:47,670 INFO L93 Difference]: Finished difference Result 39 states and 41 transitions. [2018-11-12 20:41:47,670 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-11-12 20:41:47,670 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 16 [2018-11-12 20:41:47,671 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:41:47,671 INFO L225 Difference]: With dead ends: 39 [2018-11-12 20:41:47,672 INFO L226 Difference]: Without dead ends: 25 [2018-11-12 20:41:47,673 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-11-12 20:41:47,673 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2018-11-12 20:41:47,677 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 24. [2018-11-12 20:41:47,677 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 24 states. [2018-11-12 20:41:47,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 25 transitions. [2018-11-12 20:41:47,679 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 25 transitions. Word has length 16 [2018-11-12 20:41:47,679 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:41:47,679 INFO L480 AbstractCegarLoop]: Abstraction has 24 states and 25 transitions. [2018-11-12 20:41:47,679 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-11-12 20:41:47,680 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 25 transitions. [2018-11-12 20:41:47,680 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-11-12 20:41:47,681 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:41:47,681 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:41:47,681 INFO L423 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:41:47,681 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:41:47,682 INFO L82 PathProgramCache]: Analyzing trace with hash -1557204615, now seen corresponding path program 1 times [2018-11-12 20:41:47,682 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:41:47,685 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:47,686 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:41:47,686 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:47,686 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:41:47,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:47,957 WARN L179 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 14 [2018-11-12 20:41:48,300 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:48,300 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:48,301 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:41:48,302 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 20 with the following transitions: [2018-11-12 20:41:48,303 INFO L202 CegarAbsIntRunner]: [0], [1], [5], [9], [13], [16], [18], [20], [24], [28], [33], [43], [46], [48], [54], [55], [56], [58] [2018-11-12 20:41:48,338 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, IntervalDomain] [2018-11-12 20:41:48,338 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-12 20:41:48,735 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-12 20:41:48,739 INFO L272 AbstractInterpreter]: Visited 18 different actions 69 times. Merged at 7 different actions 34 times. Widened at 2 different actions 2 times. Performed 277 root evaluator evaluations with a maximum evaluation depth of 4. Performed 277 inverse root evaluator evaluations with a maximum inverse evaluation depth of 4. Found 1 fixpoints after 1 different actions. Largest state had 20 variables. [2018-11-12 20:41:48,778 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:41:48,780 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-12 20:41:48,780 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:48,781 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:41:48,791 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:41:48,791 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:41:48,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:48,822 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:41:48,893 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 8 [2018-11-12 20:41:48,914 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2018-11-12 20:41:48,914 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:41:48,940 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:48,958 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:48,958 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:11, output treesize:7 [2018-11-12 20:41:49,129 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-11-12 20:41:49,134 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-11-12 20:41:49,134 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:41:49,159 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:49,166 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:49,166 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:15, output treesize:3 [2018-11-12 20:41:49,191 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:49,191 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:41:49,328 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 12 [2018-11-12 20:41:49,365 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2018-11-12 20:41:49,365 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:41:49,367 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:49,368 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:49,368 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:14, output treesize:5 [2018-11-12 20:41:49,413 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:49,434 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:41:49,434 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8, 8] total 15 [2018-11-12 20:41:49,434 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:41:49,435 INFO L459 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-11-12 20:41:49,435 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-11-12 20:41:49,436 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=169, Unknown=0, NotChecked=0, Total=210 [2018-11-12 20:41:49,436 INFO L87 Difference]: Start difference. First operand 24 states and 25 transitions. Second operand 12 states. [2018-11-12 20:41:49,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:41:49,907 INFO L93 Difference]: Finished difference Result 36 states and 37 transitions. [2018-11-12 20:41:49,908 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-11-12 20:41:49,908 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 19 [2018-11-12 20:41:49,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:41:49,909 INFO L225 Difference]: With dead ends: 36 [2018-11-12 20:41:49,910 INFO L226 Difference]: Without dead ends: 34 [2018-11-12 20:41:49,911 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 29 SyntacticMatches, 4 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=55, Invalid=217, Unknown=0, NotChecked=0, Total=272 [2018-11-12 20:41:49,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-11-12 20:41:49,917 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 31. [2018-11-12 20:41:49,918 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-11-12 20:41:49,919 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-11-12 20:41:49,919 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 19 [2018-11-12 20:41:49,919 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:41:49,920 INFO L480 AbstractCegarLoop]: Abstraction has 31 states and 32 transitions. [2018-11-12 20:41:49,920 INFO L481 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-11-12 20:41:49,920 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 32 transitions. [2018-11-12 20:41:49,921 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-11-12 20:41:49,921 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:41:49,921 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:41:49,921 INFO L423 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:41:49,922 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:41:49,922 INFO L82 PathProgramCache]: Analyzing trace with hash -1892261924, now seen corresponding path program 1 times [2018-11-12 20:41:49,922 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:41:49,923 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:49,923 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:41:49,923 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:49,923 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:41:49,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:50,046 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 3 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:50,047 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:50,047 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:41:50,048 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 29 with the following transitions: [2018-11-12 20:41:50,048 INFO L202 CegarAbsIntRunner]: [0], [1], [5], [9], [13], [16], [18], [20], [24], [28], [33], [35], [37], [43], [46], [48], [51], [53], [54], [55], [56], [58], [59] [2018-11-12 20:41:50,050 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, IntervalDomain] [2018-11-12 20:41:50,050 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-11-12 20:41:50,362 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-11-12 20:41:50,363 INFO L272 AbstractInterpreter]: Visited 23 different actions 138 times. Merged at 10 different actions 62 times. Widened at 3 different actions 5 times. Performed 491 root evaluator evaluations with a maximum evaluation depth of 6. Performed 491 inverse root evaluator evaluations with a maximum inverse evaluation depth of 6. Found 6 fixpoints after 2 different actions. Largest state had 21 variables. [2018-11-12 20:41:50,384 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:41:50,384 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-11-12 20:41:50,384 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:50,384 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:41:50,396 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:41:50,396 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:41:50,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:50,438 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:41:50,633 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:50,633 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:41:50,761 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:50,782 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:41:50,782 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 11 [2018-11-12 20:41:50,783 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:41:50,783 INFO L459 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-11-12 20:41:50,783 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-11-12 20:41:50,784 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=32, Invalid=78, Unknown=0, NotChecked=0, Total=110 [2018-11-12 20:41:50,784 INFO L87 Difference]: Start difference. First operand 31 states and 32 transitions. Second operand 10 states. [2018-11-12 20:41:50,906 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:41:50,906 INFO L93 Difference]: Finished difference Result 54 states and 57 transitions. [2018-11-12 20:41:50,907 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-11-12 20:41:50,907 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 28 [2018-11-12 20:41:50,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:41:50,910 INFO L225 Difference]: With dead ends: 54 [2018-11-12 20:41:50,910 INFO L226 Difference]: Without dead ends: 35 [2018-11-12 20:41:50,911 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 50 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=53, Invalid=129, Unknown=0, NotChecked=0, Total=182 [2018-11-12 20:41:50,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2018-11-12 20:41:50,920 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2018-11-12 20:41:50,920 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 34 states. [2018-11-12 20:41:50,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 35 transitions. [2018-11-12 20:41:50,922 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 35 transitions. Word has length 28 [2018-11-12 20:41:50,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:41:50,922 INFO L480 AbstractCegarLoop]: Abstraction has 34 states and 35 transitions. [2018-11-12 20:41:50,922 INFO L481 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-11-12 20:41:50,922 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 35 transitions. [2018-11-12 20:41:50,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2018-11-12 20:41:50,923 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:41:50,924 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:41:50,924 INFO L423 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:41:50,924 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:41:50,924 INFO L82 PathProgramCache]: Analyzing trace with hash 2043007747, now seen corresponding path program 2 times [2018-11-12 20:41:50,924 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:41:50,925 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:50,925 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:41:50,926 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:50,926 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:41:50,944 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:51,219 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 1 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:51,220 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:51,220 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:41:51,220 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:41:51,220 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:41:51,220 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:51,221 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:41:51,235 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:41:51,235 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:41:51,264 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-11-12 20:41:51,264 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:41:51,269 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:41:51,350 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 10 [2018-11-12 20:41:51,357 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2018-11-12 20:41:51,358 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:41:51,361 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:51,370 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:51,371 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:17, output treesize:13 [2018-11-12 20:41:51,540 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-11-12 20:41:51,542 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-11-12 20:41:51,542 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:41:51,543 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:51,544 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:51,545 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:15, output treesize:3 [2018-11-12 20:41:51,673 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:51,674 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:41:51,798 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-12 20:41:51,817 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-12 20:41:51,818 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:41:51,820 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:51,821 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:51,822 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:18, output treesize:5 [2018-11-12 20:41:51,861 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 2 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-11-12 20:41:51,891 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:41:51,891 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11, 10] total 21 [2018-11-12 20:41:51,891 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:41:51,891 INFO L459 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-11-12 20:41:51,892 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-11-12 20:41:51,892 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=362, Unknown=0, NotChecked=0, Total=420 [2018-11-12 20:41:51,892 INFO L87 Difference]: Start difference. First operand 34 states and 35 transitions. Second operand 20 states. [2018-11-12 20:41:52,474 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:41:52,475 INFO L93 Difference]: Finished difference Result 48 states and 49 transitions. [2018-11-12 20:41:52,475 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-11-12 20:41:52,475 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 31 [2018-11-12 20:41:52,476 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:41:52,478 INFO L225 Difference]: With dead ends: 48 [2018-11-12 20:41:52,478 INFO L226 Difference]: Without dead ends: 46 [2018-11-12 20:41:52,479 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 47 SyntacticMatches, 10 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 215 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=118, Invalid=694, Unknown=0, NotChecked=0, Total=812 [2018-11-12 20:41:52,479 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2018-11-12 20:41:52,485 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 43. [2018-11-12 20:41:52,486 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 43 states. [2018-11-12 20:41:52,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 44 transitions. [2018-11-12 20:41:52,487 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 44 transitions. Word has length 31 [2018-11-12 20:41:52,487 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:41:52,487 INFO L480 AbstractCegarLoop]: Abstraction has 43 states and 44 transitions. [2018-11-12 20:41:52,487 INFO L481 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-11-12 20:41:52,488 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 44 transitions. [2018-11-12 20:41:52,489 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-11-12 20:41:52,489 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:41:52,489 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:41:52,489 INFO L423 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:41:52,489 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:41:52,489 INFO L82 PathProgramCache]: Analyzing trace with hash -43804270, now seen corresponding path program 3 times [2018-11-12 20:41:52,490 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:41:52,490 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:52,490 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:41:52,491 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:52,491 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:41:52,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:52,704 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-11-12 20:41:52,705 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:52,705 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:41:52,705 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:41:52,706 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:41:52,706 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:52,706 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:41:52,714 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:41:52,714 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:41:52,760 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:41:52,760 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:41:52,763 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:41:52,854 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 15 proven. 7 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-11-12 20:41:52,854 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:41:52,927 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 15 proven. 7 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-11-12 20:41:52,947 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:41:52,947 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9] total 14 [2018-11-12 20:41:52,947 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:41:52,948 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-11-12 20:41:52,948 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-11-12 20:41:52,948 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=133, Unknown=0, NotChecked=0, Total=182 [2018-11-12 20:41:52,949 INFO L87 Difference]: Start difference. First operand 43 states and 44 transitions. Second operand 13 states. [2018-11-12 20:41:53,198 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:41:53,199 INFO L93 Difference]: Finished difference Result 71 states and 75 transitions. [2018-11-12 20:41:53,200 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-11-12 20:41:53,200 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 40 [2018-11-12 20:41:53,201 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:41:53,201 INFO L225 Difference]: With dead ends: 71 [2018-11-12 20:41:53,202 INFO L226 Difference]: Without dead ends: 47 [2018-11-12 20:41:53,202 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 71 SyntacticMatches, 5 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=82, Invalid=224, Unknown=0, NotChecked=0, Total=306 [2018-11-12 20:41:53,203 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-11-12 20:41:53,209 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2018-11-12 20:41:53,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-11-12 20:41:53,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 47 transitions. [2018-11-12 20:41:53,210 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 47 transitions. Word has length 40 [2018-11-12 20:41:53,211 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:41:53,211 INFO L480 AbstractCegarLoop]: Abstraction has 46 states and 47 transitions. [2018-11-12 20:41:53,211 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-11-12 20:41:53,211 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 47 transitions. [2018-11-12 20:41:53,212 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2018-11-12 20:41:53,212 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:41:53,213 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:41:53,213 INFO L423 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:41:53,213 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:41:53,213 INFO L82 PathProgramCache]: Analyzing trace with hash -1152087495, now seen corresponding path program 4 times [2018-11-12 20:41:53,213 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:41:53,214 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:53,214 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:41:53,215 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:41:53,215 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:41:53,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:53,523 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 3 proven. 30 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-11-12 20:41:53,523 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:53,523 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:41:53,524 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:41:53,524 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:41:53,524 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:41:53,524 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:41:53,533 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:41:53,533 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:41:53,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:41:53,557 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:41:53,617 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-11-12 20:41:53,622 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-11-12 20:41:53,623 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:41:53,628 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:41:53,636 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-12 20:41:53,637 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:18 [2018-11-12 20:42:00,496 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-12 20:42:00,498 INFO L682 Elim1Store]: detected equality via solver [2018-11-12 20:42:00,498 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-12 20:42:00,499 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:42:00,503 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:00,504 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:00,505 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:23, output treesize:3 [2018-11-12 20:42:00,542 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 0 proven. 30 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-11-12 20:42:00,542 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:42:02,656 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 18 [2018-11-12 20:42:02,678 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-11-12 20:42:02,679 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:42:02,680 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:02,682 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:02,682 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:20, output treesize:5 [2018-11-12 20:42:02,697 INFO L134 CoverageAnalysis]: Checked inductivity of 34 backedges. 4 proven. 26 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-11-12 20:42:02,717 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:42:02,717 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13, 12] total 20 [2018-11-12 20:42:02,718 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:42:02,718 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-11-12 20:42:02,718 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-11-12 20:42:02,719 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=325, Unknown=3, NotChecked=0, Total=380 [2018-11-12 20:42:02,719 INFO L87 Difference]: Start difference. First operand 46 states and 47 transitions. Second operand 19 states. [2018-11-12 20:42:07,191 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:42:07,191 INFO L93 Difference]: Finished difference Result 60 states and 61 transitions. [2018-11-12 20:42:07,192 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-11-12 20:42:07,192 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 43 [2018-11-12 20:42:07,192 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:42:07,193 INFO L225 Difference]: With dead ends: 60 [2018-11-12 20:42:07,194 INFO L226 Difference]: Without dead ends: 58 [2018-11-12 20:42:07,195 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 70 SyntacticMatches, 15 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 177 ImplicationChecksByTransitivity, 9.3s TimeCoverageRelationStatistics Valid=108, Invalid=645, Unknown=3, NotChecked=0, Total=756 [2018-11-12 20:42:07,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2018-11-12 20:42:07,201 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 55. [2018-11-12 20:42:07,202 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 55 states. [2018-11-12 20:42:07,203 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 56 transitions. [2018-11-12 20:42:07,203 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 56 transitions. Word has length 43 [2018-11-12 20:42:07,203 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:42:07,203 INFO L480 AbstractCegarLoop]: Abstraction has 55 states and 56 transitions. [2018-11-12 20:42:07,203 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-11-12 20:42:07,204 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 56 transitions. [2018-11-12 20:42:07,205 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2018-11-12 20:42:07,205 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:42:07,205 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:42:07,206 INFO L423 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:42:07,206 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:42:07,206 INFO L82 PathProgramCache]: Analyzing trace with hash -1561288932, now seen corresponding path program 5 times [2018-11-12 20:42:07,206 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:42:07,207 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:07,207 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:42:07,207 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:07,207 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:42:07,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:42:07,418 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 18 proven. 27 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-12 20:42:07,419 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:07,419 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:42:07,419 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:42:07,419 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:42:07,419 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:07,419 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:42:07,427 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:42:07,428 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:42:07,491 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-11-12 20:42:07,491 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:42:07,498 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:42:07,926 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 30 proven. 15 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-12 20:42:07,926 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:42:08,029 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 30 proven. 15 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-12 20:42:08,049 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:42:08,049 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 17 [2018-11-12 20:42:08,049 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:42:08,049 INFO L459 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-11-12 20:42:08,050 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-11-12 20:42:08,050 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=202, Unknown=0, NotChecked=0, Total=272 [2018-11-12 20:42:08,050 INFO L87 Difference]: Start difference. First operand 55 states and 56 transitions. Second operand 16 states. [2018-11-12 20:42:08,306 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:42:08,306 INFO L93 Difference]: Finished difference Result 88 states and 93 transitions. [2018-11-12 20:42:08,307 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-11-12 20:42:08,307 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 52 [2018-11-12 20:42:08,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:42:08,308 INFO L225 Difference]: With dead ends: 88 [2018-11-12 20:42:08,308 INFO L226 Difference]: Without dead ends: 59 [2018-11-12 20:42:08,309 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 92 SyntacticMatches, 7 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=118, Invalid=344, Unknown=0, NotChecked=0, Total=462 [2018-11-12 20:42:08,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2018-11-12 20:42:08,316 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2018-11-12 20:42:08,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 58 states. [2018-11-12 20:42:08,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 59 transitions. [2018-11-12 20:42:08,318 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 59 transitions. Word has length 52 [2018-11-12 20:42:08,318 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:42:08,318 INFO L480 AbstractCegarLoop]: Abstraction has 58 states and 59 transitions. [2018-11-12 20:42:08,318 INFO L481 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-11-12 20:42:08,318 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 59 transitions. [2018-11-12 20:42:08,319 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2018-11-12 20:42:08,320 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:42:08,320 INFO L375 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:42:08,320 INFO L423 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:42:08,320 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:42:08,321 INFO L82 PathProgramCache]: Analyzing trace with hash 1718799683, now seen corresponding path program 6 times [2018-11-12 20:42:08,321 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:42:08,322 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:08,322 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:42:08,322 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:08,322 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:42:08,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:42:08,677 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 5 proven. 57 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-11-12 20:42:08,678 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:08,678 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:42:08,678 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:42:08,678 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:42:08,678 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:08,678 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:42:08,687 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:42:08,688 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:42:08,734 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:42:08,734 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:42:08,738 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:42:09,119 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 10 [2018-11-12 20:42:09,121 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2018-11-12 20:42:09,122 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:42:09,123 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:09,128 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:09,128 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:17, output treesize:13 [2018-11-12 20:42:09,621 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-11-12 20:42:09,624 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-11-12 20:42:09,624 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:42:09,625 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:09,626 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:09,627 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:15, output treesize:3 [2018-11-12 20:42:09,699 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 0 proven. 56 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-12 20:42:09,699 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:42:09,853 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 18 [2018-11-12 20:42:09,868 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-11-12 20:42:09,869 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:42:09,871 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:09,872 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:09,872 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:20, output treesize:5 [2018-11-12 20:42:09,888 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 6 proven. 50 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-11-12 20:42:09,908 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:42:09,908 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15, 14] total 29 [2018-11-12 20:42:09,908 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:42:09,909 INFO L459 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-11-12 20:42:09,909 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-11-12 20:42:09,910 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=728, Unknown=0, NotChecked=0, Total=812 [2018-11-12 20:42:09,910 INFO L87 Difference]: Start difference. First operand 58 states and 59 transitions. Second operand 28 states. [2018-11-12 20:42:10,788 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:42:10,788 INFO L93 Difference]: Finished difference Result 72 states and 73 transitions. [2018-11-12 20:42:10,788 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-11-12 20:42:10,788 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 55 [2018-11-12 20:42:10,789 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:42:10,790 INFO L225 Difference]: With dead ends: 72 [2018-11-12 20:42:10,790 INFO L226 Difference]: Without dead ends: 70 [2018-11-12 20:42:10,791 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 86 SyntacticMatches, 16 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 439 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=162, Invalid=1320, Unknown=0, NotChecked=0, Total=1482 [2018-11-12 20:42:10,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2018-11-12 20:42:10,798 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 67. [2018-11-12 20:42:10,798 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 67 states. [2018-11-12 20:42:10,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 68 transitions. [2018-11-12 20:42:10,799 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 68 transitions. Word has length 55 [2018-11-12 20:42:10,800 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:42:10,800 INFO L480 AbstractCegarLoop]: Abstraction has 67 states and 68 transitions. [2018-11-12 20:42:10,800 INFO L481 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-11-12 20:42:10,800 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 68 transitions. [2018-11-12 20:42:10,801 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-11-12 20:42:10,801 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:42:10,801 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:42:10,802 INFO L423 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:42:10,802 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:42:10,802 INFO L82 PathProgramCache]: Analyzing trace with hash 1561077586, now seen corresponding path program 7 times [2018-11-12 20:42:10,802 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:42:10,803 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:10,803 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:42:10,803 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:10,803 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:42:10,815 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:42:11,603 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 33 proven. 43 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-11-12 20:42:11,604 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:11,604 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:42:11,604 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:42:11,604 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:42:11,604 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:11,605 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:42:11,621 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:42:11,621 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:42:11,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:42:11,642 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:42:11,802 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 50 proven. 26 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-11-12 20:42:11,803 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:42:11,945 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 50 proven. 26 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-11-12 20:42:11,965 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:42:11,965 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13, 13] total 20 [2018-11-12 20:42:11,965 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:42:11,965 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-11-12 20:42:11,966 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-11-12 20:42:11,966 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=285, Unknown=0, NotChecked=0, Total=380 [2018-11-12 20:42:11,966 INFO L87 Difference]: Start difference. First operand 67 states and 68 transitions. Second operand 19 states. [2018-11-12 20:42:12,235 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:42:12,236 INFO L93 Difference]: Finished difference Result 105 states and 111 transitions. [2018-11-12 20:42:12,236 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-11-12 20:42:12,236 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 64 [2018-11-12 20:42:12,236 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:42:12,237 INFO L225 Difference]: With dead ends: 105 [2018-11-12 20:42:12,237 INFO L226 Difference]: Without dead ends: 71 [2018-11-12 20:42:12,238 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 113 SyntacticMatches, 9 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 229 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=161, Invalid=489, Unknown=0, NotChecked=0, Total=650 [2018-11-12 20:42:12,238 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2018-11-12 20:42:12,246 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 70. [2018-11-12 20:42:12,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 70 states. [2018-11-12 20:42:12,247 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 71 transitions. [2018-11-12 20:42:12,247 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 71 transitions. Word has length 64 [2018-11-12 20:42:12,247 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:42:12,248 INFO L480 AbstractCegarLoop]: Abstraction has 70 states and 71 transitions. [2018-11-12 20:42:12,248 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-11-12 20:42:12,248 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 71 transitions. [2018-11-12 20:42:12,249 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2018-11-12 20:42:12,249 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:42:12,249 INFO L375 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:42:12,249 INFO L423 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:42:12,249 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:42:12,250 INFO L82 PathProgramCache]: Analyzing trace with hash -827370759, now seen corresponding path program 8 times [2018-11-12 20:42:12,250 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:42:12,251 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:12,251 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:42:12,251 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:12,251 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:42:12,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:42:12,685 INFO L134 CoverageAnalysis]: Checked inductivity of 114 backedges. 7 proven. 92 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-11-12 20:42:12,685 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:12,685 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:42:12,685 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:42:12,685 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:42:12,685 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:12,686 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:42:12,697 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:42:12,697 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:42:12,744 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-11-12 20:42:12,744 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:42:12,750 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:42:12,866 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-11-12 20:42:12,867 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-11-12 20:42:12,868 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:42:12,869 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:12,874 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:12,875 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-11-12 20:42:13,889 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-12 20:42:13,904 INFO L682 Elim1Store]: detected equality via solver [2018-11-12 20:42:13,905 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-12 20:42:13,905 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:42:13,912 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:13,919 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:13,919 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:32, output treesize:3 [2018-11-12 20:42:13,985 INFO L134 CoverageAnalysis]: Checked inductivity of 114 backedges. 38 proven. 52 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-11-12 20:42:13,985 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:42:14,440 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-12 20:42:14,458 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-12 20:42:14,459 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:42:14,461 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:14,469 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:14,470 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:25, output treesize:7 [2018-11-12 20:42:14,683 INFO L134 CoverageAnalysis]: Checked inductivity of 114 backedges. 38 proven. 52 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-11-12 20:42:14,704 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:42:14,705 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 19, 18] total 42 [2018-11-12 20:42:14,705 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:42:14,706 INFO L459 AbstractCegarLoop]: Interpolant automaton has 34 states [2018-11-12 20:42:14,706 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2018-11-12 20:42:14,707 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=198, Invalid=1524, Unknown=0, NotChecked=0, Total=1722 [2018-11-12 20:42:14,707 INFO L87 Difference]: Start difference. First operand 70 states and 71 transitions. Second operand 34 states. [2018-11-12 20:42:27,697 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:42:27,697 INFO L93 Difference]: Finished difference Result 119 states and 125 transitions. [2018-11-12 20:42:27,697 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-11-12 20:42:27,697 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 67 [2018-11-12 20:42:27,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:42:27,699 INFO L225 Difference]: With dead ends: 119 [2018-11-12 20:42:27,700 INFO L226 Difference]: Without dead ends: 85 [2018-11-12 20:42:27,702 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 188 GetRequests, 98 SyntacticMatches, 17 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1336 ImplicationChecksByTransitivity, 9.5s TimeCoverageRelationStatistics Valid=590, Invalid=4960, Unknown=0, NotChecked=0, Total=5550 [2018-11-12 20:42:27,702 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 85 states. [2018-11-12 20:42:27,711 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 85 to 82. [2018-11-12 20:42:27,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 82 states. [2018-11-12 20:42:27,712 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 83 transitions. [2018-11-12 20:42:27,712 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 83 transitions. Word has length 67 [2018-11-12 20:42:27,713 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:42:27,713 INFO L480 AbstractCegarLoop]: Abstraction has 82 states and 83 transitions. [2018-11-12 20:42:27,713 INFO L481 AbstractCegarLoop]: Interpolant automaton has 34 states. [2018-11-12 20:42:27,713 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 83 transitions. [2018-11-12 20:42:27,714 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2018-11-12 20:42:27,715 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:42:27,715 INFO L375 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:42:27,715 INFO L423 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:42:27,715 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:42:27,715 INFO L82 PathProgramCache]: Analyzing trace with hash -83912829, now seen corresponding path program 9 times [2018-11-12 20:42:27,716 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:42:27,716 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:27,716 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:42:27,717 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:42:27,717 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:42:27,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:42:28,266 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 9 proven. 135 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-11-12 20:42:28,266 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:28,266 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:42:28,266 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:42:28,266 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:42:28,266 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:42:28,267 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:42:28,275 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:42:28,275 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:42:28,315 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:42:28,316 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:42:28,321 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:42:28,367 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-11-12 20:42:28,369 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-11-12 20:42:28,369 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:42:28,375 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:42:28,383 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-12 20:42:28,383 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:18 [2018-11-12 20:43:05,032 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 17 [2018-11-12 20:43:05,033 INFO L682 Elim1Store]: detected equality via solver [2018-11-12 20:43:05,034 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 13 [2018-11-12 20:43:05,034 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:43:05,037 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:05,038 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:05,038 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:21, output treesize:3 [2018-11-12 20:43:05,099 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 0 proven. 132 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-11-12 20:43:05,100 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:43:07,232 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-12 20:43:07,255 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-12 20:43:07,255 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:43:07,257 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:07,258 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:07,259 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:18, output treesize:5 [2018-11-12 20:43:07,278 INFO L134 CoverageAnalysis]: Checked inductivity of 172 backedges. 10 proven. 122 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-11-12 20:43:07,298 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:43:07,298 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19, 18] total 29 [2018-11-12 20:43:07,298 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:43:07,299 INFO L459 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-11-12 20:43:07,299 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-11-12 20:43:07,300 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=727, Unknown=6, NotChecked=0, Total=812 [2018-11-12 20:43:07,300 INFO L87 Difference]: Start difference. First operand 82 states and 83 transitions. Second operand 28 states. [2018-11-12 20:43:16,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:43:16,742 INFO L93 Difference]: Finished difference Result 96 states and 97 transitions. [2018-11-12 20:43:16,742 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-11-12 20:43:16,743 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 79 [2018-11-12 20:43:16,744 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:43:16,744 INFO L225 Difference]: With dead ends: 96 [2018-11-12 20:43:16,744 INFO L226 Difference]: Without dead ends: 94 [2018-11-12 20:43:16,745 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 192 GetRequests, 130 SyntacticMatches, 24 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 384 ImplicationChecksByTransitivity, 39.4s TimeCoverageRelationStatistics Valid=159, Invalid=1395, Unknown=6, NotChecked=0, Total=1560 [2018-11-12 20:43:16,746 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2018-11-12 20:43:16,755 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 91. [2018-11-12 20:43:16,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 91 states. [2018-11-12 20:43:16,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 92 transitions. [2018-11-12 20:43:16,756 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 92 transitions. Word has length 79 [2018-11-12 20:43:16,757 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:43:16,757 INFO L480 AbstractCegarLoop]: Abstraction has 91 states and 92 transitions. [2018-11-12 20:43:16,757 INFO L481 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-11-12 20:43:16,757 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 92 transitions. [2018-11-12 20:43:16,758 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2018-11-12 20:43:16,758 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:43:16,758 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:43:16,759 INFO L423 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:43:16,759 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:43:16,759 INFO L82 PathProgramCache]: Analyzing trace with hash 731833618, now seen corresponding path program 10 times [2018-11-12 20:43:16,759 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:43:16,760 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:43:16,760 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:43:16,760 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:43:16,760 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:43:16,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:43:17,556 INFO L134 CoverageAnalysis]: Checked inductivity of 222 backedges. 78 proven. 84 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2018-11-12 20:43:17,557 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:43:17,557 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:43:17,557 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:43:17,557 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:43:17,557 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:43:17,557 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:43:17,566 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:43:17,566 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:43:17,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:43:17,605 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:43:17,772 INFO L134 CoverageAnalysis]: Checked inductivity of 222 backedges. 105 proven. 57 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2018-11-12 20:43:17,772 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:43:17,970 INFO L134 CoverageAnalysis]: Checked inductivity of 222 backedges. 105 proven. 57 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2018-11-12 20:43:17,989 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:43:17,990 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17, 17] total 26 [2018-11-12 20:43:17,990 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:43:17,990 INFO L459 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-11-12 20:43:17,991 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-11-12 20:43:17,991 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=493, Unknown=0, NotChecked=0, Total=650 [2018-11-12 20:43:17,991 INFO L87 Difference]: Start difference. First operand 91 states and 92 transitions. Second operand 25 states. [2018-11-12 20:43:18,225 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:43:18,225 INFO L93 Difference]: Finished difference Result 139 states and 147 transitions. [2018-11-12 20:43:18,225 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-11-12 20:43:18,225 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 88 [2018-11-12 20:43:18,225 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:43:18,226 INFO L225 Difference]: With dead ends: 139 [2018-11-12 20:43:18,226 INFO L226 Difference]: Without dead ends: 95 [2018-11-12 20:43:18,227 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 155 SyntacticMatches, 13 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 427 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=268, Invalid=854, Unknown=0, NotChecked=0, Total=1122 [2018-11-12 20:43:18,228 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2018-11-12 20:43:18,237 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 94. [2018-11-12 20:43:18,237 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 94 states. [2018-11-12 20:43:18,238 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 95 transitions. [2018-11-12 20:43:18,238 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 95 transitions. Word has length 88 [2018-11-12 20:43:18,238 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:43:18,239 INFO L480 AbstractCegarLoop]: Abstraction has 94 states and 95 transitions. [2018-11-12 20:43:18,239 INFO L481 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-11-12 20:43:18,239 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 95 transitions. [2018-11-12 20:43:18,240 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2018-11-12 20:43:18,240 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:43:18,240 INFO L375 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:43:18,241 INFO L423 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:43:18,241 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:43:18,241 INFO L82 PathProgramCache]: Analyzing trace with hash -55358535, now seen corresponding path program 11 times [2018-11-12 20:43:18,241 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:43:18,242 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:43:18,242 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:43:18,242 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:43:18,242 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:43:18,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:43:18,769 INFO L134 CoverageAnalysis]: Checked inductivity of 242 backedges. 11 proven. 186 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-11-12 20:43:18,770 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:43:18,770 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:43:18,770 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:43:18,770 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:43:18,770 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:43:18,770 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:43:18,780 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:43:18,780 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:43:18,817 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-11-12 20:43:18,818 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:43:18,822 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:43:19,384 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-11-12 20:43:19,386 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-11-12 20:43:19,386 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:43:19,388 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:19,399 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:19,399 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-11-12 20:43:22,780 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-12 20:43:22,804 INFO L682 Elim1Store]: detected equality via solver [2018-11-12 20:43:22,805 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-12 20:43:22,805 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:43:22,863 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:22,983 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:22,983 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:32, output treesize:3 [2018-11-12 20:43:24,108 INFO L134 CoverageAnalysis]: Checked inductivity of 242 backedges. 87 proven. 95 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2018-11-12 20:43:24,109 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:43:24,924 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-12 20:43:24,936 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-12 20:43:24,937 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:43:24,939 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:24,945 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:24,946 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:25, output treesize:7 [2018-11-12 20:43:25,122 INFO L134 CoverageAnalysis]: Checked inductivity of 242 backedges. 87 proven. 95 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2018-11-12 20:43:25,143 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:43:25,144 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 23, 22] total 52 [2018-11-12 20:43:25,144 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:43:25,144 INFO L459 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-11-12 20:43:25,145 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-11-12 20:43:25,145 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=291, Invalid=2361, Unknown=0, NotChecked=0, Total=2652 [2018-11-12 20:43:25,146 INFO L87 Difference]: Start difference. First operand 94 states and 95 transitions. Second operand 42 states. [2018-11-12 20:43:30,302 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:43:30,303 INFO L93 Difference]: Finished difference Result 149 states and 158 transitions. [2018-11-12 20:43:30,303 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-11-12 20:43:30,303 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 91 [2018-11-12 20:43:30,304 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:43:30,305 INFO L225 Difference]: With dead ends: 149 [2018-11-12 20:43:30,305 INFO L226 Difference]: Without dead ends: 109 [2018-11-12 20:43:30,308 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 249 GetRequests, 134 SyntacticMatches, 23 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2095 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=852, Invalid=7890, Unknown=0, NotChecked=0, Total=8742 [2018-11-12 20:43:30,308 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2018-11-12 20:43:30,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 106. [2018-11-12 20:43:30,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 106 states. [2018-11-12 20:43:30,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 107 transitions. [2018-11-12 20:43:30,319 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 107 transitions. Word has length 91 [2018-11-12 20:43:30,319 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:43:30,319 INFO L480 AbstractCegarLoop]: Abstraction has 106 states and 107 transitions. [2018-11-12 20:43:30,319 INFO L481 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-11-12 20:43:30,319 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 107 transitions. [2018-11-12 20:43:30,321 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2018-11-12 20:43:30,321 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:43:30,321 INFO L375 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:43:30,321 INFO L423 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:43:30,322 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:43:30,322 INFO L82 PathProgramCache]: Analyzing trace with hash 762851779, now seen corresponding path program 12 times [2018-11-12 20:43:30,322 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:43:30,322 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:43:30,323 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:43:30,323 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:43:30,323 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:43:30,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:43:30,796 INFO L134 CoverageAnalysis]: Checked inductivity of 324 backedges. 13 proven. 245 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-11-12 20:43:30,796 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:43:30,796 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:43:30,796 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:43:30,796 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:43:30,796 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:43:30,796 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:43:30,805 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:43:30,806 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:43:30,865 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:43:30,865 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:43:30,869 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:43:30,922 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-11-12 20:43:30,924 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-11-12 20:43:30,924 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:43:30,931 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:43:30,941 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-12 20:43:30,942 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:18 [2018-11-12 20:44:27,632 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-12 20:44:27,634 INFO L682 Elim1Store]: detected equality via solver [2018-11-12 20:44:27,635 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-12 20:44:27,635 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:44:27,637 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:27,638 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:27,638 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:23, output treesize:3 [2018-11-12 20:44:27,723 INFO L134 CoverageAnalysis]: Checked inductivity of 324 backedges. 0 proven. 240 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-11-12 20:44:27,723 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:44:30,000 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 18 [2018-11-12 20:44:30,014 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-11-12 20:44:30,015 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:44:30,016 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:30,017 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:30,017 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:20, output treesize:5 [2018-11-12 20:44:30,043 INFO L134 CoverageAnalysis]: Checked inductivity of 324 backedges. 14 proven. 226 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2018-11-12 20:44:30,064 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:44:30,064 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 23, 22] total 35 [2018-11-12 20:44:30,064 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:44:30,065 INFO L459 AbstractCegarLoop]: Interpolant automaton has 34 states [2018-11-12 20:44:30,065 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2018-11-12 20:44:30,066 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=1085, Unknown=8, NotChecked=0, Total=1190 [2018-11-12 20:44:30,066 INFO L87 Difference]: Start difference. First operand 106 states and 107 transitions. Second operand 34 states. [2018-11-12 20:44:44,257 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:44:44,257 INFO L93 Difference]: Finished difference Result 120 states and 121 transitions. [2018-11-12 20:44:44,257 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2018-11-12 20:44:44,258 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 103 [2018-11-12 20:44:44,258 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:44:44,259 INFO L225 Difference]: With dead ends: 120 [2018-11-12 20:44:44,259 INFO L226 Difference]: Without dead ends: 118 [2018-11-12 20:44:44,260 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 171 SyntacticMatches, 29 SemanticMatches, 46 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 554 ImplicationChecksByTransitivity, 59.6s TimeCoverageRelationStatistics Valid=193, Invalid=2055, Unknown=8, NotChecked=0, Total=2256 [2018-11-12 20:44:44,261 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2018-11-12 20:44:44,270 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 115. [2018-11-12 20:44:44,270 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 115 states. [2018-11-12 20:44:44,271 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 116 transitions. [2018-11-12 20:44:44,271 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 116 transitions. Word has length 103 [2018-11-12 20:44:44,271 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:44:44,271 INFO L480 AbstractCegarLoop]: Abstraction has 115 states and 116 transitions. [2018-11-12 20:44:44,271 INFO L481 AbstractCegarLoop]: Interpolant automaton has 34 states. [2018-11-12 20:44:44,271 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 116 transitions. [2018-11-12 20:44:44,273 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2018-11-12 20:44:44,273 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:44:44,273 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:44:44,273 INFO L423 AbstractCegarLoop]: === Iteration 16 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:44:44,274 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:44:44,274 INFO L82 PathProgramCache]: Analyzing trace with hash -2138058030, now seen corresponding path program 13 times [2018-11-12 20:44:44,274 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:44:44,275 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:44:44,275 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:44:44,275 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:44:44,275 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:44:44,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:44:44,638 INFO L134 CoverageAnalysis]: Checked inductivity of 392 backedges. 143 proven. 137 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2018-11-12 20:44:44,639 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:44:44,639 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:44:44,639 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:44:44,639 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:44:44,639 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:44:44,639 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:44:44,649 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:44:44,649 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:44:44,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:44:44,690 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:44:44,954 INFO L134 CoverageAnalysis]: Checked inductivity of 392 backedges. 180 proven. 100 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2018-11-12 20:44:44,954 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:44:45,131 INFO L134 CoverageAnalysis]: Checked inductivity of 392 backedges. 180 proven. 100 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2018-11-12 20:44:45,153 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:44:45,153 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21, 21] total 32 [2018-11-12 20:44:45,153 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:44:45,153 INFO L459 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-11-12 20:44:45,154 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-11-12 20:44:45,154 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=235, Invalid=757, Unknown=0, NotChecked=0, Total=992 [2018-11-12 20:44:45,154 INFO L87 Difference]: Start difference. First operand 115 states and 116 transitions. Second operand 31 states. [2018-11-12 20:44:45,566 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:44:45,567 INFO L93 Difference]: Finished difference Result 173 states and 183 transitions. [2018-11-12 20:44:45,567 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-11-12 20:44:45,567 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 112 [2018-11-12 20:44:45,567 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:44:45,568 INFO L225 Difference]: With dead ends: 173 [2018-11-12 20:44:45,568 INFO L226 Difference]: Without dead ends: 119 [2018-11-12 20:44:45,570 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 254 GetRequests, 197 SyntacticMatches, 17 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 681 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=403, Invalid=1319, Unknown=0, NotChecked=0, Total=1722 [2018-11-12 20:44:45,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2018-11-12 20:44:45,579 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 118. [2018-11-12 20:44:45,580 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 118 states. [2018-11-12 20:44:45,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 119 transitions. [2018-11-12 20:44:45,580 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 119 transitions. Word has length 112 [2018-11-12 20:44:45,581 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:44:45,581 INFO L480 AbstractCegarLoop]: Abstraction has 118 states and 119 transitions. [2018-11-12 20:44:45,581 INFO L481 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-11-12 20:44:45,581 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 119 transitions. [2018-11-12 20:44:45,582 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 116 [2018-11-12 20:44:45,582 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:44:45,582 INFO L375 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:44:45,582 INFO L423 AbstractCegarLoop]: === Iteration 17 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:44:45,583 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:44:45,583 INFO L82 PathProgramCache]: Analyzing trace with hash -808160135, now seen corresponding path program 14 times [2018-11-12 20:44:45,583 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:44:45,584 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:44:45,584 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:44:45,584 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:44:45,584 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:44:45,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:44:46,252 INFO L134 CoverageAnalysis]: Checked inductivity of 418 backedges. 15 proven. 312 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2018-11-12 20:44:46,252 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:44:46,252 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:44:46,252 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:44:46,252 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:44:46,253 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:44:46,253 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:44:46,263 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:44:46,263 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:44:46,339 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-11-12 20:44:46,339 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:44:46,342 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:44:46,735 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-11-12 20:44:46,749 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-11-12 20:44:46,749 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:44:46,751 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:46,755 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:46,755 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-11-12 20:44:49,852 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-12 20:44:49,855 INFO L682 Elim1Store]: detected equality via solver [2018-11-12 20:44:49,856 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-12 20:44:49,856 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:44:49,867 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:49,874 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:49,874 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:32, output treesize:3 [2018-11-12 20:44:49,998 INFO L134 CoverageAnalysis]: Checked inductivity of 418 backedges. 160 proven. 150 refuted. 24 times theorem prover too weak. 84 trivial. 0 not checked. [2018-11-12 20:44:49,998 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:44:50,759 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-12 20:44:50,774 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-12 20:44:50,775 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:44:50,777 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:50,781 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:44:50,781 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:25, output treesize:7 [2018-11-12 20:44:51,010 INFO L134 CoverageAnalysis]: Checked inductivity of 418 backedges. 156 proven. 150 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2018-11-12 20:44:51,032 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:44:51,033 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 28, 26] total 63 [2018-11-12 20:44:51,033 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:44:51,033 INFO L459 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-11-12 20:44:51,034 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-11-12 20:44:51,035 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=430, Invalid=3475, Unknown=1, NotChecked=0, Total=3906 [2018-11-12 20:44:51,035 INFO L87 Difference]: Start difference. First operand 118 states and 119 transitions. Second operand 51 states. [2018-11-12 20:45:11,001 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:45:11,001 INFO L93 Difference]: Finished difference Result 203 states and 210 transitions. [2018-11-12 20:45:11,001 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 70 states. [2018-11-12 20:45:11,002 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 115 [2018-11-12 20:45:11,002 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:45:11,003 INFO L225 Difference]: With dead ends: 203 [2018-11-12 20:45:11,003 INFO L226 Difference]: Without dead ends: 133 [2018-11-12 20:45:11,008 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 319 GetRequests, 169 SyntacticMatches, 28 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3785 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=1333, Invalid=13918, Unknown=1, NotChecked=0, Total=15252 [2018-11-12 20:45:11,008 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2018-11-12 20:45:11,020 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 130. [2018-11-12 20:45:11,020 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 130 states. [2018-11-12 20:45:11,021 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 131 transitions. [2018-11-12 20:45:11,021 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 131 transitions. Word has length 115 [2018-11-12 20:45:11,021 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:45:11,021 INFO L480 AbstractCegarLoop]: Abstraction has 130 states and 131 transitions. [2018-11-12 20:45:11,021 INFO L481 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-11-12 20:45:11,022 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 131 transitions. [2018-11-12 20:45:11,022 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2018-11-12 20:45:11,022 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:45:11,023 INFO L375 BasicCegarLoop]: trace histogram [11, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:45:11,023 INFO L423 AbstractCegarLoop]: === Iteration 18 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:45:11,023 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:45:11,023 INFO L82 PathProgramCache]: Analyzing trace with hash -387408893, now seen corresponding path program 15 times [2018-11-12 20:45:11,023 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:45:11,024 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:11,024 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:45:11,024 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:11,024 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:45:11,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:45:12,028 INFO L134 CoverageAnalysis]: Checked inductivity of 524 backedges. 17 proven. 387 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2018-11-12 20:45:12,028 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:12,028 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:45:12,029 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:45:12,029 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:45:12,029 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:12,029 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:45:12,038 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:45:12,038 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:45:12,239 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:45:12,239 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:45:12,244 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:45:12,570 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 10 [2018-11-12 20:45:12,572 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2018-11-12 20:45:12,572 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:12,573 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:12,578 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:12,578 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:17, output treesize:13 [2018-11-12 20:45:13,749 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2018-11-12 20:45:13,753 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 3 [2018-11-12 20:45:13,753 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:13,754 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:13,755 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:13,756 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:15, output treesize:3 [2018-11-12 20:45:13,874 INFO L134 CoverageAnalysis]: Checked inductivity of 524 backedges. 0 proven. 380 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2018-11-12 20:45:13,875 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:45:14,181 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-12 20:45:14,195 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-12 20:45:14,195 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:14,197 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:14,198 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:14,198 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:18, output treesize:5 [2018-11-12 20:45:14,234 INFO L134 CoverageAnalysis]: Checked inductivity of 524 backedges. 18 proven. 362 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2018-11-12 20:45:14,256 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:45:14,256 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 27, 26] total 53 [2018-11-12 20:45:14,257 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:45:14,257 INFO L459 AbstractCegarLoop]: Interpolant automaton has 52 states [2018-11-12 20:45:14,257 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2018-11-12 20:45:14,258 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=162, Invalid=2594, Unknown=0, NotChecked=0, Total=2756 [2018-11-12 20:45:14,259 INFO L87 Difference]: Start difference. First operand 130 states and 131 transitions. Second operand 52 states. [2018-11-12 20:45:16,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:45:16,603 INFO L93 Difference]: Finished difference Result 144 states and 145 transitions. [2018-11-12 20:45:16,603 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-11-12 20:45:16,603 INFO L78 Accepts]: Start accepts. Automaton has 52 states. Word has length 127 [2018-11-12 20:45:16,604 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:45:16,605 INFO L225 Difference]: With dead ends: 144 [2018-11-12 20:45:16,605 INFO L226 Difference]: Without dead ends: 142 [2018-11-12 20:45:16,608 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 301 GetRequests, 200 SyntacticMatches, 34 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1591 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=294, Invalid=4398, Unknown=0, NotChecked=0, Total=4692 [2018-11-12 20:45:16,608 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2018-11-12 20:45:16,620 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 139. [2018-11-12 20:45:16,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 139 states. [2018-11-12 20:45:16,621 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 140 transitions. [2018-11-12 20:45:16,621 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 140 transitions. Word has length 127 [2018-11-12 20:45:16,622 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:45:16,622 INFO L480 AbstractCegarLoop]: Abstraction has 139 states and 140 transitions. [2018-11-12 20:45:16,622 INFO L481 AbstractCegarLoop]: Interpolant automaton has 52 states. [2018-11-12 20:45:16,622 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 140 transitions. [2018-11-12 20:45:16,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 137 [2018-11-12 20:45:16,623 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:45:16,623 INFO L375 BasicCegarLoop]: trace histogram [11, 11, 11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:45:16,623 INFO L423 AbstractCegarLoop]: === Iteration 19 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:45:16,623 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:45:16,624 INFO L82 PathProgramCache]: Analyzing trace with hash 508752018, now seen corresponding path program 16 times [2018-11-12 20:45:16,624 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:45:16,624 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:16,625 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:45:16,625 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:16,625 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:45:16,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:45:17,267 INFO L134 CoverageAnalysis]: Checked inductivity of 610 backedges. 228 proven. 202 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2018-11-12 20:45:17,267 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:17,267 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:45:17,267 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:45:17,267 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:45:17,268 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:17,268 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:45:17,277 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:45:17,277 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:45:17,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:45:17,317 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:45:17,635 INFO L134 CoverageAnalysis]: Checked inductivity of 610 backedges. 275 proven. 155 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2018-11-12 20:45:17,635 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:45:17,956 INFO L134 CoverageAnalysis]: Checked inductivity of 610 backedges. 275 proven. 155 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2018-11-12 20:45:17,976 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:45:17,977 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25, 25] total 38 [2018-11-12 20:45:17,977 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:45:17,977 INFO L459 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-11-12 20:45:17,978 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-11-12 20:45:17,978 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=329, Invalid=1077, Unknown=0, NotChecked=0, Total=1406 [2018-11-12 20:45:17,978 INFO L87 Difference]: Start difference. First operand 139 states and 140 transitions. Second operand 37 states. [2018-11-12 20:45:18,552 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:45:18,552 INFO L93 Difference]: Finished difference Result 207 states and 219 transitions. [2018-11-12 20:45:18,555 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-11-12 20:45:18,555 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 136 [2018-11-12 20:45:18,555 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:45:18,556 INFO L225 Difference]: With dead ends: 207 [2018-11-12 20:45:18,556 INFO L226 Difference]: Without dead ends: 143 [2018-11-12 20:45:18,557 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 308 GetRequests, 239 SyntacticMatches, 21 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 991 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=566, Invalid=1884, Unknown=0, NotChecked=0, Total=2450 [2018-11-12 20:45:18,558 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2018-11-12 20:45:18,568 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 142. [2018-11-12 20:45:18,569 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 142 states. [2018-11-12 20:45:18,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 143 transitions. [2018-11-12 20:45:18,570 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 143 transitions. Word has length 136 [2018-11-12 20:45:18,570 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:45:18,570 INFO L480 AbstractCegarLoop]: Abstraction has 142 states and 143 transitions. [2018-11-12 20:45:18,570 INFO L481 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-11-12 20:45:18,570 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 143 transitions. [2018-11-12 20:45:18,571 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 140 [2018-11-12 20:45:18,571 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:45:18,571 INFO L375 BasicCegarLoop]: trace histogram [12, 11, 11, 11, 11, 11, 11, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:45:18,571 INFO L423 AbstractCegarLoop]: === Iteration 20 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:45:18,571 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:45:18,572 INFO L82 PathProgramCache]: Analyzing trace with hash 2105986361, now seen corresponding path program 17 times [2018-11-12 20:45:18,572 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:45:18,572 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:18,573 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:45:18,573 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:18,573 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:45:18,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:45:19,231 INFO L134 CoverageAnalysis]: Checked inductivity of 642 backedges. 19 proven. 470 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2018-11-12 20:45:19,231 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:19,231 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:45:19,231 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:45:19,231 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:45:19,231 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:19,232 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:45:19,241 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-11-12 20:45:19,241 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-11-12 20:45:19,377 INFO L249 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) [2018-11-12 20:45:19,377 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:45:19,383 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:45:19,685 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-11-12 20:45:19,687 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-11-12 20:45:19,687 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:19,689 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:19,693 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:19,694 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:19, output treesize:15 [2018-11-12 20:45:22,803 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 19 [2018-11-12 20:45:22,805 INFO L682 Elim1Store]: detected equality via solver [2018-11-12 20:45:22,806 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 15 [2018-11-12 20:45:22,807 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:22,818 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:22,824 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:22,824 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 5 variables, input treesize:32, output treesize:3 [2018-11-12 20:45:22,979 INFO L134 CoverageAnalysis]: Checked inductivity of 642 backedges. 245 proven. 217 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2018-11-12 20:45:22,979 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:45:24,187 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-12 20:45:24,201 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-12 20:45:24,201 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:24,203 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:24,210 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:24,210 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:25, output treesize:7 [2018-11-12 20:45:24,556 INFO L134 CoverageAnalysis]: Checked inductivity of 642 backedges. 245 proven. 217 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2018-11-12 20:45:24,578 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:45:24,578 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 31, 30] total 72 [2018-11-12 20:45:24,578 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:45:24,579 INFO L459 AbstractCegarLoop]: Interpolant automaton has 58 states [2018-11-12 20:45:24,579 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 58 interpolants. [2018-11-12 20:45:24,579 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=537, Invalid=4575, Unknown=0, NotChecked=0, Total=5112 [2018-11-12 20:45:24,580 INFO L87 Difference]: Start difference. First operand 142 states and 143 transitions. Second operand 58 states. [2018-11-12 20:45:31,251 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:45:31,251 INFO L93 Difference]: Finished difference Result 250 states and 252 transitions. [2018-11-12 20:45:31,252 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-11-12 20:45:31,252 INFO L78 Accepts]: Start accepts. Automaton has 58 states. Word has length 139 [2018-11-12 20:45:31,252 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:45:31,253 INFO L225 Difference]: With dead ends: 250 [2018-11-12 20:45:31,253 INFO L226 Difference]: Without dead ends: 146 [2018-11-12 20:45:31,257 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 360 GetRequests, 205 SyntacticMatches, 35 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3408 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=1428, Invalid=13334, Unknown=0, NotChecked=0, Total=14762 [2018-11-12 20:45:31,257 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2018-11-12 20:45:31,271 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 145. [2018-11-12 20:45:31,271 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 145 states. [2018-11-12 20:45:31,272 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 146 transitions. [2018-11-12 20:45:31,272 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 146 transitions. Word has length 139 [2018-11-12 20:45:31,273 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:45:31,273 INFO L480 AbstractCegarLoop]: Abstraction has 145 states and 146 transitions. [2018-11-12 20:45:31,273 INFO L481 AbstractCegarLoop]: Interpolant automaton has 58 states. [2018-11-12 20:45:31,273 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 146 transitions. [2018-11-12 20:45:31,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 143 [2018-11-12 20:45:31,274 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:45:31,274 INFO L375 BasicCegarLoop]: trace histogram [13, 12, 12, 11, 11, 11, 11, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:45:31,274 INFO L423 AbstractCegarLoop]: === Iteration 21 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:45:31,275 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:45:31,275 INFO L82 PathProgramCache]: Analyzing trace with hash 1371626290, now seen corresponding path program 18 times [2018-11-12 20:45:31,275 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:45:31,276 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:31,278 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:45:31,278 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:31,278 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:45:31,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:45:32,064 INFO L134 CoverageAnalysis]: Checked inductivity of 677 backedges. 19 proven. 505 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2018-11-12 20:45:32,064 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:32,064 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:45:32,065 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:45:32,065 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:45:32,065 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:32,065 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:45:32,073 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-11-12 20:45:32,074 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-11-12 20:45:32,303 INFO L249 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-11-12 20:45:32,303 INFO L250 tOrderPrioritization]: Conjunction of SSA is unsat [2018-11-12 20:45:32,308 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:45:32,828 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-11-12 20:45:32,830 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-11-12 20:45:32,830 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:32,832 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:32,838 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:32,838 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:22, output treesize:18 [2018-11-12 20:45:32,921 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 25 treesize of output 20 [2018-11-12 20:45:32,924 INFO L700 Elim1Store]: detected not equals via solver [2018-11-12 20:45:32,925 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 31 [2018-11-12 20:45:32,925 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:32,939 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:32,948 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-12 20:45:32,949 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:31, output treesize:27 [2018-11-12 20:45:35,097 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 18 [2018-11-12 20:45:35,099 INFO L700 Elim1Store]: detected not equals via solver [2018-11-12 20:45:35,099 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 10 [2018-11-12 20:45:35,099 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:35,102 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:35,106 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:35,106 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:27, output treesize:3 [2018-11-12 20:45:35,288 INFO L134 CoverageAnalysis]: Checked inductivity of 677 backedges. 0 proven. 497 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2018-11-12 20:45:35,288 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-11-12 20:45:35,691 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 16 [2018-11-12 20:45:35,704 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 3 [2018-11-12 20:45:35,704 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:35,706 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:35,707 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:35,707 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:18, output treesize:5 [2018-11-12 20:45:35,751 INFO L134 CoverageAnalysis]: Checked inductivity of 677 backedges. 22 proven. 474 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2018-11-12 20:45:35,772 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 3 imperfect interpolant sequences. [2018-11-12 20:45:35,772 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31, 29] total 61 [2018-11-12 20:45:35,772 INFO L249 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-11-12 20:45:35,773 INFO L459 AbstractCegarLoop]: Interpolant automaton has 59 states [2018-11-12 20:45:35,773 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 59 interpolants. [2018-11-12 20:45:35,774 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=210, Invalid=3450, Unknown=0, NotChecked=0, Total=3660 [2018-11-12 20:45:35,774 INFO L87 Difference]: Start difference. First operand 145 states and 146 transitions. Second operand 59 states. [2018-11-12 20:45:40,200 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-11-12 20:45:40,200 INFO L93 Difference]: Finished difference Result 158 states and 159 transitions. [2018-11-12 20:45:40,200 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-11-12 20:45:40,201 INFO L78 Accepts]: Start accepts. Automaton has 59 states. Word has length 142 [2018-11-12 20:45:40,201 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-11-12 20:45:40,202 INFO L225 Difference]: With dead ends: 158 [2018-11-12 20:45:40,202 INFO L226 Difference]: Without dead ends: 156 [2018-11-12 20:45:40,203 INFO L604 BasicCegarLoop]: 0 DeclaredPredicates, 346 GetRequests, 221 SyntacticMatches, 38 SemanticMatches, 87 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2566 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=532, Invalid=7300, Unknown=0, NotChecked=0, Total=7832 [2018-11-12 20:45:40,203 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2018-11-12 20:45:40,220 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 154. [2018-11-12 20:45:40,220 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 154 states. [2018-11-12 20:45:40,221 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 155 transitions. [2018-11-12 20:45:40,221 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 155 transitions. Word has length 142 [2018-11-12 20:45:40,221 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-11-12 20:45:40,221 INFO L480 AbstractCegarLoop]: Abstraction has 154 states and 155 transitions. [2018-11-12 20:45:40,222 INFO L481 AbstractCegarLoop]: Interpolant automaton has 59 states. [2018-11-12 20:45:40,222 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 155 transitions. [2018-11-12 20:45:40,223 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 152 [2018-11-12 20:45:40,223 INFO L367 BasicCegarLoop]: Found error trace [2018-11-12 20:45:40,223 INFO L375 BasicCegarLoop]: trace histogram [13, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-11-12 20:45:40,223 INFO L423 AbstractCegarLoop]: === Iteration 22 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-11-12 20:45:40,224 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-11-12 20:45:40,224 INFO L82 PathProgramCache]: Analyzing trace with hash -849553853, now seen corresponding path program 19 times [2018-11-12 20:45:40,224 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-11-12 20:45:40,225 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:40,225 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-11-12 20:45:40,225 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-11-12 20:45:40,225 INFO L286 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-11-12 20:45:40,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:45:40,948 INFO L134 CoverageAnalysis]: Checked inductivity of 772 backedges. 21 proven. 561 refuted. 0 times theorem prover too weak. 190 trivial. 0 not checked. [2018-11-12 20:45:40,948 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:40,948 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-11-12 20:45:40,948 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-11-12 20:45:40,948 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-11-12 20:45:40,948 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-11-12 20:45:40,948 INFO L192 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:45:40,958 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-11-12 20:45:40,958 INFO L286 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-11-12 20:45:41,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-11-12 20:45:41,005 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-11-12 20:45:41,025 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 12 [2018-11-12 20:45:41,027 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-11-12 20:45:41,027 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-11-12 20:45:41,031 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-11-12 20:45:41,039 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-11-12 20:45:41,040 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:22, output treesize:18 Received shutdown request... [2018-11-12 20:46:16,024 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-11-12 20:46:16,224 WARN L521 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-11-12 20:46:16,225 WARN L549 AbstractCegarLoop]: Verification canceled [2018-11-12 20:46:16,231 WARN L205 ceAbstractionStarter]: Timeout [2018-11-12 20:46:16,231 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 12.11 08:46:16 BoogieIcfgContainer [2018-11-12 20:46:16,231 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-11-12 20:46:16,232 INFO L168 Benchmark]: Toolchain (without parser) took 270090.71 ms. Allocated memory was 1.5 GB in the beginning and 2.4 GB in the end (delta: 879.8 MB). Free memory was 1.4 GB in the beginning and 1.7 GB in the end (delta: -243.2 MB). Peak memory consumption was 636.5 MB. Max. memory is 7.1 GB. [2018-11-12 20:46:16,232 INFO L168 Benchmark]: CDTParser took 0.24 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-12 20:46:16,232 INFO L168 Benchmark]: CACSL2BoogieTranslator took 323.46 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. [2018-11-12 20:46:16,233 INFO L168 Benchmark]: Boogie Procedure Inliner took 22.09 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-12 20:46:16,233 INFO L168 Benchmark]: Boogie Preprocessor took 26.15 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-11-12 20:46:16,233 INFO L168 Benchmark]: RCFGBuilder took 490.98 ms. Allocated memory was 1.5 GB in the beginning and 2.2 GB in the end (delta: 728.8 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -771.3 MB). Peak memory consumption was 14.8 MB. Max. memory is 7.1 GB. [2018-11-12 20:46:16,233 INFO L168 Benchmark]: TraceAbstraction took 269223.71 ms. Allocated memory was 2.2 GB in the beginning and 2.4 GB in the end (delta: 151.0 MB). Free memory was 2.2 GB in the beginning and 1.7 GB in the end (delta: 517.5 MB). Peak memory consumption was 668.5 MB. Max. memory is 7.1 GB. [2018-11-12 20:46:16,235 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.24 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * CACSL2BoogieTranslator took 323.46 ms. Allocated memory is still 1.5 GB. Free memory was 1.4 GB in the beginning and 1.4 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. * Boogie Procedure Inliner took 22.09 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 26.15 ms. Allocated memory is still 1.5 GB. Free memory is still 1.4 GB. There was no memory consumed. Max. memory is 7.1 GB. * RCFGBuilder took 490.98 ms. Allocated memory was 1.5 GB in the beginning and 2.2 GB in the end (delta: 728.8 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -771.3 MB). Peak memory consumption was 14.8 MB. Max. memory is 7.1 GB. * TraceAbstraction took 269223.71 ms. Allocated memory was 2.2 GB in the beginning and 2.4 GB in the end (delta: 151.0 MB). Free memory was 2.2 GB in the beginning and 1.7 GB in the end (delta: 517.5 MB). Peak memory consumption was 668.5 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 6]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 6). Cancelled while BasicCegarLoop was analyzing trace of length 152 with TraceHistMax 13,while TraceCheckSpWp was constructing forward predicates,while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 35 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 27 locations, 1 error locations. TIMEOUT Result, 269.1s OverallTime, 22 OverallIterations, 13 TraceHistogramMax, 83.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 769 SDtfs, 1290 SDslu, 12105 SDs, 0 SdLazy, 15531 SolverSat, 985 SolverUnsat, 25 SolverUnknown, 0 SolverNotchecked, 63.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 3776 GetRequests, 2481 SyntacticMatches, 348 SemanticMatches, 947 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19228 ImplicationChecksByTransitivity, 158.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=154occurred in iteration=21, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.8s AbstIntTime, 2 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 21 MinimizatonAttempts, 41 StatesRemovedByMinimization, 20 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.4s SatisfiabilityAnalysisTime, 145.4s InterpolantComputationTime, 3093 NumberOfCodeBlocks, 3093 NumberOfCodeBlocksAsserted, 83 NumberOfCheckSat, 4565 ConstructedInterpolants, 632 QuantifiedInterpolants, 3518416 SizeOfPredicates, 156 NumberOfNonLiveVariables, 3341 ConjunctsInSsa, 478 ConjunctsInUnsatCore, 59 InterpolantComputations, 2 PerfectInterpolantSequences, 6589/13929 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown