java -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/chccomp2018/chcToBoogie_automizer.epf -i /storage/chc-comp/vmt-chc-benchmarks/lustre/car_5_e2_405_e2_1083.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 13:55:38,560 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 13:55:38,562 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 13:55:38,575 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 13:55:38,575 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 13:55:38,576 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 13:55:38,581 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 13:55:38,583 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 13:55:38,586 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 13:55:38,587 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 13:55:38,588 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 13:55:38,588 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 13:55:38,589 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 13:55:38,593 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 13:55:38,593 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 13:55:38,594 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 13:55:38,607 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 13:55:38,609 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 13:55:38,611 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 13:55:38,612 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 13:55:38,613 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 13:55:38,620 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 13:55:38,620 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 13:55:38,621 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 13:55:38,622 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 13:55:38,623 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 13:55:38,623 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 13:55:38,627 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 13:55:38,628 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 13:55:38,628 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 13:55:38,629 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 13:55:38,645 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 13:55:38,645 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 13:55:38,646 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 13:55:38,647 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 13:55:38,647 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 13:55:38,669 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 13:55:38,670 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 13:55:38,671 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 13:55:38,671 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 13:55:38,673 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 13:55:38,673 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 13:55:38,673 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 13:55:38,674 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 13:55:38,674 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 13:55:38,674 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 13:55:38,674 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 13:55:38,675 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 13:55:38,677 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 13:55:38,678 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 13:55:38,678 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 13:55:38,678 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 13:55:38,678 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 13:55:38,680 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 13:55:38,680 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 13:55:38,736 INFO ]: Repository-Root is: /tmp [2018-06-18 13:55:38,755 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 13:55:38,761 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 13:55:38,763 INFO ]: Initializing SmtParser... [2018-06-18 13:55:38,763 INFO ]: SmtParser initialized [2018-06-18 13:55:38,764 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/car_5_e2_405_e2_1083.smt2 [2018-06-18 13:55:38,765 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-18 13:55:38,865 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/car_5_e2_405_e2_1083.smt2 unknown [2018-06-18 13:55:39,338 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/car_5_e2_405_e2_1083.smt2 [2018-06-18 13:55:39,343 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 13:55:39,349 INFO ]: Walking toolchain with 4 elements. [2018-06-18 13:55:39,352 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 13:55:39,352 INFO ]: Initializing ChcToBoogie... [2018-06-18 13:55:39,353 INFO ]: ChcToBoogie initialized [2018-06-18 13:55:39,361 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:55:39" (1/1) ... [2018-06-18 13:55:39,446 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39 Unit [2018-06-18 13:55:39,446 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 13:55:39,447 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 13:55:39,447 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 13:55:39,447 INFO ]: Boogie Preprocessor initialized [2018-06-18 13:55:39,478 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39" (1/1) ... [2018-06-18 13:55:39,478 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39" (1/1) ... [2018-06-18 13:55:39,490 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39" (1/1) ... [2018-06-18 13:55:39,491 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39" (1/1) ... [2018-06-18 13:55:39,506 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39" (1/1) ... [2018-06-18 13:55:39,508 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39" (1/1) ... [2018-06-18 13:55:39,509 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39" (1/1) ... [2018-06-18 13:55:39,512 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 13:55:39,513 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 13:55:39,513 INFO ]: Initializing RCFGBuilder... [2018-06-18 13:55:39,513 INFO ]: RCFGBuilder initialized [2018-06-18 13:55:39,514 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39" (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-18 13:55:39,548 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 13:55:39,548 INFO ]: Found specification of procedure False [2018-06-18 13:55:39,548 INFO ]: Found implementation of procedure False [2018-06-18 13:55:39,548 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-18 13:55:39,548 INFO ]: Found specification of procedure state [2018-06-18 13:55:39,548 INFO ]: Found implementation of procedure state Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 13:55:39,548 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 13:55:39,548 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 13:55:39,548 INFO ]: Found implementation of procedure Ultimate.START [2018-06-18 13:55:39,921 INFO ]: Using library mode [2018-06-18 13:55:39,922 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:55:39 BoogieIcfgContainer [2018-06-18 13:55:39,922 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 13:55:39,923 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 13:55:39,923 INFO ]: Initializing TraceAbstraction... [2018-06-18 13:55:39,926 INFO ]: TraceAbstraction initialized [2018-06-18 13:55:39,927 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 01:55:39" (1/3) ... [2018-06-18 13:55:39,928 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@27a3716c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 01:55:39, skipping insertion in model container [2018-06-18 13:55:39,928 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 01:55:39" (2/3) ... [2018-06-18 13:55:39,928 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@27a3716c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 01:55:39, skipping insertion in model container [2018-06-18 13:55:39,928 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 01:55:39" (3/3) ... [2018-06-18 13:55:39,930 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 13:55:39,938 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 13:55:39,946 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 13:55:39,996 INFO ]: Using default assertion order modulation [2018-06-18 13:55:39,997 INFO ]: Interprodecural is true [2018-06-18 13:55:39,997 INFO ]: Hoare is false [2018-06-18 13:55:39,997 INFO ]: Compute interpolants for FPandBP [2018-06-18 13:55:39,997 INFO ]: Backedges is TWOTRACK [2018-06-18 13:55:39,997 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 13:55:39,997 INFO ]: Difference is false [2018-06-18 13:55:39,997 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 13:55:39,997 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 13:55:40,011 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 13:55:40,022 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 13:55:40,022 INFO ]: Found error trace [2018-06-18 13:55:40,023 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:55:40,023 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:55:40,028 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-18 13:55:40,029 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:55:40,030 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:55:40,070 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:40,071 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:55:40,071 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:40,171 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:40,181 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:55:40,324 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-18 13:55:40,326 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 13:55:40,326 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 13:55:40,328 INFO ]: Interpolant automaton has 4 states [2018-06-18 13:55:40,339 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 13:55:40,339 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 13:55:40,341 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 13:55:40,473 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:55:40,474 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 13:55:40,474 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 13:55:40,476 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 13:55:40,476 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:55:40,486 INFO ]: With dead ends: 13 [2018-06-18 13:55:40,486 INFO ]: Without dead ends: 13 [2018-06-18 13:55:40,488 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 13:55:40,502 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 13:55:40,525 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 13:55:40,526 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 13:55:40,527 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 13:55:40,528 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 13:55:40,528 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:55:40,528 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 13:55:40,528 INFO ]: Interpolant automaton has 4 states. [2018-06-18 13:55:40,528 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 13:55:40,530 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 13:55:40,530 INFO ]: Found error trace [2018-06-18 13:55:40,530 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:55:40,530 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:55:40,530 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-18 13:55:40,530 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:55:40,530 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:55:40,531 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:40,531 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:55:40,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:40,602 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:40,603 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:55:41,473 WARN ]: Spent 612.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 18 [2018-06-18 13:55:41,729 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 1 [2018-06-18 13:55:41,731 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:55:41,731 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:55:41,731 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-18 13:55:41,743 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:55:41,872 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:41,883 INFO ]: Computing forward predicates... [2018-06-18 13:55:42,820 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 5 [2018-06-18 13:55:42,908 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 13:55:42,936 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:55:42,936 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-18 13:55:42,937 INFO ]: Interpolant automaton has 8 states [2018-06-18 13:55:42,937 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-18 13:55:42,937 INFO ]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2018-06-18 13:55:42,937 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 8 states. [2018-06-18 13:55:43,229 WARN ]: Spent 197.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-18 13:55:43,477 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:55:43,478 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-18 13:55:43,478 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-18 13:55:43,478 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-18 13:55:43,478 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:55:43,479 INFO ]: With dead ends: 15 [2018-06-18 13:55:43,479 INFO ]: Without dead ends: 15 [2018-06-18 13:55:43,480 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-06-18 13:55:43,480 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-18 13:55:43,482 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-18 13:55:43,482 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-18 13:55:43,483 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-18 13:55:43,483 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-18 13:55:43,483 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:55:43,483 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-18 13:55:43,483 INFO ]: Interpolant automaton has 8 states. [2018-06-18 13:55:43,483 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-18 13:55:43,484 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-18 13:55:43,484 INFO ]: Found error trace [2018-06-18 13:55:43,484 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:55:43,484 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:55:43,484 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-18 13:55:43,484 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:55:43,484 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:55:43,485 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:43,485 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:55:43,485 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:43,532 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:43,533 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:55:43,958 WARN ]: Spent 228.00 ms on a formula simplification that was a NOOP. DAG size: 16 [2018-06-18 13:55:44,278 WARN ]: Spent 235.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 31 [2018-06-18 13:55:44,342 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:55:44,342 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:55:44,342 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-18 13:55:44,349 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-18 13:55:44,435 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 13:55:44,435 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:44,440 INFO ]: Computing forward predicates... [2018-06-18 13:55:45,195 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 13:55:45,230 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:55:45,230 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-18 13:55:45,231 INFO ]: Interpolant automaton has 13 states [2018-06-18 13:55:45,231 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-18 13:55:45,231 INFO ]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2018-06-18 13:55:45,231 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 13 states. [2018-06-18 13:55:45,495 WARN ]: Spent 190.00 ms on a formula simplification that was a NOOP. DAG size: 54 [2018-06-18 13:55:45,738 WARN ]: Spent 135.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 48 [2018-06-18 13:55:45,823 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:55:45,823 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-18 13:55:45,824 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-18 13:55:45,824 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-18 13:55:45,824 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:55:45,825 INFO ]: With dead ends: 17 [2018-06-18 13:55:45,825 INFO ]: Without dead ends: 17 [2018-06-18 13:55:45,825 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=64, Invalid=208, Unknown=0, NotChecked=0, Total=272 [2018-06-18 13:55:45,825 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-18 13:55:45,828 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-18 13:55:45,828 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-18 13:55:45,829 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-18 13:55:45,829 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-18 13:55:45,829 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:55:45,829 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-18 13:55:45,829 INFO ]: Interpolant automaton has 13 states. [2018-06-18 13:55:45,829 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-18 13:55:45,830 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-18 13:55:45,830 INFO ]: Found error trace [2018-06-18 13:55:45,830 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:55:45,830 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:55:45,830 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-18 13:55:45,830 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:55:45,830 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:55:45,831 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:45,831 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:55:45,831 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:45,875 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:45,876 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:55:46,204 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:55:46,204 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:55:46,204 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-18 13:55:46,220 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-18 13:55:46,337 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-18 13:55:46,337 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:46,343 INFO ]: Computing forward predicates... [2018-06-18 13:55:46,905 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 13:55:46,927 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:55:46,927 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2018-06-18 13:55:46,927 INFO ]: Interpolant automaton has 16 states [2018-06-18 13:55:46,928 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-18 13:55:46,928 INFO ]: CoverageRelationStatistics Valid=34, Invalid=206, Unknown=0, NotChecked=0, Total=240 [2018-06-18 13:55:46,928 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 16 states. [2018-06-18 13:55:47,149 WARN ]: Spent 188.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 66 [2018-06-18 13:55:47,376 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 48 [2018-06-18 13:55:47,592 WARN ]: Spent 193.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 64 [2018-06-18 13:55:47,802 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 58 [2018-06-18 13:55:47,837 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:55:47,837 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-18 13:55:47,839 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-18 13:55:47,839 INFO ]: Start accepts. Automaton has 16 states. Word has length 21 [2018-06-18 13:55:47,840 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:55:47,840 INFO ]: With dead ends: 19 [2018-06-18 13:55:47,840 INFO ]: Without dead ends: 19 [2018-06-18 13:55:47,840 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=91, Invalid=329, Unknown=0, NotChecked=0, Total=420 [2018-06-18 13:55:47,841 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-18 13:55:47,844 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-18 13:55:47,844 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-18 13:55:47,844 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-18 13:55:47,844 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-18 13:55:47,845 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:55:47,845 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-18 13:55:47,845 INFO ]: Interpolant automaton has 16 states. [2018-06-18 13:55:47,845 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-18 13:55:47,845 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-18 13:55:47,845 INFO ]: Found error trace [2018-06-18 13:55:47,846 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:55:47,846 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:55:47,846 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-18 13:55:47,846 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:55:47,846 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:55:47,847 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:47,847 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:55:47,847 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:47,918 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:47,919 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:55:48,458 WARN ]: Spent 201.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 32 [2018-06-18 13:55:48,744 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 15 [2018-06-18 13:55:48,853 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 13:55:48,853 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:55:48,853 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-18 13:55:48,865 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-18 13:55:48,961 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-18 13:55:48,961 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:48,967 INFO ]: Computing forward predicates... [2018-06-18 13:55:49,598 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 13:55:49,620 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:55:49,620 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 20 [2018-06-18 13:55:49,620 INFO ]: Interpolant automaton has 20 states [2018-06-18 13:55:49,620 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-18 13:55:49,621 INFO ]: CoverageRelationStatistics Valid=54, Invalid=326, Unknown=0, NotChecked=0, Total=380 [2018-06-18 13:55:49,621 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 20 states. [2018-06-18 13:55:49,903 WARN ]: Spent 249.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 89 [2018-06-18 13:55:50,255 WARN ]: Spent 290.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 73 [2018-06-18 13:55:50,576 WARN ]: Spent 283.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 75 [2018-06-18 13:55:50,930 WARN ]: Spent 319.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 77 [2018-06-18 13:55:51,125 WARN ]: Spent 161.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 68 [2018-06-18 13:55:51,294 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:55:51,294 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-18 13:55:51,295 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-18 13:55:51,295 INFO ]: Start accepts. Automaton has 20 states. Word has length 25 [2018-06-18 13:55:51,295 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:55:51,295 INFO ]: With dead ends: 21 [2018-06-18 13:55:51,295 INFO ]: Without dead ends: 21 [2018-06-18 13:55:51,296 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=139, Invalid=511, Unknown=0, NotChecked=0, Total=650 [2018-06-18 13:55:51,296 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-18 13:55:51,299 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-18 13:55:51,299 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-18 13:55:51,300 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-18 13:55:51,300 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-18 13:55:51,300 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:55:51,300 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-18 13:55:51,300 INFO ]: Interpolant automaton has 20 states. [2018-06-18 13:55:51,300 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-18 13:55:51,301 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-18 13:55:51,301 INFO ]: Found error trace [2018-06-18 13:55:51,301 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:55:51,301 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:55:51,301 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-18 13:55:51,301 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:55:51,301 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:55:51,302 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:51,302 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:55:51,302 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:51,357 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:51,357 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:55:52,077 WARN ]: Spent 472.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 11 [2018-06-18 13:55:52,260 WARN ]: Spent 109.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 26 [2018-06-18 13:55:52,782 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 13:55:52,783 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:55:52,783 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-18 13:55:52,793 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-18 13:55:52,900 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-18 13:55:52,901 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:52,907 INFO ]: Computing forward predicates... [2018-06-18 13:55:54,609 WARN ]: Spent 393.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 8 [2018-06-18 13:55:55,073 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 13:55:55,095 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:55:55,095 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 24 [2018-06-18 13:55:55,095 INFO ]: Interpolant automaton has 24 states [2018-06-18 13:55:55,095 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-18 13:55:55,095 INFO ]: CoverageRelationStatistics Valid=59, Invalid=493, Unknown=0, NotChecked=0, Total=552 [2018-06-18 13:55:55,095 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 24 states. [2018-06-18 13:55:55,305 WARN ]: Spent 148.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 61 [2018-06-18 13:55:55,704 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 67 [2018-06-18 13:55:56,071 WARN ]: Spent 308.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 68 [2018-06-18 13:55:56,263 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 65 [2018-06-18 13:55:56,621 WARN ]: Spent 187.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 69 [2018-06-18 13:55:56,791 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 57 [2018-06-18 13:55:56,835 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:55:56,835 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-18 13:55:56,835 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-18 13:55:56,835 INFO ]: Start accepts. Automaton has 24 states. Word has length 29 [2018-06-18 13:55:56,836 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:55:56,836 INFO ]: With dead ends: 23 [2018-06-18 13:55:56,836 INFO ]: Without dead ends: 23 [2018-06-18 13:55:56,837 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=183, Invalid=747, Unknown=0, NotChecked=0, Total=930 [2018-06-18 13:55:56,837 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-18 13:55:56,841 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-18 13:55:56,841 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-18 13:55:56,842 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-18 13:55:56,842 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-18 13:55:56,842 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:55:56,842 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-18 13:55:56,842 INFO ]: Interpolant automaton has 24 states. [2018-06-18 13:55:56,842 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-18 13:55:56,843 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-18 13:55:56,843 INFO ]: Found error trace [2018-06-18 13:55:56,843 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:55:56,843 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:55:56,843 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-18 13:55:56,843 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:55:56,843 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:55:56,843 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:56,844 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:55:56,844 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:55:56,930 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:56,931 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:55:57,710 WARN ]: Spent 506.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 11 [2018-06-18 13:55:58,335 INFO ]: Checked inductivity of 78 backedges. 1 proven. 55 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-18 13:55:58,336 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:55:58,336 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-18 13:55:58,342 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-18 13:55:58,514 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-18 13:55:58,514 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:55:58,527 INFO ]: Computing forward predicates... [2018-06-18 13:55:59,477 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-18 13:55:59,511 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:55:59,511 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 16] total 27 [2018-06-18 13:55:59,511 INFO ]: Interpolant automaton has 27 states [2018-06-18 13:55:59,512 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-18 13:55:59,512 INFO ]: CoverageRelationStatistics Valid=69, Invalid=633, Unknown=0, NotChecked=0, Total=702 [2018-06-18 13:55:59,512 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 27 states. [2018-06-18 13:55:59,722 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 75 [2018-06-18 13:56:00,322 WARN ]: Spent 466.00 ms on a formula simplification. DAG size of input: 113 DAG size of output: 79 [2018-06-18 13:56:00,769 WARN ]: Spent 315.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 83 [2018-06-18 13:56:01,010 WARN ]: Spent 210.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 88 [2018-06-18 13:56:01,261 WARN ]: Spent 194.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 84 [2018-06-18 13:56:01,588 WARN ]: Spent 286.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 79 [2018-06-18 13:56:01,786 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 71 [2018-06-18 13:56:01,859 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:56:01,859 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-18 13:56:01,860 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-18 13:56:01,860 INFO ]: Start accepts. Automaton has 27 states. Word has length 33 [2018-06-18 13:56:01,860 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:56:01,861 INFO ]: With dead ends: 25 [2018-06-18 13:56:01,861 INFO ]: Without dead ends: 25 [2018-06-18 13:56:01,862 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 112 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=228, Invalid=962, Unknown=0, NotChecked=0, Total=1190 [2018-06-18 13:56:01,862 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-18 13:56:01,867 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-18 13:56:01,867 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-18 13:56:01,867 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-18 13:56:01,867 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-18 13:56:01,868 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:56:01,868 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-18 13:56:01,868 INFO ]: Interpolant automaton has 27 states. [2018-06-18 13:56:01,868 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-18 13:56:01,869 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-18 13:56:01,869 INFO ]: Found error trace [2018-06-18 13:56:01,869 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:56:01,869 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:56:01,871 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-18 13:56:01,871 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:56:01,871 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:56:01,871 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:56:01,871 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:56:01,871 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:56:01,947 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:56:01,948 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:56:02,397 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 26 [2018-06-18 13:56:03,116 WARN ]: Spent 139.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 16 [2018-06-18 13:56:03,136 INFO ]: Checked inductivity of 105 backedges. 0 proven. 74 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-06-18 13:56:03,136 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:56:03,136 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-18 13:56:03,143 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:56:03,295 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:56:03,303 INFO ]: Computing forward predicates... [2018-06-18 13:56:04,244 INFO ]: Checked inductivity of 105 backedges. 0 proven. 71 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2018-06-18 13:56:04,267 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:56:04,267 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 27 [2018-06-18 13:56:04,268 INFO ]: Interpolant automaton has 27 states [2018-06-18 13:56:04,268 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-18 13:56:04,268 INFO ]: CoverageRelationStatistics Valid=99, Invalid=603, Unknown=0, NotChecked=0, Total=702 [2018-06-18 13:56:04,268 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 27 states. [2018-06-18 13:56:04,568 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 56 [2018-06-18 13:56:04,749 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 53 [2018-06-18 13:56:04,905 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 53 [2018-06-18 13:56:05,157 WARN ]: Spent 226.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 56 [2018-06-18 13:56:05,483 WARN ]: Spent 298.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 56 [2018-06-18 13:56:05,721 WARN ]: Spent 206.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 56 [2018-06-18 13:56:05,966 WARN ]: Spent 208.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 56 [2018-06-18 13:56:06,129 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 48 [2018-06-18 13:56:06,179 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:56:06,179 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-18 13:56:06,181 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-18 13:56:06,181 INFO ]: Start accepts. Automaton has 27 states. Word has length 37 [2018-06-18 13:56:06,181 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:56:06,182 INFO ]: With dead ends: 27 [2018-06-18 13:56:06,182 INFO ]: Without dead ends: 27 [2018-06-18 13:56:06,182 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 27 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 135 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=276, Invalid=984, Unknown=0, NotChecked=0, Total=1260 [2018-06-18 13:56:06,182 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-18 13:56:06,186 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-18 13:56:06,186 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-18 13:56:06,186 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-18 13:56:06,186 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-18 13:56:06,187 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:56:06,187 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-18 13:56:06,187 INFO ]: Interpolant automaton has 27 states. [2018-06-18 13:56:06,187 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-18 13:56:06,188 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-18 13:56:06,188 INFO ]: Found error trace [2018-06-18 13:56:06,188 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:56:06,188 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:56:06,188 INFO ]: Analyzing trace with hash -544278078, now seen corresponding path program 8 times [2018-06-18 13:56:06,188 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:56:06,188 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:56:06,189 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:56:06,189 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 13:56:06,189 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:56:06,270 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:56:06,271 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:56:07,311 WARN ]: Spent 305.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 27 [2018-06-18 13:56:07,547 WARN ]: Spent 155.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 25 [2018-06-18 13:56:07,662 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 25 [2018-06-18 13:56:07,829 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 26 [2018-06-18 13:56:08,277 WARN ]: Spent 309.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 20 [2018-06-18 13:56:08,640 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 17 [2018-06-18 13:56:08,826 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 16 [2018-06-18 13:56:08,981 WARN ]: Spent 120.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 16 [2018-06-18 13:56:09,198 WARN ]: Spent 144.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 11 [2018-06-18 13:56:09,332 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 12 [2018-06-18 13:56:09,355 INFO ]: Checked inductivity of 136 backedges. 4 proven. 96 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2018-06-18 13:56:09,355 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:56:09,355 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-18 13:56:09,361 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-18 13:56:09,561 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 13:56:09,561 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:56:09,574 INFO ]: Computing forward predicates... [2018-06-18 13:56:11,006 INFO ]: Checked inductivity of 136 backedges. 0 proven. 94 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2018-06-18 13:56:11,028 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:56:11,028 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 17] total 33 [2018-06-18 13:56:11,028 INFO ]: Interpolant automaton has 33 states [2018-06-18 13:56:11,028 INFO ]: Constructing interpolant automaton starting with 33 interpolants. [2018-06-18 13:56:11,029 INFO ]: CoverageRelationStatistics Valid=119, Invalid=937, Unknown=0, NotChecked=0, Total=1056 [2018-06-18 13:56:11,029 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 33 states. [2018-06-18 13:56:11,271 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 73 [2018-06-18 13:56:11,628 WARN ]: Spent 166.00 ms on a formula simplification. DAG size of input: 87 DAG size of output: 66 [2018-06-18 13:56:11,926 WARN ]: Spent 271.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 72 [2018-06-18 13:56:12,302 WARN ]: Spent 346.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 73 [2018-06-18 13:56:12,821 WARN ]: Spent 433.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 74 [2018-06-18 13:56:13,078 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 74 [2018-06-18 13:56:13,285 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 71 [2018-06-18 13:56:13,529 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 71 [2018-06-18 13:56:13,766 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 65 [2018-06-18 13:56:13,812 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 13:56:13,812 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-18 13:56:13,812 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-18 13:56:13,812 INFO ]: Start accepts. Automaton has 33 states. Word has length 41 [2018-06-18 13:56:13,812 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 13:56:13,813 INFO ]: With dead ends: 29 [2018-06-18 13:56:13,813 INFO ]: Without dead ends: 29 [2018-06-18 13:56:13,814 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 282 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=367, Invalid=1439, Unknown=0, NotChecked=0, Total=1806 [2018-06-18 13:56:13,814 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-18 13:56:13,822 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-18 13:56:13,822 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-18 13:56:13,822 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-18 13:56:13,822 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 41 [2018-06-18 13:56:13,823 INFO ]: Finished accepts. word is rejected. [2018-06-18 13:56:13,823 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-18 13:56:13,823 INFO ]: Interpolant automaton has 33 states. [2018-06-18 13:56:13,823 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-18 13:56:13,824 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-18 13:56:13,824 INFO ]: Found error trace [2018-06-18 13:56:13,824 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 13:56:13,824 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 13:56:13,824 INFO ]: Analyzing trace with hash 1442343014, now seen corresponding path program 9 times [2018-06-18 13:56:13,824 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 13:56:13,824 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 13:56:13,825 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:56:13,825 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 13:56:13,825 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 13:56:14,027 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:56:14,029 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 13:56:15,726 WARN ]: Spent 487.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 26 [2018-06-18 13:56:16,007 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 26 [2018-06-18 13:56:16,211 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 26 [2018-06-18 13:56:16,462 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 24 [2018-06-18 13:56:16,641 WARN ]: Spent 158.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 33 [2018-06-18 13:56:17,228 WARN ]: Spent 526.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 14 [2018-06-18 13:56:17,839 WARN ]: Spent 545.00 ms on a formula simplification. DAG size of input: 211 DAG size of output: 17 [2018-06-18 13:56:18,435 WARN ]: Spent 521.00 ms on a formula simplification. DAG size of input: 271 DAG size of output: 16 [2018-06-18 13:56:18,729 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 218 DAG size of output: 17 [2018-06-18 13:56:19,188 WARN ]: Spent 374.00 ms on a formula simplification. DAG size of input: 268 DAG size of output: 17 [2018-06-18 13:56:19,986 WARN ]: Spent 704.00 ms on a formula simplification. DAG size of input: 212 DAG size of output: 11 [2018-06-18 13:56:20,415 WARN ]: Spent 365.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 16 [2018-06-18 13:56:20,492 INFO ]: Checked inductivity of 171 backedges. 9 proven. 117 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-18 13:56:20,492 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 13:56:20,492 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-18 13:56:20,498 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-18 13:56:20,732 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-18 13:56:20,732 INFO ]: Conjunction of SSA is unsat [2018-06-18 13:56:20,742 INFO ]: Computing forward predicates... [2018-06-18 13:56:24,299 WARN ]: Spent 743.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 40 [2018-06-18 13:56:27,694 WARN ]: Spent 975.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 50 [2018-06-18 13:56:28,456 INFO ]: Checked inductivity of 171 backedges. 3 proven. 120 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2018-06-18 13:56:28,478 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 13:56:28,478 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20] total 38 [2018-06-18 13:56:28,479 INFO ]: Interpolant automaton has 38 states [2018-06-18 13:56:28,479 INFO ]: Constructing interpolant automaton starting with 38 interpolants. [2018-06-18 13:56:28,479 INFO ]: CoverageRelationStatistics Valid=124, Invalid=1282, Unknown=0, NotChecked=0, Total=1406 [2018-06-18 13:56:28,480 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 38 states. [2018-06-18 13:56:29,890 WARN ]: Spent 1.23 s on a formula simplification. DAG size of input: 133 DAG size of output: 103 [2018-06-18 13:56:30,214 WARN ]: Spent 300.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 21 [2018-06-18 13:56:30,852 WARN ]: Spent 285.00 ms on a formula simplification. DAG size of input: 157 DAG size of output: 66 [2018-06-18 13:56:31,187 WARN ]: Spent 283.00 ms on a formula simplification. DAG size of input: 156 DAG size of output: 77 [2018-06-18 13:56:32,428 WARN ]: Spent 1.20 s on a formula simplification. DAG size of input: 150 DAG size of output: 115 [2018-06-18 13:56:33,774 WARN ]: Spent 1.29 s on a formula simplification. DAG size of input: 143 DAG size of output: 110 [2018-06-18 13:56:37,940 WARN ]: Spent 4.01 s on a formula simplification. DAG size of input: 138 DAG size of output: 104 Received shutdown request... [2018-06-18 13:56:41,307 WARN ]: Removed 2 from assertion stack [2018-06-18 13:56:41,307 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-18 13:56:41,308 WARN ]: Verification canceled [2018-06-18 13:56:41,313 WARN ]: Timeout [2018-06-18 13:56:41,313 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 01:56:41 BoogieIcfgContainer [2018-06-18 13:56:41,313 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 13:56:41,316 INFO ]: Toolchain (without parser) took 61972.35 ms. Allocated memory was 297.3 MB in the beginning and 901.3 MB in the end (delta: 604.0 MB). Free memory was 245.7 MB in the beginning and 842.1 MB in the end (delta: -596.4 MB). Peak memory consumption was 681.2 MB. Max. memory is 3.6 GB. [2018-06-18 13:56:41,317 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 297.3 MB. Free memory is still 261.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 13:56:41,317 INFO ]: ChcToBoogie took 93.93 ms. Allocated memory is still 297.3 MB. Free memory was 245.7 MB in the beginning and 241.7 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:56:41,318 INFO ]: Boogie Preprocessor took 65.14 ms. Allocated memory is still 297.3 MB. Free memory is still 241.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 13:56:41,318 INFO ]: RCFGBuilder took 409.22 ms. Allocated memory is still 297.3 MB. Free memory was 241.7 MB in the beginning and 225.7 MB in the end (delta: 16.0 MB). Peak memory consumption was 16.0 MB. Max. memory is 3.6 GB. [2018-06-18 13:56:41,318 INFO ]: TraceAbstraction took 61390.32 ms. Allocated memory was 297.3 MB in the beginning and 901.3 MB in the end (delta: 604.0 MB). Free memory was 225.7 MB in the beginning and 842.1 MB in the end (delta: -616.3 MB). Peak memory consumption was 661.3 MB. Max. memory is 3.6 GB. [2018-06-18 13:56:41,327 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 297.3 MB. Free memory is still 261.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 93.93 ms. Allocated memory is still 297.3 MB. Free memory was 245.7 MB in the beginning and 241.7 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 65.14 ms. Allocated memory is still 297.3 MB. Free memory is still 241.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 409.22 ms. Allocated memory is still 297.3 MB. Free memory was 241.7 MB in the beginning and 225.7 MB in the end (delta: 16.0 MB). Peak memory consumption was 16.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61390.32 ms. Allocated memory was 297.3 MB in the beginning and 901.3 MB in the end (delta: 604.0 MB). Free memory was 225.7 MB in the beginning and 842.1 MB in the end (delta: -616.3 MB). Peak memory consumption was 661.3 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 (29states) and interpolant automaton (currently 10 states, 38 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 136. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 61.3s OverallTime, 10 OverallIterations, 10 TraceHistogramMax, 25.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 106 SDtfs, 418 SDslu, 893 SDs, 0 SdLazy, 733 SolverSat, 516 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 2.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 441 GetRequests, 189 SyntacticMatches, 3 SemanticMatches, 248 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1001 ImplicationChecksByTransitivity, 40.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=29occurred in iteration=9, 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.0s AutomataMinimizationTime, 9 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.7s SatisfiabilityAnalysisTime, 33.1s InterpolantComputationTime, 531 NumberOfCodeBlocks, 531 NumberOfCodeBlocksAsserted, 44 NumberOfCheckSat, 512 ConstructedInterpolants, 0 QuantifiedInterpolants, 182204 SizeOfPredicates, 488 NumberOfNonLiveVariables, 6669 ConjunctsInSsa, 521 ConjunctsInUnsatCore, 19 InterpolantComputations, 1 PerfectInterpolantSequences, 366/1230 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/car_5_e2_405_e2_1083.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_13-56-41-354.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/car_5_e2_405_e2_1083.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_13-56-41-354.csv Completed graceful shutdown