java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data --generate-csv --csv-dir csv -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml -s ../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default.epf -i ../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/AnnoyingVillain.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-b2fde6a [2018-09-28 10:10:39,292 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-09-28 10:10:39,294 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-09-28 10:10:39,305 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-09-28 10:10:39,306 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-09-28 10:10:39,307 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-09-28 10:10:39,308 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-09-28 10:10:39,310 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-09-28 10:10:39,311 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-09-28 10:10:39,312 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-09-28 10:10:39,313 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-09-28 10:10:39,313 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-09-28 10:10:39,314 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-09-28 10:10:39,315 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-09-28 10:10:39,316 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-09-28 10:10:39,317 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-09-28 10:10:39,318 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-09-28 10:10:39,320 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-09-28 10:10:39,322 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-09-28 10:10:39,323 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-09-28 10:10:39,324 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-09-28 10:10:39,325 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-09-28 10:10:39,328 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-09-28 10:10:39,328 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-09-28 10:10:39,328 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-09-28 10:10:39,329 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-09-28 10:10:39,330 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-09-28 10:10:39,331 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-09-28 10:10:39,332 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-09-28 10:10:39,333 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-09-28 10:10:39,333 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-09-28 10:10:39,334 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-09-28 10:10:39,334 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-09-28 10:10:39,334 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-09-28 10:10:39,335 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-09-28 10:10:39,336 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-09-28 10:10:39,336 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/pu-bench/svcomp-Reach-32bit-Automizer_Default.epf [2018-09-28 10:10:39,351 INFO L110 SettingsManager]: Loading preferences was successful [2018-09-28 10:10:39,352 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-09-28 10:10:39,352 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-09-28 10:10:39,353 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-09-28 10:10:39,353 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-09-28 10:10:39,356 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-09-28 10:10:39,356 INFO L133 SettingsManager]: * Use SBE=true [2018-09-28 10:10:39,356 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-09-28 10:10:39,357 INFO L133 SettingsManager]: * sizeof long=4 [2018-09-28 10:10:39,357 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-09-28 10:10:39,357 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-09-28 10:10:39,357 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-09-28 10:10:39,357 INFO L133 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2018-09-28 10:10:39,358 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-09-28 10:10:39,358 INFO L133 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2018-09-28 10:10:39,358 INFO L133 SettingsManager]: * sizeof long double=12 [2018-09-28 10:10:39,358 INFO L133 SettingsManager]: * Check if freed pointer was valid=false [2018-09-28 10:10:39,358 INFO L133 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2018-09-28 10:10:39,359 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-09-28 10:10:39,359 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-09-28 10:10:39,359 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-09-28 10:10:39,359 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-09-28 10:10:39,359 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-09-28 10:10:39,359 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-09-28 10:10:39,360 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-09-28 10:10:39,360 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-09-28 10:10:39,360 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-09-28 10:10:39,360 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-09-28 10:10:39,361 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-09-28 10:10:39,361 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-09-28 10:10:39,412 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-09-28 10:10:39,428 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-09-28 10:10:39,435 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-09-28 10:10:39,436 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-09-28 10:10:39,437 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-09-28 10:10:39,438 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/AnnoyingVillain.bpl [2018-09-28 10:10:39,438 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/AnnoyingVillain.bpl' [2018-09-28 10:10:39,493 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-09-28 10:10:39,496 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-09-28 10:10:39,497 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-09-28 10:10:39,498 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-09-28 10:10:39,499 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-09-28 10:10:39,519 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... [2018-09-28 10:10:39,532 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... [2018-09-28 10:10:39,537 WARN L165 Inliner]: Program contained no entry procedure! [2018-09-28 10:10:39,537 WARN L168 Inliner]: Missing entry procedures: [ULTIMATE.start] [2018-09-28 10:10:39,537 WARN L175 Inliner]: Fallback enabled. All procedures will be processed. [2018-09-28 10:10:39,540 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-09-28 10:10:39,540 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-09-28 10:10:39,541 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-09-28 10:10:39,541 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-09-28 10:10:39,555 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... [2018-09-28 10:10:39,555 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... [2018-09-28 10:10:39,556 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... [2018-09-28 10:10:39,556 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... [2018-09-28 10:10:39,558 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... [2018-09-28 10:10:39,561 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... [2018-09-28 10:10:39,562 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... [2018-09-28 10:10:39,563 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-09-28 10:10:39,564 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-09-28 10:10:39,564 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-09-28 10:10:39,564 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-09-28 10:10:39,565 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-09-28 10:10:39,623 INFO L124 BoogieDeclarations]: Specification and implementation of procedure main given in one single declaration [2018-09-28 10:10:39,624 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-09-28 10:10:39,624 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-09-28 10:10:39,820 INFO L350 CfgBuilder]: Using library mode [2018-09-28 10:10:39,821 INFO L202 PluginConnector]: Adding new model AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.09 10:10:39 BoogieIcfgContainer [2018-09-28 10:10:39,821 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-09-28 10:10:39,822 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-09-28 10:10:39,822 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-09-28 10:10:39,827 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-09-28 10:10:39,827 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 28.09 10:10:39" (1/2) ... [2018-09-28 10:10:39,828 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@295cbd5e and model type AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 28.09 10:10:39, skipping insertion in model container [2018-09-28 10:10:39,828 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 28.09 10:10:39" (2/2) ... [2018-09-28 10:10:39,830 INFO L112 eAbstractionObserver]: Analyzing ICFG AnnoyingVillain.bpl [2018-09-28 10:10:39,840 INFO L137 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-09-28 10:10:39,854 INFO L149 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-09-28 10:10:39,911 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-09-28 10:10:39,912 INFO L381 AbstractCegarLoop]: Interprodecural is true [2018-09-28 10:10:39,912 INFO L382 AbstractCegarLoop]: Hoare is true [2018-09-28 10:10:39,912 INFO L383 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-09-28 10:10:39,912 INFO L384 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-09-28 10:10:39,912 INFO L385 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-09-28 10:10:39,913 INFO L386 AbstractCegarLoop]: Difference is false [2018-09-28 10:10:39,913 INFO L387 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-09-28 10:10:39,913 INFO L392 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-09-28 10:10:39,929 INFO L276 IsEmpty]: Start isEmpty. Operand 6 states. [2018-09-28 10:10:39,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-09-28 10:10:39,945 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:39,946 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-09-28 10:10:39,947 INFO L423 AbstractCegarLoop]: === Iteration 1 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:39,958 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:39,959 INFO L82 PathProgramCache]: Analyzing trace with hash 30048, now seen corresponding path program 1 times [2018-09-28 10:10:39,961 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:39,961 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:40,018 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:40,019 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:10:40,019 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:40,063 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:40,168 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:40,171 INFO L313 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-09-28 10:10:40,171 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [1] imperfect sequences [] total 1 [2018-09-28 10:10:40,176 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-09-28 10:10:40,191 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-09-28 10:10:40,192 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-09-28 10:10:40,194 INFO L87 Difference]: Start difference. First operand 6 states. Second operand 3 states. [2018-09-28 10:10:40,289 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:40,289 INFO L93 Difference]: Finished difference Result 11 states and 13 transitions. [2018-09-28 10:10:40,290 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-09-28 10:10:40,291 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2018-09-28 10:10:40,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:40,302 INFO L225 Difference]: With dead ends: 11 [2018-09-28 10:10:40,303 INFO L226 Difference]: Without dead ends: 5 [2018-09-28 10:10:40,307 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 1 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-09-28 10:10:40,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5 states. [2018-09-28 10:10:40,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5 to 5. [2018-09-28 10:10:40,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2018-09-28 10:10:40,342 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 5 transitions. [2018-09-28 10:10:40,344 INFO L78 Accepts]: Start accepts. Automaton has 5 states and 5 transitions. Word has length 3 [2018-09-28 10:10:40,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:40,344 INFO L480 AbstractCegarLoop]: Abstraction has 5 states and 5 transitions. [2018-09-28 10:10:40,344 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-09-28 10:10:40,345 INFO L276 IsEmpty]: Start isEmpty. Operand 5 states and 5 transitions. [2018-09-28 10:10:40,345 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2018-09-28 10:10:40,345 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:40,345 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2018-09-28 10:10:40,346 INFO L423 AbstractCegarLoop]: === Iteration 2 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:40,346 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:40,346 INFO L82 PathProgramCache]: Analyzing trace with hash 927622, now seen corresponding path program 1 times [2018-09-28 10:10:40,346 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:40,346 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:40,347 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:40,348 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:10:40,348 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:40,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:40,580 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:40,580 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:40,580 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:40,596 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:10:40,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:40,621 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:40,664 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:40,685 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:40,685 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [3, 3] total 3 [2018-09-28 10:10:40,686 INFO L459 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-09-28 10:10:40,686 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-09-28 10:10:40,686 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-09-28 10:10:40,687 INFO L87 Difference]: Start difference. First operand 5 states and 5 transitions. Second operand 4 states. [2018-09-28 10:10:40,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:40,711 INFO L93 Difference]: Finished difference Result 8 states and 8 transitions. [2018-09-28 10:10:40,712 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-09-28 10:10:40,712 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 4 [2018-09-28 10:10:40,712 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:40,713 INFO L225 Difference]: With dead ends: 8 [2018-09-28 10:10:40,713 INFO L226 Difference]: Without dead ends: 6 [2018-09-28 10:10:40,714 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-09-28 10:10:40,714 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6 states. [2018-09-28 10:10:40,716 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6 to 6. [2018-09-28 10:10:40,716 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2018-09-28 10:10:40,716 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 6 transitions. [2018-09-28 10:10:40,717 INFO L78 Accepts]: Start accepts. Automaton has 6 states and 6 transitions. Word has length 4 [2018-09-28 10:10:40,717 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:40,717 INFO L480 AbstractCegarLoop]: Abstraction has 6 states and 6 transitions. [2018-09-28 10:10:40,717 INFO L481 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-09-28 10:10:40,717 INFO L276 IsEmpty]: Start isEmpty. Operand 6 states and 6 transitions. [2018-09-28 10:10:40,718 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2018-09-28 10:10:40,718 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:40,718 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1] [2018-09-28 10:10:40,718 INFO L423 AbstractCegarLoop]: === Iteration 3 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:40,718 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:40,719 INFO L82 PathProgramCache]: Analyzing trace with hash 28752416, now seen corresponding path program 2 times [2018-09-28 10:10:40,719 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:40,719 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:40,720 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:40,720 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:10:40,720 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:40,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:40,862 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:40,863 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:40,863 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:40,878 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-28 10:10:40,911 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-28 10:10:40,912 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:40,913 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:40,941 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:40,961 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:40,961 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-09-28 10:10:40,961 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-09-28 10:10:40,962 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-09-28 10:10:40,962 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-09-28 10:10:40,962 INFO L87 Difference]: Start difference. First operand 6 states and 6 transitions. Second operand 5 states. [2018-09-28 10:10:41,016 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:41,016 INFO L93 Difference]: Finished difference Result 9 states and 9 transitions. [2018-09-28 10:10:41,017 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-09-28 10:10:41,017 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 5 [2018-09-28 10:10:41,017 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:41,018 INFO L225 Difference]: With dead ends: 9 [2018-09-28 10:10:41,018 INFO L226 Difference]: Without dead ends: 7 [2018-09-28 10:10:41,019 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-09-28 10:10:41,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7 states. [2018-09-28 10:10:41,021 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-09-28 10:10:41,021 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-09-28 10:10:41,022 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-09-28 10:10:41,022 INFO L78 Accepts]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 5 [2018-09-28 10:10:41,022 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:41,022 INFO L480 AbstractCegarLoop]: Abstraction has 7 states and 7 transitions. [2018-09-28 10:10:41,022 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-09-28 10:10:41,023 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states and 7 transitions. [2018-09-28 10:10:41,023 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2018-09-28 10:10:41,024 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:41,024 INFO L375 BasicCegarLoop]: trace histogram [3, 1, 1, 1] [2018-09-28 10:10:41,024 INFO L423 AbstractCegarLoop]: === Iteration 4 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:41,024 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:41,025 INFO L82 PathProgramCache]: Analyzing trace with hash 891321030, now seen corresponding path program 3 times [2018-09-28 10:10:41,025 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:41,025 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:41,026 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:41,026 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:41,026 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:41,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:41,218 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:41,219 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:41,219 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:41,230 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-28 10:10:41,250 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-09-28 10:10:41,251 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:41,252 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:41,273 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:41,293 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:41,293 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2018-09-28 10:10:41,293 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-09-28 10:10:41,294 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-09-28 10:10:41,294 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-09-28 10:10:41,294 INFO L87 Difference]: Start difference. First operand 7 states and 7 transitions. Second operand 6 states. [2018-09-28 10:10:41,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:41,523 INFO L93 Difference]: Finished difference Result 10 states and 10 transitions. [2018-09-28 10:10:41,523 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-09-28 10:10:41,524 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 6 [2018-09-28 10:10:41,524 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:41,524 INFO L225 Difference]: With dead ends: 10 [2018-09-28 10:10:41,525 INFO L226 Difference]: Without dead ends: 8 [2018-09-28 10:10:41,525 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-09-28 10:10:41,526 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8 states. [2018-09-28 10:10:41,527 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-09-28 10:10:41,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 8 states. [2018-09-28 10:10:41,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 8 transitions. [2018-09-28 10:10:41,528 INFO L78 Accepts]: Start accepts. Automaton has 8 states and 8 transitions. Word has length 6 [2018-09-28 10:10:41,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:41,529 INFO L480 AbstractCegarLoop]: Abstraction has 8 states and 8 transitions. [2018-09-28 10:10:41,529 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-09-28 10:10:41,529 INFO L276 IsEmpty]: Start isEmpty. Operand 8 states and 8 transitions. [2018-09-28 10:10:41,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2018-09-28 10:10:41,530 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:41,530 INFO L375 BasicCegarLoop]: trace histogram [4, 1, 1, 1] [2018-09-28 10:10:41,530 INFO L423 AbstractCegarLoop]: === Iteration 5 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:41,530 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:41,531 INFO L82 PathProgramCache]: Analyzing trace with hash 1861144288, now seen corresponding path program 4 times [2018-09-28 10:10:41,531 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:41,531 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:41,532 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:41,532 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:41,532 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:41,541 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:41,669 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:41,669 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:41,670 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:41,679 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-28 10:10:41,689 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-28 10:10:41,689 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:41,690 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:41,708 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:41,729 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:41,729 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-09-28 10:10:41,729 INFO L459 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-09-28 10:10:41,731 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-09-28 10:10:41,731 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-09-28 10:10:41,731 INFO L87 Difference]: Start difference. First operand 8 states and 8 transitions. Second operand 7 states. [2018-09-28 10:10:41,822 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:41,822 INFO L93 Difference]: Finished difference Result 11 states and 11 transitions. [2018-09-28 10:10:41,823 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-09-28 10:10:41,823 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 7 [2018-09-28 10:10:41,823 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:41,824 INFO L225 Difference]: With dead ends: 11 [2018-09-28 10:10:41,824 INFO L226 Difference]: Without dead ends: 9 [2018-09-28 10:10:41,825 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 6 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-09-28 10:10:41,825 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 9 states. [2018-09-28 10:10:41,828 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-09-28 10:10:41,828 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2018-09-28 10:10:41,828 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-09-28 10:10:41,828 INFO L78 Accepts]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-09-28 10:10:41,829 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:41,829 INFO L480 AbstractCegarLoop]: Abstraction has 9 states and 9 transitions. [2018-09-28 10:10:41,829 INFO L481 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-09-28 10:10:41,829 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states and 9 transitions. [2018-09-28 10:10:41,829 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2018-09-28 10:10:41,829 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:41,829 INFO L375 BasicCegarLoop]: trace histogram [5, 1, 1, 1] [2018-09-28 10:10:41,830 INFO L423 AbstractCegarLoop]: === Iteration 6 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:41,830 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:41,830 INFO L82 PathProgramCache]: Analyzing trace with hash 1860894214, now seen corresponding path program 5 times [2018-09-28 10:10:41,830 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:41,830 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:41,831 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:41,831 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:41,831 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:41,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:42,034 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:42,034 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:42,034 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:42,043 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-28 10:10:42,054 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-09-28 10:10:42,054 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:42,057 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:42,102 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:42,123 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:42,123 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-09-28 10:10:42,124 INFO L459 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-09-28 10:10:42,124 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-09-28 10:10:42,124 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-09-28 10:10:42,124 INFO L87 Difference]: Start difference. First operand 9 states and 9 transitions. Second operand 8 states. [2018-09-28 10:10:42,211 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:42,211 INFO L93 Difference]: Finished difference Result 12 states and 12 transitions. [2018-09-28 10:10:42,211 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-09-28 10:10:42,212 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 8 [2018-09-28 10:10:42,212 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:42,212 INFO L225 Difference]: With dead ends: 12 [2018-09-28 10:10:42,212 INFO L226 Difference]: Without dead ends: 10 [2018-09-28 10:10:42,213 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-09-28 10:10:42,213 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10 states. [2018-09-28 10:10:42,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-09-28 10:10:42,215 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2018-09-28 10:10:42,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-09-28 10:10:42,216 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-09-28 10:10:42,216 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:42,216 INFO L480 AbstractCegarLoop]: Abstraction has 10 states and 10 transitions. [2018-09-28 10:10:42,217 INFO L481 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-09-28 10:10:42,217 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 10 transitions. [2018-09-28 10:10:42,217 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-09-28 10:10:42,217 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:42,218 INFO L375 BasicCegarLoop]: trace histogram [6, 1, 1, 1] [2018-09-28 10:10:42,218 INFO L423 AbstractCegarLoop]: === Iteration 7 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:42,218 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:42,218 INFO L82 PathProgramCache]: Analyzing trace with hash 1853141920, now seen corresponding path program 6 times [2018-09-28 10:10:42,218 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:42,219 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:42,219 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:42,220 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:42,220 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:42,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:42,420 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:42,420 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:42,420 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:42,428 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-28 10:10:42,490 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-09-28 10:10:42,490 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:42,492 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:42,559 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:42,593 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:42,594 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-09-28 10:10:42,594 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-09-28 10:10:42,595 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-09-28 10:10:42,595 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-09-28 10:10:42,595 INFO L87 Difference]: Start difference. First operand 10 states and 10 transitions. Second operand 9 states. [2018-09-28 10:10:42,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:42,830 INFO L93 Difference]: Finished difference Result 13 states and 13 transitions. [2018-09-28 10:10:42,831 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-09-28 10:10:42,831 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 9 [2018-09-28 10:10:42,831 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:42,832 INFO L225 Difference]: With dead ends: 13 [2018-09-28 10:10:42,832 INFO L226 Difference]: Without dead ends: 11 [2018-09-28 10:10:42,833 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-09-28 10:10:42,833 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2018-09-28 10:10:42,835 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-09-28 10:10:42,836 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2018-09-28 10:10:42,836 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-09-28 10:10:42,836 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-09-28 10:10:42,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:42,837 INFO L480 AbstractCegarLoop]: Abstraction has 11 states and 11 transitions. [2018-09-28 10:10:42,837 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-09-28 10:10:42,837 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 11 transitions. [2018-09-28 10:10:42,837 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-09-28 10:10:42,837 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:42,837 INFO L375 BasicCegarLoop]: trace histogram [7, 1, 1, 1] [2018-09-28 10:10:42,838 INFO L423 AbstractCegarLoop]: === Iteration 8 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:42,838 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:42,838 INFO L82 PathProgramCache]: Analyzing trace with hash 1612820806, now seen corresponding path program 7 times [2018-09-28 10:10:42,838 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:42,838 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:42,839 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:42,839 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:42,839 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:42,848 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:43,049 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:43,049 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:43,050 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:43,057 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:10:43,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:43,067 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:43,092 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:43,123 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:43,123 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2018-09-28 10:10:43,123 INFO L459 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-09-28 10:10:43,123 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-09-28 10:10:43,124 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-09-28 10:10:43,124 INFO L87 Difference]: Start difference. First operand 11 states and 11 transitions. Second operand 10 states. [2018-09-28 10:10:43,286 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:43,287 INFO L93 Difference]: Finished difference Result 14 states and 14 transitions. [2018-09-28 10:10:43,287 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-09-28 10:10:43,287 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 10 [2018-09-28 10:10:43,288 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:43,288 INFO L225 Difference]: With dead ends: 14 [2018-09-28 10:10:43,288 INFO L226 Difference]: Without dead ends: 12 [2018-09-28 10:10:43,289 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 9 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-09-28 10:10:43,289 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2018-09-28 10:10:43,291 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-09-28 10:10:43,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 12 states. [2018-09-28 10:10:43,292 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-09-28 10:10:43,292 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-09-28 10:10:43,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:43,292 INFO L480 AbstractCegarLoop]: Abstraction has 12 states and 12 transitions. [2018-09-28 10:10:43,293 INFO L481 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-09-28 10:10:43,293 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 12 transitions. [2018-09-28 10:10:43,293 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-09-28 10:10:43,293 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:43,293 INFO L375 BasicCegarLoop]: trace histogram [8, 1, 1, 1] [2018-09-28 10:10:43,293 INFO L423 AbstractCegarLoop]: === Iteration 9 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:43,294 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:43,294 INFO L82 PathProgramCache]: Analyzing trace with hash -1542166432, now seen corresponding path program 8 times [2018-09-28 10:10:43,294 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:43,294 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:43,295 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:43,295 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:10:43,295 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:43,309 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:43,514 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:43,514 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:43,515 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:43,531 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-28 10:10:43,543 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-28 10:10:43,544 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:43,545 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:43,936 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 35 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-09-28 10:10:43,966 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:43,966 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 18 [2018-09-28 10:10:43,966 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-09-28 10:10:43,967 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-09-28 10:10:43,967 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=307, Unknown=0, NotChecked=0, Total=342 [2018-09-28 10:10:43,967 INFO L87 Difference]: Start difference. First operand 12 states and 12 transitions. Second operand 19 states. [2018-09-28 10:10:44,850 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:44,851 INFO L93 Difference]: Finished difference Result 35 states and 36 transitions. [2018-09-28 10:10:44,851 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-09-28 10:10:44,851 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 11 [2018-09-28 10:10:44,852 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:44,852 INFO L225 Difference]: With dead ends: 35 [2018-09-28 10:10:44,853 INFO L226 Difference]: Without dead ends: 32 [2018-09-28 10:10:44,854 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=99, Invalid=1091, Unknown=0, NotChecked=0, Total=1190 [2018-09-28 10:10:44,855 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2018-09-28 10:10:44,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 19. [2018-09-28 10:10:44,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-09-28 10:10:44,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 25 transitions. [2018-09-28 10:10:44,860 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 25 transitions. Word has length 11 [2018-09-28 10:10:44,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:44,860 INFO L480 AbstractCegarLoop]: Abstraction has 19 states and 25 transitions. [2018-09-28 10:10:44,860 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-09-28 10:10:44,861 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 25 transitions. [2018-09-28 10:10:44,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-09-28 10:10:44,861 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:44,861 INFO L375 BasicCegarLoop]: trace histogram [9, 1, 1, 1] [2018-09-28 10:10:44,861 INFO L423 AbstractCegarLoop]: === Iteration 10 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:44,862 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:44,862 INFO L82 PathProgramCache]: Analyzing trace with hash -562523002, now seen corresponding path program 9 times [2018-09-28 10:10:44,862 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:44,862 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:44,863 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:44,863 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:44,863 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:44,871 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:45,231 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:45,232 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:45,232 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:45,242 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-28 10:10:45,253 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-09-28 10:10:45,253 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:45,255 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:45,288 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:45,313 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:45,313 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 11 [2018-09-28 10:10:45,313 INFO L459 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-09-28 10:10:45,314 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-09-28 10:10:45,314 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-09-28 10:10:45,314 INFO L87 Difference]: Start difference. First operand 19 states and 25 transitions. Second operand 12 states. [2018-09-28 10:10:45,489 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:45,490 INFO L93 Difference]: Finished difference Result 23 states and 29 transitions. [2018-09-28 10:10:45,490 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-09-28 10:10:45,490 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 12 [2018-09-28 10:10:45,491 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:45,492 INFO L225 Difference]: With dead ends: 23 [2018-09-28 10:10:45,493 INFO L226 Difference]: Without dead ends: 21 [2018-09-28 10:10:45,493 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 11 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-09-28 10:10:45,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2018-09-28 10:10:45,498 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-09-28 10:10:45,498 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-09-28 10:10:45,499 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2018-09-28 10:10:45,499 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 27 transitions. Word has length 12 [2018-09-28 10:10:45,499 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:45,499 INFO L480 AbstractCegarLoop]: Abstraction has 21 states and 27 transitions. [2018-09-28 10:10:45,499 INFO L481 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-09-28 10:10:45,500 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 27 transitions. [2018-09-28 10:10:45,500 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-09-28 10:10:45,500 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:45,500 INFO L375 BasicCegarLoop]: trace histogram [10, 1, 1, 1] [2018-09-28 10:10:45,501 INFO L423 AbstractCegarLoop]: === Iteration 11 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:45,501 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:45,501 INFO L82 PathProgramCache]: Analyzing trace with hash -258347744, now seen corresponding path program 10 times [2018-09-28 10:10:45,501 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:45,501 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:45,502 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:45,502 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:45,502 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:45,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:45,753 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:45,753 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:45,753 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:45,761 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-28 10:10:45,785 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-28 10:10:45,785 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:45,787 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:45,805 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:45,830 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:45,830 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 12 [2018-09-28 10:10:45,831 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-09-28 10:10:45,831 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-09-28 10:10:45,831 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-09-28 10:10:45,831 INFO L87 Difference]: Start difference. First operand 21 states and 27 transitions. Second operand 13 states. [2018-09-28 10:10:46,016 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:46,017 INFO L93 Difference]: Finished difference Result 24 states and 30 transitions. [2018-09-28 10:10:46,023 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-09-28 10:10:46,024 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 13 [2018-09-28 10:10:46,024 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:46,024 INFO L225 Difference]: With dead ends: 24 [2018-09-28 10:10:46,025 INFO L226 Difference]: Without dead ends: 22 [2018-09-28 10:10:46,025 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 12 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-09-28 10:10:46,025 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-09-28 10:10:46,031 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-09-28 10:10:46,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2018-09-28 10:10:46,033 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 28 transitions. [2018-09-28 10:10:46,033 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 28 transitions. Word has length 13 [2018-09-28 10:10:46,033 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:46,033 INFO L480 AbstractCegarLoop]: Abstraction has 22 states and 28 transitions. [2018-09-28 10:10:46,034 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-09-28 10:10:46,034 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 28 transitions. [2018-09-28 10:10:46,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-09-28 10:10:46,034 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:46,034 INFO L375 BasicCegarLoop]: trace histogram [11, 1, 1, 1] [2018-09-28 10:10:46,035 INFO L423 AbstractCegarLoop]: === Iteration 12 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:46,035 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:46,035 INFO L82 PathProgramCache]: Analyzing trace with hash 581150662, now seen corresponding path program 11 times [2018-09-28 10:10:46,035 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:46,036 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:46,037 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:46,037 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:46,037 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:46,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:46,442 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:46,442 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:46,443 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:46,450 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-28 10:10:46,466 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-09-28 10:10:46,467 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:46,468 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:46,495 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:46,516 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:46,517 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 13 [2018-09-28 10:10:46,517 INFO L459 AbstractCegarLoop]: Interpolant automaton has 14 states [2018-09-28 10:10:46,517 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2018-09-28 10:10:46,517 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=157, Unknown=0, NotChecked=0, Total=182 [2018-09-28 10:10:46,518 INFO L87 Difference]: Start difference. First operand 22 states and 28 transitions. Second operand 14 states. [2018-09-28 10:10:46,825 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:46,826 INFO L93 Difference]: Finished difference Result 25 states and 31 transitions. [2018-09-28 10:10:46,826 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-09-28 10:10:46,826 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 14 [2018-09-28 10:10:46,827 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:46,827 INFO L225 Difference]: With dead ends: 25 [2018-09-28 10:10:46,827 INFO L226 Difference]: Without dead ends: 23 [2018-09-28 10:10:46,828 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 13 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=25, Invalid=157, Unknown=0, NotChecked=0, Total=182 [2018-09-28 10:10:46,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2018-09-28 10:10:46,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-09-28 10:10:46,832 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-09-28 10:10:46,832 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 29 transitions. [2018-09-28 10:10:46,832 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 29 transitions. Word has length 14 [2018-09-28 10:10:46,833 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:46,833 INFO L480 AbstractCegarLoop]: Abstraction has 23 states and 29 transitions. [2018-09-28 10:10:46,833 INFO L481 AbstractCegarLoop]: Interpolant automaton has 14 states. [2018-09-28 10:10:46,833 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 29 transitions. [2018-09-28 10:10:46,833 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-09-28 10:10:46,834 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:46,834 INFO L375 BasicCegarLoop]: trace histogram [12, 1, 1, 1] [2018-09-28 10:10:46,834 INFO L423 AbstractCegarLoop]: === Iteration 13 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:46,834 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:46,834 INFO L82 PathProgramCache]: Analyzing trace with hash 835797472, now seen corresponding path program 12 times [2018-09-28 10:10:46,834 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:46,834 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:46,835 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:46,835 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:46,835 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:46,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:47,242 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:47,243 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:47,243 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:47,250 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-28 10:10:47,263 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-09-28 10:10:47,263 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:47,265 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:47,288 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:47,310 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:47,311 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 14 [2018-09-28 10:10:47,311 INFO L459 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-09-28 10:10:47,311 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-09-28 10:10:47,311 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-09-28 10:10:47,312 INFO L87 Difference]: Start difference. First operand 23 states and 29 transitions. Second operand 15 states. [2018-09-28 10:10:47,539 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:47,540 INFO L93 Difference]: Finished difference Result 26 states and 32 transitions. [2018-09-28 10:10:47,541 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-09-28 10:10:47,541 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 15 [2018-09-28 10:10:47,541 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:47,542 INFO L225 Difference]: With dead ends: 26 [2018-09-28 10:10:47,542 INFO L226 Difference]: Without dead ends: 24 [2018-09-28 10:10:47,542 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-09-28 10:10:47,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 24 states. [2018-09-28 10:10:47,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 24 to 24. [2018-09-28 10:10:47,546 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 24 states. [2018-09-28 10:10:47,547 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 30 transitions. [2018-09-28 10:10:47,547 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 30 transitions. Word has length 15 [2018-09-28 10:10:47,547 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:47,547 INFO L480 AbstractCegarLoop]: Abstraction has 24 states and 30 transitions. [2018-09-28 10:10:47,547 INFO L481 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-09-28 10:10:47,548 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 30 transitions. [2018-09-28 10:10:47,548 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-09-28 10:10:47,548 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:47,548 INFO L375 BasicCegarLoop]: trace histogram [13, 1, 1, 1] [2018-09-28 10:10:47,548 INFO L423 AbstractCegarLoop]: === Iteration 14 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:47,549 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:47,549 INFO L82 PathProgramCache]: Analyzing trace with hash 139913990, now seen corresponding path program 13 times [2018-09-28 10:10:47,549 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:47,549 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:47,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:47,550 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:47,550 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:47,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:47,907 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:47,907 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:47,907 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:47,917 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:10:47,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:47,930 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:47,942 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:47,962 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:47,963 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 15 [2018-09-28 10:10:47,963 INFO L459 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-09-28 10:10:47,963 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-09-28 10:10:47,964 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=211, Unknown=0, NotChecked=0, Total=240 [2018-09-28 10:10:47,964 INFO L87 Difference]: Start difference. First operand 24 states and 30 transitions. Second operand 16 states. [2018-09-28 10:10:48,510 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:48,510 INFO L93 Difference]: Finished difference Result 27 states and 33 transitions. [2018-09-28 10:10:48,513 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-09-28 10:10:48,514 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 16 [2018-09-28 10:10:48,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:48,514 INFO L225 Difference]: With dead ends: 27 [2018-09-28 10:10:48,515 INFO L226 Difference]: Without dead ends: 25 [2018-09-28 10:10:48,515 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 15 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=29, Invalid=211, Unknown=0, NotChecked=0, Total=240 [2018-09-28 10:10:48,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2018-09-28 10:10:48,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-09-28 10:10:48,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 25 states. [2018-09-28 10:10:48,520 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 31 transitions. [2018-09-28 10:10:48,520 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 31 transitions. Word has length 16 [2018-09-28 10:10:48,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:48,521 INFO L480 AbstractCegarLoop]: Abstraction has 25 states and 31 transitions. [2018-09-28 10:10:48,521 INFO L481 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-09-28 10:10:48,521 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 31 transitions. [2018-09-28 10:10:48,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-09-28 10:10:48,521 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:48,521 INFO L375 BasicCegarLoop]: trace histogram [14, 1, 1, 1] [2018-09-28 10:10:48,522 INFO L423 AbstractCegarLoop]: === Iteration 15 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:48,522 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:48,522 INFO L82 PathProgramCache]: Analyzing trace with hash 42362528, now seen corresponding path program 14 times [2018-09-28 10:10:48,522 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:48,522 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:48,523 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:48,523 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:10:48,523 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:48,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:48,853 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 0 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:48,854 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:48,854 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:48,865 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-28 10:10:48,883 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-28 10:10:48,883 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:48,885 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:48,900 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 0 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:48,921 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:48,921 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 16 [2018-09-28 10:10:48,921 INFO L459 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-09-28 10:10:48,921 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-09-28 10:10:48,922 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=241, Unknown=0, NotChecked=0, Total=272 [2018-09-28 10:10:48,922 INFO L87 Difference]: Start difference. First operand 25 states and 31 transitions. Second operand 17 states. [2018-09-28 10:10:49,275 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:49,275 INFO L93 Difference]: Finished difference Result 28 states and 34 transitions. [2018-09-28 10:10:49,276 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-09-28 10:10:49,276 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 17 [2018-09-28 10:10:49,276 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:49,277 INFO L225 Difference]: With dead ends: 28 [2018-09-28 10:10:49,277 INFO L226 Difference]: Without dead ends: 26 [2018-09-28 10:10:49,278 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=31, Invalid=241, Unknown=0, NotChecked=0, Total=272 [2018-09-28 10:10:49,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2018-09-28 10:10:49,281 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 26. [2018-09-28 10:10:49,281 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-09-28 10:10:49,282 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2018-09-28 10:10:49,282 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 17 [2018-09-28 10:10:49,282 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:49,282 INFO L480 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2018-09-28 10:10:49,282 INFO L481 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-09-28 10:10:49,283 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2018-09-28 10:10:49,283 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-09-28 10:10:49,283 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:49,283 INFO L375 BasicCegarLoop]: trace histogram [15, 1, 1, 1] [2018-09-28 10:10:49,283 INFO L423 AbstractCegarLoop]: === Iteration 16 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:49,284 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:49,284 INFO L82 PathProgramCache]: Analyzing trace with hash 1313234502, now seen corresponding path program 15 times [2018-09-28 10:10:49,284 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:49,284 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:49,284 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:49,285 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:49,285 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:49,291 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:49,947 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:49,947 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:49,947 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:49,956 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-28 10:10:49,971 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 9 check-sat command(s) [2018-09-28 10:10:49,971 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:49,973 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:49,987 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:50,007 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:50,007 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 17 [2018-09-28 10:10:50,007 INFO L459 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-09-28 10:10:50,007 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-09-28 10:10:50,008 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=273, Unknown=0, NotChecked=0, Total=306 [2018-09-28 10:10:50,008 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand 18 states. [2018-09-28 10:10:50,309 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:50,309 INFO L93 Difference]: Finished difference Result 29 states and 35 transitions. [2018-09-28 10:10:50,309 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-09-28 10:10:50,309 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 18 [2018-09-28 10:10:50,310 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:50,310 INFO L225 Difference]: With dead ends: 29 [2018-09-28 10:10:50,311 INFO L226 Difference]: Without dead ends: 27 [2018-09-28 10:10:50,314 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 17 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=33, Invalid=273, Unknown=0, NotChecked=0, Total=306 [2018-09-28 10:10:50,315 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2018-09-28 10:10:50,318 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-09-28 10:10:50,318 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 27 states. [2018-09-28 10:10:50,319 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 33 transitions. [2018-09-28 10:10:50,319 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 33 transitions. Word has length 18 [2018-09-28 10:10:50,319 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:50,319 INFO L480 AbstractCegarLoop]: Abstraction has 27 states and 33 transitions. [2018-09-28 10:10:50,319 INFO L481 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-09-28 10:10:50,320 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 33 transitions. [2018-09-28 10:10:50,320 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-09-28 10:10:50,320 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:50,320 INFO L375 BasicCegarLoop]: trace histogram [17, 1, 1, 1] [2018-09-28 10:10:50,321 INFO L423 AbstractCegarLoop]: === Iteration 17 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:50,321 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:50,321 INFO L82 PathProgramCache]: Analyzing trace with hash -702152314, now seen corresponding path program 16 times [2018-09-28 10:10:50,321 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:50,321 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:50,322 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:50,322 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:50,322 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:50,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:52,823 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:52,823 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:52,823 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:52,839 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-28 10:10:52,871 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-28 10:10:52,872 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:52,874 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:52,944 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:52,979 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:52,979 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 19 [2018-09-28 10:10:52,980 INFO L459 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-09-28 10:10:52,980 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-09-28 10:10:52,980 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=342, Unknown=1, NotChecked=0, Total=380 [2018-09-28 10:10:52,981 INFO L87 Difference]: Start difference. First operand 27 states and 33 transitions. Second operand 20 states. [2018-09-28 10:10:57,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:10:57,749 INFO L93 Difference]: Finished difference Result 31 states and 37 transitions. [2018-09-28 10:10:57,749 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-09-28 10:10:57,749 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 20 [2018-09-28 10:10:57,750 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:10:57,750 INFO L225 Difference]: With dead ends: 31 [2018-09-28 10:10:57,750 INFO L226 Difference]: Without dead ends: 29 [2018-09-28 10:10:57,751 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 19 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=37, Invalid=342, Unknown=1, NotChecked=0, Total=380 [2018-09-28 10:10:57,751 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2018-09-28 10:10:57,755 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-09-28 10:10:57,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 29 states. [2018-09-28 10:10:57,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2018-09-28 10:10:57,755 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 20 [2018-09-28 10:10:57,756 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:10:57,756 INFO L480 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2018-09-28 10:10:57,756 INFO L481 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-09-28 10:10:57,756 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2018-09-28 10:10:57,756 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-09-28 10:10:57,756 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:10:57,757 INFO L375 BasicCegarLoop]: trace histogram [18, 1, 1, 1] [2018-09-28 10:10:57,757 INFO L423 AbstractCegarLoop]: === Iteration 18 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:10:57,757 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:10:57,757 INFO L82 PathProgramCache]: Analyzing trace with hash -291889120, now seen corresponding path program 17 times [2018-09-28 10:10:57,757 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:10:57,757 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:10:57,758 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:57,758 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:10:57,758 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:10:57,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:10:58,644 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 0 proven. 171 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:58,645 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:10:58,645 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:10:58,653 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-28 10:10:58,727 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2018-09-28 10:10:58,728 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:10:58,729 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:10:58,743 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 0 proven. 171 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:10:58,764 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:10:58,764 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 20 [2018-09-28 10:10:58,764 INFO L459 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-09-28 10:10:58,765 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-09-28 10:10:58,765 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=381, Unknown=0, NotChecked=0, Total=420 [2018-09-28 10:10:58,765 INFO L87 Difference]: Start difference. First operand 29 states and 35 transitions. Second operand 21 states. [2018-09-28 10:11:01,364 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:11:01,365 INFO L93 Difference]: Finished difference Result 32 states and 38 transitions. [2018-09-28 10:11:01,365 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-09-28 10:11:01,366 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 21 [2018-09-28 10:11:01,366 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:11:01,366 INFO L225 Difference]: With dead ends: 32 [2018-09-28 10:11:01,366 INFO L226 Difference]: Without dead ends: 30 [2018-09-28 10:11:01,367 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 20 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=39, Invalid=381, Unknown=0, NotChecked=0, Total=420 [2018-09-28 10:11:01,367 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2018-09-28 10:11:01,372 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2018-09-28 10:11:01,372 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 30 states. [2018-09-28 10:11:01,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 36 transitions. [2018-09-28 10:11:01,373 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 36 transitions. Word has length 21 [2018-09-28 10:11:01,373 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:11:01,373 INFO L480 AbstractCegarLoop]: Abstraction has 30 states and 36 transitions. [2018-09-28 10:11:01,373 INFO L481 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-09-28 10:11:01,373 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 36 transitions. [2018-09-28 10:11:01,374 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-09-28 10:11:01,374 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:11:01,374 INFO L375 BasicCegarLoop]: trace histogram [19, 1, 1, 1] [2018-09-28 10:11:01,374 INFO L423 AbstractCegarLoop]: === Iteration 19 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:11:01,374 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:11:01,374 INFO L82 PathProgramCache]: Analyzing trace with hash -458631994, now seen corresponding path program 18 times [2018-09-28 10:11:01,375 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:11:01,375 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:11:01,375 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:01,375 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:11:01,376 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:01,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:11:05,718 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 189 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:05,719 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:11:05,719 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-09-28 10:11:05,733 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:11:05,778 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 11 check-sat command(s) [2018-09-28 10:11:05,778 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:11:05,780 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:11:05,795 INFO L134 CoverageAnalysis]: Checked inductivity of 190 backedges. 0 proven. 189 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:05,817 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:11:05,817 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 21 [2018-09-28 10:11:05,817 INFO L459 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-09-28 10:11:05,817 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-09-28 10:11:05,818 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=420, Unknown=1, NotChecked=0, Total=462 [2018-09-28 10:11:05,818 INFO L87 Difference]: Start difference. First operand 30 states and 36 transitions. Second operand 22 states. [2018-09-28 10:11:10,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:11:10,345 INFO L93 Difference]: Finished difference Result 33 states and 39 transitions. [2018-09-28 10:11:10,346 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-09-28 10:11:10,346 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 22 [2018-09-28 10:11:10,346 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:11:10,347 INFO L225 Difference]: With dead ends: 33 [2018-09-28 10:11:10,347 INFO L226 Difference]: Without dead ends: 31 [2018-09-28 10:11:10,348 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 21 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=41, Invalid=420, Unknown=1, NotChecked=0, Total=462 [2018-09-28 10:11:10,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 31 states. [2018-09-28 10:11:10,352 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-09-28 10:11:10,352 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-09-28 10:11:10,353 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 37 transitions. [2018-09-28 10:11:10,353 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 37 transitions. Word has length 22 [2018-09-28 10:11:10,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:11:10,353 INFO L480 AbstractCegarLoop]: Abstraction has 31 states and 37 transitions. [2018-09-28 10:11:10,353 INFO L481 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-09-28 10:11:10,353 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 37 transitions. [2018-09-28 10:11:10,354 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2018-09-28 10:11:10,354 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:11:10,354 INFO L375 BasicCegarLoop]: trace histogram [20, 1, 1, 1] [2018-09-28 10:11:10,355 INFO L423 AbstractCegarLoop]: === Iteration 20 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:11:10,355 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:11:10,355 INFO L82 PathProgramCache]: Analyzing trace with hash -1332693792, now seen corresponding path program 19 times [2018-09-28 10:11:10,355 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:11:10,355 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:11:10,356 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:10,356 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:11:10,356 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:10,362 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:11:16,528 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 0 proven. 208 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:16,529 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:11:16,529 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:11:16,538 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:11:16,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:11:16,568 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:11:16,626 INFO L134 CoverageAnalysis]: Checked inductivity of 210 backedges. 0 proven. 208 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:16,655 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:11:16,655 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 22 [2018-09-28 10:11:16,655 INFO L459 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-09-28 10:11:16,656 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-09-28 10:11:16,656 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=461, Unknown=2, NotChecked=0, Total=506 [2018-09-28 10:11:16,656 INFO L87 Difference]: Start difference. First operand 31 states and 37 transitions. Second operand 23 states. [2018-09-28 10:11:17,526 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:11:17,526 INFO L93 Difference]: Finished difference Result 34 states and 40 transitions. [2018-09-28 10:11:17,527 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-09-28 10:11:17,527 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 23 [2018-09-28 10:11:17,527 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:11:17,528 INFO L225 Difference]: With dead ends: 34 [2018-09-28 10:11:17,528 INFO L226 Difference]: Without dead ends: 32 [2018-09-28 10:11:17,529 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=43, Invalid=461, Unknown=2, NotChecked=0, Total=506 [2018-09-28 10:11:17,529 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2018-09-28 10:11:17,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2018-09-28 10:11:17,534 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 32 states. [2018-09-28 10:11:17,534 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 38 transitions. [2018-09-28 10:11:17,534 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 38 transitions. Word has length 23 [2018-09-28 10:11:17,534 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:11:17,534 INFO L480 AbstractCegarLoop]: Abstraction has 32 states and 38 transitions. [2018-09-28 10:11:17,535 INFO L481 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-09-28 10:11:17,535 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 38 transitions. [2018-09-28 10:11:17,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-09-28 10:11:17,535 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:11:17,535 INFO L375 BasicCegarLoop]: trace histogram [21, 1, 1, 1] [2018-09-28 10:11:17,536 INFO L423 AbstractCegarLoop]: === Iteration 21 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:11:17,536 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:11:17,536 INFO L82 PathProgramCache]: Analyzing trace with hash 1636161542, now seen corresponding path program 20 times [2018-09-28 10:11:17,536 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:11:17,536 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:11:17,537 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:17,537 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:11:17,537 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:17,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:11:21,611 INFO L134 CoverageAnalysis]: Checked inductivity of 231 backedges. 0 proven. 231 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:21,611 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:11:21,612 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:11:21,619 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-28 10:11:21,644 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-28 10:11:21,645 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:11:21,647 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:11:21,704 INFO L134 CoverageAnalysis]: Checked inductivity of 231 backedges. 0 proven. 231 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:21,733 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:11:21,734 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 23 [2018-09-28 10:11:21,734 INFO L459 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-09-28 10:11:21,734 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-09-28 10:11:21,735 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=506, Unknown=1, NotChecked=0, Total=552 [2018-09-28 10:11:21,735 INFO L87 Difference]: Start difference. First operand 32 states and 38 transitions. Second operand 24 states. [2018-09-28 10:11:24,734 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:11:24,734 INFO L93 Difference]: Finished difference Result 35 states and 41 transitions. [2018-09-28 10:11:24,735 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-09-28 10:11:24,735 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 24 [2018-09-28 10:11:24,735 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:11:24,736 INFO L225 Difference]: With dead ends: 35 [2018-09-28 10:11:24,736 INFO L226 Difference]: Without dead ends: 33 [2018-09-28 10:11:24,737 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=45, Invalid=506, Unknown=1, NotChecked=0, Total=552 [2018-09-28 10:11:24,737 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2018-09-28 10:11:24,741 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-09-28 10:11:24,741 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 33 states. [2018-09-28 10:11:24,741 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 39 transitions. [2018-09-28 10:11:24,741 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 39 transitions. Word has length 24 [2018-09-28 10:11:24,741 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:11:24,741 INFO L480 AbstractCegarLoop]: Abstraction has 33 states and 39 transitions. [2018-09-28 10:11:24,742 INFO L481 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-09-28 10:11:24,742 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 39 transitions. [2018-09-28 10:11:24,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-09-28 10:11:24,742 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:11:24,742 INFO L375 BasicCegarLoop]: trace histogram [22, 1, 1, 1] [2018-09-28 10:11:24,743 INFO L423 AbstractCegarLoop]: === Iteration 22 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:11:24,743 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:11:24,743 INFO L82 PathProgramCache]: Analyzing trace with hash -818603616, now seen corresponding path program 21 times [2018-09-28 10:11:24,743 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:11:24,743 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:11:24,744 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:24,744 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:11:24,744 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:24,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:11:30,094 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 0 proven. 252 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:30,095 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:11:30,095 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-09-28 10:11:30,103 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-28 10:11:30,123 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) [2018-09-28 10:11:30,123 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:11:30,126 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:11:30,164 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 0 proven. 252 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:30,194 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:11:30,194 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 24 [2018-09-28 10:11:30,194 INFO L459 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-09-28 10:11:30,194 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-09-28 10:11:30,195 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=551, Unknown=2, NotChecked=0, Total=600 [2018-09-28 10:11:30,195 INFO L87 Difference]: Start difference. First operand 33 states and 39 transitions. Second operand 25 states. [2018-09-28 10:11:37,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:11:37,542 INFO L93 Difference]: Finished difference Result 36 states and 42 transitions. [2018-09-28 10:11:37,544 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-09-28 10:11:37,544 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 25 [2018-09-28 10:11:37,544 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:11:37,545 INFO L225 Difference]: With dead ends: 36 [2018-09-28 10:11:37,545 INFO L226 Difference]: Without dead ends: 34 [2018-09-28 10:11:37,545 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=47, Invalid=551, Unknown=2, NotChecked=0, Total=600 [2018-09-28 10:11:37,546 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-09-28 10:11:37,549 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2018-09-28 10:11:37,549 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 34 states. [2018-09-28 10:11:37,549 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 40 transitions. [2018-09-28 10:11:37,550 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 40 transitions. Word has length 25 [2018-09-28 10:11:37,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:11:37,550 INFO L480 AbstractCegarLoop]: Abstraction has 34 states and 40 transitions. [2018-09-28 10:11:37,550 INFO L481 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-09-28 10:11:37,551 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 40 transitions. [2018-09-28 10:11:37,551 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2018-09-28 10:11:37,551 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:11:37,551 INFO L375 BasicCegarLoop]: trace histogram [23, 1, 1, 1] [2018-09-28 10:11:37,552 INFO L423 AbstractCegarLoop]: === Iteration 23 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:11:37,552 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:11:37,552 INFO L82 PathProgramCache]: Analyzing trace with hash 393087814, now seen corresponding path program 22 times [2018-09-28 10:11:37,552 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:11:37,552 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:11:37,553 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:37,553 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:11:37,553 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:37,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:11:38,848 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 0 proven. 276 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:38,848 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:11:38,848 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:11:38,856 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-28 10:11:38,886 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-28 10:11:38,887 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:11:38,889 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:11:38,943 INFO L134 CoverageAnalysis]: Checked inductivity of 276 backedges. 0 proven. 276 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:38,965 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:11:38,966 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 25 [2018-09-28 10:11:38,966 INFO L459 AbstractCegarLoop]: Interpolant automaton has 26 states [2018-09-28 10:11:38,966 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2018-09-28 10:11:38,967 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=601, Unknown=0, NotChecked=0, Total=650 [2018-09-28 10:11:38,967 INFO L87 Difference]: Start difference. First operand 34 states and 40 transitions. Second operand 26 states. [2018-09-28 10:11:46,001 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:11:46,001 INFO L93 Difference]: Finished difference Result 37 states and 43 transitions. [2018-09-28 10:11:46,001 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-09-28 10:11:46,002 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 26 [2018-09-28 10:11:46,002 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:11:46,002 INFO L225 Difference]: With dead ends: 37 [2018-09-28 10:11:46,003 INFO L226 Difference]: Without dead ends: 35 [2018-09-28 10:11:46,004 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 25 SyntacticMatches, 1 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=49, Invalid=601, Unknown=0, NotChecked=0, Total=650 [2018-09-28 10:11:46,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2018-09-28 10:11:46,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2018-09-28 10:11:46,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 35 states. [2018-09-28 10:11:46,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 41 transitions. [2018-09-28 10:11:46,009 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 41 transitions. Word has length 26 [2018-09-28 10:11:46,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:11:46,009 INFO L480 AbstractCegarLoop]: Abstraction has 35 states and 41 transitions. [2018-09-28 10:11:46,009 INFO L481 AbstractCegarLoop]: Interpolant automaton has 26 states. [2018-09-28 10:11:46,009 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 41 transitions. [2018-09-28 10:11:46,010 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2018-09-28 10:11:46,010 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:11:46,010 INFO L375 BasicCegarLoop]: trace histogram [25, 1, 1, 1] [2018-09-28 10:11:46,011 INFO L423 AbstractCegarLoop]: === Iteration 24 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:11:46,011 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:11:46,011 INFO L82 PathProgramCache]: Analyzing trace with hash -199856506, now seen corresponding path program 23 times [2018-09-28 10:11:46,011 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:11:46,011 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:11:46,012 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:46,012 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:11:46,012 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:46,018 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:11:51,457 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 0 proven. 323 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:51,458 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:11:51,458 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-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-09-28 10:11:51,465 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-28 10:11:51,485 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 14 check-sat command(s) [2018-09-28 10:11:51,485 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:11:51,486 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:11:51,515 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 0 proven. 323 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:11:51,540 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:11:51,541 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 27] total 27 [2018-09-28 10:11:51,541 INFO L459 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-09-28 10:11:51,541 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-09-28 10:11:51,541 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=53, Invalid=701, Unknown=2, NotChecked=0, Total=756 [2018-09-28 10:11:51,542 INFO L87 Difference]: Start difference. First operand 35 states and 41 transitions. Second operand 28 states. [2018-09-28 10:11:58,584 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:11:58,584 INFO L93 Difference]: Finished difference Result 39 states and 45 transitions. [2018-09-28 10:11:58,585 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-09-28 10:11:58,585 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 28 [2018-09-28 10:11:58,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:11:58,586 INFO L225 Difference]: With dead ends: 39 [2018-09-28 10:11:58,586 INFO L226 Difference]: Without dead ends: 37 [2018-09-28 10:11:58,586 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=53, Invalid=701, Unknown=2, NotChecked=0, Total=756 [2018-09-28 10:11:58,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2018-09-28 10:11:58,591 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2018-09-28 10:11:58,591 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 37 states. [2018-09-28 10:11:58,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 43 transitions. [2018-09-28 10:11:58,592 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 43 transitions. Word has length 28 [2018-09-28 10:11:58,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:11:58,592 INFO L480 AbstractCegarLoop]: Abstraction has 37 states and 43 transitions. [2018-09-28 10:11:58,592 INFO L481 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-09-28 10:11:58,593 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 43 transitions. [2018-09-28 10:11:58,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2018-09-28 10:11:58,593 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:11:58,594 INFO L375 BasicCegarLoop]: trace histogram [26, 1, 1, 1] [2018-09-28 10:11:58,594 INFO L423 AbstractCegarLoop]: === Iteration 25 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:11:58,594 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:11:58,594 INFO L82 PathProgramCache]: Analyzing trace with hash -1900588256, now seen corresponding path program 24 times [2018-09-28 10:11:58,594 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:11:58,594 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:11:58,595 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:58,595 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:11:58,595 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:11:58,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:12:01,957 INFO L134 CoverageAnalysis]: Checked inductivity of 351 backedges. 0 proven. 350 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:12:01,957 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:12:01,958 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:12:01,965 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-28 10:12:01,990 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 14 check-sat command(s) [2018-09-28 10:12:01,990 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:12:01,992 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:12:02,027 INFO L134 CoverageAnalysis]: Checked inductivity of 351 backedges. 0 proven. 350 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:12:02,049 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:12:02,049 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 28 [2018-09-28 10:12:02,049 INFO L459 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-09-28 10:12:02,050 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-09-28 10:12:02,050 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=756, Unknown=1, NotChecked=0, Total=812 [2018-09-28 10:12:02,050 INFO L87 Difference]: Start difference. First operand 37 states and 43 transitions. Second operand 29 states. [2018-09-28 10:12:13,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:12:13,140 INFO L93 Difference]: Finished difference Result 40 states and 46 transitions. [2018-09-28 10:12:13,141 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-09-28 10:12:13,141 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 29 [2018-09-28 10:12:13,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:12:13,141 INFO L225 Difference]: With dead ends: 40 [2018-09-28 10:12:13,142 INFO L226 Difference]: Without dead ends: 38 [2018-09-28 10:12:13,142 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=55, Invalid=756, Unknown=1, NotChecked=0, Total=812 [2018-09-28 10:12:13,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2018-09-28 10:12:13,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2018-09-28 10:12:13,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 38 states. [2018-09-28 10:12:13,146 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 44 transitions. [2018-09-28 10:12:13,146 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 44 transitions. Word has length 29 [2018-09-28 10:12:13,146 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:12:13,146 INFO L480 AbstractCegarLoop]: Abstraction has 38 states and 44 transitions. [2018-09-28 10:12:13,146 INFO L481 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-09-28 10:12:13,146 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 44 transitions. [2018-09-28 10:12:13,147 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-09-28 10:12:13,147 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:12:13,147 INFO L375 BasicCegarLoop]: trace histogram [27, 1, 1, 1] [2018-09-28 10:12:13,147 INFO L423 AbstractCegarLoop]: === Iteration 26 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:12:13,147 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:12:13,148 INFO L82 PathProgramCache]: Analyzing trace with hash 1211302342, now seen corresponding path program 25 times [2018-09-28 10:12:13,148 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:12:13,148 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:12:13,148 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:12:13,149 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:12:13,149 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:12:13,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:12:14,681 INFO L134 CoverageAnalysis]: Checked inductivity of 378 backedges. 0 proven. 378 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:12:14,681 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:12:14,681 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:12:14,690 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:12:14,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:12:14,710 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:12:14,736 INFO L134 CoverageAnalysis]: Checked inductivity of 378 backedges. 0 proven. 378 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:12:14,756 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:12:14,756 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 29] total 29 [2018-09-28 10:12:14,756 INFO L459 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-09-28 10:12:14,757 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-09-28 10:12:14,757 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=813, Unknown=0, NotChecked=0, Total=870 [2018-09-28 10:12:14,757 INFO L87 Difference]: Start difference. First operand 38 states and 44 transitions. Second operand 30 states. [2018-09-28 10:12:24,069 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:12:24,069 INFO L93 Difference]: Finished difference Result 41 states and 47 transitions. [2018-09-28 10:12:24,069 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-09-28 10:12:24,069 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 30 [2018-09-28 10:12:24,070 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:12:24,070 INFO L225 Difference]: With dead ends: 41 [2018-09-28 10:12:24,070 INFO L226 Difference]: Without dead ends: 39 [2018-09-28 10:12:24,071 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 29 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=57, Invalid=813, Unknown=0, NotChecked=0, Total=870 [2018-09-28 10:12:24,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-09-28 10:12:24,075 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2018-09-28 10:12:24,075 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 39 states. [2018-09-28 10:12:24,075 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 45 transitions. [2018-09-28 10:12:24,075 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 45 transitions. Word has length 30 [2018-09-28 10:12:24,075 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:12:24,075 INFO L480 AbstractCegarLoop]: Abstraction has 39 states and 45 transitions. [2018-09-28 10:12:24,075 INFO L481 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-09-28 10:12:24,075 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 45 transitions. [2018-09-28 10:12:24,076 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2018-09-28 10:12:24,076 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:12:24,076 INFO L375 BasicCegarLoop]: trace histogram [28, 1, 1, 1] [2018-09-28 10:12:24,077 INFO L423 AbstractCegarLoop]: === Iteration 27 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:12:24,077 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:12:24,077 INFO L82 PathProgramCache]: Analyzing trace with hash -1104336928, now seen corresponding path program 26 times [2018-09-28 10:12:24,077 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:12:24,077 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:12:24,078 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:12:24,078 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:12:24,078 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:12:24,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:12:29,442 INFO L134 CoverageAnalysis]: Checked inductivity of 406 backedges. 0 proven. 405 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:12:29,442 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:12:29,442 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:12:29,450 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-28 10:12:29,469 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-28 10:12:29,470 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:12:29,472 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:12:29,488 INFO L134 CoverageAnalysis]: Checked inductivity of 406 backedges. 0 proven. 405 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:12:29,508 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:12:29,508 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 30] total 30 [2018-09-28 10:12:29,508 INFO L459 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-09-28 10:12:29,508 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-09-28 10:12:29,509 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=870, Unknown=1, NotChecked=0, Total=930 [2018-09-28 10:12:29,509 INFO L87 Difference]: Start difference. First operand 39 states and 45 transitions. Second operand 31 states. [2018-09-28 10:12:32,643 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:12:32,644 INFO L93 Difference]: Finished difference Result 42 states and 48 transitions. [2018-09-28 10:12:32,645 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-09-28 10:12:32,645 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 31 [2018-09-28 10:12:32,645 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:12:32,646 INFO L225 Difference]: With dead ends: 42 [2018-09-28 10:12:32,646 INFO L226 Difference]: Without dead ends: 40 [2018-09-28 10:12:32,647 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=59, Invalid=870, Unknown=1, NotChecked=0, Total=930 [2018-09-28 10:12:32,647 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2018-09-28 10:12:32,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 40. [2018-09-28 10:12:32,651 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 40 states. [2018-09-28 10:12:32,651 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 46 transitions. [2018-09-28 10:12:32,651 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 46 transitions. Word has length 31 [2018-09-28 10:12:32,651 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:12:32,652 INFO L480 AbstractCegarLoop]: Abstraction has 40 states and 46 transitions. [2018-09-28 10:12:32,652 INFO L481 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-09-28 10:12:32,652 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 46 transitions. [2018-09-28 10:12:32,652 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-09-28 10:12:32,652 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:12:32,653 INFO L375 BasicCegarLoop]: trace histogram [29, 1, 1, 1] [2018-09-28 10:12:32,653 INFO L423 AbstractCegarLoop]: === Iteration 28 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:12:32,653 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:12:32,653 INFO L82 PathProgramCache]: Analyzing trace with hash 125289734, now seen corresponding path program 27 times [2018-09-28 10:12:32,653 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:12:32,653 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:12:32,654 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:12:32,654 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:12:32,654 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:12:32,660 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:12:42,655 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 0 proven. 432 refuted. 3 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:12:42,655 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:12:42,655 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:12:42,669 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-28 10:12:42,694 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2018-09-28 10:12:42,694 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:12:42,695 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:12:42,715 INFO L134 CoverageAnalysis]: Checked inductivity of 435 backedges. 0 proven. 432 refuted. 3 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:12:42,745 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:12:42,745 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 31] total 31 [2018-09-28 10:12:42,745 INFO L459 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-09-28 10:12:42,745 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-09-28 10:12:42,746 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=928, Unknown=3, NotChecked=0, Total=992 [2018-09-28 10:12:42,746 INFO L87 Difference]: Start difference. First operand 40 states and 46 transitions. Second operand 32 states. [2018-09-28 10:12:51,480 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:12:51,480 INFO L93 Difference]: Finished difference Result 43 states and 49 transitions. [2018-09-28 10:12:51,481 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-09-28 10:12:51,481 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 32 [2018-09-28 10:12:51,481 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:12:51,482 INFO L225 Difference]: With dead ends: 43 [2018-09-28 10:12:51,482 INFO L226 Difference]: Without dead ends: 41 [2018-09-28 10:12:51,483 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 31 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 9.9s TimeCoverageRelationStatistics Valid=61, Invalid=928, Unknown=3, NotChecked=0, Total=992 [2018-09-28 10:12:51,484 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2018-09-28 10:12:51,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2018-09-28 10:12:51,488 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-09-28 10:12:51,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 47 transitions. [2018-09-28 10:12:51,489 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 47 transitions. Word has length 32 [2018-09-28 10:12:51,489 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:12:51,489 INFO L480 AbstractCegarLoop]: Abstraction has 41 states and 47 transitions. [2018-09-28 10:12:51,489 INFO L481 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-09-28 10:12:51,489 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 47 transitions. [2018-09-28 10:12:51,490 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2018-09-28 10:12:51,490 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:12:51,490 INFO L375 BasicCegarLoop]: trace histogram [30, 1, 1, 1] [2018-09-28 10:12:51,491 INFO L423 AbstractCegarLoop]: === Iteration 29 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:12:51,491 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:12:51,491 INFO L82 PathProgramCache]: Analyzing trace with hash -410989408, now seen corresponding path program 28 times [2018-09-28 10:12:51,491 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:12:51,491 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:12:51,492 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:12:51,492 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:12:51,492 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:12:51,501 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:13:00,520 INFO L134 CoverageAnalysis]: Checked inductivity of 465 backedges. 0 proven. 463 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:13:00,521 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:13:00,521 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:13:00,530 INFO L103 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-09-28 10:13:00,552 INFO L242 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-09-28 10:13:00,552 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:13:00,555 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:13:00,581 INFO L134 CoverageAnalysis]: Checked inductivity of 465 backedges. 0 proven. 463 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:13:00,614 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:13:00,614 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32, 32] total 32 [2018-09-28 10:13:00,614 INFO L459 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-09-28 10:13:00,614 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-09-28 10:13:00,615 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=990, Unknown=3, NotChecked=0, Total=1056 [2018-09-28 10:13:00,615 INFO L87 Difference]: Start difference. First operand 41 states and 47 transitions. Second operand 33 states. [2018-09-28 10:13:06,323 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:13:06,323 INFO L93 Difference]: Finished difference Result 44 states and 50 transitions. [2018-09-28 10:13:06,324 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-09-28 10:13:06,324 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 33 [2018-09-28 10:13:06,324 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:13:06,325 INFO L225 Difference]: With dead ends: 44 [2018-09-28 10:13:06,325 INFO L226 Difference]: Without dead ends: 42 [2018-09-28 10:13:06,326 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 32 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 8.9s TimeCoverageRelationStatistics Valid=63, Invalid=990, Unknown=3, NotChecked=0, Total=1056 [2018-09-28 10:13:06,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2018-09-28 10:13:06,329 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 42. [2018-09-28 10:13:06,329 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 42 states. [2018-09-28 10:13:06,330 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 48 transitions. [2018-09-28 10:13:06,330 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 48 transitions. Word has length 33 [2018-09-28 10:13:06,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:13:06,330 INFO L480 AbstractCegarLoop]: Abstraction has 42 states and 48 transitions. [2018-09-28 10:13:06,330 INFO L481 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-09-28 10:13:06,330 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 48 transitions. [2018-09-28 10:13:06,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2018-09-28 10:13:06,331 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:13:06,331 INFO L375 BasicCegarLoop]: trace histogram [31, 1, 1, 1] [2018-09-28 10:13:06,331 INFO L423 AbstractCegarLoop]: === Iteration 30 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:13:06,331 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:13:06,331 INFO L82 PathProgramCache]: Analyzing trace with hash 144226374, now seen corresponding path program 29 times [2018-09-28 10:13:06,331 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:13:06,331 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:13:06,332 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:13:06,332 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:13:06,332 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:13:06,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:13:14,605 INFO L134 CoverageAnalysis]: Checked inductivity of 496 backedges. 0 proven. 495 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:13:14,606 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:13:14,606 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:13:14,614 INFO L103 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-09-28 10:13:14,649 INFO L242 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 17 check-sat command(s) [2018-09-28 10:13:14,649 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:13:14,651 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:13:14,669 INFO L134 CoverageAnalysis]: Checked inductivity of 496 backedges. 0 proven. 495 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:13:14,689 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:13:14,690 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33, 33] total 33 [2018-09-28 10:13:14,690 INFO L459 AbstractCegarLoop]: Interpolant automaton has 34 states [2018-09-28 10:13:14,690 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2018-09-28 10:13:14,690 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=1055, Unknown=2, NotChecked=0, Total=1122 [2018-09-28 10:13:14,691 INFO L87 Difference]: Start difference. First operand 42 states and 48 transitions. Second operand 34 states. [2018-09-28 10:13:20,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:13:20,366 INFO L93 Difference]: Finished difference Result 45 states and 51 transitions. [2018-09-28 10:13:20,366 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2018-09-28 10:13:20,367 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 34 [2018-09-28 10:13:20,367 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:13:20,367 INFO L225 Difference]: With dead ends: 45 [2018-09-28 10:13:20,367 INFO L226 Difference]: Without dead ends: 43 [2018-09-28 10:13:20,369 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 33 SyntacticMatches, 1 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=65, Invalid=1055, Unknown=2, NotChecked=0, Total=1122 [2018-09-28 10:13:20,369 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2018-09-28 10:13:20,372 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 43. [2018-09-28 10:13:20,372 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 43 states. [2018-09-28 10:13:20,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 43 states to 43 states and 49 transitions. [2018-09-28 10:13:20,372 INFO L78 Accepts]: Start accepts. Automaton has 43 states and 49 transitions. Word has length 34 [2018-09-28 10:13:20,372 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:13:20,373 INFO L480 AbstractCegarLoop]: Abstraction has 43 states and 49 transitions. [2018-09-28 10:13:20,373 INFO L481 AbstractCegarLoop]: Interpolant automaton has 34 states. [2018-09-28 10:13:20,373 INFO L276 IsEmpty]: Start isEmpty. Operand 43 states and 49 transitions. [2018-09-28 10:13:20,373 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2018-09-28 10:13:20,373 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:13:20,373 INFO L375 BasicCegarLoop]: trace histogram [33, 1, 1, 1] [2018-09-28 10:13:20,374 INFO L423 AbstractCegarLoop]: === Iteration 31 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:13:20,374 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:13:20,374 INFO L82 PathProgramCache]: Analyzing trace with hash 1162468230, now seen corresponding path program 30 times [2018-09-28 10:13:20,374 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:13:20,374 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:13:20,375 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:13:20,375 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:13:20,375 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:13:20,382 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:13:29,772 INFO L134 CoverageAnalysis]: Checked inductivity of 561 backedges. 0 proven. 560 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:13:29,772 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:13:29,772 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:13:29,782 INFO L103 rtionOrderModulation]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-09-28 10:13:29,812 INFO L242 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 18 check-sat command(s) [2018-09-28 10:13:29,812 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:13:29,814 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:13:29,831 INFO L134 CoverageAnalysis]: Checked inductivity of 561 backedges. 0 proven. 560 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:13:29,852 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:13:29,852 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35, 35] total 35 [2018-09-28 10:13:29,852 INFO L459 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-09-28 10:13:29,853 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-09-28 10:13:29,853 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=1188, Unknown=3, NotChecked=0, Total=1260 [2018-09-28 10:13:29,853 INFO L87 Difference]: Start difference. First operand 43 states and 49 transitions. Second operand 36 states. [2018-09-28 10:13:48,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:13:48,614 INFO L93 Difference]: Finished difference Result 47 states and 53 transitions. [2018-09-28 10:13:48,615 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-09-28 10:13:48,615 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 36 [2018-09-28 10:13:48,615 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:13:48,616 INFO L225 Difference]: With dead ends: 47 [2018-09-28 10:13:48,616 INFO L226 Difference]: Without dead ends: 45 [2018-09-28 10:13:48,617 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 35 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 9.3s TimeCoverageRelationStatistics Valid=69, Invalid=1188, Unknown=3, NotChecked=0, Total=1260 [2018-09-28 10:13:48,617 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2018-09-28 10:13:48,620 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2018-09-28 10:13:48,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 45 states. [2018-09-28 10:13:48,621 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 51 transitions. [2018-09-28 10:13:48,621 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 51 transitions. Word has length 36 [2018-09-28 10:13:48,621 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:13:48,621 INFO L480 AbstractCegarLoop]: Abstraction has 45 states and 51 transitions. [2018-09-28 10:13:48,621 INFO L481 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-09-28 10:13:48,621 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 51 transitions. [2018-09-28 10:13:48,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2018-09-28 10:13:48,622 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:13:48,622 INFO L375 BasicCegarLoop]: trace histogram [34, 1, 1, 1] [2018-09-28 10:13:48,622 INFO L423 AbstractCegarLoop]: === Iteration 32 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:13:48,622 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:13:48,622 INFO L82 PathProgramCache]: Analyzing trace with hash 1676772896, now seen corresponding path program 31 times [2018-09-28 10:13:48,622 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:13:48,622 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:13:48,623 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:13:48,623 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:13:48,623 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:13:48,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:13:59,843 INFO L134 CoverageAnalysis]: Checked inductivity of 595 backedges. 0 proven. 593 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:13:59,844 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:13:59,844 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:13:59,852 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:13:59,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:13:59,877 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:13:59,903 INFO L134 CoverageAnalysis]: Checked inductivity of 595 backedges. 0 proven. 593 refuted. 2 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:13:59,928 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:13:59,929 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [36, 36] total 36 [2018-09-28 10:13:59,929 INFO L459 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-09-28 10:13:59,929 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-09-28 10:13:59,930 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=1257, Unknown=4, NotChecked=0, Total=1332 [2018-09-28 10:13:59,930 INFO L87 Difference]: Start difference. First operand 45 states and 51 transitions. Second operand 37 states. [2018-09-28 10:14:13,951 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:14:13,951 INFO L93 Difference]: Finished difference Result 48 states and 54 transitions. [2018-09-28 10:14:13,952 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-09-28 10:14:13,952 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 37 [2018-09-28 10:14:13,952 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:14:13,953 INFO L225 Difference]: With dead ends: 48 [2018-09-28 10:14:13,953 INFO L226 Difference]: Without dead ends: 46 [2018-09-28 10:14:13,954 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 36 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 11.1s TimeCoverageRelationStatistics Valid=71, Invalid=1257, Unknown=4, NotChecked=0, Total=1332 [2018-09-28 10:14:13,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2018-09-28 10:14:13,958 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2018-09-28 10:14:13,958 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-09-28 10:14:13,958 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 52 transitions. [2018-09-28 10:14:13,959 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 52 transitions. Word has length 37 [2018-09-28 10:14:13,959 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:14:13,959 INFO L480 AbstractCegarLoop]: Abstraction has 46 states and 52 transitions. [2018-09-28 10:14:13,959 INFO L481 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-09-28 10:14:13,959 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 52 transitions. [2018-09-28 10:14:13,959 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2018-09-28 10:14:13,960 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:14:13,960 INFO L375 BasicCegarLoop]: trace histogram [35, 1, 1, 1] [2018-09-28 10:14:13,960 INFO L423 AbstractCegarLoop]: === Iteration 33 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:14:13,960 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:14:13,960 INFO L82 PathProgramCache]: Analyzing trace with hash 440348358, now seen corresponding path program 32 times [2018-09-28 10:14:13,960 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:14:13,961 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:14:13,961 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:14:13,961 INFO L103 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-09-28 10:14:13,961 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:14:13,970 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:14:29,116 INFO L134 CoverageAnalysis]: Checked inductivity of 630 backedges. 0 proven. 629 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:14:29,117 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:14:29,117 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:14:29,124 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-09-28 10:14:29,145 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-09-28 10:14:29,146 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:14:29,148 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:14:29,160 INFO L134 CoverageAnalysis]: Checked inductivity of 630 backedges. 0 proven. 629 refuted. 1 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:14:29,181 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:14:29,181 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37, 37] total 37 [2018-09-28 10:14:29,182 INFO L459 AbstractCegarLoop]: Interpolant automaton has 38 states [2018-09-28 10:14:29,182 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2018-09-28 10:14:29,182 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=1328, Unknown=5, NotChecked=0, Total=1406 [2018-09-28 10:14:29,183 INFO L87 Difference]: Start difference. First operand 46 states and 52 transitions. Second operand 38 states. [2018-09-28 10:14:35,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:14:35,087 INFO L93 Difference]: Finished difference Result 49 states and 55 transitions. [2018-09-28 10:14:35,088 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2018-09-28 10:14:35,088 INFO L78 Accepts]: Start accepts. Automaton has 38 states. Word has length 38 [2018-09-28 10:14:35,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:14:35,089 INFO L225 Difference]: With dead ends: 49 [2018-09-28 10:14:35,089 INFO L226 Difference]: Without dead ends: 47 [2018-09-28 10:14:35,090 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 37 SyntacticMatches, 1 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 15.1s TimeCoverageRelationStatistics Valid=73, Invalid=1328, Unknown=5, NotChecked=0, Total=1406 [2018-09-28 10:14:35,090 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2018-09-28 10:14:35,093 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 47. [2018-09-28 10:14:35,093 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 47 states. [2018-09-28 10:14:35,094 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 53 transitions. [2018-09-28 10:14:35,094 INFO L78 Accepts]: Start accepts. Automaton has 47 states and 53 transitions. Word has length 38 [2018-09-28 10:14:35,094 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:14:35,094 INFO L480 AbstractCegarLoop]: Abstraction has 47 states and 53 transitions. [2018-09-28 10:14:35,094 INFO L481 AbstractCegarLoop]: Interpolant automaton has 38 states. [2018-09-28 10:14:35,094 INFO L276 IsEmpty]: Start isEmpty. Operand 47 states and 53 transitions. [2018-09-28 10:14:35,095 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-09-28 10:14:35,095 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:14:35,095 INFO L375 BasicCegarLoop]: trace histogram [36, 1, 1, 1] [2018-09-28 10:14:35,095 INFO L423 AbstractCegarLoop]: === Iteration 34 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:14:35,095 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:14:35,095 INFO L82 PathProgramCache]: Analyzing trace with hash 765893344, now seen corresponding path program 33 times [2018-09-28 10:14:35,095 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:14:35,095 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:14:35,096 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:14:35,096 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:14:35,096 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:14:35,104 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-28 10:14:57,589 INFO L134 CoverageAnalysis]: Checked inductivity of 666 backedges. 0 proven. 661 refuted. 5 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:14:57,589 INFO L301 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-09-28 10:14:57,589 INFO L227 ckRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-09-28 10:14:57,596 INFO L103 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-09-28 10:14:57,629 INFO L242 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 19 check-sat command(s) [2018-09-28 10:14:57,629 INFO L243 tOrderPrioritization]: Conjunction of SSA is unsat [2018-09-28 10:14:57,631 INFO L273 TraceCheckSpWp]: Computing forward predicates... [2018-09-28 10:14:57,645 INFO L134 CoverageAnalysis]: Checked inductivity of 666 backedges. 0 proven. 661 refuted. 5 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-28 10:14:57,666 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-09-28 10:14:57,666 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [38, 38] total 38 [2018-09-28 10:14:57,666 INFO L459 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-09-28 10:14:57,667 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-09-28 10:14:57,667 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=1398, Unknown=9, NotChecked=0, Total=1482 [2018-09-28 10:14:57,667 INFO L87 Difference]: Start difference. First operand 47 states and 53 transitions. Second operand 39 states. [2018-09-28 10:15:14,057 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-28 10:15:14,057 INFO L93 Difference]: Finished difference Result 50 states and 56 transitions. [2018-09-28 10:15:14,058 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-09-28 10:15:14,058 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 39 [2018-09-28 10:15:14,058 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-28 10:15:14,058 INFO L225 Difference]: With dead ends: 50 [2018-09-28 10:15:14,059 INFO L226 Difference]: Without dead ends: 48 [2018-09-28 10:15:14,060 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 38 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 22.4s TimeCoverageRelationStatistics Valid=75, Invalid=1398, Unknown=9, NotChecked=0, Total=1482 [2018-09-28 10:15:14,060 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2018-09-28 10:15:14,064 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 48. [2018-09-28 10:15:14,064 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 48 states. [2018-09-28 10:15:14,065 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 48 states to 48 states and 54 transitions. [2018-09-28 10:15:14,065 INFO L78 Accepts]: Start accepts. Automaton has 48 states and 54 transitions. Word has length 39 [2018-09-28 10:15:14,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-28 10:15:14,065 INFO L480 AbstractCegarLoop]: Abstraction has 48 states and 54 transitions. [2018-09-28 10:15:14,065 INFO L481 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-09-28 10:15:14,065 INFO L276 IsEmpty]: Start isEmpty. Operand 48 states and 54 transitions. [2018-09-28 10:15:14,066 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-09-28 10:15:14,066 INFO L367 BasicCegarLoop]: Found error trace [2018-09-28 10:15:14,066 INFO L375 BasicCegarLoop]: trace histogram [37, 1, 1, 1] [2018-09-28 10:15:14,066 INFO L423 AbstractCegarLoop]: === Iteration 35 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-28 10:15:14,066 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-28 10:15:14,067 INFO L82 PathProgramCache]: Analyzing trace with hash -2027113978, now seen corresponding path program 34 times [2018-09-28 10:15:14,067 INFO L227 ckRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-09-28 10:15:14,067 INFO L69 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-09-28 10:15:14,067 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:15:14,067 INFO L101 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-09-28 10:15:14,068 INFO L119 rtionOrderModulation]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-09-28 10:15:14,076 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat Received shutdown request... [2018-09-28 10:15:19,557 WARN L549 AbstractCegarLoop]: Verification canceled [2018-09-28 10:15:19,561 WARN L206 ceAbstractionStarter]: Timeout [2018-09-28 10:15:19,562 INFO L202 PluginConnector]: Adding new model AnnoyingVillain.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 28.09 10:15:19 BoogieIcfgContainer [2018-09-28 10:15:19,562 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-09-28 10:15:19,563 INFO L168 Benchmark]: Toolchain (without parser) took 280069.16 ms. Allocated memory was 1.5 GB in the beginning and 1.7 GB in the end (delta: 134.2 MB). Free memory was 1.5 GB in the beginning and 1.5 GB in the end (delta: 10.1 MB). Peak memory consumption was 144.3 MB. Max. memory is 7.1 GB. [2018-09-28 10:15:19,565 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.20 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-09-28 10:15:19,565 INFO L168 Benchmark]: Boogie Procedure Inliner took 42.74 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-09-28 10:15:19,565 INFO L168 Benchmark]: Boogie Preprocessor took 22.76 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-09-28 10:15:19,566 INFO L168 Benchmark]: RCFGBuilder took 257.33 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 21.1 MB). Peak memory consumption was 21.1 MB. Max. memory is 7.1 GB. [2018-09-28 10:15:19,567 INFO L168 Benchmark]: TraceAbstraction took 279740.10 ms. Allocated memory was 1.5 GB in the beginning and 1.7 GB in the end (delta: 134.2 MB). Free memory was 1.4 GB in the beginning and 1.5 GB in the end (delta: -11.1 MB). Peak memory consumption was 123.2 MB. Max. memory is 7.1 GB. [2018-09-28 10:15:19,570 INFO L336 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Boogie PL CUP Parser took 0.20 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. * Boogie Procedure Inliner took 42.74 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. * Boogie Preprocessor took 22.76 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. * RCFGBuilder took 257.33 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 21.1 MB). Peak memory consumption was 21.1 MB. Max. memory is 7.1 GB. * TraceAbstraction took 279740.10 ms. Allocated memory was 1.5 GB in the beginning and 1.7 GB in the end (delta: 134.2 MB). Free memory was 1.4 GB in the beginning and 1.5 GB in the end (delta: -11.1 MB). Peak memory consumption was 123.2 MB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 24]: Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 24). Cancelled while BasicCegarLoop was analyzing trace of length 41 with TraceHistMax 37, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateComparison was comparing new predicate (quantifier-free) to 34 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 6 locations, 1 error locations. TIMEOUT Result, 279.6s OverallTime, 35 OverallIterations, 37 TraceHistogramMax, 140.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 110 SDtfs, 56 SDslu, 645 SDs, 0 SdLazy, 16986 SolverSat, 41 SolverUnsat, 55 SolverUnknown, 0 SolverNotchecked, 135.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1337 GetRequests, 653 SyntacticMatches, 32 SemanticMatches, 652 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 130.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=48occurred in iteration=34, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 34 MinimizatonAttempts, 13 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 131.3s InterpolantComputationTime, 1389 NumberOfCodeBlocks, 1389 NumberOfCodeBlocksAsserted, 233 NumberOfCheckSat, 1322 ConstructedInterpolants, 0 QuantifiedInterpolants, 352104 SizeOfPredicates, 32 NumberOfNonLiveVariables, 2673 ConjunctsInSsa, 1254 ConjunctsInUnsatCore, 67 InterpolantComputations, 1 PerfectInterpolantSequences, 1/14944 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/AnnoyingVillain.bpl_svcomp-Reach-32bit-Automizer_Default.epf_AutomizerBplInline.xml/Csv-Benchmark-0-2018-09-28_10-15-19-580.csv Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/AnnoyingVillain.bpl_svcomp-Reach-32bit-Automizer_Default.epf_AutomizerBplInline.xml/Csv-TraceAbstractionBenchmarks-0-2018-09-28_10-15-19-580.csv Completed graceful shutdown