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/MESI_2.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 15:52:29,578 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 15:52:29,579 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 15:52:29,593 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 15:52:29,593 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 15:52:29,594 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 15:52:29,595 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 15:52:29,600 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 15:52:29,601 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 15:52:29,603 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 15:52:29,604 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 15:52:29,604 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 15:52:29,605 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 15:52:29,606 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 15:52:29,607 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 15:52:29,608 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 15:52:29,610 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 15:52:29,612 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 15:52:29,613 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 15:52:29,614 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 15:52:29,615 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 15:52:29,618 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 15:52:29,618 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 15:52:29,618 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 15:52:29,619 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 15:52:29,620 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 15:52:29,621 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 15:52:29,622 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 15:52:29,623 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 15:52:29,623 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 15:52:29,624 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 15:52:29,625 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 15:52:29,625 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 15:52:29,626 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 15:52:29,626 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 15:52:29,627 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 15:52:29,649 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 15:52:29,650 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 15:52:29,650 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 15:52:29,650 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 15:52:29,651 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 15:52:29,652 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 15:52:29,652 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 15:52:29,652 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 15:52:29,652 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 15:52:29,652 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 15:52:29,652 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 15:52:29,653 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 15:52:29,653 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 15:52:29,653 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 15:52:29,653 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 15:52:29,653 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 15:52:29,653 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 15:52:29,655 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 15:52:29,655 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 15:52:29,694 INFO ]: Repository-Root is: /tmp [2018-06-18 15:52:29,709 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 15:52:29,712 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 15:52:29,714 INFO ]: Initializing SmtParser... [2018-06-18 15:52:29,714 INFO ]: SmtParser initialized [2018-06-18 15:52:29,715 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_2.smt2 [2018-06-18 15:52:29,716 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 15:52:29,812 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_2.smt2 unknown [2018-06-18 15:52:30,259 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_2.smt2 [2018-06-18 15:52:30,263 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 15:52:30,277 INFO ]: Walking toolchain with 4 elements. [2018-06-18 15:52:30,278 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 15:52:30,278 INFO ]: Initializing ChcToBoogie... [2018-06-18 15:52:30,278 INFO ]: ChcToBoogie initialized [2018-06-18 15:52:30,284 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 03:52:30" (1/1) ... [2018-06-18 15:52:30,370 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30 Unit [2018-06-18 15:52:30,370 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 15:52:30,371 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 15:52:30,371 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 15:52:30,371 INFO ]: Boogie Preprocessor initialized [2018-06-18 15:52:30,392 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30" (1/1) ... [2018-06-18 15:52:30,392 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30" (1/1) ... [2018-06-18 15:52:30,403 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30" (1/1) ... [2018-06-18 15:52:30,403 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30" (1/1) ... [2018-06-18 15:52:30,410 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30" (1/1) ... [2018-06-18 15:52:30,411 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30" (1/1) ... [2018-06-18 15:52:30,414 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30" (1/1) ... [2018-06-18 15:52:30,420 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 15:52:30,421 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 15:52:30,421 INFO ]: Initializing RCFGBuilder... [2018-06-18 15:52:30,421 INFO ]: RCFGBuilder initialized [2018-06-18 15:52:30,422 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30" (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 15:52:30,441 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 15:52:30,441 INFO ]: Found specification of procedure False [2018-06-18 15:52:30,441 INFO ]: Found implementation of procedure False [2018-06-18 15:52:30,441 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-18 15:52:30,441 INFO ]: Found specification of procedure state [2018-06-18 15:52:30,442 INFO ]: Found implementation of procedure state [2018-06-18 15:52:30,442 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 15:52:30,442 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 15:52:30,442 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-18 15:52:30,799 INFO ]: Using library mode [2018-06-18 15:52:30,800 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 03:52:30 BoogieIcfgContainer [2018-06-18 15:52:30,800 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 15:52:30,801 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 15:52:30,801 INFO ]: Initializing TraceAbstraction... [2018-06-18 15:52:30,808 INFO ]: TraceAbstraction initialized [2018-06-18 15:52:30,808 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 03:52:30" (1/3) ... [2018-06-18 15:52:30,810 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19e79f81 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 03:52:30, skipping insertion in model container [2018-06-18 15:52:30,810 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 03:52:30" (2/3) ... [2018-06-18 15:52:30,810 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19e79f81 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 03:52:30, skipping insertion in model container [2018-06-18 15:52:30,810 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 03:52:30" (3/3) ... [2018-06-18 15:52:30,812 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 15:52:30,821 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 15:52:30,832 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 15:52:30,881 INFO ]: Using default assertion order modulation [2018-06-18 15:52:30,882 INFO ]: Interprodecural is true [2018-06-18 15:52:30,882 INFO ]: Hoare is false [2018-06-18 15:52:30,882 INFO ]: Compute interpolants for FPandBP [2018-06-18 15:52:30,882 INFO ]: Backedges is TWOTRACK [2018-06-18 15:52:30,882 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 15:52:30,882 INFO ]: Difference is false [2018-06-18 15:52:30,882 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 15:52:30,882 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 15:52:30,901 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 15:52:30,918 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 15:52:30,918 INFO ]: Found error trace [2018-06-18 15:52:30,919 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 15:52:30,919 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 15:52:30,925 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-18 15:52:30,927 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 15:52:30,927 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 15:52:30,980 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 15:52:30,980 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 15:52:30,980 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 15:52:31,073 INFO ]: Conjunction of SSA is unsat [2018-06-18 15:52:31,083 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 15:52:31,290 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-18 15:52:31,291 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 15:52:31,292 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 15:52:31,293 INFO ]: Interpolant automaton has 4 states [2018-06-18 15:52:31,303 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 15:52:31,304 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 15:52:31,305 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 15:52:31,449 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 15:52:31,449 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 15:52:31,449 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 15:52:31,451 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 15:52:31,451 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 15:52:31,472 INFO ]: With dead ends: 13 [2018-06-18 15:52:31,472 INFO ]: Without dead ends: 13 [2018-06-18 15:52:31,474 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 15:52:31,511 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 15:52:31,563 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 15:52:31,565 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 15:52:31,566 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 15:52:31,567 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 15:52:31,567 INFO ]: Finished accepts. word is rejected. [2018-06-18 15:52:31,567 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 15:52:31,567 INFO ]: Interpolant automaton has 4 states. [2018-06-18 15:52:31,567 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 15:52:31,568 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 15:52:31,569 INFO ]: Found error trace [2018-06-18 15:52:31,569 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 15:52:31,569 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 15:52:31,569 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-18 15:52:31,569 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 15:52:31,569 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 15:52:31,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 15:52:31,579 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 15:52:31,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 15:52:31,683 INFO ]: Conjunction of SSA is unsat [2018-06-18 15:52:31,683 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 15:52:32,681 WARN ]: Spent 762.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 37 [2018-06-18 15:52:32,750 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 15:52:32,750 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 15:52:32,750 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 15:52:32,759 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 15:52:32,877 INFO ]: Conjunction of SSA is unsat [2018-06-18 15:52:32,889 INFO ]: Computing forward predicates... [2018-06-18 15:52:34,359 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,369 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,376 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,385 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,402 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,410 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,550 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,559 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,583 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,584 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,589 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,593 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,609 WARN ]: expecting exponential blowup for input size 7 [2018-06-18 15:52:34,613 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,625 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,626 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,632 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,633 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,641 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,647 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,717 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,721 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,749 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,750 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,756 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,760 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,761 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,763 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:34,764 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:51,026 WARN ]: Spent 188.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 12 [2018-06-18 15:52:51,047 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 15:52:51,083 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 15:52:51,083 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-18 15:52:51,084 INFO ]: Interpolant automaton has 8 states [2018-06-18 15:52:51,084 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-18 15:52:51,084 INFO ]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2018-06-18 15:52:51,084 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 8 states. [2018-06-18 15:52:51,269 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 15:52:51,269 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-18 15:52:51,270 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-18 15:52:51,270 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-18 15:52:51,270 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 15:52:51,271 INFO ]: With dead ends: 15 [2018-06-18 15:52:51,271 INFO ]: Without dead ends: 15 [2018-06-18 15:52:51,272 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2018-06-18 15:52:51,272 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-18 15:52:51,274 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-18 15:52:51,274 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-18 15:52:51,275 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-18 15:52:51,275 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-18 15:52:51,275 INFO ]: Finished accepts. word is rejected. [2018-06-18 15:52:51,275 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-18 15:52:51,275 INFO ]: Interpolant automaton has 8 states. [2018-06-18 15:52:51,275 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-18 15:52:51,276 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-18 15:52:51,276 INFO ]: Found error trace [2018-06-18 15:52:51,276 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 15:52:51,276 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 15:52:51,276 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-18 15:52:51,276 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 15:52:51,276 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 15:52:51,277 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 15:52:51,277 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 15:52:51,277 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 15:52:51,397 INFO ]: Conjunction of SSA is unsat [2018-06-18 15:52:51,398 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 15:52:51,842 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 50 [2018-06-18 15:52:51,928 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-18 15:52:51,928 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 15:52:51,928 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 15:52:51,947 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-18 15:52:52,062 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 15:52:52,062 INFO ]: Conjunction of SSA is unsat [2018-06-18 15:52:52,072 INFO ]: Computing forward predicates... [2018-06-18 15:52:52,805 WARN ]: expecting exponential blowup for input size 9 [2018-06-18 15:52:52,820 WARN ]: expecting exponential blowup for input size 9 [2018-06-18 15:52:52,823 WARN ]: expecting exponential blowup for input size 9 [2018-06-18 15:52:52,841 WARN ]: expecting exponential blowup for input size 12 [2018-06-18 15:52:52,895 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:52,904 WARN ]: expecting exponential blowup for input size 8 [2018-06-18 15:52:52,910 WARN ]: expecting exponential blowup for input size 8 [2018-06-18 15:52:52,911 WARN ]: expecting exponential blowup for input size 11 [2018-06-18 15:52:52,962 WARN ]: expecting exponential blowup for input size 6 [2018-06-18 15:52:52,963 WARN ]: expecting exponential blowup for input size 20 [2018-06-18 15:53:19,220 WARN ]: Simplifying disjunction of 1049760 conjuctions. This might take some time... Received shutdown request... [2018-06-18 15:53:23,145 INFO ]: Timeout while computing interpolants [2018-06-18 15:53:23,346 WARN ]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 15:53:23,346 WARN ]: Verification canceled [2018-06-18 15:53:23,351 WARN ]: Timeout [2018-06-18 15:53:23,351 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 03:53:23 BoogieIcfgContainer [2018-06-18 15:53:23,351 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 15:53:23,352 INFO ]: Toolchain (without parser) took 53088.20 ms. Allocated memory was 308.3 MB in the beginning and 2.6 GB in the end (delta: 2.2 GB). Free memory was 250.9 MB in the beginning and 1.1 GB in the end (delta: -828.3 MB). Peak memory consumption was 2.7 GB. Max. memory is 3.6 GB. [2018-06-18 15:53:23,353 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.3 MB. Free memory is still 273.9 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 15:53:23,354 INFO ]: ChcToBoogie took 92.70 ms. Allocated memory is still 308.3 MB. Free memory was 250.9 MB in the beginning and 246.9 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-18 15:53:23,354 INFO ]: Boogie Preprocessor took 49.71 ms. Allocated memory is still 308.3 MB. Free memory was 246.9 MB in the beginning and 245.9 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-18 15:53:23,355 INFO ]: RCFGBuilder took 379.09 ms. Allocated memory is still 308.3 MB. Free memory was 244.9 MB in the beginning and 223.9 MB in the end (delta: 21.0 MB). Peak memory consumption was 21.0 MB. Max. memory is 3.6 GB. [2018-06-18 15:53:23,355 INFO ]: TraceAbstraction took 52549.71 ms. Allocated memory was 308.3 MB in the beginning and 2.6 GB in the end (delta: 2.2 GB). Free memory was 223.9 MB in the beginning and 1.1 GB in the end (delta: -855.2 MB). Peak memory consumption was 2.7 GB. Max. memory is 3.6 GB. [2018-06-18 15:53:23,359 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 308.3 MB. Free memory is still 273.9 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 92.70 ms. Allocated memory is still 308.3 MB. Free memory was 250.9 MB in the beginning and 246.9 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 49.71 ms. Allocated memory is still 308.3 MB. Free memory was 246.9 MB in the beginning and 245.9 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 379.09 ms. Allocated memory is still 308.3 MB. Free memory was 244.9 MB in the beginning and 223.9 MB in the end (delta: 21.0 MB). Peak memory consumption was 21.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 52549.71 ms. Allocated memory was 308.3 MB in the beginning and 2.6 GB in the end (delta: 2.2 GB). Free memory was 223.9 MB in the beginning and 1.1 GB in the end (delta: -855.2 MB). Peak memory consumption was 2.7 GB. 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 analyzing trace of length 18 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was XNF transformer was simplifying 1049760 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 52.4s OverallTime, 3 OverallIterations, 3 TraceHistogramMax, 0.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 21 SDtfs, 8 SDslu, 45 SDs, 0 SdLazy, 28 SolverSat, 9 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 24 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=15occurred in iteration=2, 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, 2 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 19.4s InterpolantComputationTime, 35 NumberOfCodeBlocks, 35 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 32 ConstructedInterpolants, 0 QuantifiedInterpolants, 1680 SizeOfPredicates, 28 NumberOfNonLiveVariables, 425 ConjunctsInSsa, 38 ConjunctsInUnsatCore, 3 InterpolantComputations, 1 PerfectInterpolantSequences, 2/6 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/MESI_2.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_15-53-23-370.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/MESI_2.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_15-53-23-370.csv Completed graceful shutdown