java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf -i ../../../trunk/examples/svcomp/loops/linear_search_false-unreach-call.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8c3fbe1 [2018-10-22 15:55:29,404 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-22 15:55:29,407 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-22 15:55:29,425 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-22 15:55:29,425 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-22 15:55:29,427 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-22 15:55:29,429 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-22 15:55:29,432 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-22 15:55:29,434 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-22 15:55:29,434 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-22 15:55:29,436 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-22 15:55:29,437 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-22 15:55:29,439 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-22 15:55:29,440 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-22 15:55:29,443 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-22 15:55:29,445 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-22 15:55:29,452 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-22 15:55:29,456 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-22 15:55:29,461 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-22 15:55:29,462 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-22 15:55:29,463 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-22 15:55:29,467 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-22 15:55:29,470 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-22 15:55:29,470 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-22 15:55:29,470 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-22 15:55:29,473 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-22 15:55:29,475 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-22 15:55:29,476 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-22 15:55:29,478 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-22 15:55:29,480 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-22 15:55:29,481 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-22 15:55:29,481 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-22 15:55:29,482 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-22 15:55:29,483 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-22 15:55:29,484 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-22 15:55:29,485 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-22 15:55:29,486 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-64bit-Taipan_Default.epf [2018-10-22 15:55:29,512 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-22 15:55:29,513 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-22 15:55:29,514 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-10-22 15:55:29,517 INFO L133 SettingsManager]: * User list type=DISABLED [2018-10-22 15:55:29,517 INFO L133 SettingsManager]: * calls to implemented procedures=false [2018-10-22 15:55:29,517 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-22 15:55:29,518 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2018-10-22 15:55:29,518 INFO L133 SettingsManager]: * Abstract domain=CompoundDomain [2018-10-22 15:55:29,518 INFO L133 SettingsManager]: * Log string format=TERM [2018-10-22 15:55:29,519 INFO L133 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2018-10-22 15:55:29,519 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-22 15:55:29,519 INFO L133 SettingsManager]: * Interval Domain=false [2018-10-22 15:55:29,522 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-10-22 15:55:29,522 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-10-22 15:55:29,523 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-10-22 15:55:29,523 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-10-22 15:55:29,523 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-10-22 15:55:29,523 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-10-22 15:55:29,523 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-10-22 15:55:29,524 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-10-22 15:55:29,524 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-22 15:55:29,524 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-10-22 15:55:29,524 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-10-22 15:55:29,524 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-10-22 15:55:29,524 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-10-22 15:55:29,526 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-22 15:55:29,527 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-10-22 15:55:29,527 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-10-22 15:55:29,527 INFO L133 SettingsManager]: * Trace refinement strategy=TAIPAN [2018-10-22 15:55:29,527 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-10-22 15:55:29,527 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-22 15:55:29,530 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-10-22 15:55:29,531 INFO L133 SettingsManager]: * To the following directory=dump/ [2018-10-22 15:55:29,531 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-22 15:55:29,608 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-22 15:55:29,632 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-22 15:55:29,636 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-22 15:55:29,645 INFO L271 PluginConnector]: Initializing CDTParser... [2018-10-22 15:55:29,646 INFO L276 PluginConnector]: CDTParser initialized [2018-10-22 15:55:29,646 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/../../../trunk/examples/svcomp/loops/linear_search_false-unreach-call.i [2018-10-22 15:55:29,708 INFO L218 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/d86515834/2ecaad6523774a3da520dbaed379361a/FLAG4129c0c68 [2018-10-22 15:55:30,167 INFO L298 CDTParser]: Found 1 translation units. [2018-10-22 15:55:30,168 INFO L158 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/loops/linear_search_false-unreach-call.i [2018-10-22 15:55:30,175 INFO L346 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/d86515834/2ecaad6523774a3da520dbaed379361a/FLAG4129c0c68 [2018-10-22 15:55:30,188 INFO L354 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/data/d86515834/2ecaad6523774a3da520dbaed379361a [2018-10-22 15:55:30,201 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-22 15:55:30,202 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2018-10-22 15:55:30,203 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-10-22 15:55:30,203 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-10-22 15:55:30,206 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-10-22 15:55:30,207 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,210 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@63112924 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30, skipping insertion in model container [2018-10-22 15:55:30,211 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,220 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2018-10-22 15:55:30,243 INFO L174 MainTranslator]: Built tables and reachable declarations [2018-10-22 15:55:30,438 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-22 15:55:30,448 INFO L189 MainTranslator]: Completed pre-run [2018-10-22 15:55:30,471 INFO L202 PostProcessor]: Analyzing one entry point: main [2018-10-22 15:55:30,490 INFO L193 MainTranslator]: Completed translation [2018-10-22 15:55:30,491 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30 WrapperNode [2018-10-22 15:55:30,491 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-10-22 15:55:30,492 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-10-22 15:55:30,492 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-10-22 15:55:30,492 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-10-22 15:55:30,503 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,513 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,538 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-10-22 15:55:30,539 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-22 15:55:30,539 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-22 15:55:30,539 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-22 15:55:30,550 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,551 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,553 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,553 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,561 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,571 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,573 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... [2018-10-22 15:55:30,575 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-22 15:55:30,576 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-22 15:55:30,576 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-22 15:55:30,576 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-22 15:55:30,577 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:55:30,724 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-10-22 15:55:30,725 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-10-22 15:55:30,725 INFO L130 BoogieDeclarations]: Found specification of procedure linear_search [2018-10-22 15:55:30,725 INFO L138 BoogieDeclarations]: Found implementation of procedure linear_search [2018-10-22 15:55:30,725 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-22 15:55:30,725 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-22 15:55:30,726 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-10-22 15:55:30,726 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-10-22 15:55:30,726 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2018-10-22 15:55:30,726 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2018-10-22 15:55:31,215 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-22 15:55:31,215 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.10 03:55:31 BoogieIcfgContainer [2018-10-22 15:55:31,216 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-22 15:55:31,216 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-22 15:55:31,217 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-22 15:55:31,220 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-22 15:55:31,220 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 22.10 03:55:30" (1/3) ... [2018-10-22 15:55:31,221 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@197f3976 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.10 03:55:31, skipping insertion in model container [2018-10-22 15:55:31,221 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 22.10 03:55:30" (2/3) ... [2018-10-22 15:55:31,222 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@197f3976 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.10 03:55:31, skipping insertion in model container [2018-10-22 15:55:31,222 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.10 03:55:31" (3/3) ... [2018-10-22 15:55:31,224 INFO L112 eAbstractionObserver]: Analyzing ICFG linear_search_false-unreach-call.i [2018-10-22 15:55:31,234 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-10-22 15:55:31,243 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-22 15:55:31,260 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-22 15:55:31,295 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-22 15:55:31,295 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-22 15:55:31,296 INFO L383 AbstractCegarLoop]: Hoare is true [2018-10-22 15:55:31,296 INFO L384 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-10-22 15:55:31,296 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-22 15:55:31,296 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-22 15:55:31,296 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-22 15:55:31,296 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-22 15:55:31,297 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-22 15:55:31,316 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states. [2018-10-22 15:55:31,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-10-22 15:55:31,323 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:55:31,324 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:55:31,326 INFO L424 AbstractCegarLoop]: === Iteration 1 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:55:31,332 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:31,333 INFO L82 PathProgramCache]: Analyzing trace with hash 1855752643, now seen corresponding path program 1 times [2018-10-22 15:55:31,335 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:55:31,380 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:31,380 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:31,380 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:31,381 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:55:31,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:31,527 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:31,529 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-22 15:55:31,530 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-10-22 15:55:31,530 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:55:31,535 INFO L460 AbstractCegarLoop]: Interpolant automaton has 2 states [2018-10-22 15:55:31,550 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2018-10-22 15:55:31,551 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2018-10-22 15:55:31,554 INFO L87 Difference]: Start difference. First operand 29 states. Second operand 2 states. [2018-10-22 15:55:31,579 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:55:31,580 INFO L93 Difference]: Finished difference Result 45 states and 52 transitions. [2018-10-22 15:55:31,580 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2018-10-22 15:55:31,582 INFO L78 Accepts]: Start accepts. Automaton has 2 states. Word has length 17 [2018-10-22 15:55:31,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:55:31,592 INFO L225 Difference]: With dead ends: 45 [2018-10-22 15:55:31,593 INFO L226 Difference]: Without dead ends: 22 [2018-10-22 15:55:31,596 INFO L605 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-10-22 15:55:31,613 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-10-22 15:55:31,627 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-10-22 15:55:31,629 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2018-10-22 15:55:31,630 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 25 transitions. [2018-10-22 15:55:31,631 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 25 transitions. Word has length 17 [2018-10-22 15:55:31,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:55:31,632 INFO L481 AbstractCegarLoop]: Abstraction has 22 states and 25 transitions. [2018-10-22 15:55:31,632 INFO L482 AbstractCegarLoop]: Interpolant automaton has 2 states. [2018-10-22 15:55:31,632 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 25 transitions. [2018-10-22 15:55:31,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-22 15:55:31,633 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:55:31,634 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:55:31,634 INFO L424 AbstractCegarLoop]: === Iteration 2 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:55:31,634 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:31,635 INFO L82 PathProgramCache]: Analyzing trace with hash -1049182020, now seen corresponding path program 1 times [2018-10-22 15:55:31,635 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:55:31,636 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:31,636 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:31,636 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:31,636 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:55:31,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:32,053 WARN L179 SmtUtils]: Spent 131.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 17 [2018-10-22 15:55:32,188 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:32,189 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-22 15:55:32,189 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-10-22 15:55:32,189 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:55:32,191 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-10-22 15:55:32,192 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-10-22 15:55:32,192 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-10-22 15:55:32,192 INFO L87 Difference]: Start difference. First operand 22 states and 25 transitions. Second operand 6 states. [2018-10-22 15:55:32,491 WARN L179 SmtUtils]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-10-22 15:55:32,709 WARN L179 SmtUtils]: Spent 153.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-10-22 15:55:32,931 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:55:32,931 INFO L93 Difference]: Finished difference Result 41 states and 48 transitions. [2018-10-22 15:55:32,931 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-22 15:55:32,932 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 20 [2018-10-22 15:55:32,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:55:32,935 INFO L225 Difference]: With dead ends: 41 [2018-10-22 15:55:32,936 INFO L226 Difference]: Without dead ends: 33 [2018-10-22 15:55:32,937 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=28, Invalid=44, Unknown=0, NotChecked=0, Total=72 [2018-10-22 15:55:32,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2018-10-22 15:55:32,943 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 27. [2018-10-22 15:55:32,943 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2018-10-22 15:55:32,945 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 32 transitions. [2018-10-22 15:55:32,945 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 32 transitions. Word has length 20 [2018-10-22 15:55:32,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:55:32,946 INFO L481 AbstractCegarLoop]: Abstraction has 27 states and 32 transitions. [2018-10-22 15:55:32,946 INFO L482 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-10-22 15:55:32,946 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 32 transitions. [2018-10-22 15:55:32,947 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-22 15:55:32,947 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:55:32,947 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:55:32,947 INFO L424 AbstractCegarLoop]: === Iteration 3 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:55:32,948 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:32,948 INFO L82 PathProgramCache]: Analyzing trace with hash 1502974941, now seen corresponding path program 1 times [2018-10-22 15:55:32,948 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:55:32,949 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:32,949 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:32,950 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:32,950 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:55:32,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:33,180 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:33,180 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-22 15:55:33,181 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-10-22 15:55:33,181 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:55:33,181 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-10-22 15:55:33,182 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-10-22 15:55:33,182 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-10-22 15:55:33,182 INFO L87 Difference]: Start difference. First operand 27 states and 32 transitions. Second operand 6 states. [2018-10-22 15:55:33,231 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:55:33,231 INFO L93 Difference]: Finished difference Result 35 states and 39 transitions. [2018-10-22 15:55:33,233 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-22 15:55:33,233 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 20 [2018-10-22 15:55:33,234 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:55:33,235 INFO L225 Difference]: With dead ends: 35 [2018-10-22 15:55:33,235 INFO L226 Difference]: Without dead ends: 26 [2018-10-22 15:55:33,235 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2018-10-22 15:55:33,236 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2018-10-22 15:55:33,239 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2018-10-22 15:55:33,240 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-10-22 15:55:33,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2018-10-22 15:55:33,241 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 20 [2018-10-22 15:55:33,241 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:55:33,241 INFO L481 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2018-10-22 15:55:33,242 INFO L482 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-10-22 15:55:33,242 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2018-10-22 15:55:33,242 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-22 15:55:33,243 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:55:33,243 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:55:33,243 INFO L424 AbstractCegarLoop]: === Iteration 4 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:55:33,243 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:33,244 INFO L82 PathProgramCache]: Analyzing trace with hash -1442209030, now seen corresponding path program 1 times [2018-10-22 15:55:33,244 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:55:33,245 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:33,245 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:33,245 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:33,245 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:55:33,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:33,577 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:33,577 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-22 15:55:33,577 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-10-22 15:55:33,578 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:55:33,578 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-22 15:55:33,578 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-22 15:55:33,579 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-10-22 15:55:33,579 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand 5 states. [2018-10-22 15:55:33,706 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:55:33,706 INFO L93 Difference]: Finished difference Result 36 states and 39 transitions. [2018-10-22 15:55:33,706 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-22 15:55:33,706 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 20 [2018-10-22 15:55:33,707 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:55:33,707 INFO L225 Difference]: With dead ends: 36 [2018-10-22 15:55:33,708 INFO L226 Difference]: Without dead ends: 27 [2018-10-22 15:55:33,708 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-10-22 15:55:33,709 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-10-22 15:55:33,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2018-10-22 15:55:33,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-10-22 15:55:33,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 29 transitions. [2018-10-22 15:55:33,714 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 29 transitions. Word has length 20 [2018-10-22 15:55:33,715 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:55:33,715 INFO L481 AbstractCegarLoop]: Abstraction has 26 states and 29 transitions. [2018-10-22 15:55:33,715 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-22 15:55:33,715 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 29 transitions. [2018-10-22 15:55:33,716 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-22 15:55:33,716 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:55:33,716 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:55:33,717 INFO L424 AbstractCegarLoop]: === Iteration 5 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:55:33,717 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:33,717 INFO L82 PathProgramCache]: Analyzing trace with hash -469535236, now seen corresponding path program 1 times [2018-10-22 15:55:33,717 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:55:33,718 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:33,719 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:33,719 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:33,719 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:55:33,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:33,851 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:33,852 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-22 15:55:33,852 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-22 15:55:33,852 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:55:33,853 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-22 15:55:33,853 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-22 15:55:33,853 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-10-22 15:55:33,854 INFO L87 Difference]: Start difference. First operand 26 states and 29 transitions. Second operand 4 states. [2018-10-22 15:55:33,923 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:55:33,923 INFO L93 Difference]: Finished difference Result 49 states and 57 transitions. [2018-10-22 15:55:33,924 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-22 15:55:33,924 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 25 [2018-10-22 15:55:33,925 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:55:33,925 INFO L225 Difference]: With dead ends: 49 [2018-10-22 15:55:33,926 INFO L226 Difference]: Without dead ends: 34 [2018-10-22 15:55:33,926 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 2 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-10-22 15:55:33,927 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-10-22 15:55:33,932 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 30. [2018-10-22 15:55:33,932 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 30 states. [2018-10-22 15:55:33,933 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 32 transitions. [2018-10-22 15:55:33,933 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 32 transitions. Word has length 25 [2018-10-22 15:55:33,934 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:55:33,934 INFO L481 AbstractCegarLoop]: Abstraction has 30 states and 32 transitions. [2018-10-22 15:55:33,934 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-22 15:55:33,934 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 32 transitions. [2018-10-22 15:55:33,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-22 15:55:33,935 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:55:33,935 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:55:33,936 INFO L424 AbstractCegarLoop]: === Iteration 6 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:55:33,936 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:33,936 INFO L82 PathProgramCache]: Analyzing trace with hash -862562246, now seen corresponding path program 1 times [2018-10-22 15:55:33,936 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:55:33,937 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:33,937 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:33,937 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:33,937 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:55:33,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:34,045 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:34,046 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-22 15:55:34,046 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-22 15:55:34,046 INFO L265 anRefinementStrategy]: Using the first perfect interpolant sequence [2018-10-22 15:55:34,046 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-22 15:55:34,047 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-22 15:55:34,047 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-10-22 15:55:34,047 INFO L87 Difference]: Start difference. First operand 30 states and 32 transitions. Second operand 4 states. [2018-10-22 15:55:34,157 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:55:34,158 INFO L93 Difference]: Finished difference Result 52 states and 56 transitions. [2018-10-22 15:55:34,159 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-22 15:55:34,160 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 25 [2018-10-22 15:55:34,160 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:55:34,160 INFO L225 Difference]: With dead ends: 52 [2018-10-22 15:55:34,161 INFO L226 Difference]: Without dead ends: 39 [2018-10-22 15:55:34,161 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-10-22 15:55:34,162 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-10-22 15:55:34,169 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 31. [2018-10-22 15:55:34,169 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-10-22 15:55:34,170 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 33 transitions. [2018-10-22 15:55:34,170 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 33 transitions. Word has length 25 [2018-10-22 15:55:34,171 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:55:34,171 INFO L481 AbstractCegarLoop]: Abstraction has 31 states and 33 transitions. [2018-10-22 15:55:34,171 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-22 15:55:34,171 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 33 transitions. [2018-10-22 15:55:34,172 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-22 15:55:34,172 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:55:34,172 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:55:34,173 INFO L424 AbstractCegarLoop]: === Iteration 7 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:55:34,173 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:34,173 INFO L82 PathProgramCache]: Analyzing trace with hash -1056341250, now seen corresponding path program 1 times [2018-10-22 15:55:34,173 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:55:34,174 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:34,174 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:34,175 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:34,175 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:55:34,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:34,750 WARN L179 SmtUtils]: Spent 219.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 16 [2018-10-22 15:55:35,030 WARN L179 SmtUtils]: Spent 202.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2018-10-22 15:55:35,413 WARN L179 SmtUtils]: Spent 188.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 12 [2018-10-22 15:55:35,417 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:35,418 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:55:35,418 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:55:35,419 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 26 with the following transitions: [2018-10-22 15:55:35,421 INFO L202 CegarAbsIntRunner]: [0], [1], [2], [6], [8], [11], [17], [19], [24], [32], [33], [37], [39], [43], [46], [48], [54], [55], [56], [58], [59], [60] [2018-10-22 15:55:35,506 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-22 15:55:35,507 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-22 15:55:35,706 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-22 15:55:40,968 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-22 15:55:40,969 INFO L272 AbstractInterpreter]: Visited 22 different actions 337 times. Merged at 8 different actions 280 times. Widened at 1 different actions 31 times. Found 36 fixpoints after 2 different actions. Largest state had 29 variables. [2018-10-22 15:55:40,982 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:40,984 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-22 15:55:40,984 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:55:40,984 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:55:40,994 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:40,994 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-22 15:55:41,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:41,045 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:55:41,288 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-22 15:55:41,288 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:55:41,402 WARN L179 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 14 [2018-10-22 15:55:41,905 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-22 15:55:41,935 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:55:41,935 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 3 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:55:41,955 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:41,955 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-22 15:55:42,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:42,065 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:55:42,075 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-22 15:55:42,076 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:55:42,344 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-22 15:55:42,346 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:55:42,346 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6, 6, 6, 6] total 16 [2018-10-22 15:55:42,346 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:55:42,347 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-22 15:55:42,347 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-22 15:55:42,347 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=192, Unknown=0, NotChecked=0, Total=240 [2018-10-22 15:55:42,349 INFO L87 Difference]: Start difference. First operand 31 states and 33 transitions. Second operand 12 states. [2018-10-22 15:55:42,702 WARN L179 SmtUtils]: Spent 133.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 11 [2018-10-22 15:55:43,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:55:43,168 INFO L93 Difference]: Finished difference Result 51 states and 54 transitions. [2018-10-22 15:55:43,168 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-22 15:55:43,168 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 25 [2018-10-22 15:55:43,169 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:55:43,170 INFO L225 Difference]: With dead ends: 51 [2018-10-22 15:55:43,170 INFO L226 Difference]: Without dead ends: 39 [2018-10-22 15:55:43,171 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 88 SyntacticMatches, 6 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=142, Invalid=458, Unknown=0, NotChecked=0, Total=600 [2018-10-22 15:55:43,172 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-10-22 15:55:43,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 31. [2018-10-22 15:55:43,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-10-22 15:55:43,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-10-22 15:55:43,177 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 25 [2018-10-22 15:55:43,177 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:55:43,177 INFO L481 AbstractCegarLoop]: Abstraction has 31 states and 32 transitions. [2018-10-22 15:55:43,177 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-22 15:55:43,177 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 32 transitions. [2018-10-22 15:55:43,178 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-22 15:55:43,178 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:55:43,178 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:55:43,179 INFO L424 AbstractCegarLoop]: === Iteration 8 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:55:43,179 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:43,179 INFO L82 PathProgramCache]: Analyzing trace with hash -1449368260, now seen corresponding path program 1 times [2018-10-22 15:55:43,179 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:55:43,180 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:43,180 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:43,181 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:55:43,181 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:55:43,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:43,899 WARN L179 SmtUtils]: Spent 570.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 27 [2018-10-22 15:55:44,209 WARN L179 SmtUtils]: Spent 143.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-10-22 15:55:44,410 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:44,410 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:55:44,410 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:55:44,411 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 26 with the following transitions: [2018-10-22 15:55:44,411 INFO L202 CegarAbsIntRunner]: [0], [1], [2], [6], [8], [11], [13], [17], [19], [24], [32], [33], [37], [39], [43], [46], [48], [54], [55], [56], [58], [59], [60] [2018-10-22 15:55:44,413 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-22 15:55:44,414 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-22 15:55:44,421 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-22 15:55:48,756 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-22 15:55:48,757 INFO L272 AbstractInterpreter]: Visited 23 different actions 404 times. Merged at 9 different actions 305 times. Widened at 1 different actions 32 times. Found 78 fixpoints after 5 different actions. Largest state had 29 variables. [2018-10-22 15:55:48,788 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:55:48,789 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-22 15:55:48,789 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:55:48,789 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:55:48,800 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:48,800 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-22 15:55:48,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:48,845 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:55:48,875 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:55:48,876 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-22 15:55:57,020 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 21 treesize of output 18 [2018-10-22 15:55:57,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 18 treesize of output 17 [2018-10-22 15:55:57,028 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-22 15:55:57,030 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:55:57,035 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:55:57,036 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-22 15:55:57,541 WARN L179 SmtUtils]: Spent 184.00 ms on a formula simplification that was a NOOP. DAG size: 37 [2018-10-22 15:55:57,984 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:57,984 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:55:58,637 WARN L179 SmtUtils]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-10-22 15:55:59,326 WARN L179 SmtUtils]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2018-10-22 15:55:59,588 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:55:59,609 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:55:59,610 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 5 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:55:59,628 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:55:59,628 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-22 15:55:59,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:55:59,747 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:55:59,789 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:55:59,790 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-22 15:55:59,800 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:55:59,801 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-22 15:55:59,816 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 44 treesize of output 41 [2018-10-22 15:55:59,823 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 18 treesize of output 17 [2018-10-22 15:55:59,824 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-22 15:55:59,846 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:55:59,852 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 46 treesize of output 43 [2018-10-22 15:55:59,856 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 18 treesize of output 17 [2018-10-22 15:55:59,856 INFO L267 ElimStorePlain]: Start of recursive call 7: End of recursive call: and 1 xjuncts. [2018-10-22 15:55:59,881 INFO L267 ElimStorePlain]: Start of recursive call 6: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:55:59,887 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 45 treesize of output 42 [2018-10-22 15:55:59,896 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 18 treesize of output 17 [2018-10-22 15:55:59,897 INFO L267 ElimStorePlain]: Start of recursive call 9: End of recursive call: and 1 xjuncts. [2018-10-22 15:55:59,915 INFO L267 ElimStorePlain]: Start of recursive call 8: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:55:59,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 45 treesize of output 42 [2018-10-22 15:55:59,926 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 18 treesize of output 17 [2018-10-22 15:55:59,927 INFO L267 ElimStorePlain]: Start of recursive call 11: End of recursive call: and 1 xjuncts. [2018-10-22 15:55:59,946 INFO L267 ElimStorePlain]: Start of recursive call 10: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:56:02,087 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-10-22 15:56:02,087 INFO L202 ElimStorePlain]: Needed 11 recursive calls to eliminate 5 variables, input treesize:445, output treesize:66 [2018-10-22 15:56:02,771 WARN L179 SmtUtils]: Spent 185.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2018-10-22 15:56:03,503 WARN L179 SmtUtils]: Spent 636.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-10-22 15:56:05,831 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:05,832 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:56:05,937 WARN L179 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 49 [2018-10-22 15:56:06,176 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:06,182 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:56:06,182 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10, 10, 10, 10] total 32 [2018-10-22 15:56:06,182 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:56:06,183 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-10-22 15:56:06,183 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-10-22 15:56:06,183 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=175, Invalid=816, Unknown=1, NotChecked=0, Total=992 [2018-10-22 15:56:06,184 INFO L87 Difference]: Start difference. First operand 31 states and 32 transitions. Second operand 16 states. [2018-10-22 15:56:06,692 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:56:06,693 INFO L93 Difference]: Finished difference Result 45 states and 46 transitions. [2018-10-22 15:56:06,693 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-22 15:56:06,693 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 25 [2018-10-22 15:56:06,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:56:06,695 INFO L225 Difference]: With dead ends: 45 [2018-10-22 15:56:06,695 INFO L226 Difference]: Without dead ends: 35 [2018-10-22 15:56:06,696 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 73 SyntacticMatches, 4 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 376 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=202, Invalid=919, Unknown=1, NotChecked=0, Total=1122 [2018-10-22 15:56:06,697 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2018-10-22 15:56:06,701 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2018-10-22 15:56:06,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 34 states. [2018-10-22 15:56:06,702 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 35 transitions. [2018-10-22 15:56:06,702 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 35 transitions. Word has length 25 [2018-10-22 15:56:06,703 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:56:06,703 INFO L481 AbstractCegarLoop]: Abstraction has 34 states and 35 transitions. [2018-10-22 15:56:06,703 INFO L482 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-10-22 15:56:06,703 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 35 transitions. [2018-10-22 15:56:06,704 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-10-22 15:56:06,704 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:56:06,704 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:56:06,704 INFO L424 AbstractCegarLoop]: === Iteration 9 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:56:06,705 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:56:06,705 INFO L82 PathProgramCache]: Analyzing trace with hash 890023736, now seen corresponding path program 1 times [2018-10-22 15:56:06,705 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:56:06,706 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:56:06,706 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:56:06,706 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:56:06,706 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:56:06,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:56:06,939 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:06,939 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:06,939 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:56:06,939 INFO L200 CegarAbsIntRunner]: Running AI on error trace of length 31 with the following transitions: [2018-10-22 15:56:06,940 INFO L202 CegarAbsIntRunner]: [0], [1], [2], [6], [8], [11], [13], [17], [19], [22], [24], [32], [33], [37], [39], [43], [46], [48], [54], [55], [56], [58], [59], [60] [2018-10-22 15:56:06,942 INFO L148 AbstractInterpreter]: Using domain PoormanAbstractDomain with backing domain CompoundDomain [CongruenceDomain, OctagonDomain] [2018-10-22 15:56:06,942 INFO L101 FixpointEngine]: Starting fixpoint engine with domain PoormanAbstractDomain (maxUnwinding=3, maxParallelStates=2) [2018-10-22 15:56:06,953 WARN L79 EvaluatorLogger]: Possible loss of precision. Operator ARITHMOD has no precise implementation. [2018-10-22 15:56:11,474 INFO L263 AbstractInterpreter]: Some error location(s) were reachable [2018-10-22 15:56:11,475 INFO L272 AbstractInterpreter]: Visited 24 different actions 461 times. Merged at 10 different actions 318 times. Widened at 2 different actions 33 times. Found 106 fixpoints after 6 different actions. Largest state had 29 variables. [2018-10-22 15:56:11,512 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:56:11,512 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: Unknown [2018-10-22 15:56:11,512 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:11,512 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-10-22 15:56:11,523 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:56:11,523 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-22 15:56:11,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:56:11,561 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:56:11,800 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:11,801 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:56:12,419 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:12,449 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:12,449 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 7 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:56:12,476 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:56:12,476 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: FPandBP) [2018-10-22 15:56:12,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:56:12,538 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:56:12,547 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:12,547 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:56:12,712 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:12,714 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:56:12,715 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5, 5, 5, 5] total 10 [2018-10-22 15:56:12,715 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:56:12,715 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-22 15:56:12,716 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-22 15:56:12,716 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=56, Unknown=0, NotChecked=0, Total=90 [2018-10-22 15:56:12,716 INFO L87 Difference]: Start difference. First operand 34 states and 35 transitions. Second operand 7 states. [2018-10-22 15:56:13,490 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:56:13,491 INFO L93 Difference]: Finished difference Result 57 states and 59 transitions. [2018-10-22 15:56:13,491 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-10-22 15:56:13,491 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 30 [2018-10-22 15:56:13,492 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:56:13,492 INFO L225 Difference]: With dead ends: 57 [2018-10-22 15:56:13,493 INFO L226 Difference]: Without dead ends: 44 [2018-10-22 15:56:13,496 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 115 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=34, Invalid=56, Unknown=0, NotChecked=0, Total=90 [2018-10-22 15:56:13,496 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2018-10-22 15:56:13,505 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 36. [2018-10-22 15:56:13,505 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2018-10-22 15:56:13,506 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 37 transitions. [2018-10-22 15:56:13,506 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 37 transitions. Word has length 30 [2018-10-22 15:56:13,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:56:13,507 INFO L481 AbstractCegarLoop]: Abstraction has 36 states and 37 transitions. [2018-10-22 15:56:13,507 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-22 15:56:13,507 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 37 transitions. [2018-10-22 15:56:13,508 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-10-22 15:56:13,510 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:56:13,510 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:56:13,510 INFO L424 AbstractCegarLoop]: === Iteration 10 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:56:13,510 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:56:13,511 INFO L82 PathProgramCache]: Analyzing trace with hash 303217722, now seen corresponding path program 2 times [2018-10-22 15:56:13,511 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:56:13,511 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:56:13,512 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-10-22 15:56:13,512 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:56:13,512 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:56:13,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:56:17,953 WARN L179 SmtUtils]: Spent 4.26 s on a formula simplification. DAG size of input: 102 DAG size of output: 30 [2018-10-22 15:56:18,872 WARN L179 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 52 [2018-10-22 15:56:19,971 WARN L179 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 51 [2018-10-22 15:56:22,156 WARN L179 SmtUtils]: Spent 2.12 s on a formula simplification. DAG size of input: 102 DAG size of output: 46 [2018-10-22 15:56:22,164 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:22,164 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:22,164 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:56:22,165 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-22 15:56:22,165 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-22 15:56:22,165 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:22,165 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:56:22,178 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-22 15:56:22,178 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-22 15:56:22,228 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-22 15:56:22,228 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:56:22,233 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:56:22,254 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:56:22,254 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-22 15:56:22,365 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 21 treesize of output 18 [2018-10-22 15:56:22,370 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 18 treesize of output 17 [2018-10-22 15:56:22,370 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-22 15:56:22,372 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:56:22,377 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:56:22,378 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-22 15:56:22,954 WARN L179 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 49 [2018-10-22 15:56:26,226 WARN L179 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 48 [2018-10-22 15:56:28,418 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:28,418 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:56:28,618 WARN L179 SmtUtils]: Spent 198.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 71 [2018-10-22 15:56:28,788 WARN L179 SmtUtils]: Spent 125.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 60 [2018-10-22 15:56:29,461 WARN L179 SmtUtils]: Spent 181.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 44 [2018-10-22 15:56:30,231 WARN L179 SmtUtils]: Spent 280.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 58 [2018-10-22 15:56:30,662 WARN L179 SmtUtils]: Spent 284.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 57 [2018-10-22 15:56:30,914 WARN L179 SmtUtils]: Spent 149.00 ms on a formula simplification that was a NOOP. DAG size: 61 [2018-10-22 15:56:31,511 WARN L179 SmtUtils]: Spent 173.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2018-10-22 15:56:31,801 WARN L179 SmtUtils]: Spent 172.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2018-10-22 15:56:31,912 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:31,946 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:31,946 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 9 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:56:31,976 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-22 15:56:31,976 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-22 15:56:32,126 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-22 15:56:32,127 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:56:32,135 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:56:32,182 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 31 treesize of output 28 [2018-10-22 15:56:32,196 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 18 treesize of output 17 [2018-10-22 15:56:32,197 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-22 15:56:32,206 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:56:32,212 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 30 treesize of output 27 [2018-10-22 15:56:32,214 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 18 treesize of output 17 [2018-10-22 15:56:32,215 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-22 15:56:32,226 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:56:38,269 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:56:38,269 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-22 15:56:38,950 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:38,950 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:56:39,118 WARN L179 SmtUtils]: Spent 166.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 60 [2018-10-22 15:56:40,052 WARN L179 SmtUtils]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2018-10-22 15:56:40,158 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:40,161 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:56:40,161 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 14, 14, 10, 9] total 50 [2018-10-22 15:56:40,161 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:56:40,162 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-22 15:56:40,163 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-22 15:56:40,167 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=255, Invalid=2193, Unknown=2, NotChecked=0, Total=2450 [2018-10-22 15:56:40,167 INFO L87 Difference]: Start difference. First operand 36 states and 37 transitions. Second operand 25 states. [2018-10-22 15:56:40,971 WARN L179 SmtUtils]: Spent 153.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 55 [2018-10-22 15:56:41,467 WARN L179 SmtUtils]: Spent 130.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 52 [2018-10-22 15:56:42,848 WARN L179 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 46 [2018-10-22 15:56:51,031 WARN L179 SmtUtils]: Spent 8.12 s on a formula simplification. DAG size of input: 94 DAG size of output: 41 [2018-10-22 15:56:51,104 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:56:51,104 INFO L93 Difference]: Finished difference Result 50 states and 51 transitions. [2018-10-22 15:56:51,104 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-22 15:56:51,104 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 30 [2018-10-22 15:56:51,105 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:56:51,106 INFO L225 Difference]: With dead ends: 50 [2018-10-22 15:56:51,106 INFO L226 Difference]: Without dead ends: 40 [2018-10-22 15:56:51,109 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 79 SyntacticMatches, 6 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 898 ImplicationChecksByTransitivity, 27.8s TimeCoverageRelationStatistics Valid=369, Invalid=2599, Unknown=2, NotChecked=0, Total=2970 [2018-10-22 15:56:51,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2018-10-22 15:56:51,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 39. [2018-10-22 15:56:51,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 39 states. [2018-10-22 15:56:51,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 40 transitions. [2018-10-22 15:56:51,116 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 40 transitions. Word has length 30 [2018-10-22 15:56:51,116 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:56:51,116 INFO L481 AbstractCegarLoop]: Abstraction has 39 states and 40 transitions. [2018-10-22 15:56:51,116 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-22 15:56:51,116 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 40 transitions. [2018-10-22 15:56:51,117 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-10-22 15:56:51,117 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:56:51,117 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:56:51,118 INFO L424 AbstractCegarLoop]: === Iteration 11 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:56:51,118 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:56:51,118 INFO L82 PathProgramCache]: Analyzing trace with hash 411764474, now seen corresponding path program 2 times [2018-10-22 15:56:51,118 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:56:51,119 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:56:51,119 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-22 15:56:51,119 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:56:51,119 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:56:51,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:56:53,376 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:53,376 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:53,376 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:56:53,376 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-22 15:56:53,377 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-22 15:56:53,377 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:53,377 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:56:53,386 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-22 15:56:53,386 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-22 15:56:53,414 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-22 15:56:53,414 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:56:53,417 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:56:53,487 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:53,488 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:56:53,608 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:53,629 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:53,629 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 11 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:56:53,647 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-10-22 15:56:53,647 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-22 15:56:53,726 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-10-22 15:56:53,726 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:56:53,731 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:56:53,734 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:53,735 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:56:53,770 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:53,772 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:56:53,772 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6, 6, 6] total 13 [2018-10-22 15:56:53,772 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:56:53,773 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-22 15:56:53,773 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-22 15:56:53,773 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=101, Unknown=1, NotChecked=0, Total=156 [2018-10-22 15:56:53,773 INFO L87 Difference]: Start difference. First operand 39 states and 40 transitions. Second operand 9 states. [2018-10-22 15:56:53,848 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:56:53,849 INFO L93 Difference]: Finished difference Result 62 states and 64 transitions. [2018-10-22 15:56:53,850 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-22 15:56:53,850 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 35 [2018-10-22 15:56:53,850 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:56:53,851 INFO L225 Difference]: With dead ends: 62 [2018-10-22 15:56:53,851 INFO L226 Difference]: Without dead ends: 49 [2018-10-22 15:56:53,851 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 145 GetRequests, 133 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=54, Invalid=101, Unknown=1, NotChecked=0, Total=156 [2018-10-22 15:56:53,852 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-10-22 15:56:53,857 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 41. [2018-10-22 15:56:53,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-10-22 15:56:53,858 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 42 transitions. [2018-10-22 15:56:53,858 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 42 transitions. Word has length 35 [2018-10-22 15:56:53,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:56:53,858 INFO L481 AbstractCegarLoop]: Abstraction has 41 states and 42 transitions. [2018-10-22 15:56:53,858 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-22 15:56:53,858 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 42 transitions. [2018-10-22 15:56:53,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-10-22 15:56:53,859 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:56:53,859 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:56:53,860 INFO L424 AbstractCegarLoop]: === Iteration 12 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:56:53,860 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:56:53,860 INFO L82 PathProgramCache]: Analyzing trace with hash -175041540, now seen corresponding path program 3 times [2018-10-22 15:56:53,860 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:56:53,861 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:56:53,861 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-22 15:56:53,861 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:56:53,861 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:56:53,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:56:54,462 WARN L179 SmtUtils]: Spent 432.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 29 [2018-10-22 15:56:55,033 WARN L179 SmtUtils]: Spent 276.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 36 [2018-10-22 15:56:55,509 WARN L179 SmtUtils]: Spent 440.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 56 [2018-10-22 15:56:58,492 WARN L179 SmtUtils]: Spent 2.88 s on a formula simplification. DAG size of input: 101 DAG size of output: 53 [2018-10-22 15:56:58,684 WARN L179 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 58 [2018-10-22 15:56:58,881 WARN L179 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 51 [2018-10-22 15:56:59,072 WARN L179 SmtUtils]: Spent 156.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 45 [2018-10-22 15:56:59,387 WARN L179 SmtUtils]: Spent 145.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 41 [2018-10-22 15:56:59,581 WARN L179 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 45 [2018-10-22 15:56:59,730 WARN L179 SmtUtils]: Spent 102.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 36 [2018-10-22 15:56:59,956 WARN L179 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 31 [2018-10-22 15:56:59,966 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:56:59,966 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:59,967 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:56:59,967 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-22 15:56:59,967 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-22 15:56:59,967 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:56:59,967 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:56:59,975 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-22 15:56:59,975 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-22 15:57:00,767 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-10-22 15:57:00,767 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:57:00,771 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:57:00,778 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:57:00,778 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:00,783 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:57:00,783 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:00,788 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:57:00,788 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:04,871 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 34 treesize of output 31 [2018-10-22 15:57:04,875 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 18 treesize of output 17 [2018-10-22 15:57:04,876 INFO L267 ElimStorePlain]: Start of recursive call 6: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:04,891 INFO L267 ElimStorePlain]: Start of recursive call 5: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:57:04,896 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 39 treesize of output 36 [2018-10-22 15:57:04,899 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 18 treesize of output 17 [2018-10-22 15:57:04,900 INFO L267 ElimStorePlain]: Start of recursive call 8: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:04,915 INFO L267 ElimStorePlain]: Start of recursive call 7: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:57:04,947 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 2 dim-2 vars, End of recursive call: 2 dim-0 vars, and 2 xjuncts. [2018-10-22 15:57:04,948 INFO L202 ElimStorePlain]: Needed 8 recursive calls to eliminate 5 variables, input treesize:445, output treesize:66 [2018-10-22 15:57:05,647 WARN L179 SmtUtils]: Spent 472.00 ms on a formula simplification that was a NOOP. DAG size: 38 [2018-10-22 15:57:06,376 WARN L179 SmtUtils]: Spent 599.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2018-10-22 15:57:07,279 WARN L179 SmtUtils]: Spent 516.00 ms on a formula simplification that was a NOOP. DAG size: 48 [2018-10-22 15:57:08,433 WARN L179 SmtUtils]: Spent 710.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 55 [2018-10-22 15:57:09,228 WARN L179 SmtUtils]: Spent 691.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2018-10-22 15:57:09,825 WARN L179 SmtUtils]: Spent 526.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2018-10-22 15:57:11,452 WARN L179 SmtUtils]: Spent 1.40 s on a formula simplification. DAG size of input: 55 DAG size of output: 55 [2018-10-22 15:57:11,852 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:11,852 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:57:12,095 WARN L179 SmtUtils]: Spent 241.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 74 [2018-10-22 15:57:12,223 WARN L179 SmtUtils]: Spent 126.00 ms on a formula simplification that was a NOOP. DAG size: 52 [2018-10-22 15:57:12,331 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 61 [2018-10-22 15:57:13,148 WARN L179 SmtUtils]: Spent 182.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 45 [2018-10-22 15:57:13,989 WARN L179 SmtUtils]: Spent 252.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 60 [2018-10-22 15:57:14,331 WARN L179 SmtUtils]: Spent 127.00 ms on a formula simplification that was a NOOP. DAG size: 59 [2018-10-22 15:57:14,688 WARN L179 SmtUtils]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 63 [2018-10-22 15:57:15,081 WARN L179 SmtUtils]: Spent 182.00 ms on a formula simplification that was a NOOP. DAG size: 67 [2018-10-22 15:57:15,622 WARN L179 SmtUtils]: Spent 354.00 ms on a formula simplification. DAG size of input: 66 DAG size of output: 66 [2018-10-22 15:57:19,408 WARN L179 SmtUtils]: Spent 625.00 ms on a formula simplification that was a NOOP. DAG size: 67 [2018-10-22 15:57:19,437 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:19,458 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:57:19,458 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 13 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:57:19,474 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-22 15:57:19,474 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-22 15:57:19,722 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-10-22 15:57:19,722 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:57:19,728 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:57:19,736 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:57:19,736 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:19,758 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 21 treesize of output 18 [2018-10-22 15:57:19,761 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 18 treesize of output 17 [2018-10-22 15:57:19,761 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:19,771 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:57:19,778 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:57:19,778 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-22 15:57:20,856 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:20,856 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:57:20,989 WARN L179 SmtUtils]: Spent 131.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 63 [2018-10-22 15:57:22,405 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:22,407 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:57:22,407 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 15, 15, 11, 10] total 60 [2018-10-22 15:57:22,407 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:57:22,408 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-10-22 15:57:22,408 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-10-22 15:57:22,409 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=294, Invalid=3245, Unknown=1, NotChecked=0, Total=3540 [2018-10-22 15:57:22,409 INFO L87 Difference]: Start difference. First operand 41 states and 42 transitions. Second operand 30 states. [2018-10-22 15:57:22,823 WARN L179 SmtUtils]: Spent 262.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 48 [2018-10-22 15:57:25,695 WARN L179 SmtUtils]: Spent 2.25 s on a formula simplification. DAG size of input: 112 DAG size of output: 66 [2018-10-22 15:57:27,269 WARN L179 SmtUtils]: Spent 1.24 s on a formula simplification. DAG size of input: 60 DAG size of output: 59 [2018-10-22 15:57:28,603 WARN L179 SmtUtils]: Spent 1.20 s on a formula simplification. DAG size of input: 83 DAG size of output: 55 [2018-10-22 15:57:30,861 WARN L179 SmtUtils]: Spent 2.09 s on a formula simplification. DAG size of input: 54 DAG size of output: 53 [2018-10-22 15:57:31,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:57:31,297 INFO L93 Difference]: Finished difference Result 55 states and 56 transitions. [2018-10-22 15:57:31,297 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-22 15:57:31,298 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 35 [2018-10-22 15:57:31,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:57:31,299 INFO L225 Difference]: With dead ends: 55 [2018-10-22 15:57:31,299 INFO L226 Difference]: Without dead ends: 45 [2018-10-22 15:57:31,301 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 94 SyntacticMatches, 4 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1230 ImplicationChecksByTransitivity, 30.4s TimeCoverageRelationStatistics Valid=438, Invalid=4117, Unknown=1, NotChecked=0, Total=4556 [2018-10-22 15:57:31,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2018-10-22 15:57:31,308 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 44. [2018-10-22 15:57:31,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 44 states. [2018-10-22 15:57:31,309 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 45 transitions. [2018-10-22 15:57:31,309 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 45 transitions. Word has length 35 [2018-10-22 15:57:31,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:57:31,309 INFO L481 AbstractCegarLoop]: Abstraction has 44 states and 45 transitions. [2018-10-22 15:57:31,310 INFO L482 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-10-22 15:57:31,310 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 45 transitions. [2018-10-22 15:57:31,311 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-10-22 15:57:31,311 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:57:31,311 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:57:31,311 INFO L424 AbstractCegarLoop]: === Iteration 13 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:57:31,311 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:57:31,311 INFO L82 PathProgramCache]: Analyzing trace with hash 1953970296, now seen corresponding path program 3 times [2018-10-22 15:57:31,312 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:57:31,312 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:57:31,312 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-22 15:57:31,313 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:57:31,313 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:57:31,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:57:32,454 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 16 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:32,454 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:57:32,454 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:57:32,454 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-22 15:57:32,454 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-22 15:57:32,454 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:57:32,455 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:57:32,463 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-22 15:57:32,463 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-22 15:57:32,761 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-10-22 15:57:32,762 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:57:32,764 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:57:32,819 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 16 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:32,819 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:57:32,919 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 16 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:32,941 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:57:32,941 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 15 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:57:32,956 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-10-22 15:57:32,956 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder OUTSIDE_LOOP_FIRST2 (IT: FPandBP) [2018-10-22 15:57:33,247 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-10-22 15:57:33,248 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:57:33,252 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:57:33,255 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 16 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:33,255 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:57:33,319 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 16 proven. 30 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:33,323 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:57:33,323 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7, 7, 7] total 16 [2018-10-22 15:57:33,323 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:57:33,325 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-22 15:57:33,325 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-22 15:57:33,325 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-10-22 15:57:33,325 INFO L87 Difference]: Start difference. First operand 44 states and 45 transitions. Second operand 11 states. [2018-10-22 15:57:33,497 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:57:33,497 INFO L93 Difference]: Finished difference Result 67 states and 69 transitions. [2018-10-22 15:57:33,498 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-10-22 15:57:33,498 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 40 [2018-10-22 15:57:33,498 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:57:33,499 INFO L225 Difference]: With dead ends: 67 [2018-10-22 15:57:33,499 INFO L226 Difference]: Without dead ends: 54 [2018-10-22 15:57:33,500 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 151 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=78, Invalid=162, Unknown=0, NotChecked=0, Total=240 [2018-10-22 15:57:33,500 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-10-22 15:57:33,509 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 46. [2018-10-22 15:57:33,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-10-22 15:57:33,510 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 47 transitions. [2018-10-22 15:57:33,510 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 47 transitions. Word has length 40 [2018-10-22 15:57:33,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:57:33,510 INFO L481 AbstractCegarLoop]: Abstraction has 46 states and 47 transitions. [2018-10-22 15:57:33,510 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-22 15:57:33,510 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 47 transitions. [2018-10-22 15:57:33,511 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-10-22 15:57:33,512 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:57:33,514 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:57:33,514 INFO L424 AbstractCegarLoop]: === Iteration 14 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:57:33,514 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:57:33,514 INFO L82 PathProgramCache]: Analyzing trace with hash 1367164282, now seen corresponding path program 4 times [2018-10-22 15:57:33,514 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:57:33,515 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:57:33,515 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-22 15:57:33,515 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:57:33,515 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:57:33,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:57:35,933 WARN L179 SmtUtils]: Spent 2.18 s on a formula simplification. DAG size of input: 111 DAG size of output: 24 [2018-10-22 15:57:36,308 WARN L179 SmtUtils]: Spent 161.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 31 [2018-10-22 15:57:36,696 WARN L179 SmtUtils]: Spent 159.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 47 [2018-10-22 15:57:36,840 WARN L179 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 43 [2018-10-22 15:57:37,030 WARN L179 SmtUtils]: Spent 155.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 55 [2018-10-22 15:57:37,245 WARN L179 SmtUtils]: Spent 155.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 63 [2018-10-22 15:57:37,425 WARN L179 SmtUtils]: Spent 124.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 54 [2018-10-22 15:57:37,729 WARN L179 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 46 [2018-10-22 15:57:40,023 WARN L854 $PredicateComparison]: unable to prove that (or (let ((.cse13 (div c_~SIZE~0 4294967296))) (let ((.cse9 (* 4294967296 .cse13))) (and (let ((.cse11 (* 2 (div c_~SIZE~0 2)))) (let ((.cse4 (= .cse11 c_~SIZE~0)) (.cse6 (<= .cse9 c_~SIZE~0)) (.cse10 (div (+ c_~SIZE~0 (* (- 4294967296) .cse13)) 2))) (let ((.cse0 (div .cse10 4294967296)) (.cse1 (or .cse4 .cse6)) (.cse12 (not (= c_~SIZE~0 (+ |c_linear_search_#in~n| .cse9)))) (.cse5 (div (+ .cse10 1) 4294967296)) (.cse2 (not .cse4)) (.cse3 (< c_~SIZE~0 .cse9))) (or (and (<= (+ .cse0 1) 0) .cse1) (let ((.cse8 (* 8589934592 .cse13))) (and (or (and (or (and .cse2 .cse3) (< 0 .cse0)) (or .cse4 (< 0 .cse5) .cse6)) (and (let ((.cse7 (<= (+ c_~SIZE~0 1) .cse9))) (or .cse7 (and (or (not (= (select (select |c_#memory_int| |c_linear_search_#in~a.base|) (- (+ .cse8 (* (- 2) c_~SIZE~0)))) |c_linear_search_#in~q|)) (< (+ .cse9 (* 2 .cse10)) c_~SIZE~0)) (or (<= c_~SIZE~0 .cse11) (<= (+ .cse9 4294967300) c_~SIZE~0) (<= (+ .cse11 2) c_~SIZE~0) .cse7 .cse12)))) (not (= c_~SIZE~0 (+ |c_linear_search_#in~n| .cse9 4294967296))))) (or (<= (* 2 c_~SIZE~0) (+ .cse8 8)) (and (<= .cse0 0) .cse1) (and .cse2 (<= .cse5 0) .cse3)))) .cse12 (and (<= (+ .cse5 1) 0) .cse2 .cse3))))) (<= c_~SIZE~0 (+ .cse9 4))))) (not (= 0 |c_linear_search_#in~a.offset|))) is different from true [2018-10-22 15:57:40,038 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 46 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:40,038 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:57:40,038 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:57:40,038 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-22 15:57:40,038 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-22 15:57:40,038 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:57:40,038 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:57:40,047 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-22 15:57:40,047 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-22 15:57:40,171 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-22 15:57:40,171 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:57:40,174 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:57:40,177 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:57:40,178 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:40,206 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 21 treesize of output 18 [2018-10-22 15:57:40,210 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 18 treesize of output 17 [2018-10-22 15:57:40,210 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:40,212 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:57:40,220 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:57:40,220 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-22 15:57:41,249 WARN L179 SmtUtils]: Spent 563.00 ms on a formula simplification that was a NOOP. DAG size: 45 [2018-10-22 15:57:41,781 WARN L179 SmtUtils]: Spent 149.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2018-10-22 15:57:42,741 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 46 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:42,741 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:57:43,093 WARN L179 SmtUtils]: Spent 351.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 91 [2018-10-22 15:57:44,093 WARN L179 SmtUtils]: Spent 155.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 58 [2018-10-22 15:57:44,645 WARN L179 SmtUtils]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 64 [2018-10-22 15:57:44,909 WARN L179 SmtUtils]: Spent 119.00 ms on a formula simplification that was a NOOP. DAG size: 65 [2018-10-22 15:57:45,257 WARN L179 SmtUtils]: Spent 169.00 ms on a formula simplification that was a NOOP. DAG size: 69 [2018-10-22 15:57:45,682 WARN L179 SmtUtils]: Spent 173.00 ms on a formula simplification that was a NOOP. DAG size: 72 [2018-10-22 15:57:45,850 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 46 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:57:45,871 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:57:45,871 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 17 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:57:45,889 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-22 15:57:45,890 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-22 15:57:46,050 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-22 15:57:46,051 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:57:46,059 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:57:46,066 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 30 treesize of output 27 [2018-10-22 15:57:46,071 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 18 treesize of output 17 [2018-10-22 15:57:46,072 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:46,084 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:57:46,090 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 31 treesize of output 28 [2018-10-22 15:57:46,101 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 18 treesize of output 17 [2018-10-22 15:57:46,101 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-22 15:57:46,122 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:57:48,153 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:57:48,154 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-22 15:57:50,091 WARN L179 SmtUtils]: Spent 233.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 68 [2018-10-22 15:57:59,018 WARN L179 SmtUtils]: Spent 6.63 s on a formula simplification. DAG size of input: 77 DAG size of output: 71 [2018-10-22 15:58:00,928 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 46 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:00,928 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:58:01,426 WARN L179 SmtUtils]: Spent 497.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 107 [2018-10-22 15:58:03,710 WARN L179 SmtUtils]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 59 [2018-10-22 15:58:04,125 WARN L179 SmtUtils]: Spent 120.00 ms on a formula simplification that was a NOOP. DAG size: 63 [2018-10-22 15:58:04,897 WARN L179 SmtUtils]: Spent 247.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 85 [2018-10-22 15:58:05,546 WARN L179 SmtUtils]: Spent 158.00 ms on a formula simplification that was a NOOP. DAG size: 88 [2018-10-22 15:58:06,528 WARN L179 SmtUtils]: Spent 192.00 ms on a formula simplification that was a NOOP. DAG size: 91 [2018-10-22 15:58:07,934 WARN L179 SmtUtils]: Spent 296.00 ms on a formula simplification that was a NOOP. DAG size: 94 [2018-10-22 15:58:09,186 WARN L179 SmtUtils]: Spent 319.00 ms on a formula simplification that was a NOOP. DAG size: 97 [2018-10-22 15:58:09,232 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 0 proven. 46 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:09,234 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:58:09,234 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 14, 15, 17, 17] total 64 [2018-10-22 15:58:09,234 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:58:09,235 INFO L460 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-10-22 15:58:09,235 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-10-22 15:58:09,238 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=315, Invalid=3593, Unknown=2, NotChecked=122, Total=4032 [2018-10-22 15:58:09,238 INFO L87 Difference]: Start difference. First operand 46 states and 47 transitions. Second operand 28 states. [2018-10-22 15:58:09,770 WARN L179 SmtUtils]: Spent 121.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 52 [2018-10-22 15:58:10,547 WARN L179 SmtUtils]: Spent 161.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 61 [2018-10-22 15:58:11,088 WARN L179 SmtUtils]: Spent 194.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 69 [2018-10-22 15:58:14,381 WARN L179 SmtUtils]: Spent 121.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 72 [2018-10-22 15:58:16,937 WARN L179 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 69 [2018-10-22 15:58:17,409 WARN L179 SmtUtils]: Spent 121.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 71 [2018-10-22 15:58:17,834 WARN L179 SmtUtils]: Spent 235.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 78 [2018-10-22 15:58:18,117 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 104 DAG size of output: 70 [2018-10-22 15:58:26,490 WARN L179 SmtUtils]: Spent 8.19 s on a formula simplification. DAG size of input: 172 DAG size of output: 72 [2018-10-22 15:58:26,739 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:58:26,739 INFO L93 Difference]: Finished difference Result 60 states and 61 transitions. [2018-10-22 15:58:26,741 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-22 15:58:26,741 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 40 [2018-10-22 15:58:26,742 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:58:26,743 INFO L225 Difference]: With dead ends: 60 [2018-10-22 15:58:26,743 INFO L226 Difference]: Without dead ends: 50 [2018-10-22 15:58:26,745 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 190 GetRequests, 103 SyntacticMatches, 11 SemanticMatches, 76 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 1581 ImplicationChecksByTransitivity, 47.6s TimeCoverageRelationStatistics Valid=483, Invalid=5370, Unknown=3, NotChecked=150, Total=6006 [2018-10-22 15:58:26,746 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2018-10-22 15:58:26,762 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 49. [2018-10-22 15:58:26,762 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 49 states. [2018-10-22 15:58:26,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 50 transitions. [2018-10-22 15:58:26,763 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 50 transitions. Word has length 40 [2018-10-22 15:58:26,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:58:26,763 INFO L481 AbstractCegarLoop]: Abstraction has 49 states and 50 transitions. [2018-10-22 15:58:26,763 INFO L482 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-10-22 15:58:26,764 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 50 transitions. [2018-10-22 15:58:26,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2018-10-22 15:58:26,772 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:58:26,772 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:58:26,772 INFO L424 AbstractCegarLoop]: === Iteration 15 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:58:26,773 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:58:26,773 INFO L82 PathProgramCache]: Analyzing trace with hash 545539514, now seen corresponding path program 4 times [2018-10-22 15:58:26,773 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:58:26,774 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:58:26,774 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-22 15:58:26,774 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:58:26,774 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:58:26,795 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:58:28,872 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 20 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:28,872 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:58:28,872 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:58:28,873 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-22 15:58:28,873 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-22 15:58:28,873 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:58:28,873 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:58:28,881 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-22 15:58:28,881 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-22 15:58:28,936 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-22 15:58:28,936 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:58:28,938 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:58:29,000 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 20 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:29,000 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:58:29,126 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 20 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:29,147 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:58:29,147 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 19 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:58:29,164 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-10-22 15:58:29,164 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder TERMS_WITH_SMALL_CONSTANTS_FIRST (IT: FPandBP) [2018-10-22 15:58:29,241 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-10-22 15:58:29,242 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:58:29,247 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:58:29,251 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 20 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:29,251 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:58:29,277 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 20 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:29,278 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:58:29,279 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8, 8, 8] total 19 [2018-10-22 15:58:29,279 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:58:29,279 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-22 15:58:29,279 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-22 15:58:29,280 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=236, Unknown=0, NotChecked=0, Total=342 [2018-10-22 15:58:29,280 INFO L87 Difference]: Start difference. First operand 49 states and 50 transitions. Second operand 13 states. [2018-10-22 15:58:29,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:58:29,483 INFO L93 Difference]: Finished difference Result 72 states and 74 transitions. [2018-10-22 15:58:29,483 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-10-22 15:58:29,483 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 45 [2018-10-22 15:58:29,483 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:58:29,484 INFO L225 Difference]: With dead ends: 72 [2018-10-22 15:58:29,484 INFO L226 Difference]: Without dead ends: 59 [2018-10-22 15:58:29,484 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 169 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=106, Invalid=236, Unknown=0, NotChecked=0, Total=342 [2018-10-22 15:58:29,485 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2018-10-22 15:58:29,492 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 51. [2018-10-22 15:58:29,492 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-10-22 15:58:29,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 52 transitions. [2018-10-22 15:58:29,493 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 52 transitions. Word has length 45 [2018-10-22 15:58:29,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:58:29,493 INFO L481 AbstractCegarLoop]: Abstraction has 51 states and 52 transitions. [2018-10-22 15:58:29,494 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-22 15:58:29,494 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 52 transitions. [2018-10-22 15:58:29,495 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2018-10-22 15:58:29,495 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:58:29,495 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:58:29,495 INFO L424 AbstractCegarLoop]: === Iteration 16 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:58:29,495 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:58:29,495 INFO L82 PathProgramCache]: Analyzing trace with hash -41266500, now seen corresponding path program 5 times [2018-10-22 15:58:29,495 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:58:29,500 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:58:29,500 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-22 15:58:29,500 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:58:29,501 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:58:29,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:58:30,390 WARN L179 SmtUtils]: Spent 759.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 28 [2018-10-22 15:58:31,028 WARN L179 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 49 [2018-10-22 15:58:31,163 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 49 [2018-10-22 15:58:31,789 WARN L179 SmtUtils]: Spent 215.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 46 [2018-10-22 15:58:31,804 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:31,805 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:58:31,805 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:58:31,805 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-22 15:58:31,805 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-22 15:58:31,805 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:58:31,805 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-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-10-22 15:58:31,812 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-22 15:58:31,812 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder INSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-22 15:58:36,986 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-10-22 15:58:36,986 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:58:37,014 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:58:37,022 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 31 treesize of output 28 [2018-10-22 15:58:37,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 18 treesize of output 17 [2018-10-22 15:58:37,027 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-22 15:58:37,037 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:58:37,042 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 30 treesize of output 27 [2018-10-22 15:58:37,044 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 18 treesize of output 17 [2018-10-22 15:58:37,044 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-22 15:58:37,055 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:58:43,099 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:58:43,099 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-22 15:58:43,944 WARN L179 SmtUtils]: Spent 153.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 54 [2018-10-22 15:58:45,017 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:45,018 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:58:45,470 WARN L179 SmtUtils]: Spent 450.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 101 [2018-10-22 15:58:47,643 WARN L179 SmtUtils]: Spent 117.00 ms on a formula simplification that was a NOOP. DAG size: 57 [2018-10-22 15:58:47,982 WARN L179 SmtUtils]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 62 [2018-10-22 15:58:48,473 WARN L179 SmtUtils]: Spent 175.00 ms on a formula simplification that was a NOOP. DAG size: 66 [2018-10-22 15:58:49,118 WARN L179 SmtUtils]: Spent 347.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 81 [2018-10-22 15:58:49,153 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:49,174 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:58:49,174 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 21 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:58:49,189 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-22 15:58:49,190 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder INSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-22 15:58:49,472 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-10-22 15:58:49,472 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:58:49,478 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:58:49,486 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 31 treesize of output 28 [2018-10-22 15:58:49,488 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 18 treesize of output 17 [2018-10-22 15:58:49,488 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-10-22 15:58:49,504 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:58:49,509 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 30 treesize of output 27 [2018-10-22 15:58:49,511 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 18 treesize of output 17 [2018-10-22 15:58:49,512 INFO L267 ElimStorePlain]: Start of recursive call 5: End of recursive call: and 1 xjuncts. [2018-10-22 15:58:49,521 INFO L267 ElimStorePlain]: Start of recursive call 4: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:58:51,550 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:58:51,551 INFO L202 ElimStorePlain]: Needed 5 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-22 15:58:53,088 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:53,089 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:58:53,235 WARN L179 SmtUtils]: Spent 144.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 63 [2018-10-22 15:58:54,779 WARN L179 SmtUtils]: Spent 166.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 42 [2018-10-22 15:58:55,117 WARN L179 SmtUtils]: Spent 119.00 ms on a formula simplification that was a NOOP. DAG size: 46 [2018-10-22 15:58:55,465 WARN L179 SmtUtils]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 55 [2018-10-22 15:58:56,331 WARN L179 SmtUtils]: Spent 110.00 ms on a formula simplification that was a NOOP. DAG size: 57 [2018-10-22 15:58:57,214 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification that was a NOOP. DAG size: 56 [2018-10-22 15:58:57,269 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 0 proven. 70 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:58:57,271 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:58:57,271 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 18, 18, 15, 14] total 71 [2018-10-22 15:58:57,271 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:58:57,272 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-10-22 15:58:57,272 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-10-22 15:58:57,273 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=314, Invalid=4656, Unknown=0, NotChecked=0, Total=4970 [2018-10-22 15:58:57,273 INFO L87 Difference]: Start difference. First operand 51 states and 52 transitions. Second operand 32 states. [2018-10-22 15:58:57,932 WARN L179 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 45 [2018-10-22 15:58:58,650 WARN L179 SmtUtils]: Spent 158.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 54 [2018-10-22 15:58:59,674 WARN L179 SmtUtils]: Spent 164.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 57 [2018-10-22 15:59:00,240 WARN L179 SmtUtils]: Spent 159.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 61 [2018-10-22 15:59:00,859 WARN L179 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 53 [2018-10-22 15:59:02,368 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:59:02,369 INFO L93 Difference]: Finished difference Result 65 states and 66 transitions. [2018-10-22 15:59:02,378 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-22 15:59:02,378 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 45 [2018-10-22 15:59:02,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:59:02,379 INFO L225 Difference]: With dead ends: 65 [2018-10-22 15:59:02,379 INFO L226 Difference]: Without dead ends: 55 [2018-10-22 15:59:02,381 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 121 SyntacticMatches, 8 SemanticMatches, 82 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1749 ImplicationChecksByTransitivity, 16.7s TimeCoverageRelationStatistics Valid=500, Invalid=6472, Unknown=0, NotChecked=0, Total=6972 [2018-10-22 15:59:02,382 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2018-10-22 15:59:02,399 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2018-10-22 15:59:02,399 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 54 states. [2018-10-22 15:59:02,400 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 55 transitions. [2018-10-22 15:59:02,400 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 55 transitions. Word has length 45 [2018-10-22 15:59:02,400 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:59:02,400 INFO L481 AbstractCegarLoop]: Abstraction has 54 states and 55 transitions. [2018-10-22 15:59:02,400 INFO L482 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-10-22 15:59:02,401 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 55 transitions. [2018-10-22 15:59:02,401 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-10-22 15:59:02,402 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:59:02,402 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:59:02,402 INFO L424 AbstractCegarLoop]: === Iteration 17 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:59:02,402 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:59:02,402 INFO L82 PathProgramCache]: Analyzing trace with hash -1808322120, now seen corresponding path program 5 times [2018-10-22 15:59:02,402 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:59:02,406 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:59:02,406 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-22 15:59:02,406 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:59:02,406 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:59:02,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:59:04,632 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 24 proven. 75 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:59:04,632 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:59:04,633 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:59:04,633 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-22 15:59:04,633 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-22 15:59:04,633 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:59:04,633 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-22 15:59:04,641 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-22 15:59:04,642 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder INSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-22 15:59:05,069 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-10-22 15:59:05,070 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:59:05,072 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:59:05,151 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 24 proven. 75 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:59:05,152 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:59:05,447 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 24 proven. 75 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:59:05,468 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:59:05,469 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode CVC4_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/cvc4nyu Starting monitored process 23 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with cvc4nyu --tear-down-incremental --print-success --lang smt --rewrite-divk --tlimit-per=12000 [2018-10-22 15:59:05,484 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-10-22 15:59:05,484 INFO L295 anRefinementStrategy]: Using traceCheck mode CVC4_IG with AssertCodeBlockOrder INSIDE_LOOP_FIRST1 (IT: FPandBP) [2018-10-22 15:59:05,638 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-10-22 15:59:05,638 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:59:05,644 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:59:05,647 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 24 proven. 75 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:59:05,647 INFO L316 TraceCheckSpWp]: Computing backward predicates... [2018-10-22 15:59:05,673 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 24 proven. 75 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:59:05,674 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 5 imperfect interpolant sequences. [2018-10-22 15:59:05,675 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9, 9, 9, 9] total 22 [2018-10-22 15:59:05,675 INFO L258 anRefinementStrategy]: Using the first two imperfect interpolant sequences [2018-10-22 15:59:05,675 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-22 15:59:05,675 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-22 15:59:05,676 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=138, Invalid=324, Unknown=0, NotChecked=0, Total=462 [2018-10-22 15:59:05,676 INFO L87 Difference]: Start difference. First operand 54 states and 55 transitions. Second operand 15 states. [2018-10-22 15:59:05,980 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-22 15:59:05,980 INFO L93 Difference]: Finished difference Result 77 states and 79 transitions. [2018-10-22 15:59:05,980 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-22 15:59:05,980 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 50 [2018-10-22 15:59:05,981 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-22 15:59:05,981 INFO L225 Difference]: With dead ends: 77 [2018-10-22 15:59:05,981 INFO L226 Difference]: Without dead ends: 64 [2018-10-22 15:59:05,982 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 187 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 99 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=138, Invalid=324, Unknown=0, NotChecked=0, Total=462 [2018-10-22 15:59:05,982 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2018-10-22 15:59:05,990 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 56. [2018-10-22 15:59:05,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-10-22 15:59:05,990 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 57 transitions. [2018-10-22 15:59:05,991 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 57 transitions. Word has length 50 [2018-10-22 15:59:05,991 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-22 15:59:05,991 INFO L481 AbstractCegarLoop]: Abstraction has 56 states and 57 transitions. [2018-10-22 15:59:05,991 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-22 15:59:05,991 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 57 transitions. [2018-10-22 15:59:05,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-10-22 15:59:05,993 INFO L367 BasicCegarLoop]: Found error trace [2018-10-22 15:59:05,993 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-22 15:59:05,993 INFO L424 AbstractCegarLoop]: === Iteration 18 === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION]=== [2018-10-22 15:59:05,993 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-22 15:59:05,994 INFO L82 PathProgramCache]: Analyzing trace with hash 1899839162, now seen corresponding path program 6 times [2018-10-22 15:59:05,994 INFO L69 tionRefinementEngine]: Using refinement strategy TaipanRefinementStrategy [2018-10-22 15:59:05,994 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:59:05,995 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-10-22 15:59:05,995 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-10-22 15:59:05,995 INFO L295 anRefinementStrategy]: Using traceCheck mode SMTINTERPOL with AssertCodeBlockOrder NOT_INCREMENTALLY (IT: Craig_TreeInterpolation) [2018-10-22 15:59:06,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-22 15:59:08,366 WARN L179 SmtUtils]: Spent 2.19 s on a formula simplification. DAG size of input: 120 DAG size of output: 26 [2018-10-22 15:59:08,943 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 38 [2018-10-22 15:59:09,086 WARN L179 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 35 [2018-10-22 15:59:09,398 WARN L179 SmtUtils]: Spent 144.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 44 [2018-10-22 15:59:09,600 WARN L179 SmtUtils]: Spent 162.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 52 [2018-10-22 15:59:09,772 WARN L179 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 43 [2018-10-22 15:59:10,056 WARN L179 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 38 [2018-10-22 15:59:10,511 WARN L179 SmtUtils]: Spent 122.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 35 [2018-10-22 15:59:10,530 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 0 proven. 99 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:59:10,530 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:59:10,530 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode ABSTRACT_INTERPRETATION [2018-10-22 15:59:10,531 INFO L184 CegarAbsIntRunner]: Skipping current iteration for AI because we have already analyzed this path program [2018-10-22 15:59:10,531 INFO L422 seRefinementStrategy]: Interpolation failed due to KNOWN_IGNORE: AbsInt can only provide a hoare triple checker if it generated fixpoints [2018-10-22 15:59:10,531 INFO L300 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-10-22 15:59:10,531 INFO L197 anRefinementStrategy]: Switched to InterpolantGenerator mode Z3_IG No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UTaipan-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-22 15:59:10,538 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-10-22 15:59:10,539 INFO L295 anRefinementStrategy]: Using traceCheck mode Z3_IG with AssertCodeBlockOrder MIX_INSIDE_OUTSIDE (IT: FPandBP) [2018-10-22 15:59:29,580 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-10-22 15:59:29,580 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-10-22 15:59:29,599 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-10-22 15:59:29,616 WARN L307 Elim1Store]: Array PQE input equivalent to false [2018-10-22 15:59:29,616 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-10-22 15:59:29,652 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 21 treesize of output 18 [2018-10-22 15:59:29,654 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 18 treesize of output 17 [2018-10-22 15:59:29,654 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-10-22 15:59:29,656 INFO L267 ElimStorePlain]: Start of recursive call 3: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:59:29,662 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-10-22 15:59:29,662 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 2 variables, input treesize:100, output treesize:21 [2018-10-22 15:59:30,370 WARN L179 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 48 [2018-10-22 15:59:30,922 WARN L179 SmtUtils]: Spent 110.00 ms on a formula simplification that was a NOOP. DAG size: 59 [2018-10-22 15:59:31,436 WARN L179 SmtUtils]: Spent 194.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 64 [2018-10-22 15:59:31,862 WARN L179 SmtUtils]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 67 [2018-10-22 15:59:33,127 WARN L179 SmtUtils]: Spent 348.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 73 [2018-10-22 15:59:33,835 WARN L179 SmtUtils]: Spent 105.00 ms on a formula simplification that was a NOOP. DAG size: 83 [2018-10-22 15:59:35,777 WARN L179 SmtUtils]: Spent 388.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 73 [2018-10-22 15:59:36,173 INFO L134 CoverageAnalysis]: Checked inductivity of 99 backedges. 0 proven. 99 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-22 15:59:36,173 INFO L316 TraceCheckSpWp]: Computing backward predicates... Received shutdown request... [2018-10-22 15:59:42,660 WARN L187 SmtUtils]: Removed 49 from assertion stack [2018-10-22 15:59:42,661 INFO L177 TraceCheckSpWp]: Timeout while computing interpolants [2018-10-22 15:59:42,861 WARN L522 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 24 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-10-22 15:59:42,862 WARN L550 AbstractCegarLoop]: Verification canceled [2018-10-22 15:59:42,867 WARN L205 ceAbstractionStarter]: Timeout [2018-10-22 15:59:42,867 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.10 03:59:42 BoogieIcfgContainer [2018-10-22 15:59:42,867 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-10-22 15:59:42,868 INFO L168 Benchmark]: Toolchain (without parser) took 252666.73 ms. Allocated memory was 1.5 GB in the beginning and 4.1 GB in the end (delta: 2.6 GB). Free memory was 1.4 GB in the beginning and 2.3 GB in the end (delta: -898.4 MB). Peak memory consumption was 1.7 GB. Max. memory is 7.1 GB. [2018-10-22 15:59:42,869 INFO L168 Benchmark]: CDTParser took 0.15 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-10-22 15:59:42,869 INFO L168 Benchmark]: CACSL2BoogieTranslator took 288.10 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-10-22 15:59:42,869 INFO L168 Benchmark]: Boogie Procedure Inliner took 46.55 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-10-22 15:59:42,870 INFO L168 Benchmark]: Boogie Preprocessor took 36.77 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-10-22 15:59:42,870 INFO L168 Benchmark]: RCFGBuilder took 639.98 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 745.0 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -780.8 MB). Peak memory consumption was 15.3 MB. Max. memory is 7.1 GB. [2018-10-22 15:59:42,870 INFO L168 Benchmark]: TraceAbstraction took 251650.98 ms. Allocated memory was 2.3 GB in the beginning and 4.1 GB in the end (delta: 1.8 GB). Free memory was 2.2 GB in the beginning and 2.3 GB in the end (delta: -128.2 MB). Peak memory consumption was 1.7 GB. Max. memory is 7.1 GB. [2018-10-22 15:59:42,872 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.15 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * CACSL2BoogieTranslator took 288.10 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 46.55 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 36.77 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 639.98 ms. Allocated memory was 1.5 GB in the beginning and 2.3 GB in the end (delta: 745.0 MB). Free memory was 1.4 GB in the beginning and 2.2 GB in the end (delta: -780.8 MB). Peak memory consumption was 15.3 MB. Max. memory is 7.1 GB. * TraceAbstraction took 251650.98 ms. Allocated memory was 2.3 GB in the beginning and 4.1 GB in the end (delta: 1.8 GB). Free memory was 2.2 GB in the beginning and 2.3 GB in the end (delta: -128.2 MB). Peak memory consumption was 1.7 GB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 5]: Timeout (TraceAbstraction) Unable to prove that call of __VERIFIER_error() unreachable (line 5). Cancelled while BasicCegarLoop was analyzing trace of length 51 with TraceHistMax 7,while TraceCheckSpWp was constructing backward predicates,while PartialQuantifierElimination was doing sequential composition of 37 TransFormulas,while SimplifyDDAWithTimeout was simplifying term of DAG size 188. - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 29 locations, 1 error locations. TIMEOUT Result, 251.5s OverallTime, 18 OverallIterations, 7 TraceHistogramMax, 46.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 368 SDtfs, 420 SDslu, 2133 SDs, 0 SdLazy, 2859 SolverSat, 122 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 6.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1797 GetRequests, 1326 SyntacticMatches, 48 SemanticMatches, 423 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 6168 ImplicationChecksByTransitivity, 142.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=56occurred in iteration=17, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 14.5s AbstIntTime, 3 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 17 MinimizatonAttempts, 72 StatesRemovedByMinimization, 15 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 9.1s SatisfiabilityAnalysisTime, 143.2s InterpolantComputationTime, 1327 NumberOfCodeBlocks, 1327 NumberOfCodeBlocksAsserted, 83 NumberOfCheckSat, 2066 ConstructedInterpolants, 286 QuantifiedInterpolants, 2352133 SizeOfPredicates, 261 NumberOfNonLiveVariables, 3658 ConjunctsInSsa, 745 ConjunctsInUnsatCore, 61 InterpolantComputations, 6 PerfectInterpolantSequences, 416/2103 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown