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 08:50:25,454 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-07-25 08:50:25,456 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-07-25 08:50:25,468 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-07-25 08:50:25,468 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-07-25 08:50:25,469 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-07-25 08:50:25,471 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-07-25 08:50:25,473 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-07-25 08:50:25,474 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-07-25 08:50:25,475 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-07-25 08:50:25,476 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-07-25 08:50:25,476 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-07-25 08:50:25,477 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-07-25 08:50:25,478 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-07-25 08:50:25,483 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-07-25 08:50:25,484 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-07-25 08:50:25,485 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-07-25 08:50:25,486 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-07-25 08:50:25,488 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-07-25 08:50:25,489 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-07-25 08:50:25,491 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-07-25 08:50:25,492 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-07-25 08:50:25,494 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-07-25 08:50:25,494 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-07-25 08:50:25,494 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-07-25 08:50:25,495 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-07-25 08:50:25,496 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-07-25 08:50:25,497 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-07-25 08:50:25,497 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-07-25 08:50:25,499 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-07-25 08:50:25,499 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-07-25 08:50:25,499 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-07-25 08:50:25,500 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-07-25 08:50:25,500 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-07-25 08:50:25,501 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-07-25 08:50:25,501 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-07-25 08:50:25,502 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/Pdr/AutomizerBpl-nestedInterpolants.epf [2018-07-25 08:50:25,515 INFO L110 SettingsManager]: Loading preferences was successful [2018-07-25 08:50:25,515 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-07-25 08:50:25,516 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-07-25 08:50:25,517 INFO L133 SettingsManager]: * SMT solver=Internal_SMTInterpol [2018-07-25 08:50:25,517 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-07-25 08:50:25,517 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2018-07-25 08:50:25,517 INFO L133 SettingsManager]: * Use separate solver for trace checks=false [2018-07-25 08:50:25,517 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-07-25 08:50:25,559 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-07-25 08:50:25,570 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-07-25 08:50:25,574 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-07-25 08:50:25,576 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-07-25 08:50:25,576 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-07-25 08:50:25,577 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 08:50:25,577 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/ArrayInit01.bpl' [2018-07-25 08:50:25,626 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-07-25 08:50:25,627 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-07-25 08:50:25,628 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-07-25 08:50:25,629 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-07-25 08:50:25,629 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-07-25 08:50:25,648 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 08:50:25" (1/1) ... [2018-07-25 08:50:25,662 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 08:50:25" (1/1) ... [2018-07-25 08:50:25,668 WARN L165 Inliner]: Program contained no entry procedure! [2018-07-25 08:50:25,669 WARN L168 Inliner]: Missing entry procedures: [ULTIMATE.start] [2018-07-25 08:50:25,669 WARN L175 Inliner]: Fallback enabled. All procedures will be processed. [2018-07-25 08:50:25,671 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-07-25 08:50:25,672 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-07-25 08:50:25,672 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-07-25 08:50:25,672 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-07-25 08:50:25,683 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 08:50:25" (1/1) ... [2018-07-25 08:50:25,683 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 08:50:25" (1/1) ... [2018-07-25 08:50:25,684 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 08:50:25" (1/1) ... [2018-07-25 08:50:25,684 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 08:50:25" (1/1) ... [2018-07-25 08:50:25,686 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 08:50:25" (1/1) ... [2018-07-25 08:50:25,691 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 08:50:25" (1/1) ... [2018-07-25 08:50:25,692 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 08:50:25" (1/1) ... [2018-07-25 08:50:25,694 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-07-25 08:50:25,695 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-07-25 08:50:25,695 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-07-25 08:50:25,695 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-07-25 08:50:25,696 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 08:50:25" (1/1) ... [2018-07-25 08:50:25,779 INFO L124 BoogieDeclarations]: Specification and implementation of procedure main given in one single declaration [2018-07-25 08:50:25,780 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-07-25 08:50:25,780 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-07-25 08:50:25,911 INFO L270 CfgBuilder]: Using library mode [2018-07-25 08:50:25,912 INFO L202 PluginConnector]: Adding new model ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.07 08:50:25 BoogieIcfgContainer [2018-07-25 08:50:25,912 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-07-25 08:50:25,914 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-07-25 08:50:25,914 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-07-25 08:50:25,917 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-07-25 08:50:25,918 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 25.07 08:50:25" (1/2) ... [2018-07-25 08:50:25,919 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 08:50:25, skipping insertion in model container [2018-07-25 08:50:25,919 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.07 08:50:25" (2/2) ... [2018-07-25 08:50:25,922 INFO L112 eAbstractionObserver]: Analyzing ICFG ArrayInit01.bpl [2018-07-25 08:50:25,932 INFO L133 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2018-07-25 08:50:25,940 INFO L145 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-07-25 08:50:25,988 INFO L128 ementStrategyFactory]: Using default assertion order modulation [2018-07-25 08:50:25,989 INFO L374 AbstractCegarLoop]: Interprodecural is true [2018-07-25 08:50:25,989 INFO L375 AbstractCegarLoop]: Hoare is true [2018-07-25 08:50:25,990 INFO L376 AbstractCegarLoop]: Compute interpolants for Craig_NestedInterpolation [2018-07-25 08:50:25,990 INFO L377 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-07-25 08:50:25,990 INFO L378 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-07-25 08:50:25,990 INFO L379 AbstractCegarLoop]: Difference is false [2018-07-25 08:50:25,990 INFO L380 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-07-25 08:50:25,991 INFO L385 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-07-25 08:50:26,004 INFO L276 IsEmpty]: Start isEmpty. Operand 5 states. [2018-07-25 08:50:26,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-07-25 08:50:26,012 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:26,013 INFO L354 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-07-25 08:50:26,015 INFO L415 AbstractCegarLoop]: === Iteration 1 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:26,020 INFO L82 PathProgramCache]: Analyzing trace with hash 29984, now seen corresponding path program 1 times [2018-07-25 08:50:26,026 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:26,045 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:26,096 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 08:50:26,099 INFO L309 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-07-25 08:50:26,099 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-07-25 08:50:26,104 INFO L451 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-07-25 08:50:26,116 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-07-25 08:50:26,117 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-07-25 08:50:26,119 INFO L87 Difference]: Start difference. First operand 5 states. Second operand 3 states. [2018-07-25 08:50:26,146 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:26,146 INFO L93 Difference]: Finished difference Result 9 states and 9 transitions. [2018-07-25 08:50:26,147 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-07-25 08:50:26,148 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2018-07-25 08:50:26,149 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:26,159 INFO L225 Difference]: With dead ends: 9 [2018-07-25 08:50:26,160 INFO L226 Difference]: Without dead ends: 5 [2018-07-25 08:50:26,163 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 08:50:26,183 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5 states. [2018-07-25 08:50:26,198 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5 to 5. [2018-07-25 08:50:26,200 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2018-07-25 08:50:26,200 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 5 transitions. [2018-07-25 08:50:26,204 INFO L78 Accepts]: Start accepts. Automaton has 5 states and 5 transitions. Word has length 3 [2018-07-25 08:50:26,205 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:26,205 INFO L472 AbstractCegarLoop]: Abstraction has 5 states and 5 transitions. [2018-07-25 08:50:26,205 INFO L473 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-07-25 08:50:26,205 INFO L276 IsEmpty]: Start isEmpty. Operand 5 states and 5 transitions. [2018-07-25 08:50:26,206 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2018-07-25 08:50:26,206 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:26,206 INFO L354 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2018-07-25 08:50:26,206 INFO L415 AbstractCegarLoop]: === Iteration 2 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:26,207 INFO L82 PathProgramCache]: Analyzing trace with hash 927558, now seen corresponding path program 1 times [2018-07-25 08:50:26,207 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:26,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:26,332 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 08:50:26,333 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:26,333 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [3] total 3 [2018-07-25 08:50:26,335 INFO L451 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-07-25 08:50:26,335 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-07-25 08:50:26,336 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-07-25 08:50:26,336 INFO L87 Difference]: Start difference. First operand 5 states and 5 transitions. Second operand 5 states. [2018-07-25 08:50:26,396 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:26,397 INFO L93 Difference]: Finished difference Result 8 states and 8 transitions. [2018-07-25 08:50:26,397 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-07-25 08:50:26,399 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 4 [2018-07-25 08:50:26,399 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:26,399 INFO L225 Difference]: With dead ends: 8 [2018-07-25 08:50:26,399 INFO L226 Difference]: Without dead ends: 6 [2018-07-25 08:50:26,401 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 08:50:26,401 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6 states. [2018-07-25 08:50:26,403 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6 to 6. [2018-07-25 08:50:26,403 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2018-07-25 08:50:26,403 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 6 transitions. [2018-07-25 08:50:26,404 INFO L78 Accepts]: Start accepts. Automaton has 6 states and 6 transitions. Word has length 4 [2018-07-25 08:50:26,404 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:26,404 INFO L472 AbstractCegarLoop]: Abstraction has 6 states and 6 transitions. [2018-07-25 08:50:26,404 INFO L473 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-07-25 08:50:26,405 INFO L276 IsEmpty]: Start isEmpty. Operand 6 states and 6 transitions. [2018-07-25 08:50:26,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2018-07-25 08:50:26,406 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:26,406 INFO L354 BasicCegarLoop]: trace histogram [2, 1, 1, 1] [2018-07-25 08:50:26,406 INFO L415 AbstractCegarLoop]: === Iteration 3 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:26,407 INFO L82 PathProgramCache]: Analyzing trace with hash 28752352, now seen corresponding path program 2 times [2018-07-25 08:50:26,407 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:26,418 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:26,542 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 08:50:26,542 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:26,542 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4] total 4 [2018-07-25 08:50:26,543 INFO L451 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-07-25 08:50:26,543 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-07-25 08:50:26,543 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-07-25 08:50:26,544 INFO L87 Difference]: Start difference. First operand 6 states and 6 transitions. Second operand 6 states. [2018-07-25 08:50:26,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:26,607 INFO L93 Difference]: Finished difference Result 9 states and 9 transitions. [2018-07-25 08:50:26,607 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-07-25 08:50:26,607 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 5 [2018-07-25 08:50:26,608 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:26,608 INFO L225 Difference]: With dead ends: 9 [2018-07-25 08:50:26,608 INFO L226 Difference]: Without dead ends: 7 [2018-07-25 08:50:26,609 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-07-25 08:50:26,609 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7 states. [2018-07-25 08:50:26,611 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-07-25 08:50:26,611 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-07-25 08:50:26,612 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-07-25 08:50:26,612 INFO L78 Accepts]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 5 [2018-07-25 08:50:26,612 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:26,612 INFO L472 AbstractCegarLoop]: Abstraction has 7 states and 7 transitions. [2018-07-25 08:50:26,613 INFO L473 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-07-25 08:50:26,613 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states and 7 transitions. [2018-07-25 08:50:26,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2018-07-25 08:50:26,613 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:26,613 INFO L354 BasicCegarLoop]: trace histogram [3, 1, 1, 1] [2018-07-25 08:50:26,614 INFO L415 AbstractCegarLoop]: === Iteration 4 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:26,614 INFO L82 PathProgramCache]: Analyzing trace with hash 891320966, now seen corresponding path program 3 times [2018-07-25 08:50:26,614 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:26,639 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:26,771 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 08:50:26,772 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:26,772 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5] total 5 [2018-07-25 08:50:26,772 INFO L451 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-07-25 08:50:26,773 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-07-25 08:50:26,773 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-07-25 08:50:26,774 INFO L87 Difference]: Start difference. First operand 7 states and 7 transitions. Second operand 7 states. [2018-07-25 08:50:26,819 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:26,819 INFO L93 Difference]: Finished difference Result 10 states and 10 transitions. [2018-07-25 08:50:26,819 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-07-25 08:50:26,820 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 6 [2018-07-25 08:50:26,820 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:26,820 INFO L225 Difference]: With dead ends: 10 [2018-07-25 08:50:26,821 INFO L226 Difference]: Without dead ends: 8 [2018-07-25 08:50:26,821 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 08:50:26,822 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8 states. [2018-07-25 08:50:26,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-07-25 08:50:26,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 8 states. [2018-07-25 08:50:26,825 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 8 transitions. [2018-07-25 08:50:26,826 INFO L78 Accepts]: Start accepts. Automaton has 8 states and 8 transitions. Word has length 6 [2018-07-25 08:50:26,826 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:26,826 INFO L472 AbstractCegarLoop]: Abstraction has 8 states and 8 transitions. [2018-07-25 08:50:26,826 INFO L473 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-07-25 08:50:26,826 INFO L276 IsEmpty]: Start isEmpty. Operand 8 states and 8 transitions. [2018-07-25 08:50:26,827 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2018-07-25 08:50:26,827 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:26,827 INFO L354 BasicCegarLoop]: trace histogram [4, 1, 1, 1] [2018-07-25 08:50:26,828 INFO L415 AbstractCegarLoop]: === Iteration 5 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:26,828 INFO L82 PathProgramCache]: Analyzing trace with hash 1861144224, now seen corresponding path program 4 times [2018-07-25 08:50:26,828 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:26,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:27,121 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 08:50:27,121 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:27,121 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2018-07-25 08:50:27,122 INFO L451 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-07-25 08:50:27,122 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-07-25 08:50:27,123 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-07-25 08:50:27,123 INFO L87 Difference]: Start difference. First operand 8 states and 8 transitions. Second operand 8 states. [2018-07-25 08:50:27,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:27,214 INFO L93 Difference]: Finished difference Result 11 states and 11 transitions. [2018-07-25 08:50:27,214 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-07-25 08:50:27,214 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 7 [2018-07-25 08:50:27,215 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:27,215 INFO L225 Difference]: With dead ends: 11 [2018-07-25 08:50:27,216 INFO L226 Difference]: Without dead ends: 9 [2018-07-25 08:50:27,216 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 08:50:27,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 9 states. [2018-07-25 08:50:27,226 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-07-25 08:50:27,227 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2018-07-25 08:50:27,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-07-25 08:50:27,228 INFO L78 Accepts]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-07-25 08:50:27,228 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:27,228 INFO L472 AbstractCegarLoop]: Abstraction has 9 states and 9 transitions. [2018-07-25 08:50:27,228 INFO L473 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-07-25 08:50:27,229 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states and 9 transitions. [2018-07-25 08:50:27,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2018-07-25 08:50:27,229 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:27,232 INFO L354 BasicCegarLoop]: trace histogram [5, 1, 1, 1] [2018-07-25 08:50:27,233 INFO L415 AbstractCegarLoop]: === Iteration 6 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:27,233 INFO L82 PathProgramCache]: Analyzing trace with hash 1860894150, now seen corresponding path program 5 times [2018-07-25 08:50:27,233 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:27,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:27,524 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 08:50:27,525 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:27,525 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2018-07-25 08:50:27,525 INFO L451 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-07-25 08:50:27,525 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-07-25 08:50:27,526 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-07-25 08:50:27,527 INFO L87 Difference]: Start difference. First operand 9 states and 9 transitions. Second operand 9 states. [2018-07-25 08:50:27,590 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:27,590 INFO L93 Difference]: Finished difference Result 12 states and 12 transitions. [2018-07-25 08:50:27,591 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-07-25 08:50:27,591 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 8 [2018-07-25 08:50:27,591 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:27,592 INFO L225 Difference]: With dead ends: 12 [2018-07-25 08:50:27,592 INFO L226 Difference]: Without dead ends: 10 [2018-07-25 08:50:27,593 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 08:50:27,593 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10 states. [2018-07-25 08:50:27,596 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-07-25 08:50:27,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2018-07-25 08:50:27,597 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-07-25 08:50:27,598 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-07-25 08:50:27,598 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:27,598 INFO L472 AbstractCegarLoop]: Abstraction has 10 states and 10 transitions. [2018-07-25 08:50:27,598 INFO L473 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-07-25 08:50:27,599 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 10 transitions. [2018-07-25 08:50:27,599 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-07-25 08:50:27,599 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:27,600 INFO L354 BasicCegarLoop]: trace histogram [6, 1, 1, 1] [2018-07-25 08:50:27,600 INFO L415 AbstractCegarLoop]: === Iteration 7 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:27,600 INFO L82 PathProgramCache]: Analyzing trace with hash 1853141856, now seen corresponding path program 6 times [2018-07-25 08:50:27,601 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:27,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:28,019 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 08:50:28,019 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:28,020 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2018-07-25 08:50:28,020 INFO L451 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-07-25 08:50:28,021 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-07-25 08:50:28,021 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-07-25 08:50:28,021 INFO L87 Difference]: Start difference. First operand 10 states and 10 transitions. Second operand 10 states. [2018-07-25 08:50:28,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:28,102 INFO L93 Difference]: Finished difference Result 13 states and 13 transitions. [2018-07-25 08:50:28,104 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-07-25 08:50:28,104 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 9 [2018-07-25 08:50:28,104 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:28,105 INFO L225 Difference]: With dead ends: 13 [2018-07-25 08:50:28,105 INFO L226 Difference]: Without dead ends: 11 [2018-07-25 08:50:28,107 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-07-25 08:50:28,107 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2018-07-25 08:50:28,113 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-07-25 08:50:28,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2018-07-25 08:50:28,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-07-25 08:50:28,115 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-07-25 08:50:28,115 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:28,115 INFO L472 AbstractCegarLoop]: Abstraction has 11 states and 11 transitions. [2018-07-25 08:50:28,115 INFO L473 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-07-25 08:50:28,116 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 11 transitions. [2018-07-25 08:50:28,116 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-07-25 08:50:28,118 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:28,118 INFO L354 BasicCegarLoop]: trace histogram [7, 1, 1, 1] [2018-07-25 08:50:28,119 INFO L415 AbstractCegarLoop]: === Iteration 8 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:28,119 INFO L82 PathProgramCache]: Analyzing trace with hash 1612820742, now seen corresponding path program 7 times [2018-07-25 08:50:28,119 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:28,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:28,690 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 08:50:28,690 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:28,691 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-07-25 08:50:28,691 INFO L451 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-07-25 08:50:28,692 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-07-25 08:50:28,692 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-07-25 08:50:28,692 INFO L87 Difference]: Start difference. First operand 11 states and 11 transitions. Second operand 11 states. [2018-07-25 08:50:28,811 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:28,811 INFO L93 Difference]: Finished difference Result 14 states and 14 transitions. [2018-07-25 08:50:28,811 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-07-25 08:50:28,811 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 10 [2018-07-25 08:50:28,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:28,814 INFO L225 Difference]: With dead ends: 14 [2018-07-25 08:50:28,815 INFO L226 Difference]: Without dead ends: 12 [2018-07-25 08:50:28,815 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=55, Invalid=155, Unknown=0, NotChecked=0, Total=210 [2018-07-25 08:50:28,816 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2018-07-25 08:50:28,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-07-25 08:50:28,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 12 states. [2018-07-25 08:50:28,824 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-07-25 08:50:28,824 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-07-25 08:50:28,825 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:28,825 INFO L472 AbstractCegarLoop]: Abstraction has 12 states and 12 transitions. [2018-07-25 08:50:28,825 INFO L473 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-07-25 08:50:28,825 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 12 transitions. [2018-07-25 08:50:28,826 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-07-25 08:50:28,826 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:28,826 INFO L354 BasicCegarLoop]: trace histogram [8, 1, 1, 1] [2018-07-25 08:50:28,826 INFO L415 AbstractCegarLoop]: === Iteration 9 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:28,827 INFO L82 PathProgramCache]: Analyzing trace with hash -1542166496, now seen corresponding path program 8 times [2018-07-25 08:50:28,827 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:28,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:29,427 WARN L169 SmtUtils]: Spent 161.00 ms on a formula simplification. DAG size of input: 147 DAG size of output: 44 [2018-07-25 08:50:29,660 WARN L169 SmtUtils]: Spent 169.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 57 [2018-07-25 08:50:29,675 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 08:50:29,675 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:29,675 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2018-07-25 08:50:29,676 INFO L451 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-07-25 08:50:29,676 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-07-25 08:50:29,676 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-07-25 08:50:29,677 INFO L87 Difference]: Start difference. First operand 12 states and 12 transitions. Second operand 12 states. [2018-07-25 08:50:29,773 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:29,773 INFO L93 Difference]: Finished difference Result 15 states and 15 transitions. [2018-07-25 08:50:29,773 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-07-25 08:50:29,773 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 11 [2018-07-25 08:50:29,774 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:29,774 INFO L225 Difference]: With dead ends: 15 [2018-07-25 08:50:29,774 INFO L226 Difference]: Without dead ends: 13 [2018-07-25 08:50:29,775 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 08:50:29,776 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2018-07-25 08:50:29,780 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-07-25 08:50:29,780 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13 states. [2018-07-25 08:50:29,781 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-07-25 08:50:29,781 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-07-25 08:50:29,781 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:29,782 INFO L472 AbstractCegarLoop]: Abstraction has 13 states and 13 transitions. [2018-07-25 08:50:29,782 INFO L473 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-07-25 08:50:29,782 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 13 transitions. [2018-07-25 08:50:29,783 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-07-25 08:50:29,783 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:29,783 INFO L354 BasicCegarLoop]: trace histogram [9, 1, 1, 1] [2018-07-25 08:50:29,783 INFO L415 AbstractCegarLoop]: === Iteration 10 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:29,784 INFO L82 PathProgramCache]: Analyzing trace with hash -562523066, now seen corresponding path program 9 times [2018-07-25 08:50:29,784 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:29,805 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:30,334 WARN L169 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 34 [2018-07-25 08:50:30,595 WARN L169 SmtUtils]: Spent 198.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 52 [2018-07-25 08:50:30,916 WARN L169 SmtUtils]: Spent 232.00 ms on a formula simplification. DAG size of input: 212 DAG size of output: 59 [2018-07-25 08:50:30,933 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 08:50:30,933 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:30,933 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2018-07-25 08:50:30,934 INFO L451 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-07-25 08:50:30,934 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-07-25 08:50:30,935 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2018-07-25 08:50:30,936 INFO L87 Difference]: Start difference. First operand 13 states and 13 transitions. Second operand 13 states. [2018-07-25 08:50:31,077 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:31,077 INFO L93 Difference]: Finished difference Result 16 states and 16 transitions. [2018-07-25 08:50:31,077 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-07-25 08:50:31,077 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 12 [2018-07-25 08:50:31,078 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:31,078 INFO L225 Difference]: With dead ends: 16 [2018-07-25 08:50:31,078 INFO L226 Difference]: Without dead ends: 14 [2018-07-25 08:50:31,079 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-07-25 08:50:31,079 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2018-07-25 08:50:31,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-07-25 08:50:31,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2018-07-25 08:50:31,085 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-07-25 08:50:31,085 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-07-25 08:50:31,085 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:31,086 INFO L472 AbstractCegarLoop]: Abstraction has 14 states and 14 transitions. [2018-07-25 08:50:31,086 INFO L473 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-07-25 08:50:31,086 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 14 transitions. [2018-07-25 08:50:31,086 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-07-25 08:50:31,086 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:31,087 INFO L354 BasicCegarLoop]: trace histogram [10, 1, 1, 1] [2018-07-25 08:50:31,087 INFO L415 AbstractCegarLoop]: === Iteration 11 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:31,087 INFO L82 PathProgramCache]: Analyzing trace with hash -258347808, now seen corresponding path program 10 times [2018-07-25 08:50:31,087 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:31,115 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:31,819 WARN L169 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 61 [2018-07-25 08:50:32,225 WARN L169 SmtUtils]: Spent 301.00 ms on a formula simplification. DAG size of input: 327 DAG size of output: 56 [2018-07-25 08:50:32,493 WARN L169 SmtUtils]: Spent 161.00 ms on a formula simplification. DAG size of input: 440 DAG size of output: 80 [2018-07-25 08:50:32,509 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 08:50:32,509 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:32,510 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-07-25 08:50:32,510 INFO L451 AbstractCegarLoop]: Interpolant automaton has 14 states [2018-07-25 08:50:32,510 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2018-07-25 08:50:32,511 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2018-07-25 08:50:32,511 INFO L87 Difference]: Start difference. First operand 14 states and 14 transitions. Second operand 14 states. [2018-07-25 08:50:32,834 WARN L169 SmtUtils]: Spent 123.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 76 [2018-07-25 08:50:32,927 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:32,927 INFO L93 Difference]: Finished difference Result 17 states and 17 transitions. [2018-07-25 08:50:32,927 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-07-25 08:50:32,927 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 13 [2018-07-25 08:50:32,928 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:32,928 INFO L225 Difference]: With dead ends: 17 [2018-07-25 08:50:32,929 INFO L226 Difference]: Without dead ends: 15 [2018-07-25 08:50:32,930 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=102, Invalid=240, Unknown=0, NotChecked=0, Total=342 [2018-07-25 08:50:32,930 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2018-07-25 08:50:32,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-07-25 08:50:32,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2018-07-25 08:50:32,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-07-25 08:50:32,939 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-07-25 08:50:32,940 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:32,940 INFO L472 AbstractCegarLoop]: Abstraction has 15 states and 15 transitions. [2018-07-25 08:50:32,940 INFO L473 AbstractCegarLoop]: Interpolant automaton has 14 states. [2018-07-25 08:50:32,940 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 15 transitions. [2018-07-25 08:50:32,941 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-07-25 08:50:32,941 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:32,941 INFO L354 BasicCegarLoop]: trace histogram [11, 1, 1, 1] [2018-07-25 08:50:32,942 INFO L415 AbstractCegarLoop]: === Iteration 12 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:32,942 INFO L82 PathProgramCache]: Analyzing trace with hash 581150598, now seen corresponding path program 11 times [2018-07-25 08:50:32,942 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:32,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:33,594 WARN L169 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 64 [2018-07-25 08:50:33,812 WARN L169 SmtUtils]: Spent 174.00 ms on a formula simplification. DAG size of input: 183 DAG size of output: 54 [2018-07-25 08:50:34,091 WARN L169 SmtUtils]: Spent 208.00 ms on a formula simplification. DAG size of input: 307 DAG size of output: 96 [2018-07-25 08:50:34,640 WARN L169 SmtUtils]: Spent 440.00 ms on a formula simplification. DAG size of input: 389 DAG size of output: 81 [2018-07-25 08:50:35,457 WARN L169 SmtUtils]: Spent 672.00 ms on a formula simplification. DAG size of input: 498 DAG size of output: 79 [2018-07-25 08:50:36,705 WARN L169 SmtUtils]: Spent 1.06 s on a formula simplification. DAG size of input: 582 DAG size of output: 90 [2018-07-25 08:50:36,722 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 08:50:36,722 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:36,722 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-07-25 08:50:36,723 INFO L451 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-07-25 08:50:36,723 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-07-25 08:50:36,723 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2018-07-25 08:50:36,724 INFO L87 Difference]: Start difference. First operand 15 states and 15 transitions. Second operand 15 states. [2018-07-25 08:50:37,001 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:37,001 INFO L93 Difference]: Finished difference Result 18 states and 18 transitions. [2018-07-25 08:50:37,001 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-07-25 08:50:37,001 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 14 [2018-07-25 08:50:37,002 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:37,002 INFO L225 Difference]: With dead ends: 18 [2018-07-25 08:50:37,003 INFO L226 Difference]: Without dead ends: 16 [2018-07-25 08:50:37,004 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 08:50:37,004 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2018-07-25 08:50:37,012 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-07-25 08:50:37,013 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16 states. [2018-07-25 08:50:37,014 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-07-25 08:50:37,015 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 14 [2018-07-25 08:50:37,015 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:37,015 INFO L472 AbstractCegarLoop]: Abstraction has 16 states and 16 transitions. [2018-07-25 08:50:37,015 INFO L473 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-07-25 08:50:37,015 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 16 transitions. [2018-07-25 08:50:37,016 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-07-25 08:50:37,016 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:37,017 INFO L354 BasicCegarLoop]: trace histogram [12, 1, 1, 1] [2018-07-25 08:50:37,018 INFO L415 AbstractCegarLoop]: === Iteration 13 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:37,018 INFO L82 PathProgramCache]: Analyzing trace with hash 835797408, now seen corresponding path program 12 times [2018-07-25 08:50:37,018 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:37,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:37,689 WARN L169 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 225 DAG size of output: 38 [2018-07-25 08:50:37,949 WARN L169 SmtUtils]: Spent 165.00 ms on a formula simplification. DAG size of input: 367 DAG size of output: 40 [2018-07-25 08:50:38,536 WARN L169 SmtUtils]: Spent 430.00 ms on a formula simplification. DAG size of input: 483 DAG size of output: 45 [2018-07-25 08:50:39,816 WARN L169 SmtUtils]: Spent 1.07 s on a formula simplification. DAG size of input: 985 DAG size of output: 170 [2018-07-25 08:50:41,100 WARN L169 SmtUtils]: Spent 1.07 s on a formula simplification. DAG size of input: 1009 DAG size of output: 125 [2018-07-25 08:50:41,120 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 08:50:41,121 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:41,121 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2018-07-25 08:50:41,121 INFO L451 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-07-25 08:50:41,122 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-07-25 08:50:41,122 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=190, Unknown=0, NotChecked=0, Total=240 [2018-07-25 08:50:41,122 INFO L87 Difference]: Start difference. First operand 16 states and 16 transitions. Second operand 16 states. [2018-07-25 08:50:41,267 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:41,267 INFO L93 Difference]: Finished difference Result 19 states and 19 transitions. [2018-07-25 08:50:41,267 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-07-25 08:50:41,267 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 15 [2018-07-25 08:50:41,268 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:41,268 INFO L225 Difference]: With dead ends: 19 [2018-07-25 08:50:41,268 INFO L226 Difference]: Without dead ends: 17 [2018-07-25 08:50:41,269 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2018-07-25 08:50:41,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2018-07-25 08:50:41,277 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-07-25 08:50:41,278 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2018-07-25 08:50:41,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-07-25 08:50:41,278 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 15 [2018-07-25 08:50:41,279 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:41,279 INFO L472 AbstractCegarLoop]: Abstraction has 17 states and 17 transitions. [2018-07-25 08:50:41,279 INFO L473 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-07-25 08:50:41,279 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 17 transitions. [2018-07-25 08:50:41,280 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-07-25 08:50:41,280 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:41,280 INFO L354 BasicCegarLoop]: trace histogram [13, 1, 1, 1] [2018-07-25 08:50:41,280 INFO L415 AbstractCegarLoop]: === Iteration 14 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:41,281 INFO L82 PathProgramCache]: Analyzing trace with hash 139913926, now seen corresponding path program 13 times [2018-07-25 08:50:41,281 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:41,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:42,230 WARN L169 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 391 DAG size of output: 40 [2018-07-25 08:50:42,877 WARN L169 SmtUtils]: Spent 487.00 ms on a formula simplification. DAG size of input: 506 DAG size of output: 44 [2018-07-25 08:50:43,571 WARN L169 SmtUtils]: Spent 490.00 ms on a formula simplification. DAG size of input: 607 DAG size of output: 48 [2018-07-25 08:50:44,744 WARN L169 SmtUtils]: Spent 894.00 ms on a formula simplification. DAG size of input: 939 DAG size of output: 76 [2018-07-25 08:50:46,339 WARN L169 SmtUtils]: Spent 1.16 s on a formula simplification. DAG size of input: 1530 DAG size of output: 94 [2018-07-25 08:50:46,355 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 08:50:46,355 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:46,356 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-07-25 08:50:46,356 INFO L451 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-07-25 08:50:46,356 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-07-25 08:50:46,357 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2018-07-25 08:50:46,357 INFO L87 Difference]: Start difference. First operand 17 states and 17 transitions. Second operand 17 states. [2018-07-25 08:50:46,509 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:46,509 INFO L93 Difference]: Finished difference Result 20 states and 20 transitions. [2018-07-25 08:50:46,509 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-07-25 08:50:46,510 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 16 [2018-07-25 08:50:46,510 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:46,510 INFO L225 Difference]: With dead ends: 20 [2018-07-25 08:50:46,510 INFO L226 Difference]: Without dead ends: 18 [2018-07-25 08:50:46,511 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2018-07-25 08:50:46,511 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2018-07-25 08:50:46,519 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-07-25 08:50:46,519 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18 states. [2018-07-25 08:50:46,520 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 18 transitions. [2018-07-25 08:50:46,520 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 18 transitions. Word has length 16 [2018-07-25 08:50:46,520 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:46,521 INFO L472 AbstractCegarLoop]: Abstraction has 18 states and 18 transitions. [2018-07-25 08:50:46,521 INFO L473 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-07-25 08:50:46,521 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 18 transitions. [2018-07-25 08:50:46,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-07-25 08:50:46,521 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:46,522 INFO L354 BasicCegarLoop]: trace histogram [14, 1, 1, 1] [2018-07-25 08:50:46,522 INFO L415 AbstractCegarLoop]: === Iteration 15 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:46,522 INFO L82 PathProgramCache]: Analyzing trace with hash 42362464, now seen corresponding path program 14 times [2018-07-25 08:50:46,522 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:46,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:47,622 WARN L169 SmtUtils]: Spent 158.00 ms on a formula simplification. DAG size of input: 373 DAG size of output: 41 [2018-07-25 08:50:48,096 WARN L169 SmtUtils]: Spent 337.00 ms on a formula simplification. DAG size of input: 473 DAG size of output: 45 [2018-07-25 08:50:48,734 WARN L169 SmtUtils]: Spent 446.00 ms on a formula simplification. DAG size of input: 637 DAG size of output: 49 [2018-07-25 08:50:49,829 WARN L169 SmtUtils]: Spent 837.00 ms on a formula simplification. DAG size of input: 768 DAG size of output: 52 [2018-07-25 08:50:51,576 WARN L169 SmtUtils]: Spent 1.32 s on a formula simplification. DAG size of input: 1621 DAG size of output: 90 [2018-07-25 08:50:54,798 WARN L169 SmtUtils]: Spent 2.51 s on a formula simplification. DAG size of input: 2892 DAG size of output: 95 [2018-07-25 08:50:54,814 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 08:50:54,814 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:50:54,815 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2018-07-25 08:50:54,815 INFO L451 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-07-25 08:50:54,815 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-07-25 08:50:54,815 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2018-07-25 08:50:54,816 INFO L87 Difference]: Start difference. First operand 18 states and 18 transitions. Second operand 18 states. [2018-07-25 08:50:54,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:50:54,971 INFO L93 Difference]: Finished difference Result 21 states and 21 transitions. [2018-07-25 08:50:54,972 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-07-25 08:50:54,972 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 17 [2018-07-25 08:50:54,972 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:50:54,973 INFO L225 Difference]: With dead ends: 21 [2018-07-25 08:50:54,973 INFO L226 Difference]: Without dead ends: 19 [2018-07-25 08:50:54,973 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 7.3s TimeCoverageRelationStatistics Valid=62, Invalid=280, Unknown=0, NotChecked=0, Total=342 [2018-07-25 08:50:54,973 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2018-07-25 08:50:54,982 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-07-25 08:50:54,982 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-07-25 08:50:54,982 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-07-25 08:50:54,983 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 17 [2018-07-25 08:50:54,983 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:50:54,983 INFO L472 AbstractCegarLoop]: Abstraction has 19 states and 19 transitions. [2018-07-25 08:50:54,983 INFO L473 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-07-25 08:50:54,983 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 19 transitions. [2018-07-25 08:50:54,984 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-07-25 08:50:54,984 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:50:54,984 INFO L354 BasicCegarLoop]: trace histogram [15, 1, 1, 1] [2018-07-25 08:50:54,984 INFO L415 AbstractCegarLoop]: === Iteration 16 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:50:54,984 INFO L82 PathProgramCache]: Analyzing trace with hash 1313234438, now seen corresponding path program 15 times [2018-07-25 08:50:54,985 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:50:55,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:50:55,959 WARN L169 SmtUtils]: Spent 129.00 ms on a formula simplification. DAG size of input: 348 DAG size of output: 40 [2018-07-25 08:50:56,245 WARN L169 SmtUtils]: Spent 166.00 ms on a formula simplification. DAG size of input: 425 DAG size of output: 44 [2018-07-25 08:50:57,301 WARN L169 SmtUtils]: Spent 833.00 ms on a formula simplification. DAG size of input: 1062 DAG size of output: 49 [2018-07-25 08:50:58,985 WARN L169 SmtUtils]: Spent 1.44 s on a formula simplification. DAG size of input: 1325 DAG size of output: 52 [2018-07-25 08:51:01,624 WARN L169 SmtUtils]: Spent 2.30 s on a formula simplification. DAG size of input: 2123 DAG size of output: 57 [2018-07-25 08:51:07,461 WARN L169 SmtUtils]: Spent 5.42 s on a formula simplification. DAG size of input: 2449 DAG size of output: 159 [2018-07-25 08:51:10,503 WARN L169 SmtUtils]: Spent 2.60 s on a formula simplification. DAG size of input: 2239 DAG size of output: 158 [2018-07-25 08:51:10,517 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 08:51:10,518 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:51:10,518 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-07-25 08:51:10,518 INFO L451 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-07-25 08:51:10,519 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-07-25 08:51:10,519 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=280, Unknown=0, NotChecked=0, Total=342 [2018-07-25 08:51:10,519 INFO L87 Difference]: Start difference. First operand 19 states and 19 transitions. Second operand 19 states. [2018-07-25 08:51:10,714 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:51:10,715 INFO L93 Difference]: Finished difference Result 22 states and 22 transitions. [2018-07-25 08:51:10,715 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-07-25 08:51:10,715 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 18 [2018-07-25 08:51:10,715 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:51:10,716 INFO L225 Difference]: With dead ends: 22 [2018-07-25 08:51:10,716 INFO L226 Difference]: Without dead ends: 20 [2018-07-25 08:51:10,716 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 14.6s TimeCoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2018-07-25 08:51:10,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2018-07-25 08:51:10,725 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2018-07-25 08:51:10,725 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 20 states. [2018-07-25 08:51:10,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 20 transitions. [2018-07-25 08:51:10,726 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 20 transitions. Word has length 18 [2018-07-25 08:51:10,726 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:51:10,726 INFO L472 AbstractCegarLoop]: Abstraction has 20 states and 20 transitions. [2018-07-25 08:51:10,726 INFO L473 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-07-25 08:51:10,726 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 20 transitions. [2018-07-25 08:51:10,727 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-07-25 08:51:10,727 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:51:10,727 INFO L354 BasicCegarLoop]: trace histogram [16, 1, 1, 1] [2018-07-25 08:51:10,727 INFO L415 AbstractCegarLoop]: === Iteration 17 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:51:10,728 INFO L82 PathProgramCache]: Analyzing trace with hash 2055559968, now seen corresponding path program 16 times [2018-07-25 08:51:10,728 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:51:10,769 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:51:12,273 WARN L169 SmtUtils]: Spent 164.00 ms on a formula simplification. DAG size of input: 444 DAG size of output: 45 [2018-07-25 08:51:13,008 WARN L169 SmtUtils]: Spent 543.00 ms on a formula simplification. DAG size of input: 995 DAG size of output: 48 [2018-07-25 08:51:14,827 WARN L169 SmtUtils]: Spent 1.58 s on a formula simplification. DAG size of input: 1311 DAG size of output: 52 [2018-07-25 08:51:17,986 WARN L169 SmtUtils]: Spent 2.77 s on a formula simplification. DAG size of input: 1626 DAG size of output: 57 [2018-07-25 08:51:26,478 WARN L169 SmtUtils]: Spent 7.82 s on a formula simplification. DAG size of input: 2313 DAG size of output: 61 [2018-07-25 08:51:39,625 WARN L169 SmtUtils]: Spent 12.39 s on a formula simplification. DAG size of input: 2780 DAG size of output: 109 [2018-07-25 08:51:59,635 WARN L169 SmtUtils]: Spent 18.73 s on a formula simplification. DAG size of input: 3963 DAG size of output: 114 [2018-07-25 08:51:59,650 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 08:51:59,651 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:51:59,651 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2018-07-25 08:51:59,651 INFO L451 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-07-25 08:51:59,651 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-07-25 08:51:59,652 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2018-07-25 08:51:59,652 INFO L87 Difference]: Start difference. First operand 20 states and 20 transitions. Second operand 20 states. [2018-07-25 08:51:59,829 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:51:59,829 INFO L93 Difference]: Finished difference Result 23 states and 23 transitions. [2018-07-25 08:51:59,829 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-07-25 08:51:59,830 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 19 [2018-07-25 08:51:59,830 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:51:59,830 INFO L225 Difference]: With dead ends: 23 [2018-07-25 08:51:59,830 INFO L226 Difference]: Without dead ends: 21 [2018-07-25 08:51:59,831 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 47.2s TimeCoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2018-07-25 08:51:59,831 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2018-07-25 08:51:59,841 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-07-25 08:51:59,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-07-25 08:51:59,841 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 21 transitions. [2018-07-25 08:51:59,842 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 21 transitions. Word has length 19 [2018-07-25 08:51:59,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:51:59,842 INFO L472 AbstractCegarLoop]: Abstraction has 21 states and 21 transitions. [2018-07-25 08:51:59,842 INFO L473 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-07-25 08:51:59,842 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 21 transitions. [2018-07-25 08:51:59,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-07-25 08:51:59,843 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:51:59,843 INFO L354 BasicCegarLoop]: trace histogram [17, 1, 1, 1] [2018-07-25 08:51:59,843 INFO L415 AbstractCegarLoop]: === Iteration 18 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:51:59,843 INFO L82 PathProgramCache]: Analyzing trace with hash -702152378, now seen corresponding path program 17 times [2018-07-25 08:51:59,844 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:51:59,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:52:01,601 WARN L169 SmtUtils]: Spent 123.00 ms on a formula simplification. DAG size of input: 356 DAG size of output: 38 [2018-07-25 08:52:02,021 WARN L169 SmtUtils]: Spent 343.00 ms on a formula simplification. DAG size of input: 466 DAG size of output: 42 [2018-07-25 08:52:02,513 WARN L169 SmtUtils]: Spent 379.00 ms on a formula simplification. DAG size of input: 550 DAG size of output: 47 [2018-07-25 08:52:03,486 WARN L169 SmtUtils]: Spent 809.00 ms on a formula simplification. DAG size of input: 744 DAG size of output: 52 [2018-07-25 08:52:05,540 WARN L169 SmtUtils]: Spent 1.79 s on a formula simplification. DAG size of input: 1123 DAG size of output: 59 [2018-07-25 08:52:09,303 WARN L169 SmtUtils]: Spent 3.42 s on a formula simplification. DAG size of input: 1482 DAG size of output: 106 [2018-07-25 08:52:17,371 WARN L169 SmtUtils]: Spent 7.47 s on a formula simplification. DAG size of input: 2585 DAG size of output: 164 [2018-07-25 08:52:36,418 WARN L169 SmtUtils]: Spent 18.09 s on a formula simplification. DAG size of input: 3233 DAG size of output: 143 [2018-07-25 08:52:47,302 WARN L169 SmtUtils]: Spent 9.98 s on a formula simplification. DAG size of input: 3190 DAG size of output: 147 [2018-07-25 08:53:00,218 WARN L169 SmtUtils]: Spent 11.75 s on a formula simplification. DAG size of input: 4334 DAG size of output: 136 [2018-07-25 08:53:00,240 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 08:53:00,240 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:53:00,240 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-07-25 08:53:00,241 INFO L451 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-07-25 08:53:00,241 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-07-25 08:53:00,241 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=312, Unknown=0, NotChecked=0, Total=420 [2018-07-25 08:53:00,241 INFO L87 Difference]: Start difference. First operand 21 states and 21 transitions. Second operand 21 states. [2018-07-25 08:53:00,726 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:53:00,727 INFO L93 Difference]: Finished difference Result 24 states and 24 transitions. [2018-07-25 08:53:00,727 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-07-25 08:53:00,727 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 20 [2018-07-25 08:53:00,727 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:53:00,728 INFO L225 Difference]: With dead ends: 24 [2018-07-25 08:53:00,728 INFO L226 Difference]: Without dead ends: 22 [2018-07-25 08:53:00,728 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 58.5s TimeCoverageRelationStatistics Valid=177, Invalid=473, Unknown=0, NotChecked=0, Total=650 [2018-07-25 08:53:00,729 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-07-25 08:53:00,739 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-07-25 08:53:00,740 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2018-07-25 08:53:00,740 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 22 transitions. [2018-07-25 08:53:00,741 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 22 transitions. Word has length 20 [2018-07-25 08:53:00,741 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:53:00,741 INFO L472 AbstractCegarLoop]: Abstraction has 22 states and 22 transitions. [2018-07-25 08:53:00,741 INFO L473 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-07-25 08:53:00,741 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 22 transitions. [2018-07-25 08:53:00,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-07-25 08:53:00,742 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:53:00,742 INFO L354 BasicCegarLoop]: trace histogram [18, 1, 1, 1] [2018-07-25 08:53:00,742 INFO L415 AbstractCegarLoop]: === Iteration 19 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:53:00,743 INFO L82 PathProgramCache]: Analyzing trace with hash -291889184, now seen corresponding path program 18 times [2018-07-25 08:53:00,743 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:53:00,786 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:53:02,798 WARN L169 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 404 DAG size of output: 40 [2018-07-25 08:53:03,203 WARN L169 SmtUtils]: Spent 310.00 ms on a formula simplification. DAG size of input: 513 DAG size of output: 45 [2018-07-25 08:53:04,444 WARN L169 SmtUtils]: Spent 1.04 s on a formula simplification. DAG size of input: 1120 DAG size of output: 49 [2018-07-25 08:53:06,937 WARN L169 SmtUtils]: Spent 2.18 s on a formula simplification. DAG size of input: 1425 DAG size of output: 52 [2018-07-25 08:53:12,209 WARN L169 SmtUtils]: Spent 4.62 s on a formula simplification. DAG size of input: 2205 DAG size of output: 57 [2018-07-25 08:53:22,699 WARN L169 SmtUtils]: Spent 9.73 s on a formula simplification. DAG size of input: 2874 DAG size of output: 61 [2018-07-25 08:53:33,021 WARN L169 SmtUtils]: Spent 9.36 s on a formula simplification. DAG size of input: 3673 DAG size of output: 65 [2018-07-25 08:53:47,908 WARN L169 SmtUtils]: Spent 13.75 s on a formula simplification. DAG size of input: 3837 DAG size of output: 69 [2018-07-25 08:54:08,200 WARN L169 SmtUtils]: Spent 18.95 s on a formula simplification. DAG size of input: 4745 DAG size of output: 130 [2018-07-25 08:54:38,096 WARN L169 SmtUtils]: Spent 28.12 s on a formula simplification. DAG size of input: 6452 DAG size of output: 155 [2018-07-25 08:54:38,114 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 08:54:38,114 INFO L309 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-07-25 08:54:38,114 INFO L324 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2018-07-25 08:54:38,114 INFO L451 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-07-25 08:54:38,115 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-07-25 08:54:38,115 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=388, Unknown=0, NotChecked=0, Total=462 [2018-07-25 08:54:38,115 INFO L87 Difference]: Start difference. First operand 22 states and 22 transitions. Second operand 22 states. [2018-07-25 08:54:38,354 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-07-25 08:54:38,354 INFO L93 Difference]: Finished difference Result 25 states and 25 transitions. [2018-07-25 08:54:38,354 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-07-25 08:54:38,355 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 21 [2018-07-25 08:54:38,355 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-07-25 08:54:38,355 INFO L225 Difference]: With dead ends: 25 [2018-07-25 08:54:38,355 INFO L226 Difference]: Without dead ends: 23 [2018-07-25 08:54:38,356 INFO L574 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 94.2s TimeCoverageRelationStatistics Valid=78, Invalid=428, Unknown=0, NotChecked=0, Total=506 [2018-07-25 08:54:38,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2018-07-25 08:54:38,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-07-25 08:54:38,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-07-25 08:54:38,367 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2018-07-25 08:54:38,367 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 21 [2018-07-25 08:54:38,368 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-07-25 08:54:38,368 INFO L472 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2018-07-25 08:54:38,368 INFO L473 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-07-25 08:54:38,368 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2018-07-25 08:54:38,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-07-25 08:54:38,369 INFO L346 BasicCegarLoop]: Found error trace [2018-07-25 08:54:38,369 INFO L354 BasicCegarLoop]: trace histogram [19, 1, 1, 1] [2018-07-25 08:54:38,369 INFO L415 AbstractCegarLoop]: === Iteration 20 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-07-25 08:54:38,369 INFO L82 PathProgramCache]: Analyzing trace with hash -458632058, now seen corresponding path program 19 times [2018-07-25 08:54:38,369 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-07-25 08:54:38,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-07-25 08:54:42,023 WARN L169 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 254 DAG size of output: 68 [2018-07-25 08:54:42,456 WARN L169 SmtUtils]: Spent 313.00 ms on a formula simplification. DAG size of input: 468 DAG size of output: 97 [2018-07-25 08:54:42,987 WARN L169 SmtUtils]: Spent 341.00 ms on a formula simplification. DAG size of input: 490 DAG size of output: 101 [2018-07-25 08:54:44,573 WARN L169 SmtUtils]: Spent 1.27 s on a formula simplification. DAG size of input: 837 DAG size of output: 118 [2018-07-25 08:54:46,155 WARN L169 SmtUtils]: Spent 1.18 s on a formula simplification. DAG size of input: 1021 DAG size of output: 101 Received shutdown request... [2018-07-25 08:54:47,440 WARN L177 SmtUtils]: Removed 2 from assertion stack [2018-07-25 08:54:47,441 WARN L541 AbstractCegarLoop]: Verification canceled [2018-07-25 08:54:47,446 WARN L202 ceAbstractionStarter]: Timeout [2018-07-25 08:54:47,447 INFO L202 PluginConnector]: Adding new model ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.07 08:54:47 BoogieIcfgContainer [2018-07-25 08:54:47,447 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-07-25 08:54:47,448 INFO L168 Benchmark]: Toolchain (without parser) took 261821.41 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.4 GB in the end (delta: 81.6 MB). Peak memory consumption was 2.1 GB. Max. memory is 7.1 GB. [2018-07-25 08:54:47,449 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.21 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 08:54:47,449 INFO L168 Benchmark]: Boogie Procedure Inliner took 43.01 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 08:54:47,450 INFO L168 Benchmark]: Boogie Preprocessor took 22.47 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 08:54:47,450 INFO L168 Benchmark]: RCFGBuilder took 217.92 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. [2018-07-25 08:54:47,451 INFO L168 Benchmark]: TraceAbstraction took 261533.55 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.4 GB in the beginning and 1.4 GB in the end (delta: 71.1 MB). Peak memory consumption was 2.1 GB. Max. memory is 7.1 GB. [2018-07-25 08:54:47,455 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.21 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 43.01 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. * Boogie Preprocessor took 22.47 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 217.92 ms. Allocated memory is still 1.5 GB. Free memory was 1.5 GB in the beginning and 1.4 GB in the end (delta: 10.6 MB). Peak memory consumption was 10.6 MB. Max. memory is 7.1 GB. * TraceAbstraction took 261533.55 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.4 GB in the beginning and 1.4 GB in the end (delta: 71.1 MB). Peak memory consumption was 2.1 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 1201. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 6 locations, 1 error locations. TIMEOUT Result, 261.4s OverallTime, 20 OverallIterations, 19 TraceHistogramMax, 3.1s 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, 238.1s 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.4s SatisfiabilityAnalysisTime, 248.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_08-54-47-468.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_08-54-47-468.csv Completed graceful shutdown