java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/eldarica-misc/LIA/reve/020-horn.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 01:30:24,527 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 01:30:24,529 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 01:30:24,544 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 01:30:24,544 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 01:30:24,545 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 01:30:24,547 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 01:30:24,548 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 01:30:24,550 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 01:30:24,552 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 01:30:24,553 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 01:30:24,553 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 01:30:24,563 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 01:30:24,564 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 01:30:24,567 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 01:30:24,567 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 01:30:24,569 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 01:30:24,571 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 01:30:24,582 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 01:30:24,583 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 01:30:24,584 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 01:30:24,587 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 01:30:24,587 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 01:30:24,587 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 01:30:24,588 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 01:30:24,589 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 01:30:24,601 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 01:30:24,602 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 01:30:24,603 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 01:30:24,603 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 01:30:24,604 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 01:30:24,604 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 01:30:24,604 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 01:30:24,605 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 01:30:24,612 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 01:30:24,612 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 01:30:24,632 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 01:30:24,632 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 01:30:24,632 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 01:30:24,633 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 01:30:24,633 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 01:30:24,637 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 01:30:24,637 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 01:30:24,638 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 01:30:24,638 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:30:24,638 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 01:30:24,638 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 01:30:24,638 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 01:30:24,639 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 01:30:24,639 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 01:30:24,639 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 01:30:24,639 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 01:30:24,639 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 01:30:24,641 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 01:30:24,642 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 01:30:24,695 INFO ]: Repository-Root is: /tmp [2018-06-22 01:30:24,709 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 01:30:24,716 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 01:30:24,717 INFO ]: Initializing SmtParser... [2018-06-22 01:30:24,717 INFO ]: SmtParser initialized [2018-06-22 01:30:24,718 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/reve/020-horn.smt2 [2018-06-22 01:30:24,719 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 01:30:24,800 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/reve/020-horn.smt2 unknown [2018-06-22 01:30:25,039 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/reve/020-horn.smt2 [2018-06-22 01:30:25,044 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 01:30:25,053 INFO ]: Walking toolchain with 4 elements. [2018-06-22 01:30:25,053 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 01:30:25,053 INFO ]: Initializing ChcToBoogie... [2018-06-22 01:30:25,054 INFO ]: ChcToBoogie initialized [2018-06-22 01:30:25,057 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:30:25" (1/1) ... [2018-06-22 01:30:25,121 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25 Unit [2018-06-22 01:30:25,121 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 01:30:25,121 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 01:30:25,121 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 01:30:25,121 INFO ]: Boogie Preprocessor initialized [2018-06-22 01:30:25,142 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25" (1/1) ... [2018-06-22 01:30:25,142 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25" (1/1) ... [2018-06-22 01:30:25,147 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25" (1/1) ... [2018-06-22 01:30:25,148 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25" (1/1) ... [2018-06-22 01:30:25,150 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25" (1/1) ... [2018-06-22 01:30:25,152 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25" (1/1) ... [2018-06-22 01:30:25,154 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25" (1/1) ... [2018-06-22 01:30:25,155 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 01:30:25,156 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 01:30:25,156 INFO ]: Initializing RCFGBuilder... [2018-06-22 01:30:25,156 INFO ]: RCFGBuilder initialized [2018-06-22 01:30:25,158 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 01:30:25,174 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 01:30:25,174 INFO ]: Found specification of procedure gotoProc [2018-06-22 01:30:25,174 INFO ]: Found implementation of procedure gotoProc [2018-06-22 01:30:25,174 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 01:30:25,174 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 01:30:25,174 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:30:25,505 INFO ]: Using library mode [2018-06-22 01:30:25,506 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:30:25 BoogieIcfgContainer [2018-06-22 01:30:25,506 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 01:30:25,507 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 01:30:25,507 INFO ]: Initializing TraceAbstraction... [2018-06-22 01:30:25,511 INFO ]: TraceAbstraction initialized [2018-06-22 01:30:25,511 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:30:25" (1/3) ... [2018-06-22 01:30:25,512 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@58d5286e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:30:25, skipping insertion in model container [2018-06-22 01:30:25,512 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:30:25" (2/3) ... [2018-06-22 01:30:25,512 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@58d5286e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:30:25, skipping insertion in model container [2018-06-22 01:30:25,512 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:30:25" (3/3) ... [2018-06-22 01:30:25,514 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 01:30:25,523 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 01:30:25,531 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 01:30:25,593 INFO ]: Using default assertion order modulation [2018-06-22 01:30:25,594 INFO ]: Interprodecural is true [2018-06-22 01:30:25,594 INFO ]: Hoare is false [2018-06-22 01:30:25,594 INFO ]: Compute interpolants for FPandBP [2018-06-22 01:30:25,594 INFO ]: Backedges is TWOTRACK [2018-06-22 01:30:25,594 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 01:30:25,594 INFO ]: Difference is false [2018-06-22 01:30:25,594 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 01:30:25,594 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 01:30:25,611 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 01:30:25,621 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 01:30:25,622 INFO ]: Found error trace [2018-06-22 01:30:25,626 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:25,626 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:25,631 INFO ]: Analyzing trace with hash -204604396, now seen corresponding path program 1 times [2018-06-22 01:30:25,633 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:25,634 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:25,682 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:25,682 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:25,682 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:25,730 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:25,807 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:25,809 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:30:25,809 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:30:25,810 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:30:25,820 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:30:25,820 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:30:25,822 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 01:30:25,882 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:25,882 INFO ]: Finished difference Result 9 states and 13 transitions. [2018-06-22 01:30:25,882 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:30:25,884 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 01:30:25,884 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:25,892 INFO ]: With dead ends: 9 [2018-06-22 01:30:25,892 INFO ]: Without dead ends: 9 [2018-06-22 01:30:25,894 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 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-06-22 01:30:25,921 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 01:30:25,937 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 01:30:25,938 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 01:30:25,938 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 13 transitions. [2018-06-22 01:30:25,939 INFO ]: Start accepts. Automaton has 9 states and 13 transitions. Word has length 7 [2018-06-22 01:30:25,940 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:25,940 INFO ]: Abstraction has 9 states and 13 transitions. [2018-06-22 01:30:25,940 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:30:25,940 INFO ]: Start isEmpty. Operand 9 states and 13 transitions. [2018-06-22 01:30:25,940 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:30:25,940 INFO ]: Found error trace [2018-06-22 01:30:25,940 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:25,941 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:25,941 INFO ]: Analyzing trace with hash -2057039604, now seen corresponding path program 1 times [2018-06-22 01:30:25,941 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:25,941 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:25,942 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:25,942 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:25,942 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:25,955 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:26,093 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:26,093 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:30:26,093 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:30:26,094 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:30:26,095 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:30:26,095 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:30:26,095 INFO ]: Start difference. First operand 9 states and 13 transitions. Second operand 3 states. [2018-06-22 01:30:26,224 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:26,224 INFO ]: Finished difference Result 10 states and 16 transitions. [2018-06-22 01:30:26,225 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:30:26,225 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:30:26,225 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:26,225 INFO ]: With dead ends: 10 [2018-06-22 01:30:26,225 INFO ]: Without dead ends: 10 [2018-06-22 01:30:26,226 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:30:26,226 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 01:30:26,227 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 01:30:26,227 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 01:30:26,228 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 16 transitions. [2018-06-22 01:30:26,228 INFO ]: Start accepts. Automaton has 10 states and 16 transitions. Word has length 8 [2018-06-22 01:30:26,228 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:26,228 INFO ]: Abstraction has 10 states and 16 transitions. [2018-06-22 01:30:26,228 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:30:26,228 INFO ]: Start isEmpty. Operand 10 states and 16 transitions. [2018-06-22 01:30:26,228 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:30:26,228 INFO ]: Found error trace [2018-06-22 01:30:26,228 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:26,228 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:26,228 INFO ]: Analyzing trace with hash -2053345520, now seen corresponding path program 1 times [2018-06-22 01:30:26,228 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:26,228 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:26,229 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:26,229 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:26,229 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:26,247 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:26,430 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:26,430 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:26,430 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:26,438 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:26,473 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:26,481 INFO ]: Computing forward predicates... [2018-06-22 01:30:26,645 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:26,676 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:26,676 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 01:30:26,677 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:30:26,677 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:30:26,677 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:30:26,677 INFO ]: Start difference. First operand 10 states and 16 transitions. Second operand 5 states. [2018-06-22 01:30:26,939 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:26,939 INFO ]: Finished difference Result 12 states and 20 transitions. [2018-06-22 01:30:26,939 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 01:30:26,939 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 01:30:26,940 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:26,940 INFO ]: With dead ends: 12 [2018-06-22 01:30:26,940 INFO ]: Without dead ends: 12 [2018-06-22 01:30:26,940 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:30:26,940 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 01:30:26,942 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 01:30:26,942 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 01:30:26,942 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 20 transitions. [2018-06-22 01:30:26,943 INFO ]: Start accepts. Automaton has 12 states and 20 transitions. Word has length 8 [2018-06-22 01:30:26,943 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:26,943 INFO ]: Abstraction has 12 states and 20 transitions. [2018-06-22 01:30:26,943 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:30:26,943 INFO ]: Start isEmpty. Operand 12 states and 20 transitions. [2018-06-22 01:30:26,943 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 01:30:26,943 INFO ]: Found error trace [2018-06-22 01:30:26,943 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:26,943 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:26,943 INFO ]: Analyzing trace with hash -2049651436, now seen corresponding path program 1 times [2018-06-22 01:30:26,943 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:26,943 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:26,944 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:26,944 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:26,944 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:26,964 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:27,026 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:27,026 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:30:27,026 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 01:30:27,026 INFO ]: Interpolant automaton has 3 states [2018-06-22 01:30:27,026 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 01:30:27,026 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 01:30:27,026 INFO ]: Start difference. First operand 12 states and 20 transitions. Second operand 3 states. [2018-06-22 01:30:27,044 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:27,044 INFO ]: Finished difference Result 14 states and 26 transitions. [2018-06-22 01:30:27,044 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 01:30:27,044 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-22 01:30:27,044 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:27,045 INFO ]: With dead ends: 14 [2018-06-22 01:30:27,045 INFO ]: Without dead ends: 14 [2018-06-22 01:30:27,045 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 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-06-22 01:30:27,045 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 01:30:27,047 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 12. [2018-06-22 01:30:27,047 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 01:30:27,047 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 20 transitions. [2018-06-22 01:30:27,047 INFO ]: Start accepts. Automaton has 12 states and 20 transitions. Word has length 8 [2018-06-22 01:30:27,047 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:27,047 INFO ]: Abstraction has 12 states and 20 transitions. [2018-06-22 01:30:27,048 INFO ]: Interpolant automaton has 3 states. [2018-06-22 01:30:27,048 INFO ]: Start isEmpty. Operand 12 states and 20 transitions. [2018-06-22 01:30:27,048 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 01:30:27,048 INFO ]: Found error trace [2018-06-22 01:30:27,048 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:27,048 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:27,048 INFO ]: Analyzing trace with hash 879738384, now seen corresponding path program 1 times [2018-06-22 01:30:27,048 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:27,048 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:27,049 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:27,049 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:27,049 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:27,069 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:27,132 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:30:27,132 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:27,132 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:27,140 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:27,177 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:27,179 INFO ]: Computing forward predicates... [2018-06-22 01:30:27,192 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 01:30:27,212 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:27,212 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-22 01:30:27,212 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:30:27,212 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:30:27,212 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:30:27,212 INFO ]: Start difference. First operand 12 states and 20 transitions. Second operand 4 states. [2018-06-22 01:30:27,322 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:27,322 INFO ]: Finished difference Result 14 states and 26 transitions. [2018-06-22 01:30:27,323 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 01:30:27,323 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 01:30:27,323 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:27,323 INFO ]: With dead ends: 14 [2018-06-22 01:30:27,323 INFO ]: Without dead ends: 14 [2018-06-22 01:30:27,324 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 9 SyntacticMatches, 2 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:30:27,324 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 01:30:27,325 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 01:30:27,325 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 01:30:27,326 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 26 transitions. [2018-06-22 01:30:27,326 INFO ]: Start accepts. Automaton has 14 states and 26 transitions. Word has length 9 [2018-06-22 01:30:27,326 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:27,326 INFO ]: Abstraction has 14 states and 26 transitions. [2018-06-22 01:30:27,326 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:30:27,326 INFO ]: Start isEmpty. Operand 14 states and 26 transitions. [2018-06-22 01:30:27,327 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:30:27,327 INFO ]: Found error trace [2018-06-22 01:30:27,327 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:27,328 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:27,328 INFO ]: Analyzing trace with hash -2053505136, now seen corresponding path program 2 times [2018-06-22 01:30:27,329 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:27,329 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:27,329 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:27,329 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:27,329 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:27,351 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:27,466 INFO ]: Checked inductivity of 6 backedges. 1 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:27,466 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:27,466 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:27,476 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:30:27,514 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:30:27,514 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:27,516 INFO ]: Computing forward predicates... [2018-06-22 01:30:27,837 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:27,872 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:27,872 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 01:30:27,872 INFO ]: Interpolant automaton has 9 states [2018-06-22 01:30:27,872 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 01:30:27,872 INFO ]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-06-22 01:30:27,873 INFO ]: Start difference. First operand 14 states and 26 transitions. Second operand 9 states. [2018-06-22 01:30:28,734 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:28,734 INFO ]: Finished difference Result 23 states and 44 transitions. [2018-06-22 01:30:28,734 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 01:30:28,734 INFO ]: Start accepts. Automaton has 9 states. Word has length 10 [2018-06-22 01:30:28,734 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:28,735 INFO ]: With dead ends: 23 [2018-06-22 01:30:28,735 INFO ]: Without dead ends: 12 [2018-06-22 01:30:28,735 INFO ]: 0 DeclaredPredicates, 23 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=98, Invalid=174, Unknown=0, NotChecked=0, Total=272 [2018-06-22 01:30:28,735 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 01:30:28,737 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 01:30:28,737 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 01:30:28,737 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 16 transitions. [2018-06-22 01:30:28,737 INFO ]: Start accepts. Automaton has 12 states and 16 transitions. Word has length 10 [2018-06-22 01:30:28,737 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:28,737 INFO ]: Abstraction has 12 states and 16 transitions. [2018-06-22 01:30:28,737 INFO ]: Interpolant automaton has 9 states. [2018-06-22 01:30:28,737 INFO ]: Start isEmpty. Operand 12 states and 16 transitions. [2018-06-22 01:30:28,737 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:30:28,738 INFO ]: Found error trace [2018-06-22 01:30:28,738 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:28,738 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:28,738 INFO ]: Analyzing trace with hash 1496509588, now seen corresponding path program 2 times [2018-06-22 01:30:28,738 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:28,738 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:28,739 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:28,739 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:28,739 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:28,757 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:28,863 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:28,863 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:28,863 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:28,875 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:30:28,896 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:30:28,896 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:28,898 INFO ]: Computing forward predicates... [2018-06-22 01:30:29,188 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:29,207 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:29,207 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 01:30:29,208 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:30:29,208 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:30:29,208 INFO ]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:30:29,208 INFO ]: Start difference. First operand 12 states and 16 transitions. Second operand 8 states. [2018-06-22 01:30:29,307 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:29,307 INFO ]: Finished difference Result 19 states and 26 transitions. [2018-06-22 01:30:29,307 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 01:30:29,307 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-22 01:30:29,307 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:29,309 INFO ]: With dead ends: 19 [2018-06-22 01:30:29,309 INFO ]: Without dead ends: 19 [2018-06-22 01:30:29,309 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:30:29,309 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 01:30:29,311 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 16. [2018-06-22 01:30:29,311 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-22 01:30:29,312 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 22 transitions. [2018-06-22 01:30:29,312 INFO ]: Start accepts. Automaton has 16 states and 22 transitions. Word has length 10 [2018-06-22 01:30:29,312 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:29,312 INFO ]: Abstraction has 16 states and 22 transitions. [2018-06-22 01:30:29,312 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:30:29,312 INFO ]: Start isEmpty. Operand 16 states and 22 transitions. [2018-06-22 01:30:29,312 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 01:30:29,312 INFO ]: Found error trace [2018-06-22 01:30:29,312 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:29,313 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:29,313 INFO ]: Analyzing trace with hash 1611026192, now seen corresponding path program 3 times [2018-06-22 01:30:29,313 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:29,313 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:29,313 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:29,313 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:29,314 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:29,332 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:29,418 INFO ]: Checked inductivity of 6 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:29,418 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:29,418 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:29,428 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:30:29,459 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 01:30:29,459 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:29,461 INFO ]: Computing forward predicates... [2018-06-22 01:30:29,530 INFO ]: Checked inductivity of 6 backedges. 5 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:29,549 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:29,549 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-22 01:30:29,549 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:30:29,549 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:30:29,549 INFO ]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:30:29,549 INFO ]: Start difference. First operand 16 states and 22 transitions. Second operand 8 states. [2018-06-22 01:30:29,610 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:29,610 INFO ]: Finished difference Result 20 states and 29 transitions. [2018-06-22 01:30:29,611 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 01:30:29,611 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-22 01:30:29,611 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:29,611 INFO ]: With dead ends: 20 [2018-06-22 01:30:29,611 INFO ]: Without dead ends: 20 [2018-06-22 01:30:29,612 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=62, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:30:29,612 INFO ]: Start minimizeSevpa. Operand 20 states. [2018-06-22 01:30:29,613 INFO ]: Finished minimizeSevpa. Reduced states from 20 to 19. [2018-06-22 01:30:29,614 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 01:30:29,614 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 28 transitions. [2018-06-22 01:30:29,614 INFO ]: Start accepts. Automaton has 19 states and 28 transitions. Word has length 10 [2018-06-22 01:30:29,614 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:29,614 INFO ]: Abstraction has 19 states and 28 transitions. [2018-06-22 01:30:29,614 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:30:29,614 INFO ]: Start isEmpty. Operand 19 states and 28 transitions. [2018-06-22 01:30:29,614 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:30:29,614 INFO ]: Found error trace [2018-06-22 01:30:29,614 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:29,614 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:29,615 INFO ]: Analyzing trace with hash -1603372140, now seen corresponding path program 4 times [2018-06-22 01:30:29,615 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:29,615 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:29,615 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:29,615 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:29,615 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:29,628 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:29,672 INFO ]: Checked inductivity of 10 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:30:29,673 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:29,673 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:29,681 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:30:29,707 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:30:29,707 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:29,710 INFO ]: Computing forward predicates... [2018-06-22 01:30:29,739 INFO ]: Checked inductivity of 10 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:30:29,758 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:29,758 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2018-06-22 01:30:29,758 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:30:29,758 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:30:29,758 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:30:29,758 INFO ]: Start difference. First operand 19 states and 28 transitions. Second operand 5 states. [2018-06-22 01:30:29,792 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:29,792 INFO ]: Finished difference Result 30 states and 49 transitions. [2018-06-22 01:30:29,792 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 01:30:29,793 INFO ]: Start accepts. Automaton has 5 states. Word has length 11 [2018-06-22 01:30:29,793 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:29,793 INFO ]: With dead ends: 30 [2018-06-22 01:30:29,793 INFO ]: Without dead ends: 30 [2018-06-22 01:30:29,793 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 6 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:30:29,794 INFO ]: Start minimizeSevpa. Operand 30 states. [2018-06-22 01:30:29,796 INFO ]: Finished minimizeSevpa. Reduced states from 30 to 18. [2018-06-22 01:30:29,796 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-22 01:30:29,796 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 26 transitions. [2018-06-22 01:30:29,796 INFO ]: Start accepts. Automaton has 18 states and 26 transitions. Word has length 11 [2018-06-22 01:30:29,796 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:29,796 INFO ]: Abstraction has 18 states and 26 transitions. [2018-06-22 01:30:29,796 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:30:29,796 INFO ]: Start isEmpty. Operand 18 states and 26 transitions. [2018-06-22 01:30:29,797 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 01:30:29,797 INFO ]: Found error trace [2018-06-22 01:30:29,797 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:29,797 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:29,797 INFO ]: Analyzing trace with hash 1829494672, now seen corresponding path program 5 times [2018-06-22 01:30:29,797 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:29,797 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:29,798 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:29,798 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:29,798 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:29,809 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:30,192 INFO ]: Checked inductivity of 15 backedges. 1 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:30,192 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:30,192 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:30,199 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:30:30,220 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 01:30:30,220 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:30,222 INFO ]: Computing forward predicates... [2018-06-22 01:30:30,355 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:30,387 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:30,387 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 01:30:30,387 INFO ]: Interpolant automaton has 11 states [2018-06-22 01:30:30,388 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 01:30:30,388 INFO ]: CoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:30:30,388 INFO ]: Start difference. First operand 18 states and 26 transitions. Second operand 11 states. [2018-06-22 01:30:30,682 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:30,682 INFO ]: Finished difference Result 32 states and 46 transitions. [2018-06-22 01:30:30,683 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-22 01:30:30,683 INFO ]: Start accepts. Automaton has 11 states. Word has length 12 [2018-06-22 01:30:30,683 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:30,683 INFO ]: With dead ends: 32 [2018-06-22 01:30:30,683 INFO ]: Without dead ends: 32 [2018-06-22 01:30:30,684 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=68, Invalid=204, Unknown=0, NotChecked=0, Total=272 [2018-06-22 01:30:30,684 INFO ]: Start minimizeSevpa. Operand 32 states. [2018-06-22 01:30:30,687 INFO ]: Finished minimizeSevpa. Reduced states from 32 to 21. [2018-06-22 01:30:30,687 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 01:30:30,687 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 30 transitions. [2018-06-22 01:30:30,687 INFO ]: Start accepts. Automaton has 21 states and 30 transitions. Word has length 12 [2018-06-22 01:30:30,688 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:30,688 INFO ]: Abstraction has 21 states and 30 transitions. [2018-06-22 01:30:30,688 INFO ]: Interpolant automaton has 11 states. [2018-06-22 01:30:30,688 INFO ]: Start isEmpty. Operand 21 states and 30 transitions. [2018-06-22 01:30:30,688 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 01:30:30,688 INFO ]: Found error trace [2018-06-22 01:30:30,688 INFO ]: trace histogram [3, 3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:30,688 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:30,688 INFO ]: Analyzing trace with hash -744509808, now seen corresponding path program 6 times [2018-06-22 01:30:30,688 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:30,688 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:30,689 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:30,689 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:30,689 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:30,702 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:30,794 INFO ]: Checked inductivity of 21 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 01:30:30,794 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:30,794 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:30,803 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:30:30,825 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-22 01:30:30,825 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:30,828 INFO ]: Computing forward predicates... [2018-06-22 01:30:30,844 INFO ]: Checked inductivity of 21 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 01:30:30,869 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:30,869 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 01:30:30,870 INFO ]: Interpolant automaton has 6 states [2018-06-22 01:30:30,870 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 01:30:30,870 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-22 01:30:30,870 INFO ]: Start difference. First operand 21 states and 30 transitions. Second operand 6 states. [2018-06-22 01:30:30,912 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:30,912 INFO ]: Finished difference Result 39 states and 63 transitions. [2018-06-22 01:30:30,912 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:30:30,912 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 01:30:30,912 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:30,912 INFO ]: With dead ends: 39 [2018-06-22 01:30:30,912 INFO ]: Without dead ends: 39 [2018-06-22 01:30:30,913 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 9 SyntacticMatches, 8 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:30:30,913 INFO ]: Start minimizeSevpa. Operand 39 states. [2018-06-22 01:30:30,916 INFO ]: Finished minimizeSevpa. Reduced states from 39 to 31. [2018-06-22 01:30:30,916 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 01:30:30,916 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 50 transitions. [2018-06-22 01:30:30,917 INFO ]: Start accepts. Automaton has 31 states and 50 transitions. Word has length 13 [2018-06-22 01:30:30,917 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:30,917 INFO ]: Abstraction has 31 states and 50 transitions. [2018-06-22 01:30:30,917 INFO ]: Interpolant automaton has 6 states. [2018-06-22 01:30:30,917 INFO ]: Start isEmpty. Operand 31 states and 50 transitions. [2018-06-22 01:30:30,917 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 01:30:30,917 INFO ]: Found error trace [2018-06-22 01:30:30,917 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:30,917 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:30,917 INFO ]: Analyzing trace with hash -1610544108, now seen corresponding path program 7 times [2018-06-22 01:30:30,917 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:30,917 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:30,918 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:30,918 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:30,918 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:30,931 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:31,050 INFO ]: Checked inductivity of 28 backedges. 3 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:31,051 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:31,051 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:31,056 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:31,085 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:31,087 INFO ]: Computing forward predicates... [2018-06-22 01:30:31,288 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:31,308 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:31,308 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-22 01:30:31,308 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:30:31,308 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:30:31,308 INFO ]: CoverageRelationStatistics Valid=44, Invalid=138, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:30:31,308 INFO ]: Start difference. First operand 31 states and 50 transitions. Second operand 14 states. [2018-06-22 01:30:31,843 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:31,843 INFO ]: Finished difference Result 51 states and 69 transitions. [2018-06-22 01:30:31,843 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-22 01:30:31,844 INFO ]: Start accepts. Automaton has 14 states. Word has length 14 [2018-06-22 01:30:31,844 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:31,844 INFO ]: With dead ends: 51 [2018-06-22 01:30:31,844 INFO ]: Without dead ends: 51 [2018-06-22 01:30:31,845 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 117 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=149, Invalid=501, Unknown=0, NotChecked=0, Total=650 [2018-06-22 01:30:31,845 INFO ]: Start minimizeSevpa. Operand 51 states. [2018-06-22 01:30:31,847 INFO ]: Finished minimizeSevpa. Reduced states from 51 to 30. [2018-06-22 01:30:31,848 INFO ]: Start removeUnreachable. Operand 30 states. [2018-06-22 01:30:31,848 INFO ]: Finished removeUnreachable. Reduced from 30 states to 30 states and 44 transitions. [2018-06-22 01:30:31,848 INFO ]: Start accepts. Automaton has 30 states and 44 transitions. Word has length 14 [2018-06-22 01:30:31,848 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:31,848 INFO ]: Abstraction has 30 states and 44 transitions. [2018-06-22 01:30:31,848 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:30:31,848 INFO ]: Start isEmpty. Operand 30 states and 44 transitions. [2018-06-22 01:30:31,849 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 01:30:31,849 INFO ]: Found error trace [2018-06-22 01:30:31,849 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:31,849 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:31,849 INFO ]: Analyzing trace with hash 1065729936, now seen corresponding path program 8 times [2018-06-22 01:30:31,849 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:31,849 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:31,850 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:31,850 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:31,850 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:31,861 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:31,963 INFO ]: Checked inductivity of 28 backedges. 16 proven. 10 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:30:31,963 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:31,963 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:31,969 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:30:32,001 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:30:32,001 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:32,003 INFO ]: Computing forward predicates... [2018-06-22 01:30:32,270 INFO ]: Checked inductivity of 28 backedges. 22 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:32,289 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:32,289 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 9] total 14 [2018-06-22 01:30:32,289 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:30:32,289 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:30:32,290 INFO ]: CoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:30:32,290 INFO ]: Start difference. First operand 30 states and 44 transitions. Second operand 14 states. [2018-06-22 01:30:32,677 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:32,677 INFO ]: Finished difference Result 58 states and 88 transitions. [2018-06-22 01:30:32,677 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-22 01:30:32,677 INFO ]: Start accepts. Automaton has 14 states. Word has length 14 [2018-06-22 01:30:32,677 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:32,678 INFO ]: With dead ends: 58 [2018-06-22 01:30:32,678 INFO ]: Without dead ends: 58 [2018-06-22 01:30:32,679 INFO ]: 0 DeclaredPredicates, 36 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 100 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=296, Invalid=460, Unknown=0, NotChecked=0, Total=756 [2018-06-22 01:30:32,679 INFO ]: Start minimizeSevpa. Operand 58 states. [2018-06-22 01:30:32,684 INFO ]: Finished minimizeSevpa. Reduced states from 58 to 36. [2018-06-22 01:30:32,684 INFO ]: Start removeUnreachable. Operand 36 states. [2018-06-22 01:30:32,685 INFO ]: Finished removeUnreachable. Reduced from 36 states to 36 states and 58 transitions. [2018-06-22 01:30:32,685 INFO ]: Start accepts. Automaton has 36 states and 58 transitions. Word has length 14 [2018-06-22 01:30:32,685 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:32,685 INFO ]: Abstraction has 36 states and 58 transitions. [2018-06-22 01:30:32,685 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:30:32,685 INFO ]: Start isEmpty. Operand 36 states and 58 transitions. [2018-06-22 01:30:32,686 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-22 01:30:32,686 INFO ]: Found error trace [2018-06-22 01:30:32,686 INFO ]: trace histogram [4, 4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:32,686 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:32,686 INFO ]: Analyzing trace with hash -1327686892, now seen corresponding path program 9 times [2018-06-22 01:30:32,686 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:32,686 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:32,687 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:32,687 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:32,687 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:32,699 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:33,034 INFO ]: Checked inductivity of 36 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-22 01:30:33,034 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:33,034 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:33,040 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:30:33,086 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 01:30:33,086 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:33,088 INFO ]: Computing forward predicates... [2018-06-22 01:30:33,270 INFO ]: Checked inductivity of 36 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-22 01:30:33,300 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:33,300 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-06-22 01:30:33,301 INFO ]: Interpolant automaton has 7 states [2018-06-22 01:30:33,301 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 01:30:33,301 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:30:33,301 INFO ]: Start difference. First operand 36 states and 58 transitions. Second operand 7 states. [2018-06-22 01:30:33,417 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:33,417 INFO ]: Finished difference Result 66 states and 112 transitions. [2018-06-22 01:30:33,417 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 01:30:33,417 INFO ]: Start accepts. Automaton has 7 states. Word has length 15 [2018-06-22 01:30:33,417 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:33,418 INFO ]: With dead ends: 66 [2018-06-22 01:30:33,418 INFO ]: Without dead ends: 66 [2018-06-22 01:30:33,419 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 9 SyntacticMatches, 11 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:30:33,419 INFO ]: Start minimizeSevpa. Operand 66 states. [2018-06-22 01:30:33,430 INFO ]: Finished minimizeSevpa. Reduced states from 66 to 37. [2018-06-22 01:30:33,430 INFO ]: Start removeUnreachable. Operand 37 states. [2018-06-22 01:30:33,432 INFO ]: Finished removeUnreachable. Reduced from 37 states to 37 states and 60 transitions. [2018-06-22 01:30:33,432 INFO ]: Start accepts. Automaton has 37 states and 60 transitions. Word has length 15 [2018-06-22 01:30:33,432 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:33,432 INFO ]: Abstraction has 37 states and 60 transitions. [2018-06-22 01:30:33,432 INFO ]: Interpolant automaton has 7 states. [2018-06-22 01:30:33,433 INFO ]: Start isEmpty. Operand 37 states and 60 transitions. [2018-06-22 01:30:33,433 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-22 01:30:33,433 INFO ]: Found error trace [2018-06-22 01:30:33,433 INFO ]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:33,433 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:33,433 INFO ]: Analyzing trace with hash 1785802768, now seen corresponding path program 10 times [2018-06-22 01:30:33,433 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:33,433 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:33,434 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:33,434 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:33,434 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:33,450 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:33,646 INFO ]: Checked inductivity of 45 backedges. 6 proven. 39 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:33,646 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:33,646 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:33,652 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:30:33,678 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:30:33,678 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:33,680 INFO ]: Computing forward predicates... [2018-06-22 01:30:33,878 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:33,900 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:33,900 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 17 [2018-06-22 01:30:33,900 INFO ]: Interpolant automaton has 17 states [2018-06-22 01:30:33,900 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 01:30:33,900 INFO ]: CoverageRelationStatistics Valid=62, Invalid=210, Unknown=0, NotChecked=0, Total=272 [2018-06-22 01:30:33,901 INFO ]: Start difference. First operand 37 states and 60 transitions. Second operand 17 states. [2018-06-22 01:30:34,457 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:34,457 INFO ]: Finished difference Result 79 states and 108 transitions. [2018-06-22 01:30:34,458 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2018-06-22 01:30:34,458 INFO ]: Start accepts. Automaton has 17 states. Word has length 16 [2018-06-22 01:30:34,458 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:34,459 INFO ]: With dead ends: 79 [2018-06-22 01:30:34,459 INFO ]: Without dead ends: 79 [2018-06-22 01:30:34,460 INFO ]: 0 DeclaredPredicates, 47 GetRequests, 7 SyntacticMatches, 5 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 280 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=286, Invalid=1046, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 01:30:34,460 INFO ]: Start minimizeSevpa. Operand 79 states. [2018-06-22 01:30:34,463 INFO ]: Finished minimizeSevpa. Reduced states from 79 to 40. [2018-06-22 01:30:34,463 INFO ]: Start removeUnreachable. Operand 40 states. [2018-06-22 01:30:34,463 INFO ]: Finished removeUnreachable. Reduced from 40 states to 40 states and 64 transitions. [2018-06-22 01:30:34,464 INFO ]: Start accepts. Automaton has 40 states and 64 transitions. Word has length 16 [2018-06-22 01:30:34,464 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:34,464 INFO ]: Abstraction has 40 states and 64 transitions. [2018-06-22 01:30:34,464 INFO ]: Interpolant automaton has 17 states. [2018-06-22 01:30:34,464 INFO ]: Start isEmpty. Operand 40 states and 64 transitions. [2018-06-22 01:30:34,464 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 01:30:34,464 INFO ]: Found error trace [2018-06-22 01:30:34,464 INFO ]: trace histogram [5, 5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:34,464 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:34,464 INFO ]: Analyzing trace with hash -1266319600, now seen corresponding path program 11 times [2018-06-22 01:30:34,464 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:34,464 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:34,465 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:34,465 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:34,465 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:34,479 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:34,583 INFO ]: Checked inductivity of 55 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-22 01:30:34,583 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:34,583 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:34,589 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:30:34,630 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 01:30:34,630 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:34,632 INFO ]: Computing forward predicates... [2018-06-22 01:30:34,710 INFO ]: Checked inductivity of 55 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-22 01:30:34,734 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:34,734 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-22 01:30:34,735 INFO ]: Interpolant automaton has 8 states [2018-06-22 01:30:34,735 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 01:30:34,735 INFO ]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:30:34,735 INFO ]: Start difference. First operand 40 states and 64 transitions. Second operand 8 states. [2018-06-22 01:30:34,787 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:34,787 INFO ]: Finished difference Result 88 states and 150 transitions. [2018-06-22 01:30:34,787 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 01:30:34,787 INFO ]: Start accepts. Automaton has 8 states. Word has length 17 [2018-06-22 01:30:34,787 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:34,788 INFO ]: With dead ends: 88 [2018-06-22 01:30:34,788 INFO ]: Without dead ends: 88 [2018-06-22 01:30:34,788 INFO ]: 0 DeclaredPredicates, 30 GetRequests, 8 SyntacticMatches, 15 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2018-06-22 01:30:34,788 INFO ]: Start minimizeSevpa. Operand 88 states. [2018-06-22 01:30:34,795 INFO ]: Finished minimizeSevpa. Reduced states from 88 to 36. [2018-06-22 01:30:34,795 INFO ]: Start removeUnreachable. Operand 36 states. [2018-06-22 01:30:34,796 INFO ]: Finished removeUnreachable. Reduced from 36 states to 36 states and 56 transitions. [2018-06-22 01:30:34,796 INFO ]: Start accepts. Automaton has 36 states and 56 transitions. Word has length 17 [2018-06-22 01:30:34,796 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:34,796 INFO ]: Abstraction has 36 states and 56 transitions. [2018-06-22 01:30:34,796 INFO ]: Interpolant automaton has 8 states. [2018-06-22 01:30:34,796 INFO ]: Start isEmpty. Operand 36 states and 56 transitions. [2018-06-22 01:30:34,797 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-22 01:30:34,797 INFO ]: Found error trace [2018-06-22 01:30:34,797 INFO ]: trace histogram [6, 5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:34,797 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:34,797 INFO ]: Analyzing trace with hash -606778476, now seen corresponding path program 12 times [2018-06-22 01:30:34,797 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:34,797 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:34,797 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:34,797 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:34,797 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:34,829 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:34,989 INFO ]: Checked inductivity of 66 backedges. 10 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:34,989 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:34,989 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:34,995 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:30:35,038 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 01:30:35,038 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:35,041 INFO ]: Computing forward predicates... [2018-06-22 01:30:35,222 INFO ]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:35,241 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:35,241 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 20 [2018-06-22 01:30:35,241 INFO ]: Interpolant automaton has 20 states [2018-06-22 01:30:35,241 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-22 01:30:35,242 INFO ]: CoverageRelationStatistics Valid=83, Invalid=297, Unknown=0, NotChecked=0, Total=380 [2018-06-22 01:30:35,242 INFO ]: Start difference. First operand 36 states and 56 transitions. Second operand 20 states. [2018-06-22 01:30:36,274 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:36,274 INFO ]: Finished difference Result 95 states and 127 transitions. [2018-06-22 01:30:36,274 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2018-06-22 01:30:36,274 INFO ]: Start accepts. Automaton has 20 states. Word has length 18 [2018-06-22 01:30:36,274 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:36,275 INFO ]: With dead ends: 95 [2018-06-22 01:30:36,275 INFO ]: Without dead ends: 95 [2018-06-22 01:30:36,276 INFO ]: 0 DeclaredPredicates, 61 GetRequests, 7 SyntacticMatches, 6 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 578 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=500, Invalid=1950, Unknown=0, NotChecked=0, Total=2450 [2018-06-22 01:30:36,276 INFO ]: Start minimizeSevpa. Operand 95 states. [2018-06-22 01:30:36,282 INFO ]: Finished minimizeSevpa. Reduced states from 95 to 39. [2018-06-22 01:30:36,282 INFO ]: Start removeUnreachable. Operand 39 states. [2018-06-22 01:30:36,282 INFO ]: Finished removeUnreachable. Reduced from 39 states to 39 states and 60 transitions. [2018-06-22 01:30:36,282 INFO ]: Start accepts. Automaton has 39 states and 60 transitions. Word has length 18 [2018-06-22 01:30:36,282 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:36,282 INFO ]: Abstraction has 39 states and 60 transitions. [2018-06-22 01:30:36,282 INFO ]: Interpolant automaton has 20 states. [2018-06-22 01:30:36,283 INFO ]: Start isEmpty. Operand 39 states and 60 transitions. [2018-06-22 01:30:36,283 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-22 01:30:36,283 INFO ]: Found error trace [2018-06-22 01:30:36,283 INFO ]: trace histogram [6, 6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:36,283 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:36,283 INFO ]: Analyzing trace with hash -233710956, now seen corresponding path program 13 times [2018-06-22 01:30:36,283 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:36,283 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:36,284 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:36,284 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:36,284 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:36,305 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:37,569 INFO ]: Checked inductivity of 78 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:30:37,569 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:37,569 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:37,575 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:37,612 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:37,615 INFO ]: Computing forward predicates... [2018-06-22 01:30:37,665 INFO ]: Checked inductivity of 78 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 01:30:37,684 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:37,684 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2018-06-22 01:30:37,684 INFO ]: Interpolant automaton has 9 states [2018-06-22 01:30:37,684 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 01:30:37,684 INFO ]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-06-22 01:30:37,685 INFO ]: Start difference. First operand 39 states and 60 transitions. Second operand 9 states. [2018-06-22 01:30:37,771 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:37,771 INFO ]: Finished difference Result 106 states and 179 transitions. [2018-06-22 01:30:37,771 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 01:30:37,771 INFO ]: Start accepts. Automaton has 9 states. Word has length 19 [2018-06-22 01:30:37,772 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:37,772 INFO ]: With dead ends: 106 [2018-06-22 01:30:37,772 INFO ]: Without dead ends: 106 [2018-06-22 01:30:37,773 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 8 SyntacticMatches, 18 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:30:37,773 INFO ]: Start minimizeSevpa. Operand 106 states. [2018-06-22 01:30:37,781 INFO ]: Finished minimizeSevpa. Reduced states from 106 to 89. [2018-06-22 01:30:37,781 INFO ]: Start removeUnreachable. Operand 89 states. [2018-06-22 01:30:37,789 INFO ]: Finished removeUnreachable. Reduced from 89 states to 89 states and 160 transitions. [2018-06-22 01:30:37,789 INFO ]: Start accepts. Automaton has 89 states and 160 transitions. Word has length 19 [2018-06-22 01:30:37,789 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:37,789 INFO ]: Abstraction has 89 states and 160 transitions. [2018-06-22 01:30:37,789 INFO ]: Interpolant automaton has 9 states. [2018-06-22 01:30:37,789 INFO ]: Start isEmpty. Operand 89 states and 160 transitions. [2018-06-22 01:30:37,790 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-22 01:30:37,790 INFO ]: Found error trace [2018-06-22 01:30:37,790 INFO ]: trace histogram [7, 6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:37,791 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:37,791 INFO ]: Analyzing trace with hash 1339318416, now seen corresponding path program 14 times [2018-06-22 01:30:37,791 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:37,791 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:37,791 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:37,791 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:37,791 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:37,806 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:37,964 INFO ]: Checked inductivity of 91 backedges. 15 proven. 76 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:37,964 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:37,964 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:37,970 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:30:38,018 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:30:38,018 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:38,022 INFO ]: Computing forward predicates... [2018-06-22 01:30:38,511 INFO ]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:38,535 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:38,549 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 23 [2018-06-22 01:30:38,549 INFO ]: Interpolant automaton has 23 states [2018-06-22 01:30:38,550 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 01:30:38,550 INFO ]: CoverageRelationStatistics Valid=107, Invalid=399, Unknown=0, NotChecked=0, Total=506 [2018-06-22 01:30:38,550 INFO ]: Start difference. First operand 89 states and 160 transitions. Second operand 23 states. [2018-06-22 01:30:40,143 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:40,143 INFO ]: Finished difference Result 129 states and 165 transitions. [2018-06-22 01:30:40,144 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-06-22 01:30:40,144 INFO ]: Start accepts. Automaton has 23 states. Word has length 20 [2018-06-22 01:30:40,144 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:40,145 INFO ]: With dead ends: 129 [2018-06-22 01:30:40,145 INFO ]: Without dead ends: 129 [2018-06-22 01:30:40,146 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 7 SyntacticMatches, 7 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1073 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=814, Invalid=3346, Unknown=0, NotChecked=0, Total=4160 [2018-06-22 01:30:40,146 INFO ]: Start minimizeSevpa. Operand 129 states. [2018-06-22 01:30:40,153 INFO ]: Finished minimizeSevpa. Reduced states from 129 to 54. [2018-06-22 01:30:40,153 INFO ]: Start removeUnreachable. Operand 54 states. [2018-06-22 01:30:40,153 INFO ]: Finished removeUnreachable. Reduced from 54 states to 54 states and 83 transitions. [2018-06-22 01:30:40,153 INFO ]: Start accepts. Automaton has 54 states and 83 transitions. Word has length 20 [2018-06-22 01:30:40,153 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:40,153 INFO ]: Abstraction has 54 states and 83 transitions. [2018-06-22 01:30:40,153 INFO ]: Interpolant automaton has 23 states. [2018-06-22 01:30:40,153 INFO ]: Start isEmpty. Operand 54 states and 83 transitions. [2018-06-22 01:30:40,154 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-22 01:30:40,154 INFO ]: Found error trace [2018-06-22 01:30:40,154 INFO ]: trace histogram [7, 6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:40,154 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:40,154 INFO ]: Analyzing trace with hash -1553519724, now seen corresponding path program 15 times [2018-06-22 01:30:40,154 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:40,154 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:40,155 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:40,155 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:40,155 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:40,172 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:40,459 INFO ]: Checked inductivity of 91 backedges. 49 proven. 37 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-22 01:30:40,459 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:40,459 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:40,466 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:30:40,504 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-06-22 01:30:40,504 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:40,508 INFO ]: Computing forward predicates... [2018-06-22 01:30:40,797 INFO ]: Checked inductivity of 91 backedges. 70 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:40,815 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:40,816 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 15] total 23 [2018-06-22 01:30:40,816 INFO ]: Interpolant automaton has 23 states [2018-06-22 01:30:40,816 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 01:30:40,816 INFO ]: CoverageRelationStatistics Valid=163, Invalid=343, Unknown=0, NotChecked=0, Total=506 [2018-06-22 01:30:40,816 INFO ]: Start difference. First operand 54 states and 83 transitions. Second operand 23 states. [2018-06-22 01:30:42,427 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:42,427 INFO ]: Finished difference Result 154 states and 231 transitions. [2018-06-22 01:30:42,430 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2018-06-22 01:30:42,430 INFO ]: Start accepts. Automaton has 23 states. Word has length 20 [2018-06-22 01:30:42,430 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:42,431 INFO ]: With dead ends: 154 [2018-06-22 01:30:42,431 INFO ]: Without dead ends: 154 [2018-06-22 01:30:42,432 INFO ]: 0 DeclaredPredicates, 76 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 689 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=1500, Invalid=2660, Unknown=0, NotChecked=0, Total=4160 [2018-06-22 01:30:42,432 INFO ]: Start minimizeSevpa. Operand 154 states. [2018-06-22 01:30:42,438 INFO ]: Finished minimizeSevpa. Reduced states from 154 to 65. [2018-06-22 01:30:42,438 INFO ]: Start removeUnreachable. Operand 65 states. [2018-06-22 01:30:42,439 INFO ]: Finished removeUnreachable. Reduced from 65 states to 65 states and 110 transitions. [2018-06-22 01:30:42,439 INFO ]: Start accepts. Automaton has 65 states and 110 transitions. Word has length 20 [2018-06-22 01:30:42,439 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:42,439 INFO ]: Abstraction has 65 states and 110 transitions. [2018-06-22 01:30:42,439 INFO ]: Interpolant automaton has 23 states. [2018-06-22 01:30:42,439 INFO ]: Start isEmpty. Operand 65 states and 110 transitions. [2018-06-22 01:30:42,440 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 01:30:42,440 INFO ]: Found error trace [2018-06-22 01:30:42,440 INFO ]: trace histogram [7, 7, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:42,440 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:42,440 INFO ]: Analyzing trace with hash -920047728, now seen corresponding path program 16 times [2018-06-22 01:30:42,440 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:42,440 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:42,441 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:42,441 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:42,441 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:42,455 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:42,589 INFO ]: Checked inductivity of 105 backedges. 0 proven. 98 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:30:42,589 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:42,589 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 01:30:42,605 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:42,642 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:30:42,642 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:42,645 INFO ]: Computing forward predicates... [2018-06-22 01:30:42,702 INFO ]: Checked inductivity of 105 backedges. 0 proven. 98 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:30:42,721 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:42,721 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-22 01:30:42,721 INFO ]: Interpolant automaton has 10 states [2018-06-22 01:30:42,721 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 01:30:42,721 INFO ]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:30:42,721 INFO ]: Start difference. First operand 65 states and 110 transitions. Second operand 10 states. [2018-06-22 01:30:42,820 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:42,820 INFO ]: Finished difference Result 148 states and 255 transitions. [2018-06-22 01:30:42,820 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 01:30:42,820 INFO ]: Start accepts. Automaton has 10 states. Word has length 21 [2018-06-22 01:30:42,820 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:42,821 INFO ]: With dead ends: 148 [2018-06-22 01:30:42,821 INFO ]: Without dead ends: 148 [2018-06-22 01:30:42,821 INFO ]: 0 DeclaredPredicates, 38 GetRequests, 12 SyntacticMatches, 17 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:30:42,821 INFO ]: Start minimizeSevpa. Operand 148 states. [2018-06-22 01:30:42,825 INFO ]: Finished minimizeSevpa. Reduced states from 148 to 67. [2018-06-22 01:30:42,825 INFO ]: Start removeUnreachable. Operand 67 states. [2018-06-22 01:30:42,826 INFO ]: Finished removeUnreachable. Reduced from 67 states to 67 states and 114 transitions. [2018-06-22 01:30:42,826 INFO ]: Start accepts. Automaton has 67 states and 114 transitions. Word has length 21 [2018-06-22 01:30:42,826 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:42,826 INFO ]: Abstraction has 67 states and 114 transitions. [2018-06-22 01:30:42,826 INFO ]: Interpolant automaton has 10 states. [2018-06-22 01:30:42,826 INFO ]: Start isEmpty. Operand 67 states and 114 transitions. [2018-06-22 01:30:42,827 INFO ]: Finished isEmpty. Found accepting run of length 23 [2018-06-22 01:30:42,827 INFO ]: Found error trace [2018-06-22 01:30:42,827 INFO ]: trace histogram [8, 7, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:42,827 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:42,827 INFO ]: Analyzing trace with hash 1537714964, now seen corresponding path program 17 times [2018-06-22 01:30:42,827 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:42,827 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:42,828 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:42,828 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:42,828 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:42,842 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:43,252 INFO ]: Checked inductivity of 120 backedges. 21 proven. 99 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:43,253 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:43,253 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:43,265 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:30:43,310 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2018-06-22 01:30:43,310 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:43,314 INFO ]: Computing forward predicates... [2018-06-22 01:30:43,677 INFO ]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:43,696 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:43,705 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 26 [2018-06-22 01:30:43,705 INFO ]: Interpolant automaton has 26 states [2018-06-22 01:30:43,705 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 01:30:43,705 INFO ]: CoverageRelationStatistics Valid=134, Invalid=516, Unknown=0, NotChecked=0, Total=650 [2018-06-22 01:30:43,705 INFO ]: Start difference. First operand 67 states and 114 transitions. Second operand 26 states. [2018-06-22 01:30:46,348 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:46,348 INFO ]: Finished difference Result 184 states and 240 transitions. [2018-06-22 01:30:46,349 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 76 states. [2018-06-22 01:30:46,349 INFO ]: Start accepts. Automaton has 26 states. Word has length 22 [2018-06-22 01:30:46,349 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:46,350 INFO ]: With dead ends: 184 [2018-06-22 01:30:46,350 INFO ]: Without dead ends: 184 [2018-06-22 01:30:46,352 INFO ]: 0 DeclaredPredicates, 95 GetRequests, 7 SyntacticMatches, 8 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1839 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=1255, Invalid=5387, Unknown=0, NotChecked=0, Total=6642 [2018-06-22 01:30:46,352 INFO ]: Start minimizeSevpa. Operand 184 states. [2018-06-22 01:30:46,355 INFO ]: Finished minimizeSevpa. Reduced states from 184 to 69. [2018-06-22 01:30:46,355 INFO ]: Start removeUnreachable. Operand 69 states. [2018-06-22 01:30:46,355 INFO ]: Finished removeUnreachable. Reduced from 69 states to 69 states and 116 transitions. [2018-06-22 01:30:46,355 INFO ]: Start accepts. Automaton has 69 states and 116 transitions. Word has length 22 [2018-06-22 01:30:46,356 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:46,356 INFO ]: Abstraction has 69 states and 116 transitions. [2018-06-22 01:30:46,356 INFO ]: Interpolant automaton has 26 states. [2018-06-22 01:30:46,356 INFO ]: Start isEmpty. Operand 69 states and 116 transitions. [2018-06-22 01:30:46,356 INFO ]: Finished isEmpty. Found accepting run of length 24 [2018-06-22 01:30:46,356 INFO ]: Found error trace [2018-06-22 01:30:46,356 INFO ]: trace histogram [8, 8, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:46,356 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:46,357 INFO ]: Analyzing trace with hash -754664940, now seen corresponding path program 18 times [2018-06-22 01:30:46,357 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:46,357 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:46,357 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:46,357 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:46,357 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:46,374 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:46,531 INFO ]: Checked inductivity of 136 backedges. 0 proven. 128 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-22 01:30:46,531 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:46,531 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:46,538 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:30:46,583 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2018-06-22 01:30:46,583 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:46,586 INFO ]: Computing forward predicates... [2018-06-22 01:30:47,672 INFO ]: Checked inductivity of 136 backedges. 0 proven. 128 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-22 01:30:47,692 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:47,692 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 11 [2018-06-22 01:30:47,692 INFO ]: Interpolant automaton has 11 states [2018-06-22 01:30:47,692 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 01:30:47,692 INFO ]: CoverageRelationStatistics Valid=19, Invalid=91, Unknown=0, NotChecked=0, Total=110 [2018-06-22 01:30:47,692 INFO ]: Start difference. First operand 69 states and 116 transitions. Second operand 11 states. [2018-06-22 01:30:47,784 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:47,784 INFO ]: Finished difference Result 176 states and 302 transitions. [2018-06-22 01:30:47,784 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 01:30:47,784 INFO ]: Start accepts. Automaton has 11 states. Word has length 23 [2018-06-22 01:30:47,784 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:47,785 INFO ]: With dead ends: 176 [2018-06-22 01:30:47,785 INFO ]: Without dead ends: 176 [2018-06-22 01:30:47,785 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 9 SyntacticMatches, 23 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2018-06-22 01:30:47,785 INFO ]: Start minimizeSevpa. Operand 176 states. [2018-06-22 01:30:47,789 INFO ]: Finished minimizeSevpa. Reduced states from 176 to 70. [2018-06-22 01:30:47,789 INFO ]: Start removeUnreachable. Operand 70 states. [2018-06-22 01:30:47,790 INFO ]: Finished removeUnreachable. Reduced from 70 states to 70 states and 118 transitions. [2018-06-22 01:30:47,790 INFO ]: Start accepts. Automaton has 70 states and 118 transitions. Word has length 23 [2018-06-22 01:30:47,790 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:47,790 INFO ]: Abstraction has 70 states and 118 transitions. [2018-06-22 01:30:47,790 INFO ]: Interpolant automaton has 11 states. [2018-06-22 01:30:47,790 INFO ]: Start isEmpty. Operand 70 states and 118 transitions. [2018-06-22 01:30:47,790 INFO ]: Finished isEmpty. Found accepting run of length 25 [2018-06-22 01:30:47,790 INFO ]: Found error trace [2018-06-22 01:30:47,790 INFO ]: trace histogram [9, 8, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:47,791 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:47,791 INFO ]: Analyzing trace with hash -1925353200, now seen corresponding path program 19 times [2018-06-22 01:30:47,791 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:47,791 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:47,791 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:47,791 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:47,791 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:47,805 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:48,002 INFO ]: Checked inductivity of 153 backedges. 28 proven. 125 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:48,002 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:48,002 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:48,009 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:48,070 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:48,074 INFO ]: Computing forward predicates... [2018-06-22 01:30:48,598 INFO ]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:48,618 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:48,618 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 29 [2018-06-22 01:30:48,618 INFO ]: Interpolant automaton has 29 states [2018-06-22 01:30:48,618 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-22 01:30:48,619 INFO ]: CoverageRelationStatistics Valid=164, Invalid=648, Unknown=0, NotChecked=0, Total=812 [2018-06-22 01:30:48,619 INFO ]: Start difference. First operand 70 states and 118 transitions. Second operand 29 states. [2018-06-22 01:30:51,147 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 15 [2018-06-22 01:30:52,402 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:52,402 INFO ]: Finished difference Result 215 states and 273 transitions. [2018-06-22 01:30:52,403 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2018-06-22 01:30:52,403 INFO ]: Start accepts. Automaton has 29 states. Word has length 24 [2018-06-22 01:30:52,403 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:52,403 INFO ]: With dead ends: 215 [2018-06-22 01:30:52,403 INFO ]: Without dead ends: 215 [2018-06-22 01:30:52,405 INFO ]: 0 DeclaredPredicates, 115 GetRequests, 7 SyntacticMatches, 9 SemanticMatches, 99 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2962 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=1852, Invalid=8248, Unknown=0, NotChecked=0, Total=10100 [2018-06-22 01:30:52,405 INFO ]: Start minimizeSevpa. Operand 215 states. [2018-06-22 01:30:52,410 INFO ]: Finished minimizeSevpa. Reduced states from 215 to 73. [2018-06-22 01:30:52,410 INFO ]: Start removeUnreachable. Operand 73 states. [2018-06-22 01:30:52,410 INFO ]: Finished removeUnreachable. Reduced from 73 states to 73 states and 122 transitions. [2018-06-22 01:30:52,410 INFO ]: Start accepts. Automaton has 73 states and 122 transitions. Word has length 24 [2018-06-22 01:30:52,410 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:52,410 INFO ]: Abstraction has 73 states and 122 transitions. [2018-06-22 01:30:52,410 INFO ]: Interpolant automaton has 29 states. [2018-06-22 01:30:52,410 INFO ]: Start isEmpty. Operand 73 states and 122 transitions. [2018-06-22 01:30:52,413 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 01:30:52,413 INFO ]: Found error trace [2018-06-22 01:30:52,413 INFO ]: trace histogram [9, 9, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:52,413 INFO ]: === Iteration 25 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:52,413 INFO ]: Analyzing trace with hash -1584218096, now seen corresponding path program 20 times [2018-06-22 01:30:52,413 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:52,413 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:52,413 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:52,413 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:30:52,413 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:52,430 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:52,632 INFO ]: Checked inductivity of 171 backedges. 0 proven. 162 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-22 01:30:52,632 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:52,632 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:52,638 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:30:52,685 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:30:52,685 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:52,689 INFO ]: Computing forward predicates... [2018-06-22 01:30:52,753 INFO ]: Checked inductivity of 171 backedges. 0 proven. 162 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-22 01:30:52,773 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:52,773 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 12 [2018-06-22 01:30:52,773 INFO ]: Interpolant automaton has 12 states [2018-06-22 01:30:52,773 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 01:30:52,774 INFO ]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-06-22 01:30:52,774 INFO ]: Start difference. First operand 73 states and 122 transitions. Second operand 12 states. [2018-06-22 01:30:52,888 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:52,888 INFO ]: Finished difference Result 214 states and 368 transitions. [2018-06-22 01:30:52,888 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 01:30:52,888 INFO ]: Start accepts. Automaton has 12 states. Word has length 25 [2018-06-22 01:30:52,888 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:52,890 INFO ]: With dead ends: 214 [2018-06-22 01:30:52,890 INFO ]: Without dead ends: 214 [2018-06-22 01:30:52,890 INFO ]: 0 DeclaredPredicates, 46 GetRequests, 13 SyntacticMatches, 22 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=32, Invalid=124, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:30:52,890 INFO ]: Start minimizeSevpa. Operand 214 states. [2018-06-22 01:30:52,893 INFO ]: Finished minimizeSevpa. Reduced states from 214 to 65. [2018-06-22 01:30:52,893 INFO ]: Start removeUnreachable. Operand 65 states. [2018-06-22 01:30:52,894 INFO ]: Finished removeUnreachable. Reduced from 65 states to 65 states and 106 transitions. [2018-06-22 01:30:52,894 INFO ]: Start accepts. Automaton has 65 states and 106 transitions. Word has length 25 [2018-06-22 01:30:52,894 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:52,894 INFO ]: Abstraction has 65 states and 106 transitions. [2018-06-22 01:30:52,894 INFO ]: Interpolant automaton has 12 states. [2018-06-22 01:30:52,894 INFO ]: Start isEmpty. Operand 65 states and 106 transitions. [2018-06-22 01:30:52,895 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-22 01:30:52,895 INFO ]: Found error trace [2018-06-22 01:30:52,895 INFO ]: trace histogram [10, 9, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:52,895 INFO ]: === Iteration 26 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:52,895 INFO ]: Analyzing trace with hash -1871697260, now seen corresponding path program 21 times [2018-06-22 01:30:52,895 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:52,895 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:52,895 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:52,895 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:52,895 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:52,919 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:53,166 INFO ]: Checked inductivity of 190 backedges. 36 proven. 154 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:53,166 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:53,166 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 01:30:53,180 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:53,242 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2018-06-22 01:30:53,242 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:53,245 INFO ]: Computing forward predicates... [2018-06-22 01:30:53,614 INFO ]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:53,633 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:53,633 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 32 [2018-06-22 01:30:53,633 INFO ]: Interpolant automaton has 32 states [2018-06-22 01:30:53,634 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-22 01:30:53,634 INFO ]: CoverageRelationStatistics Valid=197, Invalid=795, Unknown=0, NotChecked=0, Total=992 [2018-06-22 01:30:53,634 INFO ]: Start difference. First operand 65 states and 106 transitions. Second operand 32 states. [2018-06-22 01:30:58,161 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:58,161 INFO ]: Finished difference Result 240 states and 301 transitions. [2018-06-22 01:30:58,161 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 114 states. [2018-06-22 01:30:58,161 INFO ]: Start accepts. Automaton has 32 states. Word has length 26 [2018-06-22 01:30:58,161 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:58,162 INFO ]: With dead ends: 240 [2018-06-22 01:30:58,162 INFO ]: Without dead ends: 240 [2018-06-22 01:30:58,165 INFO ]: 0 DeclaredPredicates, 137 GetRequests, 7 SyntacticMatches, 10 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4540 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=2638, Invalid=12124, Unknown=0, NotChecked=0, Total=14762 [2018-06-22 01:30:58,165 INFO ]: Start minimizeSevpa. Operand 240 states. [2018-06-22 01:30:58,169 INFO ]: Finished minimizeSevpa. Reduced states from 240 to 68. [2018-06-22 01:30:58,169 INFO ]: Start removeUnreachable. Operand 68 states. [2018-06-22 01:30:58,169 INFO ]: Finished removeUnreachable. Reduced from 68 states to 68 states and 110 transitions. [2018-06-22 01:30:58,169 INFO ]: Start accepts. Automaton has 68 states and 110 transitions. Word has length 26 [2018-06-22 01:30:58,169 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:58,169 INFO ]: Abstraction has 68 states and 110 transitions. [2018-06-22 01:30:58,169 INFO ]: Interpolant automaton has 32 states. [2018-06-22 01:30:58,169 INFO ]: Start isEmpty. Operand 68 states and 110 transitions. [2018-06-22 01:30:58,170 INFO ]: Finished isEmpty. Found accepting run of length 28 [2018-06-22 01:30:58,170 INFO ]: Found error trace [2018-06-22 01:30:58,170 INFO ]: trace histogram [10, 10, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:58,170 INFO ]: === Iteration 27 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:58,170 INFO ]: Analyzing trace with hash -458376812, now seen corresponding path program 22 times [2018-06-22 01:30:58,170 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:58,170 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:58,171 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:58,171 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:58,171 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:58,193 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:58,682 INFO ]: Checked inductivity of 210 backedges. 0 proven. 200 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 01:30:58,682 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:58,682 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:58,688 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:30:58,754 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:30:58,754 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:58,760 INFO ]: Computing forward predicates... [2018-06-22 01:30:58,887 INFO ]: Checked inductivity of 210 backedges. 0 proven. 200 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 01:30:58,905 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:30:58,905 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 13 [2018-06-22 01:30:58,906 INFO ]: Interpolant automaton has 13 states [2018-06-22 01:30:58,906 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 01:30:58,906 INFO ]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:30:58,906 INFO ]: Start difference. First operand 68 states and 110 transitions. Second operand 13 states. [2018-06-22 01:30:59,053 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:30:59,053 INFO ]: Finished difference Result 246 states and 421 transitions. [2018-06-22 01:30:59,053 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 01:30:59,053 INFO ]: Start accepts. Automaton has 13 states. Word has length 27 [2018-06-22 01:30:59,054 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:30:59,055 INFO ]: With dead ends: 246 [2018-06-22 01:30:59,055 INFO ]: Without dead ends: 246 [2018-06-22 01:30:59,055 INFO ]: 0 DeclaredPredicates, 50 GetRequests, 9 SyntacticMatches, 29 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:30:59,055 INFO ]: Start minimizeSevpa. Operand 246 states. [2018-06-22 01:30:59,064 INFO ]: Finished minimizeSevpa. Reduced states from 246 to 198. [2018-06-22 01:30:59,064 INFO ]: Start removeUnreachable. Operand 198 states. [2018-06-22 01:30:59,065 INFO ]: Finished removeUnreachable. Reduced from 198 states to 198 states and 370 transitions. [2018-06-22 01:30:59,065 INFO ]: Start accepts. Automaton has 198 states and 370 transitions. Word has length 27 [2018-06-22 01:30:59,066 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:30:59,066 INFO ]: Abstraction has 198 states and 370 transitions. [2018-06-22 01:30:59,066 INFO ]: Interpolant automaton has 13 states. [2018-06-22 01:30:59,066 INFO ]: Start isEmpty. Operand 198 states and 370 transitions. [2018-06-22 01:30:59,066 INFO ]: Finished isEmpty. Found accepting run of length 29 [2018-06-22 01:30:59,066 INFO ]: Found error trace [2018-06-22 01:30:59,066 INFO ]: trace histogram [11, 10, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:30:59,066 INFO ]: === Iteration 28 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:30:59,067 INFO ]: Analyzing trace with hash -1330355824, now seen corresponding path program 23 times [2018-06-22 01:30:59,067 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:30:59,067 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:30:59,068 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:59,068 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:30:59,068 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:30:59,085 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:59,563 INFO ]: Checked inductivity of 231 backedges. 45 proven. 186 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:30:59,563 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:30:59,563 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:30:59,570 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 01:30:59,706 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-06-22 01:30:59,706 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:30:59,710 INFO ]: Computing forward predicates... [2018-06-22 01:31:00,154 INFO ]: Checked inductivity of 231 backedges. 0 proven. 231 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:31:00,174 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:31:00,174 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 35 [2018-06-22 01:31:00,174 INFO ]: Interpolant automaton has 35 states [2018-06-22 01:31:00,174 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 01:31:00,174 INFO ]: CoverageRelationStatistics Valid=233, Invalid=957, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 01:31:00,174 INFO ]: Start difference. First operand 198 states and 370 transitions. Second operand 35 states. [2018-06-22 01:31:06,543 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:31:06,543 INFO ]: Finished difference Result 294 states and 359 transitions. [2018-06-22 01:31:06,544 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 136 states. [2018-06-22 01:31:06,544 INFO ]: Start accepts. Automaton has 35 states. Word has length 28 [2018-06-22 01:31:06,544 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:31:06,545 INFO ]: With dead ends: 294 [2018-06-22 01:31:06,545 INFO ]: Without dead ends: 294 [2018-06-22 01:31:06,550 INFO ]: 0 DeclaredPredicates, 161 GetRequests, 7 SyntacticMatches, 11 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6683 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=3648, Invalid=17232, Unknown=0, NotChecked=0, Total=20880 [2018-06-22 01:31:06,550 INFO ]: Start minimizeSevpa. Operand 294 states. [2018-06-22 01:31:06,554 INFO ]: Finished minimizeSevpa. Reduced states from 294 to 91. [2018-06-22 01:31:06,554 INFO ]: Start removeUnreachable. Operand 91 states. [2018-06-22 01:31:06,554 INFO ]: Finished removeUnreachable. Reduced from 91 states to 91 states and 145 transitions. [2018-06-22 01:31:06,555 INFO ]: Start accepts. Automaton has 91 states and 145 transitions. Word has length 28 [2018-06-22 01:31:06,555 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:31:06,555 INFO ]: Abstraction has 91 states and 145 transitions. [2018-06-22 01:31:06,555 INFO ]: Interpolant automaton has 35 states. [2018-06-22 01:31:06,555 INFO ]: Start isEmpty. Operand 91 states and 145 transitions. [2018-06-22 01:31:06,555 INFO ]: Finished isEmpty. Found accepting run of length 29 [2018-06-22 01:31:06,555 INFO ]: Found error trace [2018-06-22 01:31:06,555 INFO ]: trace histogram [11, 10, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:31:06,555 INFO ]: === Iteration 29 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:31:06,555 INFO ]: Analyzing trace with hash 404884116, now seen corresponding path program 24 times [2018-06-22 01:31:06,555 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:31:06,555 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:31:06,558 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:06,558 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:31:06,558 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:06,573 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:06,704 INFO ]: Checked inductivity of 231 backedges. 121 proven. 101 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-22 01:31:06,704 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:31:06,704 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:31:06,711 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 01:31:06,788 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 12 check-sat command(s) [2018-06-22 01:31:06,788 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:06,792 INFO ]: Computing forward predicates... [2018-06-22 01:31:07,491 INFO ]: Checked inductivity of 231 backedges. 176 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:31:07,510 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:31:07,510 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 23] total 35 [2018-06-22 01:31:07,510 INFO ]: Interpolant automaton has 35 states [2018-06-22 01:31:07,510 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-22 01:31:07,510 INFO ]: CoverageRelationStatistics Valid=365, Invalid=825, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 01:31:07,510 INFO ]: Start difference. First operand 91 states and 145 transitions. Second operand 35 states. [2018-06-22 01:31:12,534 WARN ]: Spent 169.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 20 [2018-06-22 01:31:12,612 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:31:12,612 INFO ]: Finished difference Result 361 states and 534 transitions. [2018-06-22 01:31:12,613 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 127 states. [2018-06-22 01:31:12,613 INFO ]: Start accepts. Automaton has 35 states. Word has length 28 [2018-06-22 01:31:12,613 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:31:12,615 INFO ]: With dead ends: 361 [2018-06-22 01:31:12,615 INFO ]: Without dead ends: 361 [2018-06-22 01:31:12,616 INFO ]: 0 DeclaredPredicates, 155 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 138 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3837 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=6578, Invalid=12882, Unknown=0, NotChecked=0, Total=19460 [2018-06-22 01:31:12,617 INFO ]: Start minimizeSevpa. Operand 361 states. [2018-06-22 01:31:12,633 INFO ]: Finished minimizeSevpa. Reduced states from 361 to 121. [2018-06-22 01:31:12,633 INFO ]: Start removeUnreachable. Operand 121 states. [2018-06-22 01:31:12,634 INFO ]: Finished removeUnreachable. Reduced from 121 states to 121 states and 214 transitions. [2018-06-22 01:31:12,634 INFO ]: Start accepts. Automaton has 121 states and 214 transitions. Word has length 28 [2018-06-22 01:31:12,635 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:31:12,635 INFO ]: Abstraction has 121 states and 214 transitions. [2018-06-22 01:31:12,635 INFO ]: Interpolant automaton has 35 states. [2018-06-22 01:31:12,635 INFO ]: Start isEmpty. Operand 121 states and 214 transitions. [2018-06-22 01:31:12,636 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 01:31:12,636 INFO ]: Found error trace [2018-06-22 01:31:12,636 INFO ]: trace histogram [11, 11, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:31:12,636 INFO ]: === Iteration 30 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:31:12,636 INFO ]: Analyzing trace with hash -339070832, now seen corresponding path program 25 times [2018-06-22 01:31:12,636 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:31:12,636 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:31:12,637 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:12,637 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:31:12,637 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:12,661 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:13,033 INFO ]: Checked inductivity of 253 backedges. 0 proven. 242 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-06-22 01:31:13,033 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:31:13,033 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:31:13,041 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:31:13,094 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:13,099 INFO ]: Computing forward predicates... [2018-06-22 01:31:13,282 INFO ]: Checked inductivity of 253 backedges. 0 proven. 242 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2018-06-22 01:31:13,305 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:31:13,305 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 14 [2018-06-22 01:31:13,305 INFO ]: Interpolant automaton has 14 states [2018-06-22 01:31:13,305 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 01:31:13,305 INFO ]: CoverageRelationStatistics Valid=25, Invalid=157, Unknown=0, NotChecked=0, Total=182 [2018-06-22 01:31:13,305 INFO ]: Start difference. First operand 121 states and 214 transitions. Second operand 14 states. [2018-06-22 01:31:13,459 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:31:13,459 INFO ]: Finished difference Result 341 states and 599 transitions. [2018-06-22 01:31:13,459 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 01:31:13,459 INFO ]: Start accepts. Automaton has 14 states. Word has length 29 [2018-06-22 01:31:13,460 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:31:13,461 INFO ]: With dead ends: 341 [2018-06-22 01:31:13,461 INFO ]: Without dead ends: 341 [2018-06-22 01:31:13,461 INFO ]: 0 DeclaredPredicates, 54 GetRequests, 10 SyntacticMatches, 31 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=38, Invalid=172, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:31:13,461 INFO ]: Start minimizeSevpa. Operand 341 states. [2018-06-22 01:31:13,465 INFO ]: Finished minimizeSevpa. Reduced states from 341 to 125. [2018-06-22 01:31:13,465 INFO ]: Start removeUnreachable. Operand 125 states. [2018-06-22 01:31:13,466 INFO ]: Finished removeUnreachable. Reduced from 125 states to 125 states and 222 transitions. [2018-06-22 01:31:13,466 INFO ]: Start accepts. Automaton has 125 states and 222 transitions. Word has length 29 [2018-06-22 01:31:13,466 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:31:13,466 INFO ]: Abstraction has 125 states and 222 transitions. [2018-06-22 01:31:13,466 INFO ]: Interpolant automaton has 14 states. [2018-06-22 01:31:13,466 INFO ]: Start isEmpty. Operand 125 states and 222 transitions. [2018-06-22 01:31:13,466 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-22 01:31:13,466 INFO ]: Found error trace [2018-06-22 01:31:13,466 INFO ]: trace histogram [12, 11, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:31:13,466 INFO ]: === Iteration 31 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:31:13,467 INFO ]: Analyzing trace with hash -1926837740, now seen corresponding path program 26 times [2018-06-22 01:31:13,467 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:31:13,467 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:31:13,467 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:13,467 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:31:13,467 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:13,486 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:14,789 INFO ]: Checked inductivity of 276 backedges. 55 proven. 221 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:31:14,790 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:31:14,790 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:31:14,795 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:31:14,847 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:31:14,847 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:14,851 INFO ]: Computing forward predicates... [2018-06-22 01:31:15,352 INFO ]: Checked inductivity of 276 backedges. 0 proven. 276 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:31:15,371 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:31:15,372 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 26] total 38 [2018-06-22 01:31:15,372 INFO ]: Interpolant automaton has 38 states [2018-06-22 01:31:15,372 INFO ]: Constructing interpolant automaton starting with 38 interpolants. [2018-06-22 01:31:15,372 INFO ]: CoverageRelationStatistics Valid=272, Invalid=1134, Unknown=0, NotChecked=0, Total=1406 [2018-06-22 01:31:15,372 INFO ]: Start difference. First operand 125 states and 222 transitions. Second operand 38 states. [2018-06-22 01:31:23,904 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:31:23,904 INFO ]: Finished difference Result 406 states and 516 transitions. [2018-06-22 01:31:23,905 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 160 states. [2018-06-22 01:31:23,905 INFO ]: Start accepts. Automaton has 38 states. Word has length 30 [2018-06-22 01:31:23,905 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:31:23,906 INFO ]: With dead ends: 406 [2018-06-22 01:31:23,906 INFO ]: Without dead ends: 406 [2018-06-22 01:31:23,909 INFO ]: 0 DeclaredPredicates, 187 GetRequests, 7 SyntacticMatches, 12 SemanticMatches, 168 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9513 ImplicationChecksByTransitivity, 9.8s TimeCoverageRelationStatistics Valid=4921, Invalid=23809, Unknown=0, NotChecked=0, Total=28730 [2018-06-22 01:31:23,909 INFO ]: Start minimizeSevpa. Operand 406 states. [2018-06-22 01:31:23,913 INFO ]: Finished minimizeSevpa. Reduced states from 406 to 125. [2018-06-22 01:31:23,913 INFO ]: Start removeUnreachable. Operand 125 states. [2018-06-22 01:31:23,914 INFO ]: Finished removeUnreachable. Reduced from 125 states to 125 states and 220 transitions. [2018-06-22 01:31:23,914 INFO ]: Start accepts. Automaton has 125 states and 220 transitions. Word has length 30 [2018-06-22 01:31:23,914 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:31:23,914 INFO ]: Abstraction has 125 states and 220 transitions. [2018-06-22 01:31:23,914 INFO ]: Interpolant automaton has 38 states. [2018-06-22 01:31:23,914 INFO ]: Start isEmpty. Operand 125 states and 220 transitions. [2018-06-22 01:31:23,914 INFO ]: Finished isEmpty. Found accepting run of length 32 [2018-06-22 01:31:23,914 INFO ]: Found error trace [2018-06-22 01:31:23,915 INFO ]: trace histogram [12, 12, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:31:23,915 INFO ]: === Iteration 32 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:31:23,915 INFO ]: Analyzing trace with hash 1510267156, now seen corresponding path program 27 times [2018-06-22 01:31:23,915 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:31:23,915 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:31:23,915 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:23,915 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:31:23,915 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:23,936 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:24,155 INFO ]: Checked inductivity of 300 backedges. 0 proven. 288 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-06-22 01:31:24,155 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:31:24,155 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:31:24,161 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:31:24,230 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 13 check-sat command(s) [2018-06-22 01:31:24,230 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:24,235 INFO ]: Computing forward predicates... [2018-06-22 01:31:24,408 INFO ]: Checked inductivity of 300 backedges. 0 proven. 288 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-06-22 01:31:24,428 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:31:24,428 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 15 [2018-06-22 01:31:24,428 INFO ]: Interpolant automaton has 15 states [2018-06-22 01:31:24,428 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 01:31:24,428 INFO ]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:31:24,428 INFO ]: Start difference. First operand 125 states and 220 transitions. Second operand 15 states. [2018-06-22 01:31:24,770 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:31:24,770 INFO ]: Finished difference Result 391 states and 686 transitions. [2018-06-22 01:31:24,770 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-22 01:31:24,770 INFO ]: Start accepts. Automaton has 15 states. Word has length 31 [2018-06-22 01:31:24,771 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:31:24,772 INFO ]: With dead ends: 391 [2018-06-22 01:31:24,772 INFO ]: Without dead ends: 391 [2018-06-22 01:31:24,772 INFO ]: 0 DeclaredPredicates, 58 GetRequests, 11 SyntacticMatches, 33 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2018-06-22 01:31:24,773 INFO ]: Start minimizeSevpa. Operand 391 states. [2018-06-22 01:31:24,779 INFO ]: Finished minimizeSevpa. Reduced states from 391 to 128. [2018-06-22 01:31:24,779 INFO ]: Start removeUnreachable. Operand 128 states. [2018-06-22 01:31:24,780 INFO ]: Finished removeUnreachable. Reduced from 128 states to 128 states and 226 transitions. [2018-06-22 01:31:24,780 INFO ]: Start accepts. Automaton has 128 states and 226 transitions. Word has length 31 [2018-06-22 01:31:24,780 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:31:24,780 INFO ]: Abstraction has 128 states and 226 transitions. [2018-06-22 01:31:24,780 INFO ]: Interpolant automaton has 15 states. [2018-06-22 01:31:24,780 INFO ]: Start isEmpty. Operand 128 states and 226 transitions. [2018-06-22 01:31:24,780 INFO ]: Finished isEmpty. Found accepting run of length 33 [2018-06-22 01:31:24,780 INFO ]: Found error trace [2018-06-22 01:31:24,780 INFO ]: trace histogram [13, 12, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:31:24,780 INFO ]: === Iteration 33 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:31:24,780 INFO ]: Analyzing trace with hash -431934960, now seen corresponding path program 28 times [2018-06-22 01:31:24,780 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:31:24,780 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:31:24,781 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:24,781 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:31:24,781 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:31:24,799 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:25,227 INFO ]: Checked inductivity of 325 backedges. 66 proven. 259 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:31:25,227 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:31:25,227 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:31:25,234 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 01:31:25,292 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 01:31:25,292 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:31:25,298 INFO ]: Computing forward predicates... [2018-06-22 01:31:26,129 INFO ]: Checked inductivity of 325 backedges. 0 proven. 325 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:31:26,150 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:31:26,150 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 41 [2018-06-22 01:31:26,150 INFO ]: Interpolant automaton has 41 states [2018-06-22 01:31:26,150 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 01:31:26,151 INFO ]: CoverageRelationStatistics Valid=314, Invalid=1326, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 01:31:26,151 INFO ]: Start difference. First operand 128 states and 226 transitions. Second operand 41 states. Received shutdown request... [2018-06-22 01:31:27,412 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2018-06-22 01:31:27,447 WARN ]: Verification canceled [2018-06-22 01:31:27,451 WARN ]: Timeout [2018-06-22 01:31:27,451 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 01:31:27 BoogieIcfgContainer [2018-06-22 01:31:27,451 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 01:31:27,452 INFO ]: Toolchain (without parser) took 62407.81 ms. Allocated memory was 307.2 MB in the beginning and 597.7 MB in the end (delta: 290.5 MB). Free memory was 263.6 MB in the beginning and 526.0 MB in the end (delta: -262.4 MB). Peak memory consumption was 28.1 MB. Max. memory is 3.6 GB. [2018-06-22 01:31:27,454 INFO ]: SmtParser took 0.09 ms. Allocated memory is still 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 01:31:27,455 INFO ]: ChcToBoogie took 67.62 ms. Allocated memory is still 307.2 MB. Free memory was 263.6 MB in the beginning and 261.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:31:27,455 INFO ]: Boogie Preprocessor took 33.73 ms. Allocated memory is still 307.2 MB. Free memory was 261.6 MB in the beginning and 259.5 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 3.6 GB. [2018-06-22 01:31:27,455 INFO ]: RCFGBuilder took 350.10 ms. Allocated memory is still 307.2 MB. Free memory was 259.5 MB in the beginning and 251.6 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:31:27,455 INFO ]: TraceAbstraction took 61944.02 ms. Allocated memory was 307.2 MB in the beginning and 597.7 MB in the end (delta: 290.5 MB). Free memory was 251.6 MB in the beginning and 526.0 MB in the end (delta: -274.4 MB). Peak memory consumption was 16.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:31:27,458 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.09 ms. Allocated memory is still 307.2 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 67.62 ms. Allocated memory is still 307.2 MB. Free memory was 263.6 MB in the beginning and 261.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 33.73 ms. Allocated memory is still 307.2 MB. Free memory was 261.6 MB in the beginning and 259.5 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 350.10 ms. Allocated memory is still 307.2 MB. Free memory was 259.5 MB in the beginning and 251.6 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61944.02 ms. Allocated memory was 307.2 MB in the beginning and 597.7 MB in the end (delta: 290.5 MB). Free memory was 251.6 MB in the beginning and 526.0 MB in the end (delta: -274.4 MB). Peak memory consumption was 16.0 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (128states) and interpolant automaton (currently 42 states, 41 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 72 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 61.8s OverallTime, 33 OverallIterations, 13 TraceHistogramMax, 41.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 241 SDtfs, 180 SDslu, 1328 SDs, 0 SdLazy, 5449 SolverSat, 1627 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 5.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1807 GetRequests, 267 SyntacticMatches, 307 SemanticMatches, 1232 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33322 ImplicationChecksByTransitivity, 50.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=198occurred in iteration=27, 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, 32 MinimizatonAttempts, 2453 StatesRemovedByMinimization, 27 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.6s SatisfiabilityAnalysisTime, 17.3s InterpolantComputationTime, 1187 NumberOfCodeBlocks, 1187 NumberOfCodeBlocksAsserted, 159 NumberOfCheckSat, 1124 ConstructedInterpolants, 138 QuantifiedInterpolants, 157002 SizeOfPredicates, 96 NumberOfNonLiveVariables, 9708 ConjunctsInSsa, 2180 ConjunctsInUnsatCore, 63 InterpolantComputations, 3 PerfectInterpolantSequences, 924/6576 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/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/020-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_01-31-27-541.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/020-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_01-31-27-541.csv Completed graceful shutdown