java -Xmx8000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml --generate-csv --csv-dir csv -s ../../../trunk/examples/settings/Pdr/AutomizerBpl-nestedInterpolants.epf -i ../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/ArrayInit01.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-e6fd87c [2018-07-25 13:29:39,593 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-07-25 13:29:39,595 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-07-25 13:29:39,607 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-07-25 13:29:39,608 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-07-25 13:29:39,609 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-07-25 13:29:39,610 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-07-25 13:29:39,612 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-07-25 13:29:39,613 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-07-25 13:29:39,614 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-07-25 13:29:39,615 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-07-25 13:29:39,615 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-07-25 13:29:39,616 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-07-25 13:29:39,617 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-07-25 13:29:39,619 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-07-25 13:29:39,619 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-07-25 13:29:39,620 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-07-25 13:29:39,622 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-07-25 13:29:39,624 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-07-25 13:29:39,626 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-07-25 13:29:39,627 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-07-25 13:29:39,628 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-07-25 13:29:39,630 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-07-25 13:29:39,631 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-07-25 13:29:39,631 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-07-25 13:29:39,632 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-07-25 13:29:39,633 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-07-25 13:29:39,634 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-07-25 13:29:39,635 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-07-25 13:29:39,636 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-07-25 13:29:39,636 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-07-25 13:29:39,637 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-07-25 13:29:39,637 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-07-25 13:29:39,637 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-07-25 13:29:39,638 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-07-25 13:29:39,639 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-07-25 13:29:39,639 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/Pdr/AutomizerBpl-nestedInterpolants.epf [2018-07-25 13:29:39,647 INFO L110 SettingsManager]: Loading preferences was successful [2018-07-25 13:29:39,648 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-07-25 13:29:39,649 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-07-25 13:29:39,649 INFO L133 SettingsManager]: * SMT solver=Internal_SMTInterpol [2018-07-25 13:29:39,649 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-07-25 13:29:39,649 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2018-07-25 13:29:39,650 INFO L133 SettingsManager]: * Use separate solver for trace checks=false [2018-07-25 13:29:39,650 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-07-25 13:29:39,694 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-07-25 13:29:39,707 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-07-25 13:29:39,711 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-07-25 13:29:39,712 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-07-25 13:29:39,713 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-07-25 13:29:39,713 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/ArrayInit01.bpl [2018-07-25 13:29:39,713 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/ArrayInit01.bpl' [2018-07-25 13:29:39,754 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-07-25 13:29:39,755 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-07-25 13:29:39,756 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-07-25 13:29:39,756 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-07-25 13:29:39,756 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-07-25 13:29:39,775 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,789 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,795 WARN L165 Inliner]: Program contained no entry procedure! [2018-07-25 13:29:39,795 WARN L168 Inliner]: Missing entry procedures: [ULTIMATE.start] [2018-07-25 13:29:39,795 WARN L175 Inliner]: Fallback enabled. All procedures will be processed. [2018-07-25 13:29:39,797 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-07-25 13:29:39,798 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-07-25 13:29:39,798 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-07-25 13:29:39,798 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-07-25 13:29:39,809 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,809 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,810 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,810 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,812 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,817 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,818 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,820 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-07-25 13:29:39,820 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-07-25 13:29:39,820 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-07-25 13:29:39,821 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-07-25 13:29:39,821 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/1) ... [2018-07-25 13:29:39,902 INFO L124 BoogieDeclarations]: Specification and implementation of procedure main given in one single declaration [2018-07-25 13:29:39,902 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-07-25 13:29:39,902 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-07-25 13:29:40,031 INFO L270 CfgBuilder]: Using library mode [2018-07-25 13:29:40,031 INFO L202 PluginConnector]: Adding new model ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.07 01:29:40 BoogieIcfgContainer [2018-07-25 13:29:40,032 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-07-25 13:29:40,033 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-07-25 13:29:40,033 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-07-25 13:29:40,037 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-07-25 13:29:40,037 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 01:29:39" (1/2) ... [2018-07-25 13:29:40,039 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3641c5b8 and model type ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.07 01:29:40, skipping insertion in model container [2018-07-25 13:29:40,039 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.07 01:29:40" (2/2) ... [2018-07-25 13:29:40,041 INFO L112 eAbstractionObserver]: Analyzing ICFG ArrayInit01.bpl [2018-07-25 13:29:40,052 INFO L133 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2018-07-25 13:29:40,060 INFO L145 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-07-25 13:29:40,111 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-07-25 13:29:40,112 INFO L374 AbstractCegarLoop]: Interprodecural is true [2018-07-25 13:29:40,112 INFO L375 AbstractCegarLoop]: Hoare is true [2018-07-25 13:29:40,112 INFO L376 AbstractCegarLoop]: Compute interpolants for Craig_NestedInterpolation [2018-07-25 13:29:40,112 INFO L377 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-07-25 13:29:40,113 INFO L378 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-07-25 13:29:40,113 INFO L379 AbstractCegarLoop]: Difference is false [2018-07-25 13:29:40,113 INFO L380 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-07-25 13:29:40,113 INFO L385 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-07-25 13:29:40,128 INFO L276 IsEmpty]: Start isEmpty. Operand 5 states. [2018-07-25 13:29:40,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-07-25 13:29:40,136 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:40,138 INFO L354 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-07-25 13:29:40,139 INFO L415 AbstractCegarLoop]: === Iteration 1 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:40,145 INFO L82 PathProgramCache]: Analyzing trace with hash 29984, now seen corresponding path program 1 times [2018-07-25 13:29:40,151 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:40,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:40,231 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:40,235 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-25 13:29:40,236 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-07-25 13:29:40,241 INFO L451 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-07-25 13:29:40,258 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-07-25 13:29:40,258 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-07-25 13:29:40,261 INFO L87 Difference]: Start difference. First operand 5 states. Second operand 3 states. [2018-07-25 13:29:40,289 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:40,289 INFO L93 Difference]: Finished difference Result 9 states and 9 transitions. [2018-07-25 13:29:40,290 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-07-25 13:29:40,292 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2018-07-25 13:29:40,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:40,303 INFO L225 Difference]: With dead ends: 9 [2018-07-25 13:29:40,303 INFO L226 Difference]: Without dead ends: 5 [2018-07-25 13:29:40,307 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 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-07-25 13:29:40,329 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5 states. [2018-07-25 13:29:40,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5 to 5. [2018-07-25 13:29:40,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2018-07-25 13:29:40,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 5 transitions. [2018-07-25 13:29:40,351 INFO L78 Accepts]: Start accepts. Automaton has 5 states and 5 transitions. Word has length 3 [2018-07-25 13:29:40,351 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:40,352 INFO L472 AbstractCegarLoop]: Abstraction has 5 states and 5 transitions. [2018-07-25 13:29:40,352 INFO L473 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-07-25 13:29:40,352 INFO L276 IsEmpty]: Start isEmpty. Operand 5 states and 5 transitions. [2018-07-25 13:29:40,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2018-07-25 13:29:40,352 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:40,353 INFO L354 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2018-07-25 13:29:40,353 INFO L415 AbstractCegarLoop]: === Iteration 2 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:40,354 INFO L82 PathProgramCache]: Analyzing trace with hash 927558, now seen corresponding path program 1 times [2018-07-25 13:29:40,354 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:40,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:40,490 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:40,493 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:40,493 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [3] total 3 [2018-07-25 13:29:40,495 INFO L451 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-07-25 13:29:40,495 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-07-25 13:29:40,495 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-07-25 13:29:40,496 INFO L87 Difference]: Start difference. First operand 5 states and 5 transitions. Second operand 5 states. [2018-07-25 13:29:40,555 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:40,555 INFO L93 Difference]: Finished difference Result 8 states and 8 transitions. [2018-07-25 13:29:40,555 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-07-25 13:29:40,556 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 4 [2018-07-25 13:29:40,556 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:40,556 INFO L225 Difference]: With dead ends: 8 [2018-07-25 13:29:40,556 INFO L226 Difference]: Without dead ends: 6 [2018-07-25 13:29:40,558 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-07-25 13:29:40,558 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6 states. [2018-07-25 13:29:40,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6 to 6. [2018-07-25 13:29:40,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2018-07-25 13:29:40,560 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 6 transitions. [2018-07-25 13:29:40,561 INFO L78 Accepts]: Start accepts. Automaton has 6 states and 6 transitions. Word has length 4 [2018-07-25 13:29:40,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:40,561 INFO L472 AbstractCegarLoop]: Abstraction has 6 states and 6 transitions. [2018-07-25 13:29:40,561 INFO L473 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-07-25 13:29:40,562 INFO L276 IsEmpty]: Start isEmpty. Operand 6 states and 6 transitions. [2018-07-25 13:29:40,563 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2018-07-25 13:29:40,563 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:40,563 INFO L354 BasicCegarLoop]: trace histogram [2, 1, 1, 1] [2018-07-25 13:29:40,563 INFO L415 AbstractCegarLoop]: === Iteration 3 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:40,564 INFO L82 PathProgramCache]: Analyzing trace with hash 28752352, now seen corresponding path program 2 times [2018-07-25 13:29:40,564 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:40,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:40,679 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:40,679 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:40,680 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4] total 4 [2018-07-25 13:29:40,680 INFO L451 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-07-25 13:29:40,680 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-07-25 13:29:40,681 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-07-25 13:29:40,681 INFO L87 Difference]: Start difference. First operand 6 states and 6 transitions. Second operand 6 states. [2018-07-25 13:29:40,721 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:40,722 INFO L93 Difference]: Finished difference Result 9 states and 9 transitions. [2018-07-25 13:29:40,722 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-07-25 13:29:40,722 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 5 [2018-07-25 13:29:40,723 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:40,723 INFO L225 Difference]: With dead ends: 9 [2018-07-25 13:29:40,723 INFO L226 Difference]: Without dead ends: 7 [2018-07-25 13:29:40,724 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-07-25 13:29:40,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7 states. [2018-07-25 13:29:40,726 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-07-25 13:29:40,727 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-07-25 13:29:40,727 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-07-25 13:29:40,727 INFO L78 Accepts]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 5 [2018-07-25 13:29:40,728 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:40,728 INFO L472 AbstractCegarLoop]: Abstraction has 7 states and 7 transitions. [2018-07-25 13:29:40,728 INFO L473 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-07-25 13:29:40,728 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states and 7 transitions. [2018-07-25 13:29:40,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2018-07-25 13:29:40,729 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:40,729 INFO L354 BasicCegarLoop]: trace histogram [3, 1, 1, 1] [2018-07-25 13:29:40,729 INFO L415 AbstractCegarLoop]: === Iteration 4 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:40,729 INFO L82 PathProgramCache]: Analyzing trace with hash 891320966, now seen corresponding path program 3 times [2018-07-25 13:29:40,730 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:40,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:40,942 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:40,942 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:40,942 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5] total 5 [2018-07-25 13:29:40,943 INFO L451 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-07-25 13:29:40,943 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-07-25 13:29:40,945 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-07-25 13:29:40,946 INFO L87 Difference]: Start difference. First operand 7 states and 7 transitions. Second operand 7 states. [2018-07-25 13:29:41,008 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:41,008 INFO L93 Difference]: Finished difference Result 10 states and 10 transitions. [2018-07-25 13:29:41,008 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-07-25 13:29:41,008 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 6 [2018-07-25 13:29:41,009 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:41,009 INFO L225 Difference]: With dead ends: 10 [2018-07-25 13:29:41,012 INFO L226 Difference]: Without dead ends: 8 [2018-07-25 13:29:41,013 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-07-25 13:29:41,013 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8 states. [2018-07-25 13:29:41,019 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-07-25 13:29:41,019 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 8 states. [2018-07-25 13:29:41,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 8 transitions. [2018-07-25 13:29:41,020 INFO L78 Accepts]: Start accepts. Automaton has 8 states and 8 transitions. Word has length 6 [2018-07-25 13:29:41,020 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:41,020 INFO L472 AbstractCegarLoop]: Abstraction has 8 states and 8 transitions. [2018-07-25 13:29:41,021 INFO L473 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-07-25 13:29:41,021 INFO L276 IsEmpty]: Start isEmpty. Operand 8 states and 8 transitions. [2018-07-25 13:29:41,021 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2018-07-25 13:29:41,021 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:41,021 INFO L354 BasicCegarLoop]: trace histogram [4, 1, 1, 1] [2018-07-25 13:29:41,022 INFO L415 AbstractCegarLoop]: === Iteration 5 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:41,022 INFO L82 PathProgramCache]: Analyzing trace with hash 1861144224, now seen corresponding path program 4 times [2018-07-25 13:29:41,022 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:41,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:41,321 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:41,324 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:41,325 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2018-07-25 13:29:41,325 INFO L451 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-07-25 13:29:41,325 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-07-25 13:29:41,326 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-07-25 13:29:41,326 INFO L87 Difference]: Start difference. First operand 8 states and 8 transitions. Second operand 8 states. [2018-07-25 13:29:41,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:41,431 INFO L93 Difference]: Finished difference Result 11 states and 11 transitions. [2018-07-25 13:29:41,431 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-07-25 13:29:41,432 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 7 [2018-07-25 13:29:41,432 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:41,432 INFO L225 Difference]: With dead ends: 11 [2018-07-25 13:29:41,433 INFO L226 Difference]: Without dead ends: 9 [2018-07-25 13:29:41,434 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-07-25 13:29:41,434 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 9 states. [2018-07-25 13:29:41,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-07-25 13:29:41,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2018-07-25 13:29:41,442 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-07-25 13:29:41,442 INFO L78 Accepts]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-07-25 13:29:41,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:41,443 INFO L472 AbstractCegarLoop]: Abstraction has 9 states and 9 transitions. [2018-07-25 13:29:41,443 INFO L473 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-07-25 13:29:41,443 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states and 9 transitions. [2018-07-25 13:29:41,444 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2018-07-25 13:29:41,444 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:41,444 INFO L354 BasicCegarLoop]: trace histogram [5, 1, 1, 1] [2018-07-25 13:29:41,444 INFO L415 AbstractCegarLoop]: === Iteration 6 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:41,445 INFO L82 PathProgramCache]: Analyzing trace with hash 1860894150, now seen corresponding path program 5 times [2018-07-25 13:29:41,445 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:41,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:41,678 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:41,679 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:41,679 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2018-07-25 13:29:41,680 INFO L451 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-07-25 13:29:41,680 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-07-25 13:29:41,680 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-07-25 13:29:41,681 INFO L87 Difference]: Start difference. First operand 9 states and 9 transitions. Second operand 9 states. [2018-07-25 13:29:41,727 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:41,727 INFO L93 Difference]: Finished difference Result 12 states and 12 transitions. [2018-07-25 13:29:41,727 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-07-25 13:29:41,727 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 8 [2018-07-25 13:29:41,728 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:41,728 INFO L225 Difference]: With dead ends: 12 [2018-07-25 13:29:41,729 INFO L226 Difference]: Without dead ends: 10 [2018-07-25 13:29:41,729 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-07-25 13:29:41,730 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10 states. [2018-07-25 13:29:41,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-07-25 13:29:41,733 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2018-07-25 13:29:41,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-07-25 13:29:41,734 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-07-25 13:29:41,735 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:41,736 INFO L472 AbstractCegarLoop]: Abstraction has 10 states and 10 transitions. [2018-07-25 13:29:41,736 INFO L473 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-07-25 13:29:41,736 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 10 transitions. [2018-07-25 13:29:41,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-07-25 13:29:41,737 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:41,737 INFO L354 BasicCegarLoop]: trace histogram [6, 1, 1, 1] [2018-07-25 13:29:41,737 INFO L415 AbstractCegarLoop]: === Iteration 7 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:41,738 INFO L82 PathProgramCache]: Analyzing trace with hash 1853141856, now seen corresponding path program 6 times [2018-07-25 13:29:41,738 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:41,751 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:42,101 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:42,102 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:42,102 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2018-07-25 13:29:42,103 INFO L451 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-07-25 13:29:42,103 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-07-25 13:29:42,104 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-07-25 13:29:42,104 INFO L87 Difference]: Start difference. First operand 10 states and 10 transitions. Second operand 10 states. [2018-07-25 13:29:42,183 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:42,184 INFO L93 Difference]: Finished difference Result 13 states and 13 transitions. [2018-07-25 13:29:42,185 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-07-25 13:29:42,185 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 9 [2018-07-25 13:29:42,186 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:42,186 INFO L225 Difference]: With dead ends: 13 [2018-07-25 13:29:42,186 INFO L226 Difference]: Without dead ends: 11 [2018-07-25 13:29:42,187 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-07-25 13:29:42,187 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2018-07-25 13:29:42,192 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-07-25 13:29:42,192 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2018-07-25 13:29:42,193 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-07-25 13:29:42,193 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-07-25 13:29:42,193 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:42,194 INFO L472 AbstractCegarLoop]: Abstraction has 11 states and 11 transitions. [2018-07-25 13:29:42,194 INFO L473 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-07-25 13:29:42,194 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 11 transitions. [2018-07-25 13:29:42,195 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-07-25 13:29:42,195 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:42,195 INFO L354 BasicCegarLoop]: trace histogram [7, 1, 1, 1] [2018-07-25 13:29:42,196 INFO L415 AbstractCegarLoop]: === Iteration 8 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:42,196 INFO L82 PathProgramCache]: Analyzing trace with hash 1612820742, now seen corresponding path program 7 times [2018-07-25 13:29:42,196 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:42,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:42,783 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:42,788 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:42,788 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-07-25 13:29:42,788 INFO L451 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-07-25 13:29:42,789 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-07-25 13:29:42,789 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-07-25 13:29:42,789 INFO L87 Difference]: Start difference. First operand 11 states and 11 transitions. Second operand 11 states. [2018-07-25 13:29:42,929 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:42,929 INFO L93 Difference]: Finished difference Result 14 states and 14 transitions. [2018-07-25 13:29:42,930 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-07-25 13:29:42,930 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 10 [2018-07-25 13:29:42,930 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:42,931 INFO L225 Difference]: With dead ends: 14 [2018-07-25 13:29:42,931 INFO L226 Difference]: Without dead ends: 12 [2018-07-25 13:29:42,932 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=55, Invalid=155, Unknown=0, NotChecked=0, Total=210 [2018-07-25 13:29:42,933 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2018-07-25 13:29:42,941 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-07-25 13:29:42,941 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 12 states. [2018-07-25 13:29:42,942 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-07-25 13:29:42,942 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-07-25 13:29:42,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:42,942 INFO L472 AbstractCegarLoop]: Abstraction has 12 states and 12 transitions. [2018-07-25 13:29:42,943 INFO L473 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-07-25 13:29:42,943 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 12 transitions. [2018-07-25 13:29:42,943 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-07-25 13:29:42,943 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:42,944 INFO L354 BasicCegarLoop]: trace histogram [8, 1, 1, 1] [2018-07-25 13:29:42,944 INFO L415 AbstractCegarLoop]: === Iteration 9 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:42,946 INFO L82 PathProgramCache]: Analyzing trace with hash -1542166496, now seen corresponding path program 8 times [2018-07-25 13:29:42,947 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:42,973 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:43,500 WARN L169 SmtUtils]: Spent 144.00 ms on a formula simplification. DAG size of input: 147 DAG size of output: 44 [2018-07-25 13:29:43,731 WARN L169 SmtUtils]: Spent 166.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 57 [2018-07-25 13:29:43,746 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:43,747 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:43,747 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2018-07-25 13:29:43,747 INFO L451 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-07-25 13:29:43,748 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-07-25 13:29:43,748 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-07-25 13:29:43,749 INFO L87 Difference]: Start difference. First operand 12 states and 12 transitions. Second operand 12 states. [2018-07-25 13:29:43,849 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:43,849 INFO L93 Difference]: Finished difference Result 15 states and 15 transitions. [2018-07-25 13:29:43,849 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-07-25 13:29:43,850 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 11 [2018-07-25 13:29:43,850 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:43,850 INFO L225 Difference]: With dead ends: 15 [2018-07-25 13:29:43,851 INFO L226 Difference]: Without dead ends: 13 [2018-07-25 13:29:43,851 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2018-07-25 13:29:43,851 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2018-07-25 13:29:43,857 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-07-25 13:29:43,857 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13 states. [2018-07-25 13:29:43,858 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-07-25 13:29:43,858 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-07-25 13:29:43,858 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:43,858 INFO L472 AbstractCegarLoop]: Abstraction has 13 states and 13 transitions. [2018-07-25 13:29:43,859 INFO L473 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-07-25 13:29:43,859 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 13 transitions. [2018-07-25 13:29:43,859 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-07-25 13:29:43,859 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:43,860 INFO L354 BasicCegarLoop]: trace histogram [9, 1, 1, 1] [2018-07-25 13:29:43,860 INFO L415 AbstractCegarLoop]: === Iteration 10 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:43,864 INFO L82 PathProgramCache]: Analyzing trace with hash -562523066, now seen corresponding path program 9 times [2018-07-25 13:29:43,864 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:43,893 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:44,299 WARN L169 SmtUtils]: Spent 127.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 31 [2018-07-25 13:29:44,466 WARN L169 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 34 [2018-07-25 13:29:44,721 WARN L169 SmtUtils]: Spent 190.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 52 [2018-07-25 13:29:45,041 WARN L169 SmtUtils]: Spent 234.00 ms on a formula simplification. DAG size of input: 212 DAG size of output: 59 [2018-07-25 13:29:45,057 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:45,057 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:45,057 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2018-07-25 13:29:45,058 INFO L451 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-07-25 13:29:45,059 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-07-25 13:29:45,059 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2018-07-25 13:29:45,061 INFO L87 Difference]: Start difference. First operand 13 states and 13 transitions. Second operand 13 states. [2018-07-25 13:29:45,176 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:45,176 INFO L93 Difference]: Finished difference Result 16 states and 16 transitions. [2018-07-25 13:29:45,177 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-07-25 13:29:45,177 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 12 [2018-07-25 13:29:45,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:45,178 INFO L225 Difference]: With dead ends: 16 [2018-07-25 13:29:45,178 INFO L226 Difference]: Without dead ends: 14 [2018-07-25 13:29:45,178 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-07-25 13:29:45,179 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2018-07-25 13:29:45,184 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-07-25 13:29:45,184 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2018-07-25 13:29:45,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-07-25 13:29:45,185 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-07-25 13:29:45,185 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:45,185 INFO L472 AbstractCegarLoop]: Abstraction has 14 states and 14 transitions. [2018-07-25 13:29:45,185 INFO L473 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-07-25 13:29:45,185 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 14 transitions. [2018-07-25 13:29:45,186 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-07-25 13:29:45,186 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:45,186 INFO L354 BasicCegarLoop]: trace histogram [10, 1, 1, 1] [2018-07-25 13:29:45,186 INFO L415 AbstractCegarLoop]: === Iteration 11 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:45,186 INFO L82 PathProgramCache]: Analyzing trace with hash -258347808, now seen corresponding path program 10 times [2018-07-25 13:29:45,187 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:45,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:45,859 WARN L169 SmtUtils]: Spent 139.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 61 [2018-07-25 13:29:46,215 WARN L169 SmtUtils]: Spent 261.00 ms on a formula simplification. DAG size of input: 327 DAG size of output: 56 [2018-07-25 13:29:46,493 WARN L169 SmtUtils]: Spent 169.00 ms on a formula simplification. DAG size of input: 440 DAG size of output: 80 [2018-07-25 13:29:46,511 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:46,511 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:46,512 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-07-25 13:29:46,512 INFO L451 AbstractCegarLoop]: Interpolant automaton has 14 states [2018-07-25 13:29:46,513 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2018-07-25 13:29:46,513 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2018-07-25 13:29:46,514 INFO L87 Difference]: Start difference. First operand 14 states and 14 transitions. Second operand 14 states. [2018-07-25 13:29:46,844 WARN L169 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 76 [2018-07-25 13:29:46,941 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:46,942 INFO L93 Difference]: Finished difference Result 17 states and 17 transitions. [2018-07-25 13:29:46,942 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-07-25 13:29:46,942 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 13 [2018-07-25 13:29:46,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:46,943 INFO L225 Difference]: With dead ends: 17 [2018-07-25 13:29:46,943 INFO L226 Difference]: Without dead ends: 15 [2018-07-25 13:29:46,944 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=102, Invalid=240, Unknown=0, NotChecked=0, Total=342 [2018-07-25 13:29:46,944 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2018-07-25 13:29:46,951 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-07-25 13:29:46,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2018-07-25 13:29:46,952 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-07-25 13:29:46,953 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-07-25 13:29:46,953 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:46,953 INFO L472 AbstractCegarLoop]: Abstraction has 15 states and 15 transitions. [2018-07-25 13:29:46,953 INFO L473 AbstractCegarLoop]: Interpolant automaton has 14 states. [2018-07-25 13:29:46,953 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 15 transitions. [2018-07-25 13:29:46,954 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-07-25 13:29:46,954 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:46,955 INFO L354 BasicCegarLoop]: trace histogram [11, 1, 1, 1] [2018-07-25 13:29:46,955 INFO L415 AbstractCegarLoop]: === Iteration 12 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:46,955 INFO L82 PathProgramCache]: Analyzing trace with hash 581150598, now seen corresponding path program 11 times [2018-07-25 13:29:46,955 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:47,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:47,640 WARN L169 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 64 [2018-07-25 13:29:47,864 WARN L169 SmtUtils]: Spent 172.00 ms on a formula simplification. DAG size of input: 183 DAG size of output: 54 [2018-07-25 13:29:48,165 WARN L169 SmtUtils]: Spent 225.00 ms on a formula simplification. DAG size of input: 307 DAG size of output: 96 [2018-07-25 13:29:48,728 WARN L169 SmtUtils]: Spent 453.00 ms on a formula simplification. DAG size of input: 389 DAG size of output: 81 [2018-07-25 13:29:49,526 WARN L169 SmtUtils]: Spent 657.00 ms on a formula simplification. DAG size of input: 498 DAG size of output: 79 [2018-07-25 13:29:50,764 WARN L169 SmtUtils]: Spent 1.06 s on a formula simplification. DAG size of input: 582 DAG size of output: 90 [2018-07-25 13:29:50,782 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:50,782 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:50,783 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-07-25 13:29:50,783 INFO L451 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-07-25 13:29:50,783 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-07-25 13:29:50,784 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2018-07-25 13:29:50,784 INFO L87 Difference]: Start difference. First operand 15 states and 15 transitions. Second operand 15 states. [2018-07-25 13:29:51,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:51,051 INFO L93 Difference]: Finished difference Result 18 states and 18 transitions. [2018-07-25 13:29:51,051 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-07-25 13:29:51,051 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 14 [2018-07-25 13:29:51,051 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:51,052 INFO L225 Difference]: With dead ends: 18 [2018-07-25 13:29:51,052 INFO L226 Difference]: Without dead ends: 16 [2018-07-25 13:29:51,052 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=100, Invalid=320, Unknown=0, NotChecked=0, Total=420 [2018-07-25 13:29:51,053 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2018-07-25 13:29:51,059 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-07-25 13:29:51,060 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16 states. [2018-07-25 13:29:51,060 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-07-25 13:29:51,060 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 14 [2018-07-25 13:29:51,061 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:51,061 INFO L472 AbstractCegarLoop]: Abstraction has 16 states and 16 transitions. [2018-07-25 13:29:51,061 INFO L473 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-07-25 13:29:51,061 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 16 transitions. [2018-07-25 13:29:51,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-07-25 13:29:51,062 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:51,062 INFO L354 BasicCegarLoop]: trace histogram [12, 1, 1, 1] [2018-07-25 13:29:51,062 INFO L415 AbstractCegarLoop]: === Iteration 13 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:51,062 INFO L82 PathProgramCache]: Analyzing trace with hash 835797408, now seen corresponding path program 12 times [2018-07-25 13:29:51,063 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:51,089 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:51,655 WARN L169 SmtUtils]: Spent 133.00 ms on a formula simplification. DAG size of input: 225 DAG size of output: 38 [2018-07-25 13:29:51,922 WARN L169 SmtUtils]: Spent 175.00 ms on a formula simplification. DAG size of input: 367 DAG size of output: 40 [2018-07-25 13:29:52,495 WARN L169 SmtUtils]: Spent 409.00 ms on a formula simplification. DAG size of input: 483 DAG size of output: 45 [2018-07-25 13:29:53,657 WARN L169 SmtUtils]: Spent 960.00 ms on a formula simplification. DAG size of input: 985 DAG size of output: 170 [2018-07-25 13:29:54,823 WARN L169 SmtUtils]: Spent 971.00 ms on a formula simplification. DAG size of input: 1009 DAG size of output: 125 [2018-07-25 13:29:54,841 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:54,842 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:54,842 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2018-07-25 13:29:54,842 INFO L451 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-07-25 13:29:54,843 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-07-25 13:29:54,843 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=190, Unknown=0, NotChecked=0, Total=240 [2018-07-25 13:29:54,843 INFO L87 Difference]: Start difference. First operand 16 states and 16 transitions. Second operand 16 states. [2018-07-25 13:29:54,990 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:54,991 INFO L93 Difference]: Finished difference Result 19 states and 19 transitions. [2018-07-25 13:29:54,991 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-07-25 13:29:54,991 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 15 [2018-07-25 13:29:54,991 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:54,992 INFO L225 Difference]: With dead ends: 19 [2018-07-25 13:29:54,992 INFO L226 Difference]: Without dead ends: 17 [2018-07-25 13:29:54,992 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2018-07-25 13:29:54,993 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2018-07-25 13:29:55,012 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-07-25 13:29:55,013 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2018-07-25 13:29:55,013 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-07-25 13:29:55,013 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 15 [2018-07-25 13:29:55,013 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:55,014 INFO L472 AbstractCegarLoop]: Abstraction has 17 states and 17 transitions. [2018-07-25 13:29:55,014 INFO L473 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-07-25 13:29:55,014 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 17 transitions. [2018-07-25 13:29:55,014 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-07-25 13:29:55,014 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:55,015 INFO L354 BasicCegarLoop]: trace histogram [13, 1, 1, 1] [2018-07-25 13:29:55,015 INFO L415 AbstractCegarLoop]: === Iteration 14 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:55,015 INFO L82 PathProgramCache]: Analyzing trace with hash 139913926, now seen corresponding path program 13 times [2018-07-25 13:29:55,015 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:55,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:29:55,885 WARN L169 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 391 DAG size of output: 40 [2018-07-25 13:29:56,476 WARN L169 SmtUtils]: Spent 457.00 ms on a formula simplification. DAG size of input: 506 DAG size of output: 44 [2018-07-25 13:29:57,079 WARN L169 SmtUtils]: Spent 430.00 ms on a formula simplification. DAG size of input: 607 DAG size of output: 48 [2018-07-25 13:29:58,182 WARN L169 SmtUtils]: Spent 847.00 ms on a formula simplification. DAG size of input: 939 DAG size of output: 76 [2018-07-25 13:29:59,606 WARN L169 SmtUtils]: Spent 1.02 s on a formula simplification. DAG size of input: 1530 DAG size of output: 94 [2018-07-25 13:29:59,621 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:29:59,621 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:29:59,621 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-07-25 13:29:59,622 INFO L451 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-07-25 13:29:59,622 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-07-25 13:29:59,622 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2018-07-25 13:29:59,623 INFO L87 Difference]: Start difference. First operand 17 states and 17 transitions. Second operand 17 states. [2018-07-25 13:29:59,772 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:29:59,772 INFO L93 Difference]: Finished difference Result 20 states and 20 transitions. [2018-07-25 13:29:59,772 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-07-25 13:29:59,772 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 16 [2018-07-25 13:29:59,773 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:29:59,773 INFO L225 Difference]: With dead ends: 20 [2018-07-25 13:29:59,773 INFO L226 Difference]: Without dead ends: 18 [2018-07-25 13:29:59,774 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2018-07-25 13:29:59,774 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2018-07-25 13:29:59,782 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-07-25 13:29:59,782 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18 states. [2018-07-25 13:29:59,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 18 transitions. [2018-07-25 13:29:59,783 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 18 transitions. Word has length 16 [2018-07-25 13:29:59,783 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:29:59,783 INFO L472 AbstractCegarLoop]: Abstraction has 18 states and 18 transitions. [2018-07-25 13:29:59,783 INFO L473 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-07-25 13:29:59,784 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 18 transitions. [2018-07-25 13:29:59,784 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-07-25 13:29:59,784 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:29:59,784 INFO L354 BasicCegarLoop]: trace histogram [14, 1, 1, 1] [2018-07-25 13:29:59,785 INFO L415 AbstractCegarLoop]: === Iteration 15 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:29:59,785 INFO L82 PathProgramCache]: Analyzing trace with hash 42362464, now seen corresponding path program 14 times [2018-07-25 13:29:59,785 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:29:59,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:30:00,862 WARN L169 SmtUtils]: Spent 158.00 ms on a formula simplification. DAG size of input: 373 DAG size of output: 41 [2018-07-25 13:30:01,326 WARN L169 SmtUtils]: Spent 339.00 ms on a formula simplification. DAG size of input: 473 DAG size of output: 45 [2018-07-25 13:30:01,947 WARN L169 SmtUtils]: Spent 434.00 ms on a formula simplification. DAG size of input: 637 DAG size of output: 49 [2018-07-25 13:30:02,892 WARN L169 SmtUtils]: Spent 686.00 ms on a formula simplification. DAG size of input: 768 DAG size of output: 52 [2018-07-25 13:30:04,553 WARN L169 SmtUtils]: Spent 1.27 s on a formula simplification. DAG size of input: 1621 DAG size of output: 90 [2018-07-25 13:30:07,770 WARN L169 SmtUtils]: Spent 2.45 s on a formula simplification. DAG size of input: 2892 DAG size of output: 95 [2018-07-25 13:30:07,782 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 0 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:30:07,783 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:30:07,783 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2018-07-25 13:30:07,783 INFO L451 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-07-25 13:30:07,783 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-07-25 13:30:07,784 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2018-07-25 13:30:07,784 INFO L87 Difference]: Start difference. First operand 18 states and 18 transitions. Second operand 18 states. [2018-07-25 13:30:07,937 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:30:07,938 INFO L93 Difference]: Finished difference Result 21 states and 21 transitions. [2018-07-25 13:30:07,938 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-07-25 13:30:07,938 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 17 [2018-07-25 13:30:07,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:30:07,939 INFO L225 Difference]: With dead ends: 21 [2018-07-25 13:30:07,939 INFO L226 Difference]: Without dead ends: 19 [2018-07-25 13:30:07,939 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=62, Invalid=280, Unknown=0, NotChecked=0, Total=342 [2018-07-25 13:30:07,939 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2018-07-25 13:30:07,960 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-07-25 13:30:07,960 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-07-25 13:30:07,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-07-25 13:30:07,961 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 17 [2018-07-25 13:30:07,961 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:30:07,961 INFO L472 AbstractCegarLoop]: Abstraction has 19 states and 19 transitions. [2018-07-25 13:30:07,961 INFO L473 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-07-25 13:30:07,961 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 19 transitions. [2018-07-25 13:30:07,964 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-07-25 13:30:07,965 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:30:07,965 INFO L354 BasicCegarLoop]: trace histogram [15, 1, 1, 1] [2018-07-25 13:30:07,965 INFO L415 AbstractCegarLoop]: === Iteration 16 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:30:07,965 INFO L82 PathProgramCache]: Analyzing trace with hash 1313234438, now seen corresponding path program 15 times [2018-07-25 13:30:07,965 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:30:08,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:30:09,047 WARN L169 SmtUtils]: Spent 125.00 ms on a formula simplification. DAG size of input: 425 DAG size of output: 44 [2018-07-25 13:30:09,916 WARN L169 SmtUtils]: Spent 621.00 ms on a formula simplification. DAG size of input: 1062 DAG size of output: 49 [2018-07-25 13:30:11,372 WARN L169 SmtUtils]: Spent 1.22 s on a formula simplification. DAG size of input: 1325 DAG size of output: 52 [2018-07-25 13:30:13,631 WARN L169 SmtUtils]: Spent 1.93 s on a formula simplification. DAG size of input: 2123 DAG size of output: 57 [2018-07-25 13:30:18,731 WARN L169 SmtUtils]: Spent 4.74 s on a formula simplification. DAG size of input: 2449 DAG size of output: 159 [2018-07-25 13:30:21,382 WARN L169 SmtUtils]: Spent 2.24 s on a formula simplification. DAG size of input: 2239 DAG size of output: 158 [2018-07-25 13:30:21,395 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:30:21,395 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:30:21,396 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-07-25 13:30:21,396 INFO L451 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-07-25 13:30:21,396 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-07-25 13:30:21,397 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=280, Unknown=0, NotChecked=0, Total=342 [2018-07-25 13:30:21,397 INFO L87 Difference]: Start difference. First operand 19 states and 19 transitions. Second operand 19 states. [2018-07-25 13:30:21,587 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:30:21,587 INFO L93 Difference]: Finished difference Result 22 states and 22 transitions. [2018-07-25 13:30:21,587 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-07-25 13:30:21,587 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 18 [2018-07-25 13:30:21,588 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:30:21,588 INFO L225 Difference]: With dead ends: 22 [2018-07-25 13:30:21,588 INFO L226 Difference]: Without dead ends: 20 [2018-07-25 13:30:21,589 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 12.5s TimeCoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2018-07-25 13:30:21,589 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2018-07-25 13:30:21,597 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2018-07-25 13:30:21,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 20 states. [2018-07-25 13:30:21,598 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 20 transitions. [2018-07-25 13:30:21,598 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 20 transitions. Word has length 18 [2018-07-25 13:30:21,598 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:30:21,598 INFO L472 AbstractCegarLoop]: Abstraction has 20 states and 20 transitions. [2018-07-25 13:30:21,598 INFO L473 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-07-25 13:30:21,598 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 20 transitions. [2018-07-25 13:30:21,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-07-25 13:30:21,599 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:30:21,599 INFO L354 BasicCegarLoop]: trace histogram [16, 1, 1, 1] [2018-07-25 13:30:21,599 INFO L415 AbstractCegarLoop]: === Iteration 17 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:30:21,600 INFO L82 PathProgramCache]: Analyzing trace with hash 2055559968, now seen corresponding path program 16 times [2018-07-25 13:30:21,600 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:30:21,635 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:30:23,094 WARN L169 SmtUtils]: Spent 285.00 ms on a formula simplification. DAG size of input: 444 DAG size of output: 45 [2018-07-25 13:30:23,589 WARN L169 SmtUtils]: Spent 349.00 ms on a formula simplification. DAG size of input: 995 DAG size of output: 48 [2018-07-25 13:30:25,128 WARN L169 SmtUtils]: Spent 1.32 s on a formula simplification. DAG size of input: 1311 DAG size of output: 52 [2018-07-25 13:30:27,858 WARN L169 SmtUtils]: Spent 2.42 s on a formula simplification. DAG size of input: 1626 DAG size of output: 57 [2018-07-25 13:30:35,066 WARN L169 SmtUtils]: Spent 6.71 s on a formula simplification. DAG size of input: 2313 DAG size of output: 61 [2018-07-25 13:30:46,429 WARN L169 SmtUtils]: Spent 10.69 s on a formula simplification. DAG size of input: 2780 DAG size of output: 109 [2018-07-25 13:31:03,113 WARN L169 SmtUtils]: Spent 15.56 s on a formula simplification. DAG size of input: 3963 DAG size of output: 114 [2018-07-25 13:31:03,126 INFO L134 CoverageAnalysis]: Checked inductivity of 136 backedges. 0 proven. 136 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:31:03,126 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:31:03,126 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2018-07-25 13:31:03,127 INFO L451 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-07-25 13:31:03,127 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-07-25 13:31:03,127 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2018-07-25 13:31:03,128 INFO L87 Difference]: Start difference. First operand 20 states and 20 transitions. Second operand 20 states. [2018-07-25 13:31:03,279 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:31:03,279 INFO L93 Difference]: Finished difference Result 23 states and 23 transitions. [2018-07-25 13:31:03,279 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-07-25 13:31:03,279 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 19 [2018-07-25 13:31:03,280 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:31:03,280 INFO L225 Difference]: With dead ends: 23 [2018-07-25 13:31:03,280 INFO L226 Difference]: Without dead ends: 21 [2018-07-25 13:31:03,281 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 40.1s TimeCoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2018-07-25 13:31:03,281 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2018-07-25 13:31:03,290 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-07-25 13:31:03,290 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-07-25 13:31:03,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 21 transitions. [2018-07-25 13:31:03,291 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 21 transitions. Word has length 19 [2018-07-25 13:31:03,291 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:31:03,291 INFO L472 AbstractCegarLoop]: Abstraction has 21 states and 21 transitions. [2018-07-25 13:31:03,291 INFO L473 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-07-25 13:31:03,291 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 21 transitions. [2018-07-25 13:31:03,292 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-07-25 13:31:03,292 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:31:03,292 INFO L354 BasicCegarLoop]: trace histogram [17, 1, 1, 1] [2018-07-25 13:31:03,292 INFO L415 AbstractCegarLoop]: === Iteration 18 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:31:03,293 INFO L82 PathProgramCache]: Analyzing trace with hash -702152378, now seen corresponding path program 17 times [2018-07-25 13:31:03,293 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:31:03,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:31:04,963 WARN L169 SmtUtils]: Spent 210.00 ms on a formula simplification. DAG size of input: 466 DAG size of output: 42 [2018-07-25 13:31:05,467 WARN L169 SmtUtils]: Spent 412.00 ms on a formula simplification. DAG size of input: 550 DAG size of output: 47 [2018-07-25 13:31:06,446 WARN L169 SmtUtils]: Spent 847.00 ms on a formula simplification. DAG size of input: 744 DAG size of output: 52 [2018-07-25 13:31:07,968 WARN L169 SmtUtils]: Spent 1.31 s on a formula simplification. DAG size of input: 1123 DAG size of output: 59 [2018-07-25 13:31:11,171 WARN L169 SmtUtils]: Spent 2.91 s on a formula simplification. DAG size of input: 1482 DAG size of output: 106 [2018-07-25 13:31:18,836 WARN L169 SmtUtils]: Spent 7.15 s on a formula simplification. DAG size of input: 2585 DAG size of output: 164 [2018-07-25 13:31:36,613 WARN L169 SmtUtils]: Spent 16.96 s on a formula simplification. DAG size of input: 3233 DAG size of output: 143 [2018-07-25 13:31:47,048 WARN L169 SmtUtils]: Spent 9.59 s on a formula simplification. DAG size of input: 3190 DAG size of output: 147 [2018-07-25 13:31:58,172 WARN L169 SmtUtils]: Spent 10.15 s on a formula simplification. DAG size of input: 4334 DAG size of output: 136 [2018-07-25 13:31:58,189 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:31:58,189 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:31:58,189 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-07-25 13:31:58,189 INFO L451 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-07-25 13:31:58,189 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-07-25 13:31:58,190 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=312, Unknown=0, NotChecked=0, Total=420 [2018-07-25 13:31:58,190 INFO L87 Difference]: Start difference. First operand 21 states and 21 transitions. Second operand 21 states. [2018-07-25 13:31:58,451 WARN L169 SmtUtils]: Spent 144.00 ms on a formula simplification. DAG size of input: 201 DAG size of output: 117 [2018-07-25 13:31:58,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:31:58,667 INFO L93 Difference]: Finished difference Result 24 states and 24 transitions. [2018-07-25 13:31:58,668 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-07-25 13:31:58,668 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 20 [2018-07-25 13:31:58,668 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:31:58,668 INFO L225 Difference]: With dead ends: 24 [2018-07-25 13:31:58,668 INFO L226 Difference]: Without dead ends: 22 [2018-07-25 13:31:58,669 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 53.3s TimeCoverageRelationStatistics Valid=177, Invalid=473, Unknown=0, NotChecked=0, Total=650 [2018-07-25 13:31:58,669 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-07-25 13:31:58,678 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-07-25 13:31:58,678 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2018-07-25 13:31:58,679 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 22 transitions. [2018-07-25 13:31:58,679 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 22 transitions. Word has length 20 [2018-07-25 13:31:58,679 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:31:58,679 INFO L472 AbstractCegarLoop]: Abstraction has 22 states and 22 transitions. [2018-07-25 13:31:58,679 INFO L473 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-07-25 13:31:58,679 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 22 transitions. [2018-07-25 13:31:58,680 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-07-25 13:31:58,680 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:31:58,680 INFO L354 BasicCegarLoop]: trace histogram [18, 1, 1, 1] [2018-07-25 13:31:58,680 INFO L415 AbstractCegarLoop]: === Iteration 19 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:31:58,681 INFO L82 PathProgramCache]: Analyzing trace with hash -291889184, now seen corresponding path program 18 times [2018-07-25 13:31:58,681 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:31:58,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:32:00,743 WARN L169 SmtUtils]: Spent 259.00 ms on a formula simplification. DAG size of input: 513 DAG size of output: 45 [2018-07-25 13:32:01,776 WARN L169 SmtUtils]: Spent 856.00 ms on a formula simplification. DAG size of input: 1120 DAG size of output: 49 [2018-07-25 13:32:04,222 WARN L169 SmtUtils]: Spent 2.18 s on a formula simplification. DAG size of input: 1425 DAG size of output: 52 [2018-07-25 13:32:08,734 WARN L169 SmtUtils]: Spent 4.10 s on a formula simplification. DAG size of input: 2205 DAG size of output: 57 [2018-07-25 13:32:17,680 WARN L169 SmtUtils]: Spent 8.38 s on a formula simplification. DAG size of input: 2874 DAG size of output: 61 [2018-07-25 13:32:26,566 WARN L169 SmtUtils]: Spent 8.17 s on a formula simplification. DAG size of input: 3673 DAG size of output: 65 [2018-07-25 13:32:39,139 WARN L169 SmtUtils]: Spent 11.69 s on a formula simplification. DAG size of input: 3837 DAG size of output: 69 [2018-07-25 13:32:56,457 WARN L169 SmtUtils]: Spent 16.27 s on a formula simplification. DAG size of input: 4745 DAG size of output: 130 [2018-07-25 13:33:22,250 WARN L169 SmtUtils]: Spent 24.24 s on a formula simplification. DAG size of input: 6452 DAG size of output: 155 [2018-07-25 13:33:22,266 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 0 proven. 171 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-07-25 13:33:22,266 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 13:33:22,266 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2018-07-25 13:33:22,266 INFO L451 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-07-25 13:33:22,267 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-07-25 13:33:22,267 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=388, Unknown=0, NotChecked=0, Total=462 [2018-07-25 13:33:22,267 INFO L87 Difference]: Start difference. First operand 22 states and 22 transitions. Second operand 22 states. [2018-07-25 13:33:22,489 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 13:33:22,489 INFO L93 Difference]: Finished difference Result 25 states and 25 transitions. [2018-07-25 13:33:22,490 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-07-25 13:33:22,490 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 21 [2018-07-25 13:33:22,490 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 13:33:22,490 INFO L225 Difference]: With dead ends: 25 [2018-07-25 13:33:22,491 INFO L226 Difference]: Without dead ends: 23 [2018-07-25 13:33:22,491 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 80.9s TimeCoverageRelationStatistics Valid=78, Invalid=428, Unknown=0, NotChecked=0, Total=506 [2018-07-25 13:33:22,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2018-07-25 13:33:22,502 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-07-25 13:33:22,502 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-07-25 13:33:22,502 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2018-07-25 13:33:22,503 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 21 [2018-07-25 13:33:22,503 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 13:33:22,503 INFO L472 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2018-07-25 13:33:22,503 INFO L473 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-07-25 13:33:22,503 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2018-07-25 13:33:22,504 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-07-25 13:33:22,504 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 13:33:22,504 INFO L354 BasicCegarLoop]: trace histogram [19, 1, 1, 1] [2018-07-25 13:33:22,504 INFO L415 AbstractCegarLoop]: === Iteration 20 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 13:33:22,504 INFO L82 PathProgramCache]: Analyzing trace with hash -458632058, now seen corresponding path program 19 times [2018-07-25 13:33:22,505 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 13:33:22,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 13:33:26,187 WARN L169 SmtUtils]: Spent 105.00 ms on a formula simplification. DAG size of input: 254 DAG size of output: 68 [2018-07-25 13:33:26,618 WARN L169 SmtUtils]: Spent 307.00 ms on a formula simplification. DAG size of input: 468 DAG size of output: 97 [2018-07-25 13:33:27,639 WARN L169 SmtUtils]: Spent 831.00 ms on a formula simplification. DAG size of input: 490 DAG size of output: 101 [2018-07-25 13:33:28,717 WARN L169 SmtUtils]: Spent 779.00 ms on a formula simplification. DAG size of input: 837 DAG size of output: 118 [2018-07-25 13:33:30,285 WARN L169 SmtUtils]: Spent 1.14 s on a formula simplification. DAG size of input: 1021 DAG size of output: 101 [2018-07-25 13:33:32,324 WARN L169 SmtUtils]: Spent 1.47 s on a formula simplification. DAG size of input: 1201 DAG size of output: 116 [2018-07-25 13:33:35,633 WARN L169 SmtUtils]: Spent 2.49 s on a formula simplification. DAG size of input: 1571 DAG size of output: 149 [2018-07-25 13:33:55,172 WARN L169 SmtUtils]: Spent 18.24 s on a formula simplification. DAG size of input: 5382 DAG size of output: 137 Received shutdown request... [2018-07-25 13:34:03,401 WARN L177 SmtUtils]: Removed 2 from assertion stack [2018-07-25 13:34:03,401 WARN L541 AbstractCegarLoop]: Verification canceled [2018-07-25 13:34:03,405 WARN L202 ceAbstractionStarter]: Timeout [2018-07-25 13:34:03,406 INFO L202 PluginConnector]: Adding new model ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.07 01:34:03 BoogieIcfgContainer [2018-07-25 13:34:03,406 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-07-25 13:34:03,407 INFO L168 Benchmark]: Toolchain (without parser) took 263652.18 ms. Allocated memory was 1.5 GB in the beginning and 3.5 GB in the end (delta: 2.0 GB). Free memory was 1.5 GB in the beginning and 1.6 GB in the end (delta: -118.9 MB). Peak memory consumption was 2.7 GB. Max. memory is 7.1 GB. [2018-07-25 13:34:03,408 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.13 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-07-25 13:34:03,409 INFO L168 Benchmark]: Boogie Procedure Inliner took 41.69 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-07-25 13:34:03,411 INFO L168 Benchmark]: Boogie Preprocessor took 21.64 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-07-25 13:34:03,411 INFO L168 Benchmark]: RCFGBuilder took 211.65 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.5 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. [2018-07-25 13:34:03,412 INFO L168 Benchmark]: TraceAbstraction took 263372.90 ms. Allocated memory was 1.5 GB in the beginning and 3.5 GB in the end (delta: 2.0 GB). Free memory was 1.5 GB in the beginning and 1.6 GB in the end (delta: -129.5 MB). Peak memory consumption was 2.7 GB. Max. memory is 7.1 GB. [2018-07-25 13:34:03,415 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.13 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 41.69 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 21.64 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 211.65 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.5 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. * TraceAbstraction took 263372.90 ms. Allocated memory was 1.5 GB in the beginning and 3.5 GB in the end (delta: 2.0 GB). Free memory was 1.5 GB in the beginning and 1.6 GB in the end (delta: -129.5 MB). Peak memory consumption was 2.7 GB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 34]: Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 34). Cancelled while BasicCegarLoop was analyzing trace of length 23 with TraceHistMax 19, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 8018. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 6 locations, 1 error locations. TIMEOUT Result, 263.3s OverallTime, 20 OverallIterations, 19 TraceHistogramMax, 3.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 40 SDtfs, 18 SDslu, 38 SDs, 0 SdLazy, 2274 SolverSat, 132 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 244 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 243 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 132 ImplicationChecksByTransitivity, 209.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=23occurred in iteration=19, 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, 19 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 218.3s InterpolantComputationTime, 228 NumberOfCodeBlocks, 228 NumberOfCodeBlocksAsserted, 19 NumberOfCheckSat, 209 ConstructedInterpolants, 0 QuantifiedInterpolants, 251334 SizeOfPredicates, 0 NumberOfNonLiveVariables, 0 ConjunctsInSsa, 0 ConjunctsInUnsatCore, 19 InterpolantComputations, 1 PerfectInterpolantSequences, 0/1140 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/ArrayInit01.bpl_AutomizerBpl-nestedInterpolants.epf_AutomizerBplInline.xml/Csv-Benchmark-0-2018-07-25_13-34-03-428.csv Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/ArrayInit01.bpl_AutomizerBpl-nestedInterpolants.epf_AutomizerBplInline.xml/Csv-TraceAbstractionBenchmarks-0-2018-07-25_13-34-03-428.csv Completed graceful shutdown