java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc ../../../trunk/examples/toolchains/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-ff8eab6 [2018-09-26 08:20:18,861 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-09-26 08:20:18,863 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-09-26 08:20:18,877 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-09-26 08:20:18,877 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-09-26 08:20:18,879 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-09-26 08:20:18,880 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-09-26 08:20:18,883 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-09-26 08:20:18,886 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-09-26 08:20:18,888 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-09-26 08:20:18,889 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-09-26 08:20:18,889 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-09-26 08:20:18,891 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-09-26 08:20:18,899 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-09-26 08:20:18,900 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-09-26 08:20:18,901 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-09-26 08:20:18,901 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-09-26 08:20:18,903 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-09-26 08:20:18,909 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-09-26 08:20:18,913 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-09-26 08:20:18,914 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-09-26 08:20:18,915 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-09-26 08:20:18,919 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-09-26 08:20:18,919 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-09-26 08:20:18,920 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-09-26 08:20:18,926 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-09-26 08:20:18,928 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-09-26 08:20:18,931 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-09-26 08:20:18,932 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-09-26 08:20:18,933 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-09-26 08:20:18,933 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-09-26 08:20:18,935 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-09-26 08:20:18,935 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-09-26 08:20:18,935 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-09-26 08:20:18,937 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-09-26 08:20:18,937 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-09-26 08:20:18,939 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/Pdr/AutomizerBpl-nestedInterpolants.epf [2018-09-26 08:20:18,953 INFO L110 SettingsManager]: Loading preferences was successful [2018-09-26 08:20:18,953 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-09-26 08:20:18,955 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-09-26 08:20:18,955 INFO L133 SettingsManager]: * SMT solver=Internal_SMTInterpol [2018-09-26 08:20:18,955 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-09-26 08:20:18,956 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2018-09-26 08:20:18,956 INFO L133 SettingsManager]: * Use separate solver for trace checks=false [2018-09-26 08:20:18,956 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-09-26 08:20:19,002 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-09-26 08:20:19,024 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-09-26 08:20:19,031 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-09-26 08:20:19,033 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-09-26 08:20:19,033 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-09-26 08:20:19,034 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/ArrayInit01.bpl [2018-09-26 08:20:19,034 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/toy/tooDifficultLoopInvariant/ArrayInit01.bpl' [2018-09-26 08:20:19,083 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-09-26 08:20:19,086 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-09-26 08:20:19,087 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2018-09-26 08:20:19,087 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2018-09-26 08:20:19,087 INFO L276 PluginConnector]: Boogie Procedure Inliner initialized [2018-09-26 08:20:19,107 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,123 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,128 WARN L165 Inliner]: Program contained no entry procedure! [2018-09-26 08:20:19,129 WARN L168 Inliner]: Missing entry procedures: [ULTIMATE.start] [2018-09-26 08:20:19,129 WARN L175 Inliner]: Fallback enabled. All procedures will be processed. [2018-09-26 08:20:19,131 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2018-09-26 08:20:19,132 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-09-26 08:20:19,132 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-09-26 08:20:19,132 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-09-26 08:20:19,144 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,144 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,145 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,145 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,150 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,155 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,156 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,158 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-09-26 08:20:19,159 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-09-26 08:20:19,159 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-09-26 08:20:19,159 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-09-26 08:20:19,162 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/1) ... [2018-09-26 08:20:19,257 INFO L124 BoogieDeclarations]: Specification and implementation of procedure main given in one single declaration [2018-09-26 08:20:19,257 INFO L130 BoogieDeclarations]: Found specification of procedure main [2018-09-26 08:20:19,257 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2018-09-26 08:20:19,424 INFO L343 CfgBuilder]: Using library mode [2018-09-26 08:20:19,425 INFO L202 PluginConnector]: Adding new model ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.09 08:20:19 BoogieIcfgContainer [2018-09-26 08:20:19,425 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-09-26 08:20:19,426 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-09-26 08:20:19,427 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-09-26 08:20:19,431 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-09-26 08:20:19,432 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 26.09 08:20:19" (1/2) ... [2018-09-26 08:20:19,433 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5520fc7b and model type ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.09 08:20:19, skipping insertion in model container [2018-09-26 08:20:19,433 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.09 08:20:19" (2/2) ... [2018-09-26 08:20:19,436 INFO L112 eAbstractionObserver]: Analyzing ICFG ArrayInit01.bpl [2018-09-26 08:20:19,447 INFO L137 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2018-09-26 08:20:19,457 INFO L149 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-09-26 08:20:19,509 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-09-26 08:20:19,510 INFO L381 AbstractCegarLoop]: Interprodecural is true [2018-09-26 08:20:19,511 INFO L382 AbstractCegarLoop]: Hoare is true [2018-09-26 08:20:19,511 INFO L383 AbstractCegarLoop]: Compute interpolants for Craig_NestedInterpolation [2018-09-26 08:20:19,511 INFO L384 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-09-26 08:20:19,511 INFO L385 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-09-26 08:20:19,511 INFO L386 AbstractCegarLoop]: Difference is false [2018-09-26 08:20:19,512 INFO L387 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-09-26 08:20:19,512 INFO L392 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-09-26 08:20:19,529 INFO L276 IsEmpty]: Start isEmpty. Operand 5 states. [2018-09-26 08:20:19,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 4 [2018-09-26 08:20:19,541 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:19,543 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1] [2018-09-26 08:20:19,545 INFO L423 AbstractCegarLoop]: === Iteration 1 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:19,555 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:19,555 INFO L82 PathProgramCache]: Analyzing trace with hash 29984, now seen corresponding path program 1 times [2018-09-26 08:20:19,563 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:19,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:19,650 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:19,653 INFO L313 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-09-26 08:20:19,653 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-09-26 08:20:19,658 INFO L459 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-09-26 08:20:19,673 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-09-26 08:20:19,674 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-09-26 08:20:19,677 INFO L87 Difference]: Start difference. First operand 5 states. Second operand 3 states. [2018-09-26 08:20:19,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:19,704 INFO L93 Difference]: Finished difference Result 9 states and 9 transitions. [2018-09-26 08:20:19,705 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-09-26 08:20:19,708 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 3 [2018-09-26 08:20:19,709 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:19,720 INFO L225 Difference]: With dead ends: 9 [2018-09-26 08:20:19,721 INFO L226 Difference]: Without dead ends: 5 [2018-09-26 08:20:19,724 INFO L605 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-09-26 08:20:19,743 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5 states. [2018-09-26 08:20:19,758 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5 to 5. [2018-09-26 08:20:19,760 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5 states. [2018-09-26 08:20:19,761 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5 states to 5 states and 5 transitions. [2018-09-26 08:20:19,762 INFO L78 Accepts]: Start accepts. Automaton has 5 states and 5 transitions. Word has length 3 [2018-09-26 08:20:19,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:19,763 INFO L480 AbstractCegarLoop]: Abstraction has 5 states and 5 transitions. [2018-09-26 08:20:19,763 INFO L481 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-09-26 08:20:19,764 INFO L276 IsEmpty]: Start isEmpty. Operand 5 states and 5 transitions. [2018-09-26 08:20:19,764 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 5 [2018-09-26 08:20:19,764 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:19,764 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1] [2018-09-26 08:20:19,765 INFO L423 AbstractCegarLoop]: === Iteration 2 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:19,765 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:19,765 INFO L82 PathProgramCache]: Analyzing trace with hash 927558, now seen corresponding path program 1 times [2018-09-26 08:20:19,766 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:19,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:19,869 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:19,870 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:19,870 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [3] total 3 [2018-09-26 08:20:19,871 INFO L459 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-09-26 08:20:19,872 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-09-26 08:20:19,872 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-09-26 08:20:19,872 INFO L87 Difference]: Start difference. First operand 5 states and 5 transitions. Second operand 5 states. [2018-09-26 08:20:19,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:19,946 INFO L93 Difference]: Finished difference Result 8 states and 8 transitions. [2018-09-26 08:20:19,946 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-09-26 08:20:19,946 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 4 [2018-09-26 08:20:19,947 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:19,947 INFO L225 Difference]: With dead ends: 8 [2018-09-26 08:20:19,947 INFO L226 Difference]: Without dead ends: 6 [2018-09-26 08:20:19,948 INFO L605 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-09-26 08:20:19,949 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6 states. [2018-09-26 08:20:19,950 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6 to 6. [2018-09-26 08:20:19,951 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6 states. [2018-09-26 08:20:19,951 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 6 transitions. [2018-09-26 08:20:19,951 INFO L78 Accepts]: Start accepts. Automaton has 6 states and 6 transitions. Word has length 4 [2018-09-26 08:20:19,952 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:19,952 INFO L480 AbstractCegarLoop]: Abstraction has 6 states and 6 transitions. [2018-09-26 08:20:19,952 INFO L481 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-09-26 08:20:19,952 INFO L276 IsEmpty]: Start isEmpty. Operand 6 states and 6 transitions. [2018-09-26 08:20:19,952 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 6 [2018-09-26 08:20:19,952 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:19,953 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1] [2018-09-26 08:20:19,953 INFO L423 AbstractCegarLoop]: === Iteration 3 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:19,953 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:19,954 INFO L82 PathProgramCache]: Analyzing trace with hash 28752352, now seen corresponding path program 2 times [2018-09-26 08:20:19,954 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:19,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:20,140 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:20,143 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:20,144 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [4] total 4 [2018-09-26 08:20:20,144 INFO L459 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-09-26 08:20:20,145 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-09-26 08:20:20,145 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-09-26 08:20:20,145 INFO L87 Difference]: Start difference. First operand 6 states and 6 transitions. Second operand 6 states. [2018-09-26 08:20:20,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:20,213 INFO L93 Difference]: Finished difference Result 9 states and 9 transitions. [2018-09-26 08:20:20,213 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-09-26 08:20:20,214 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 5 [2018-09-26 08:20:20,214 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:20,214 INFO L225 Difference]: With dead ends: 9 [2018-09-26 08:20:20,214 INFO L226 Difference]: Without dead ends: 7 [2018-09-26 08:20:20,215 INFO L605 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-09-26 08:20:20,215 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7 states. [2018-09-26 08:20:20,218 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-09-26 08:20:20,218 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7 states. [2018-09-26 08:20:20,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 7 transitions. [2018-09-26 08:20:20,219 INFO L78 Accepts]: Start accepts. Automaton has 7 states and 7 transitions. Word has length 5 [2018-09-26 08:20:20,219 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:20,219 INFO L480 AbstractCegarLoop]: Abstraction has 7 states and 7 transitions. [2018-09-26 08:20:20,219 INFO L481 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-09-26 08:20:20,220 INFO L276 IsEmpty]: Start isEmpty. Operand 7 states and 7 transitions. [2018-09-26 08:20:20,220 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2018-09-26 08:20:20,220 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:20,220 INFO L375 BasicCegarLoop]: trace histogram [3, 1, 1, 1] [2018-09-26 08:20:20,221 INFO L423 AbstractCegarLoop]: === Iteration 4 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:20,221 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:20,221 INFO L82 PathProgramCache]: Analyzing trace with hash 891320966, now seen corresponding path program 3 times [2018-09-26 08:20:20,221 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:20,244 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:20,404 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:20,404 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:20,405 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5] total 5 [2018-09-26 08:20:20,405 INFO L459 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-09-26 08:20:20,405 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-09-26 08:20:20,406 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-09-26 08:20:20,406 INFO L87 Difference]: Start difference. First operand 7 states and 7 transitions. Second operand 7 states. [2018-09-26 08:20:20,458 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:20,458 INFO L93 Difference]: Finished difference Result 10 states and 10 transitions. [2018-09-26 08:20:20,458 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-09-26 08:20:20,458 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 6 [2018-09-26 08:20:20,459 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:20,459 INFO L225 Difference]: With dead ends: 10 [2018-09-26 08:20:20,459 INFO L226 Difference]: Without dead ends: 8 [2018-09-26 08:20:20,460 INFO L605 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-09-26 08:20:20,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8 states. [2018-09-26 08:20:20,463 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-09-26 08:20:20,463 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 8 states. [2018-09-26 08:20:20,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 8 transitions. [2018-09-26 08:20:20,464 INFO L78 Accepts]: Start accepts. Automaton has 8 states and 8 transitions. Word has length 6 [2018-09-26 08:20:20,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:20,464 INFO L480 AbstractCegarLoop]: Abstraction has 8 states and 8 transitions. [2018-09-26 08:20:20,464 INFO L481 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-09-26 08:20:20,465 INFO L276 IsEmpty]: Start isEmpty. Operand 8 states and 8 transitions. [2018-09-26 08:20:20,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2018-09-26 08:20:20,465 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:20,465 INFO L375 BasicCegarLoop]: trace histogram [4, 1, 1, 1] [2018-09-26 08:20:20,466 INFO L423 AbstractCegarLoop]: === Iteration 5 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:20,466 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:20,466 INFO L82 PathProgramCache]: Analyzing trace with hash 1861144224, now seen corresponding path program 4 times [2018-09-26 08:20:20,466 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:20,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:20,786 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:20,787 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:20,787 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2018-09-26 08:20:20,787 INFO L459 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-09-26 08:20:20,788 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-09-26 08:20:20,788 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-09-26 08:20:20,789 INFO L87 Difference]: Start difference. First operand 8 states and 8 transitions. Second operand 8 states. [2018-09-26 08:20:20,917 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:20,917 INFO L93 Difference]: Finished difference Result 11 states and 11 transitions. [2018-09-26 08:20:20,920 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-09-26 08:20:20,921 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 7 [2018-09-26 08:20:20,921 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:20,922 INFO L225 Difference]: With dead ends: 11 [2018-09-26 08:20:20,922 INFO L226 Difference]: Without dead ends: 9 [2018-09-26 08:20:20,923 INFO L605 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-09-26 08:20:20,923 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 9 states. [2018-09-26 08:20:20,931 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-09-26 08:20:20,931 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 9 states. [2018-09-26 08:20:20,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-09-26 08:20:20,932 INFO L78 Accepts]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-09-26 08:20:20,932 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:20,936 INFO L480 AbstractCegarLoop]: Abstraction has 9 states and 9 transitions. [2018-09-26 08:20:20,937 INFO L481 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-09-26 08:20:20,937 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states and 9 transitions. [2018-09-26 08:20:20,937 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2018-09-26 08:20:20,938 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:20,938 INFO L375 BasicCegarLoop]: trace histogram [5, 1, 1, 1] [2018-09-26 08:20:20,939 INFO L423 AbstractCegarLoop]: === Iteration 6 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:20,939 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:20,939 INFO L82 PathProgramCache]: Analyzing trace with hash 1860894150, now seen corresponding path program 5 times [2018-09-26 08:20:20,940 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:20,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:21,272 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:21,272 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:21,272 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2018-09-26 08:20:21,273 INFO L459 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-09-26 08:20:21,273 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-09-26 08:20:21,274 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-09-26 08:20:21,274 INFO L87 Difference]: Start difference. First operand 9 states and 9 transitions. Second operand 9 states. [2018-09-26 08:20:21,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:21,334 INFO L93 Difference]: Finished difference Result 12 states and 12 transitions. [2018-09-26 08:20:21,335 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-09-26 08:20:21,335 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 8 [2018-09-26 08:20:21,335 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:21,336 INFO L225 Difference]: With dead ends: 12 [2018-09-26 08:20:21,336 INFO L226 Difference]: Without dead ends: 10 [2018-09-26 08:20:21,338 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-09-26 08:20:21,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10 states. [2018-09-26 08:20:21,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-09-26 08:20:21,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 10 states. [2018-09-26 08:20:21,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-09-26 08:20:21,348 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-09-26 08:20:21,349 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:21,349 INFO L480 AbstractCegarLoop]: Abstraction has 10 states and 10 transitions. [2018-09-26 08:20:21,349 INFO L481 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-09-26 08:20:21,349 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 10 transitions. [2018-09-26 08:20:21,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2018-09-26 08:20:21,350 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:21,350 INFO L375 BasicCegarLoop]: trace histogram [6, 1, 1, 1] [2018-09-26 08:20:21,351 INFO L423 AbstractCegarLoop]: === Iteration 7 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:21,351 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:21,351 INFO L82 PathProgramCache]: Analyzing trace with hash 1853141856, now seen corresponding path program 6 times [2018-09-26 08:20:21,352 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:21,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:21,728 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:21,728 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:21,728 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2018-09-26 08:20:21,729 INFO L459 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-09-26 08:20:21,729 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-09-26 08:20:21,729 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-09-26 08:20:21,730 INFO L87 Difference]: Start difference. First operand 10 states and 10 transitions. Second operand 10 states. [2018-09-26 08:20:21,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:21,797 INFO L93 Difference]: Finished difference Result 13 states and 13 transitions. [2018-09-26 08:20:21,797 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-09-26 08:20:21,798 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 9 [2018-09-26 08:20:21,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:21,798 INFO L225 Difference]: With dead ends: 13 [2018-09-26 08:20:21,799 INFO L226 Difference]: Without dead ends: 11 [2018-09-26 08:20:21,799 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-09-26 08:20:21,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2018-09-26 08:20:21,803 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-09-26 08:20:21,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 11 states. [2018-09-26 08:20:21,804 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-09-26 08:20:21,804 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-09-26 08:20:21,805 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:21,805 INFO L480 AbstractCegarLoop]: Abstraction has 11 states and 11 transitions. [2018-09-26 08:20:21,805 INFO L481 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-09-26 08:20:21,805 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 11 transitions. [2018-09-26 08:20:21,806 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2018-09-26 08:20:21,806 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:21,806 INFO L375 BasicCegarLoop]: trace histogram [7, 1, 1, 1] [2018-09-26 08:20:21,806 INFO L423 AbstractCegarLoop]: === Iteration 8 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:21,807 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:21,807 INFO L82 PathProgramCache]: Analyzing trace with hash 1612820742, now seen corresponding path program 7 times [2018-09-26 08:20:21,807 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:21,821 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:22,331 WARN L178 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 131 DAG size of output: 52 [2018-09-26 08:20:22,354 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:22,354 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:22,357 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-09-26 08:20:22,357 INFO L459 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-09-26 08:20:22,358 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-09-26 08:20:22,358 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-09-26 08:20:22,358 INFO L87 Difference]: Start difference. First operand 11 states and 11 transitions. Second operand 11 states. [2018-09-26 08:20:22,494 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:22,494 INFO L93 Difference]: Finished difference Result 14 states and 14 transitions. [2018-09-26 08:20:22,494 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-09-26 08:20:22,495 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 10 [2018-09-26 08:20:22,495 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:22,495 INFO L225 Difference]: With dead ends: 14 [2018-09-26 08:20:22,496 INFO L226 Difference]: Without dead ends: 12 [2018-09-26 08:20:22,496 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=55, Invalid=155, Unknown=0, NotChecked=0, Total=210 [2018-09-26 08:20:22,497 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 12 states. [2018-09-26 08:20:22,500 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-09-26 08:20:22,501 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 12 states. [2018-09-26 08:20:22,501 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-09-26 08:20:22,502 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-09-26 08:20:22,502 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:22,502 INFO L480 AbstractCegarLoop]: Abstraction has 12 states and 12 transitions. [2018-09-26 08:20:22,502 INFO L481 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-09-26 08:20:22,502 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 12 transitions. [2018-09-26 08:20:22,503 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2018-09-26 08:20:22,503 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:22,503 INFO L375 BasicCegarLoop]: trace histogram [8, 1, 1, 1] [2018-09-26 08:20:22,504 INFO L423 AbstractCegarLoop]: === Iteration 9 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:22,504 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:22,504 INFO L82 PathProgramCache]: Analyzing trace with hash -1542166496, now seen corresponding path program 8 times [2018-09-26 08:20:22,504 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:22,522 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:23,096 WARN L178 SmtUtils]: Spent 147.00 ms on a formula simplification. DAG size of input: 147 DAG size of output: 44 [2018-09-26 08:20:23,336 WARN L178 SmtUtils]: Spent 172.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 57 [2018-09-26 08:20:23,352 INFO L134 CoverageAnalysis]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:23,353 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:23,353 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2018-09-26 08:20:23,353 INFO L459 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-09-26 08:20:23,354 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-09-26 08:20:23,354 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-09-26 08:20:23,354 INFO L87 Difference]: Start difference. First operand 12 states and 12 transitions. Second operand 12 states. [2018-09-26 08:20:23,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:23,466 INFO L93 Difference]: Finished difference Result 15 states and 15 transitions. [2018-09-26 08:20:23,467 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-09-26 08:20:23,467 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 11 [2018-09-26 08:20:23,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:23,468 INFO L225 Difference]: With dead ends: 15 [2018-09-26 08:20:23,468 INFO L226 Difference]: Without dead ends: 13 [2018-09-26 08:20:23,468 INFO L605 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-09-26 08:20:23,469 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2018-09-26 08:20:23,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-09-26 08:20:23,477 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 13 states. [2018-09-26 08:20:23,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-09-26 08:20:23,477 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-09-26 08:20:23,478 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:23,478 INFO L480 AbstractCegarLoop]: Abstraction has 13 states and 13 transitions. [2018-09-26 08:20:23,478 INFO L481 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-09-26 08:20:23,478 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 13 transitions. [2018-09-26 08:20:23,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-09-26 08:20:23,480 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:23,480 INFO L375 BasicCegarLoop]: trace histogram [9, 1, 1, 1] [2018-09-26 08:20:23,481 INFO L423 AbstractCegarLoop]: === Iteration 10 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:23,481 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:23,481 INFO L82 PathProgramCache]: Analyzing trace with hash -562523066, now seen corresponding path program 9 times [2018-09-26 08:20:23,482 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:23,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:24,100 WARN L178 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 34 [2018-09-26 08:20:24,397 WARN L178 SmtUtils]: Spent 226.00 ms on a formula simplification. DAG size of input: 185 DAG size of output: 52 [2018-09-26 08:20:24,752 WARN L178 SmtUtils]: Spent 255.00 ms on a formula simplification. DAG size of input: 212 DAG size of output: 59 [2018-09-26 08:20:24,772 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:24,773 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:24,773 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2018-09-26 08:20:24,774 INFO L459 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-09-26 08:20:24,774 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-09-26 08:20:24,774 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2018-09-26 08:20:24,774 INFO L87 Difference]: Start difference. First operand 13 states and 13 transitions. Second operand 13 states. [2018-09-26 08:20:24,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:24,925 INFO L93 Difference]: Finished difference Result 16 states and 16 transitions. [2018-09-26 08:20:24,926 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-09-26 08:20:24,926 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 12 [2018-09-26 08:20:24,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:24,927 INFO L225 Difference]: With dead ends: 16 [2018-09-26 08:20:24,927 INFO L226 Difference]: Without dead ends: 14 [2018-09-26 08:20:24,928 INFO L605 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-09-26 08:20:24,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2018-09-26 08:20:24,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-09-26 08:20:24,935 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 14 states. [2018-09-26 08:20:24,936 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-09-26 08:20:24,936 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-09-26 08:20:24,936 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:24,937 INFO L480 AbstractCegarLoop]: Abstraction has 14 states and 14 transitions. [2018-09-26 08:20:24,937 INFO L481 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-09-26 08:20:24,937 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 14 transitions. [2018-09-26 08:20:24,937 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2018-09-26 08:20:24,938 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:24,938 INFO L375 BasicCegarLoop]: trace histogram [10, 1, 1, 1] [2018-09-26 08:20:24,938 INFO L423 AbstractCegarLoop]: === Iteration 11 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:24,939 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:24,939 INFO L82 PathProgramCache]: Analyzing trace with hash -258347808, now seen corresponding path program 10 times [2018-09-26 08:20:24,939 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:24,966 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:25,688 WARN L178 SmtUtils]: Spent 163.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 61 [2018-09-26 08:20:26,119 WARN L178 SmtUtils]: Spent 319.00 ms on a formula simplification. DAG size of input: 327 DAG size of output: 56 [2018-09-26 08:20:26,452 WARN L178 SmtUtils]: Spent 204.00 ms on a formula simplification. DAG size of input: 440 DAG size of output: 80 [2018-09-26 08:20:26,472 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:26,473 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:26,473 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-09-26 08:20:26,474 INFO L459 AbstractCegarLoop]: Interpolant automaton has 14 states [2018-09-26 08:20:26,474 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2018-09-26 08:20:26,474 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=127, Unknown=0, NotChecked=0, Total=182 [2018-09-26 08:20:26,475 INFO L87 Difference]: Start difference. First operand 14 states and 14 transitions. Second operand 14 states. [2018-09-26 08:20:26,852 WARN L178 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 76 [2018-09-26 08:20:26,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:26,951 INFO L93 Difference]: Finished difference Result 17 states and 17 transitions. [2018-09-26 08:20:26,951 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-09-26 08:20:26,951 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 13 [2018-09-26 08:20:26,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:26,952 INFO L225 Difference]: With dead ends: 17 [2018-09-26 08:20:26,952 INFO L226 Difference]: Without dead ends: 15 [2018-09-26 08:20:26,953 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=102, Invalid=240, Unknown=0, NotChecked=0, Total=342 [2018-09-26 08:20:26,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2018-09-26 08:20:26,961 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-09-26 08:20:26,961 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 15 states. [2018-09-26 08:20:26,961 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-09-26 08:20:26,962 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-09-26 08:20:26,962 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:26,962 INFO L480 AbstractCegarLoop]: Abstraction has 15 states and 15 transitions. [2018-09-26 08:20:26,962 INFO L481 AbstractCegarLoop]: Interpolant automaton has 14 states. [2018-09-26 08:20:26,963 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 15 transitions. [2018-09-26 08:20:26,963 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2018-09-26 08:20:26,963 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:26,963 INFO L375 BasicCegarLoop]: trace histogram [11, 1, 1, 1] [2018-09-26 08:20:26,964 INFO L423 AbstractCegarLoop]: === Iteration 12 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:26,964 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:26,967 INFO L82 PathProgramCache]: Analyzing trace with hash 581150598, now seen corresponding path program 11 times [2018-09-26 08:20:26,967 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:27,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:27,765 WARN L178 SmtUtils]: Spent 165.00 ms on a formula simplification. DAG size of input: 183 DAG size of output: 54 [2018-09-26 08:20:28,062 WARN L178 SmtUtils]: Spent 217.00 ms on a formula simplification. DAG size of input: 307 DAG size of output: 96 [2018-09-26 08:20:28,669 WARN L178 SmtUtils]: Spent 488.00 ms on a formula simplification. DAG size of input: 389 DAG size of output: 81 [2018-09-26 08:20:29,548 WARN L178 SmtUtils]: Spent 729.00 ms on a formula simplification. DAG size of input: 498 DAG size of output: 79 [2018-09-26 08:20:30,963 WARN L178 SmtUtils]: Spent 1.19 s on a formula simplification. DAG size of input: 582 DAG size of output: 90 [2018-09-26 08:20:30,981 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:30,981 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:30,981 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-09-26 08:20:30,982 INFO L459 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-09-26 08:20:30,982 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-09-26 08:20:30,982 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2018-09-26 08:20:30,983 INFO L87 Difference]: Start difference. First operand 15 states and 15 transitions. Second operand 15 states. [2018-09-26 08:20:31,282 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:31,282 INFO L93 Difference]: Finished difference Result 18 states and 18 transitions. [2018-09-26 08:20:31,283 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-09-26 08:20:31,283 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 14 [2018-09-26 08:20:31,283 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:31,284 INFO L225 Difference]: With dead ends: 18 [2018-09-26 08:20:31,284 INFO L226 Difference]: Without dead ends: 16 [2018-09-26 08:20:31,284 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=100, Invalid=320, Unknown=0, NotChecked=0, Total=420 [2018-09-26 08:20:31,285 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16 states. [2018-09-26 08:20:31,292 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-09-26 08:20:31,293 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 16 states. [2018-09-26 08:20:31,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-09-26 08:20:31,294 INFO L78 Accepts]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 14 [2018-09-26 08:20:31,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:31,294 INFO L480 AbstractCegarLoop]: Abstraction has 16 states and 16 transitions. [2018-09-26 08:20:31,294 INFO L481 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-09-26 08:20:31,294 INFO L276 IsEmpty]: Start isEmpty. Operand 16 states and 16 transitions. [2018-09-26 08:20:31,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2018-09-26 08:20:31,295 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:31,295 INFO L375 BasicCegarLoop]: trace histogram [12, 1, 1, 1] [2018-09-26 08:20:31,295 INFO L423 AbstractCegarLoop]: === Iteration 13 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:31,296 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:31,296 INFO L82 PathProgramCache]: Analyzing trace with hash 835797408, now seen corresponding path program 12 times [2018-09-26 08:20:31,296 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:31,328 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:32,003 WARN L178 SmtUtils]: Spent 160.00 ms on a formula simplification. DAG size of input: 225 DAG size of output: 38 [2018-09-26 08:20:32,265 WARN L178 SmtUtils]: Spent 165.00 ms on a formula simplification. DAG size of input: 367 DAG size of output: 40 [2018-09-26 08:20:32,866 WARN L178 SmtUtils]: Spent 433.00 ms on a formula simplification. DAG size of input: 483 DAG size of output: 45 [2018-09-26 08:20:34,124 WARN L178 SmtUtils]: Spent 1.05 s on a formula simplification. DAG size of input: 985 DAG size of output: 170 [2018-09-26 08:20:35,423 WARN L178 SmtUtils]: Spent 1.08 s on a formula simplification. DAG size of input: 1009 DAG size of output: 125 [2018-09-26 08:20:35,441 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:35,441 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:35,442 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2018-09-26 08:20:35,442 INFO L459 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-09-26 08:20:35,442 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-09-26 08:20:35,443 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=190, Unknown=0, NotChecked=0, Total=240 [2018-09-26 08:20:35,443 INFO L87 Difference]: Start difference. First operand 16 states and 16 transitions. Second operand 16 states. [2018-09-26 08:20:35,591 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:35,592 INFO L93 Difference]: Finished difference Result 19 states and 19 transitions. [2018-09-26 08:20:35,592 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-09-26 08:20:35,592 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 15 [2018-09-26 08:20:35,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:35,593 INFO L225 Difference]: With dead ends: 19 [2018-09-26 08:20:35,593 INFO L226 Difference]: Without dead ends: 17 [2018-09-26 08:20:35,593 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2018-09-26 08:20:35,594 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 17 states. [2018-09-26 08:20:35,602 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-09-26 08:20:35,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 17 states. [2018-09-26 08:20:35,602 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-09-26 08:20:35,603 INFO L78 Accepts]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 15 [2018-09-26 08:20:35,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:35,603 INFO L480 AbstractCegarLoop]: Abstraction has 17 states and 17 transitions. [2018-09-26 08:20:35,603 INFO L481 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-09-26 08:20:35,603 INFO L276 IsEmpty]: Start isEmpty. Operand 17 states and 17 transitions. [2018-09-26 08:20:35,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2018-09-26 08:20:35,604 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:35,604 INFO L375 BasicCegarLoop]: trace histogram [13, 1, 1, 1] [2018-09-26 08:20:35,604 INFO L423 AbstractCegarLoop]: === Iteration 14 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:35,604 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:35,605 INFO L82 PathProgramCache]: Analyzing trace with hash 139913926, now seen corresponding path program 13 times [2018-09-26 08:20:35,605 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:35,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:36,522 WARN L178 SmtUtils]: Spent 135.00 ms on a formula simplification. DAG size of input: 391 DAG size of output: 40 [2018-09-26 08:20:37,139 WARN L178 SmtUtils]: Spent 461.00 ms on a formula simplification. DAG size of input: 506 DAG size of output: 44 [2018-09-26 08:20:37,822 WARN L178 SmtUtils]: Spent 486.00 ms on a formula simplification. DAG size of input: 607 DAG size of output: 48 [2018-09-26 08:20:39,118 WARN L178 SmtUtils]: Spent 999.00 ms on a formula simplification. DAG size of input: 939 DAG size of output: 76 [2018-09-26 08:20:40,960 WARN L178 SmtUtils]: Spent 1.40 s on a formula simplification. DAG size of input: 1530 DAG size of output: 94 [2018-09-26 08:20:40,977 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:40,977 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:40,977 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-09-26 08:20:40,978 INFO L459 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-09-26 08:20:40,978 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-09-26 08:20:40,978 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2018-09-26 08:20:40,979 INFO L87 Difference]: Start difference. First operand 17 states and 17 transitions. Second operand 17 states. [2018-09-26 08:20:41,140 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:41,140 INFO L93 Difference]: Finished difference Result 20 states and 20 transitions. [2018-09-26 08:20:41,140 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-09-26 08:20:41,140 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 16 [2018-09-26 08:20:41,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:41,141 INFO L225 Difference]: With dead ends: 20 [2018-09-26 08:20:41,141 INFO L226 Difference]: Without dead ends: 18 [2018-09-26 08:20:41,142 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2018-09-26 08:20:41,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2018-09-26 08:20:41,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-09-26 08:20:41,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 18 states. [2018-09-26 08:20:41,152 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 18 transitions. [2018-09-26 08:20:41,152 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 18 transitions. Word has length 16 [2018-09-26 08:20:41,152 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:41,152 INFO L480 AbstractCegarLoop]: Abstraction has 18 states and 18 transitions. [2018-09-26 08:20:41,152 INFO L481 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-09-26 08:20:41,153 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 18 transitions. [2018-09-26 08:20:41,153 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2018-09-26 08:20:41,153 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:41,153 INFO L375 BasicCegarLoop]: trace histogram [14, 1, 1, 1] [2018-09-26 08:20:41,154 INFO L423 AbstractCegarLoop]: === Iteration 15 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:41,154 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:41,154 INFO L82 PathProgramCache]: Analyzing trace with hash 42362464, now seen corresponding path program 14 times [2018-09-26 08:20:41,154 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:41,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:42,279 WARN L178 SmtUtils]: Spent 164.00 ms on a formula simplification. DAG size of input: 373 DAG size of output: 41 [2018-09-26 08:20:42,734 WARN L178 SmtUtils]: Spent 328.00 ms on a formula simplification. DAG size of input: 473 DAG size of output: 45 [2018-09-26 08:20:43,346 WARN L178 SmtUtils]: Spent 407.00 ms on a formula simplification. DAG size of input: 637 DAG size of output: 49 [2018-09-26 08:20:44,452 WARN L178 SmtUtils]: Spent 817.00 ms on a formula simplification. DAG size of input: 768 DAG size of output: 52 [2018-09-26 08:20:46,211 WARN L178 SmtUtils]: Spent 1.33 s on a formula simplification. DAG size of input: 1621 DAG size of output: 90 [2018-09-26 08:20:49,507 WARN L178 SmtUtils]: Spent 2.48 s on a formula simplification. DAG size of input: 2892 DAG size of output: 95 [2018-09-26 08:20:49,527 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 0 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:20:49,527 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:20:49,527 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2018-09-26 08:20:49,528 INFO L459 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-09-26 08:20:49,528 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-09-26 08:20:49,528 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2018-09-26 08:20:49,529 INFO L87 Difference]: Start difference. First operand 18 states and 18 transitions. Second operand 18 states. [2018-09-26 08:20:49,700 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:20:49,700 INFO L93 Difference]: Finished difference Result 21 states and 21 transitions. [2018-09-26 08:20:49,700 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-09-26 08:20:49,700 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 17 [2018-09-26 08:20:49,701 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:20:49,701 INFO L225 Difference]: With dead ends: 21 [2018-09-26 08:20:49,701 INFO L226 Difference]: Without dead ends: 19 [2018-09-26 08:20:49,702 INFO L605 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-09-26 08:20:49,702 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 19 states. [2018-09-26 08:20:49,710 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-09-26 08:20:49,710 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 19 states. [2018-09-26 08:20:49,711 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-09-26 08:20:49,711 INFO L78 Accepts]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 17 [2018-09-26 08:20:49,711 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:20:49,711 INFO L480 AbstractCegarLoop]: Abstraction has 19 states and 19 transitions. [2018-09-26 08:20:49,711 INFO L481 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-09-26 08:20:49,711 INFO L276 IsEmpty]: Start isEmpty. Operand 19 states and 19 transitions. [2018-09-26 08:20:49,712 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2018-09-26 08:20:49,712 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:20:49,712 INFO L375 BasicCegarLoop]: trace histogram [15, 1, 1, 1] [2018-09-26 08:20:49,713 INFO L423 AbstractCegarLoop]: === Iteration 16 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:20:49,713 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:20:49,713 INFO L82 PathProgramCache]: Analyzing trace with hash 1313234438, now seen corresponding path program 15 times [2018-09-26 08:20:49,713 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:20:49,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:20:50,821 WARN L178 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 425 DAG size of output: 44 [2018-09-26 08:20:51,848 WARN L178 SmtUtils]: Spent 759.00 ms on a formula simplification. DAG size of input: 1062 DAG size of output: 49 [2018-09-26 08:20:53,631 WARN L178 SmtUtils]: Spent 1.52 s on a formula simplification. DAG size of input: 1325 DAG size of output: 52 [2018-09-26 08:20:56,290 WARN L178 SmtUtils]: Spent 2.28 s on a formula simplification. DAG size of input: 2123 DAG size of output: 57 [2018-09-26 08:21:02,162 WARN L178 SmtUtils]: Spent 5.44 s on a formula simplification. DAG size of input: 2449 DAG size of output: 159 [2018-09-26 08:21:05,302 WARN L178 SmtUtils]: Spent 2.68 s on a formula simplification. DAG size of input: 2239 DAG size of output: 158 [2018-09-26 08:21:05,320 INFO L134 CoverageAnalysis]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:21:05,321 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:21:05,321 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-09-26 08:21:05,321 INFO L459 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-09-26 08:21:05,322 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-09-26 08:21:05,322 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=280, Unknown=0, NotChecked=0, Total=342 [2018-09-26 08:21:05,322 INFO L87 Difference]: Start difference. First operand 19 states and 19 transitions. Second operand 19 states. [2018-09-26 08:21:05,512 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:21:05,512 INFO L93 Difference]: Finished difference Result 22 states and 22 transitions. [2018-09-26 08:21:05,512 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-09-26 08:21:05,512 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 18 [2018-09-26 08:21:05,512 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:21:05,513 INFO L225 Difference]: With dead ends: 22 [2018-09-26 08:21:05,514 INFO L226 Difference]: Without dead ends: 20 [2018-09-26 08:21:05,515 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 14.7s TimeCoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2018-09-26 08:21:05,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2018-09-26 08:21:05,522 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2018-09-26 08:21:05,523 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 20 states. [2018-09-26 08:21:05,523 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 20 transitions. [2018-09-26 08:21:05,523 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 20 transitions. Word has length 18 [2018-09-26 08:21:05,523 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:21:05,524 INFO L480 AbstractCegarLoop]: Abstraction has 20 states and 20 transitions. [2018-09-26 08:21:05,524 INFO L481 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-09-26 08:21:05,524 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 20 transitions. [2018-09-26 08:21:05,524 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2018-09-26 08:21:05,524 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:21:05,524 INFO L375 BasicCegarLoop]: trace histogram [16, 1, 1, 1] [2018-09-26 08:21:05,525 INFO L423 AbstractCegarLoop]: === Iteration 17 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:21:05,525 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:21:05,525 INFO L82 PathProgramCache]: Analyzing trace with hash 2055559968, now seen corresponding path program 16 times [2018-09-26 08:21:05,525 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:21:05,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:21:06,944 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 344 DAG size of output: 40 [2018-09-26 08:21:07,217 WARN L178 SmtUtils]: Spent 168.00 ms on a formula simplification. DAG size of input: 444 DAG size of output: 45 [2018-09-26 08:21:07,997 WARN L178 SmtUtils]: Spent 568.00 ms on a formula simplification. DAG size of input: 995 DAG size of output: 48 [2018-09-26 08:21:09,822 WARN L178 SmtUtils]: Spent 1.57 s on a formula simplification. DAG size of input: 1311 DAG size of output: 52 [2018-09-26 08:21:13,025 WARN L178 SmtUtils]: Spent 2.83 s on a formula simplification. DAG size of input: 1626 DAG size of output: 57 [2018-09-26 08:21:21,609 WARN L178 SmtUtils]: Spent 7.90 s on a formula simplification. DAG size of input: 2313 DAG size of output: 61 [2018-09-26 08:21:35,060 WARN L178 SmtUtils]: Spent 12.65 s on a formula simplification. DAG size of input: 2780 DAG size of output: 109 [2018-09-26 08:21:54,808 WARN L178 SmtUtils]: Spent 18.46 s on a formula simplification. DAG size of input: 3963 DAG size of output: 114 [2018-09-26 08:21:54,822 INFO L134 CoverageAnalysis]: Checked inductivity of 136 backedges. 0 proven. 136 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:21:54,822 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:21:54,823 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2018-09-26 08:21:54,823 INFO L459 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-09-26 08:21:54,823 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-09-26 08:21:54,823 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2018-09-26 08:21:54,824 INFO L87 Difference]: Start difference. First operand 20 states and 20 transitions. Second operand 20 states. [2018-09-26 08:21:55,025 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:21:55,025 INFO L93 Difference]: Finished difference Result 23 states and 23 transitions. [2018-09-26 08:21:55,025 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-09-26 08:21:55,025 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 19 [2018-09-26 08:21:55,025 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:21:55,026 INFO L225 Difference]: With dead ends: 23 [2018-09-26 08:21:55,026 INFO L226 Difference]: Without dead ends: 21 [2018-09-26 08:21:55,027 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 47.4s TimeCoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2018-09-26 08:21:55,027 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2018-09-26 08:21:55,035 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-09-26 08:21:55,035 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 21 states. [2018-09-26 08:21:55,035 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 21 transitions. [2018-09-26 08:21:55,036 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 21 transitions. Word has length 19 [2018-09-26 08:21:55,036 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:21:55,036 INFO L480 AbstractCegarLoop]: Abstraction has 21 states and 21 transitions. [2018-09-26 08:21:55,036 INFO L481 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-09-26 08:21:55,036 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 21 transitions. [2018-09-26 08:21:55,037 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-09-26 08:21:55,037 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:21:55,037 INFO L375 BasicCegarLoop]: trace histogram [17, 1, 1, 1] [2018-09-26 08:21:55,037 INFO L423 AbstractCegarLoop]: === Iteration 18 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:21:55,037 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:21:55,037 INFO L82 PathProgramCache]: Analyzing trace with hash -702152378, now seen corresponding path program 17 times [2018-09-26 08:21:55,037 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:21:55,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:21:56,930 WARN L178 SmtUtils]: Spent 154.00 ms on a formula simplification. DAG size of input: 356 DAG size of output: 38 [2018-09-26 08:21:57,453 WARN L178 SmtUtils]: Spent 359.00 ms on a formula simplification. DAG size of input: 466 DAG size of output: 42 [2018-09-26 08:21:57,925 WARN L178 SmtUtils]: Spent 366.00 ms on a formula simplification. DAG size of input: 550 DAG size of output: 47 [2018-09-26 08:21:59,046 WARN L178 SmtUtils]: Spent 770.00 ms on a formula simplification. DAG size of input: 744 DAG size of output: 52 [2018-09-26 08:22:00,805 WARN L178 SmtUtils]: Spent 1.51 s on a formula simplification. DAG size of input: 1123 DAG size of output: 59 [2018-09-26 08:22:04,543 WARN L178 SmtUtils]: Spent 3.40 s on a formula simplification. DAG size of input: 1482 DAG size of output: 106 [2018-09-26 08:22:12,554 WARN L178 SmtUtils]: Spent 7.42 s on a formula simplification. DAG size of input: 2585 DAG size of output: 164 [2018-09-26 08:22:31,547 WARN L178 SmtUtils]: Spent 18.06 s on a formula simplification. DAG size of input: 3233 DAG size of output: 143 [2018-09-26 08:22:42,458 WARN L178 SmtUtils]: Spent 10.02 s on a formula simplification. DAG size of input: 3190 DAG size of output: 147 [2018-09-26 08:22:55,389 WARN L178 SmtUtils]: Spent 11.76 s on a formula simplification. DAG size of input: 4334 DAG size of output: 136 [2018-09-26 08:22:55,408 INFO L134 CoverageAnalysis]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:22:55,408 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:22:55,408 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-09-26 08:22:55,408 INFO L459 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-09-26 08:22:55,409 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-09-26 08:22:55,409 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=312, Unknown=0, NotChecked=0, Total=420 [2018-09-26 08:22:55,409 INFO L87 Difference]: Start difference. First operand 21 states and 21 transitions. Second operand 21 states. [2018-09-26 08:22:55,682 WARN L178 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 201 DAG size of output: 117 [2018-09-26 08:22:55,960 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:22:55,960 INFO L93 Difference]: Finished difference Result 24 states and 24 transitions. [2018-09-26 08:22:55,960 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-09-26 08:22:55,960 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 20 [2018-09-26 08:22:55,960 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:22:55,962 INFO L225 Difference]: With dead ends: 24 [2018-09-26 08:22:55,962 INFO L226 Difference]: Without dead ends: 22 [2018-09-26 08:22:55,963 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 58.4s TimeCoverageRelationStatistics Valid=177, Invalid=473, Unknown=0, NotChecked=0, Total=650 [2018-09-26 08:22:55,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2018-09-26 08:22:55,973 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-09-26 08:22:55,973 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 22 states. [2018-09-26 08:22:55,974 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 22 states to 22 states and 22 transitions. [2018-09-26 08:22:55,974 INFO L78 Accepts]: Start accepts. Automaton has 22 states and 22 transitions. Word has length 20 [2018-09-26 08:22:55,974 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:22:55,975 INFO L480 AbstractCegarLoop]: Abstraction has 22 states and 22 transitions. [2018-09-26 08:22:55,975 INFO L481 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-09-26 08:22:55,975 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states and 22 transitions. [2018-09-26 08:22:55,975 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-09-26 08:22:55,975 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:22:55,976 INFO L375 BasicCegarLoop]: trace histogram [18, 1, 1, 1] [2018-09-26 08:22:55,976 INFO L423 AbstractCegarLoop]: === Iteration 19 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:22:55,976 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:22:55,976 INFO L82 PathProgramCache]: Analyzing trace with hash -291889184, now seen corresponding path program 18 times [2018-09-26 08:22:55,976 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:22:56,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-09-26 08:22:58,042 WARN L178 SmtUtils]: Spent 184.00 ms on a formula simplification. DAG size of input: 404 DAG size of output: 40 [2018-09-26 08:22:58,494 WARN L178 SmtUtils]: Spent 308.00 ms on a formula simplification. DAG size of input: 513 DAG size of output: 45 [2018-09-26 08:22:59,990 WARN L178 SmtUtils]: Spent 1.03 s on a formula simplification. DAG size of input: 1120 DAG size of output: 49 [2018-09-26 08:23:02,460 WARN L178 SmtUtils]: Spent 2.15 s on a formula simplification. DAG size of input: 1425 DAG size of output: 52 [2018-09-26 08:23:07,665 WARN L178 SmtUtils]: Spent 4.71 s on a formula simplification. DAG size of input: 2205 DAG size of output: 57 [2018-09-26 08:23:18,107 WARN L178 SmtUtils]: Spent 9.80 s on a formula simplification. DAG size of input: 2874 DAG size of output: 61 [2018-09-26 08:23:28,588 WARN L178 SmtUtils]: Spent 9.61 s on a formula simplification. DAG size of input: 3673 DAG size of output: 65 [2018-09-26 08:23:43,495 WARN L178 SmtUtils]: Spent 13.76 s on a formula simplification. DAG size of input: 3837 DAG size of output: 69 [2018-09-26 08:24:04,202 WARN L178 SmtUtils]: Spent 19.38 s on a formula simplification. DAG size of input: 4745 DAG size of output: 130 [2018-09-26 08:24:34,590 WARN L178 SmtUtils]: Spent 28.55 s on a formula simplification. DAG size of input: 6452 DAG size of output: 155 [2018-09-26 08:24:34,608 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 0 proven. 171 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-09-26 08:24:34,608 INFO L313 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-09-26 08:24:34,608 INFO L328 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2018-09-26 08:24:34,609 INFO L459 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-09-26 08:24:34,609 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-09-26 08:24:34,609 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=388, Unknown=0, NotChecked=0, Total=462 [2018-09-26 08:24:34,610 INFO L87 Difference]: Start difference. First operand 22 states and 22 transitions. Second operand 22 states. [2018-09-26 08:24:34,857 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-09-26 08:24:34,858 INFO L93 Difference]: Finished difference Result 25 states and 25 transitions. [2018-09-26 08:24:34,858 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-09-26 08:24:34,858 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 21 [2018-09-26 08:24:34,858 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-09-26 08:24:34,858 INFO L225 Difference]: With dead ends: 25 [2018-09-26 08:24:34,858 INFO L226 Difference]: Without dead ends: 23 [2018-09-26 08:24:34,860 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 0 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 95.8s TimeCoverageRelationStatistics Valid=78, Invalid=428, Unknown=0, NotChecked=0, Total=506 [2018-09-26 08:24:34,860 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2018-09-26 08:24:34,871 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-09-26 08:24:34,872 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 23 states. [2018-09-26 08:24:34,872 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 23 transitions. [2018-09-26 08:24:34,872 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 23 transitions. Word has length 21 [2018-09-26 08:24:34,873 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-09-26 08:24:34,873 INFO L480 AbstractCegarLoop]: Abstraction has 23 states and 23 transitions. [2018-09-26 08:24:34,873 INFO L481 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-09-26 08:24:34,873 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 23 transitions. [2018-09-26 08:24:34,873 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2018-09-26 08:24:34,874 INFO L367 BasicCegarLoop]: Found error trace [2018-09-26 08:24:34,874 INFO L375 BasicCegarLoop]: trace histogram [19, 1, 1, 1] [2018-09-26 08:24:34,874 INFO L423 AbstractCegarLoop]: === Iteration 20 === [mainErr0ASSERT_VIOLATIONASSERT]=== [2018-09-26 08:24:34,874 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-09-26 08:24:34,874 INFO L82 PathProgramCache]: Analyzing trace with hash -458632058, now seen corresponding path program 19 times [2018-09-26 08:24:34,874 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-09-26 08:24:34,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat Received shutdown request... [2018-09-26 08:24:38,335 WARN L250 erpolLogProxyWrapper]: Unable to check validity of interpolant: cancelled [2018-09-26 08:24:38,389 WARN L250 erpolLogProxyWrapper]: Unable to check validity of interpolant: cancelled [2018-09-26 08:24:38,389 WARN L250 erpolLogProxyWrapper]: Unable to check validity of interpolant: cancelled [2018-09-26 08:24:38,393 WARN L549 AbstractCegarLoop]: Verification canceled [2018-09-26 08:24:38,398 WARN L206 ceAbstractionStarter]: Timeout [2018-09-26 08:24:38,398 INFO L202 PluginConnector]: Adding new model ArrayInit01.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.09 08:24:38 BoogieIcfgContainer [2018-09-26 08:24:38,398 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-09-26 08:24:38,399 INFO L168 Benchmark]: Toolchain (without parser) took 259315.36 ms. Allocated memory was 1.5 GB in the beginning and 3.5 GB in the end (delta: 1.9 GB). Free memory was 1.5 GB in the beginning and 3.1 GB in the end (delta: -1.7 GB). Peak memory consumption was 2.8 GB. Max. memory is 7.1 GB. [2018-09-26 08:24:38,400 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.19 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-09-26 08:24:38,401 INFO L168 Benchmark]: Boogie Procedure Inliner took 44.80 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-09-26 08:24:38,401 INFO L168 Benchmark]: Boogie Preprocessor took 26.06 ms. Allocated memory is still 1.5 GB. Free memory is still 1.5 GB. There was no memory consumed. Max. memory is 7.1 GB. [2018-09-26 08:24:38,402 INFO L168 Benchmark]: RCFGBuilder took 266.63 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-09-26 08:24:38,402 INFO L168 Benchmark]: TraceAbstraction took 258971.93 ms. Allocated memory was 1.5 GB in the beginning and 3.5 GB in the end (delta: 1.9 GB). Free memory was 1.4 GB in the beginning and 3.1 GB in the end (delta: -1.7 GB). Peak memory consumption was 2.8 GB. Max. memory is 7.1 GB. [2018-09-26 08:24:38,407 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.19 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 44.80 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 26.06 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 266.63 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 258971.93 ms. Allocated memory was 1.5 GB in the beginning and 3.5 GB in the end (delta: 1.9 GB). Free memory was 1.4 GB in the beginning and 3.1 GB in the end (delta: -1.7 GB). Peak memory consumption was 2.8 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 NestedInterpolantsBuilder was constructing predicates for 21 interpolants. - StatisticsResult: Ultimate Automizer benchmark data CFG has 1 procedures, 6 locations, 1 error locations. TIMEOUT Result, 258.9s OverallTime, 20 OverallIterations, 19 TraceHistogramMax, 3.4s 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.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 244 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 243 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 132 ImplicationChecksByTransitivity, 241.0s 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, 251.0s 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-09-26_08-24-38-418.csv Written .csv to /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/csv/ArrayInit01.bpl_AutomizerBpl-nestedInterpolants.epf_AutomizerBplInline.xml/Csv-TraceAbstractionBenchmarks-0-2018-09-26_08-24-38-418.csv Completed graceful shutdown