java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_1.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 18:45:49,268 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 18:45:49,270 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 18:45:49,282 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 18:45:49,282 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 18:45:49,283 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 18:45:49,286 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 18:45:49,288 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 18:45:49,289 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 18:45:49,290 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 18:45:49,292 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 18:45:49,292 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 18:45:49,293 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 18:45:49,294 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 18:45:49,294 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 18:45:49,297 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 18:45:49,299 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 18:45:49,308 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 18:45:49,309 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 18:45:49,310 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 18:45:49,311 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 18:45:49,316 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 18:45:49,317 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 18:45:49,317 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 18:45:49,318 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 18:45:49,319 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 18:45:49,319 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 18:45:49,320 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 18:45:49,322 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 18:45:49,322 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 18:45:49,323 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 18:45:49,323 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 18:45:49,323 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 18:45:49,324 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 18:45:49,324 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 18:45:49,329 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 18:45:49,349 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 18:45:49,349 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 18:45:49,350 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 18:45:49,350 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 18:45:49,351 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 18:45:49,351 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 18:45:49,351 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 18:45:49,351 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 18:45:49,352 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 18:45:49,352 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 18:45:49,352 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 18:45:49,352 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 18:45:49,352 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 18:45:49,353 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 18:45:49,354 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 18:45:49,354 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 18:45:49,354 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 18:45:49,354 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 18:45:49,354 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 18:45:49,356 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 18:45:49,356 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 18:45:49,404 INFO ]: Repository-Root is: /tmp [2018-06-22 18:45:49,419 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 18:45:49,424 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 18:45:49,425 INFO ]: Initializing SmtParser... [2018-06-22 18:45:49,425 INFO ]: SmtParser initialized [2018-06-22 18:45:49,426 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_1.smt2 [2018-06-22 18:45:49,428 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 18:45:49,519 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_1.smt2 unknown [2018-06-22 18:45:49,934 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_1.smt2 [2018-06-22 18:45:49,939 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 18:45:49,944 INFO ]: Walking toolchain with 4 elements. [2018-06-22 18:45:49,945 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 18:45:49,945 INFO ]: Initializing ChcToBoogie... [2018-06-22 18:45:49,945 INFO ]: ChcToBoogie initialized [2018-06-22 18:45:49,948 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 06:45:49" (1/1) ... [2018-06-22 18:45:50,023 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50 Unit [2018-06-22 18:45:50,023 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 18:45:50,024 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 18:45:50,024 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 18:45:50,024 INFO ]: Boogie Preprocessor initialized [2018-06-22 18:45:50,070 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50" (1/1) ... [2018-06-22 18:45:50,070 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50" (1/1) ... [2018-06-22 18:45:50,087 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50" (1/1) ... [2018-06-22 18:45:50,088 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50" (1/1) ... [2018-06-22 18:45:50,094 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50" (1/1) ... [2018-06-22 18:45:50,103 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50" (1/1) ... [2018-06-22 18:45:50,105 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50" (1/1) ... [2018-06-22 18:45:50,108 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 18:45:50,108 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 18:45:50,109 INFO ]: Initializing RCFGBuilder... [2018-06-22 18:45:50,109 INFO ]: RCFGBuilder initialized [2018-06-22 18:45:50,109 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 18:45:50,156 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 18:45:50,156 INFO ]: Found specification of procedure False [2018-06-22 18:45:50,156 INFO ]: Found implementation of procedure False [2018-06-22 18:45:50,156 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 18:45:50,156 INFO ]: Found specification of procedure state [2018-06-22 18:45:50,156 INFO ]: Found implementation of procedure state [2018-06-22 18:45:50,156 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 18:45:50,156 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 18:45:50,156 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 18:45:50,456 INFO ]: Using library mode [2018-06-22 18:45:50,457 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 06:45:50 BoogieIcfgContainer [2018-06-22 18:45:50,457 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 18:45:50,458 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 18:45:50,458 INFO ]: Initializing TraceAbstraction... [2018-06-22 18:45:50,464 INFO ]: TraceAbstraction initialized [2018-06-22 18:45:50,464 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 06:45:49" (1/3) ... [2018-06-22 18:45:50,465 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c3dcae7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 06:45:50, skipping insertion in model container [2018-06-22 18:45:50,465 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 06:45:50" (2/3) ... [2018-06-22 18:45:50,465 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c3dcae7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 06:45:50, skipping insertion in model container [2018-06-22 18:45:50,465 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 06:45:50" (3/3) ... [2018-06-22 18:45:50,467 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 18:45:50,475 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 18:45:50,482 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 18:45:50,526 INFO ]: Using default assertion order modulation [2018-06-22 18:45:50,526 INFO ]: Interprodecural is true [2018-06-22 18:45:50,526 INFO ]: Hoare is false [2018-06-22 18:45:50,526 INFO ]: Compute interpolants for FPandBP [2018-06-22 18:45:50,526 INFO ]: Backedges is TWOTRACK [2018-06-22 18:45:50,526 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 18:45:50,526 INFO ]: Difference is false [2018-06-22 18:45:50,527 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 18:45:50,527 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 18:45:50,540 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 18:45:50,551 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 18:45:50,552 INFO ]: Found error trace [2018-06-22 18:45:50,553 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:45:50,553 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:45:50,558 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 18:45:50,561 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:45:50,561 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:45:50,596 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:50,596 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:45:50,596 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:50,665 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:45:50,893 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 18:45:50,895 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 18:45:50,896 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 18:45:50,897 INFO ]: Interpolant automaton has 4 states [2018-06-22 18:45:50,908 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 18:45:50,908 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 18:45:50,910 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 18:45:51,043 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:45:51,043 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 18:45:51,044 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 18:45:51,045 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 18:45:51,046 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:45:51,058 INFO ]: With dead ends: 13 [2018-06-22 18:45:51,058 INFO ]: Without dead ends: 13 [2018-06-22 18:45:51,061 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-22 18:45:51,075 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 18:45:51,101 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 18:45:51,103 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 18:45:51,103 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 18:45:51,105 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 18:45:51,105 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:45:51,105 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 18:45:51,105 INFO ]: Interpolant automaton has 4 states. [2018-06-22 18:45:51,105 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 18:45:51,106 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 18:45:51,106 INFO ]: Found error trace [2018-06-22 18:45:51,106 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:45:51,107 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:45:51,107 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 18:45:51,107 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:45:51,107 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:45:51,108 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:51,108 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:45:51,108 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:45:51,197 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:45:52,246 WARN ]: Spent 759.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 43 [2018-06-22 18:45:52,471 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 11 [2018-06-22 18:45:52,554 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 18:45:52,554 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:45:52,554 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:45:52,569 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:45:52,682 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:45:52,695 INFO ]: Computing forward predicates... [2018-06-22 18:45:53,725 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:53,749 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:53,751 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:53,756 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:53,771 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:53,781 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:53,788 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:53,817 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:53,826 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:53,828 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:53,889 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:53,903 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:53,906 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:53,926 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:53,939 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:53,944 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:53,954 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:53,969 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:54,000 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:54,002 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:54,008 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 18:45:54,028 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:54,063 WARN ]: expecting exponential blowup for input size 12 [2018-06-22 18:45:54,530 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:54,541 WARN ]: expecting exponential blowup for input size 11 [2018-06-22 18:45:54,856 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 18:45:54,893 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:54,913 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:54,930 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:54,933 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:54,936 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:54,959 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:54,961 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:54,962 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:54,966 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:54,968 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:54,969 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:54,977 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:54,979 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:54,988 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:54,990 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:54,994 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:54,995 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:55,014 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:55,019 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:55,023 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:55,025 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:55,026 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:55,030 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:55,040 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 18:45:55,053 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:45:55,055 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 18:45:55,059 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:45:55,076 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 18:46:09,871 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 13 [2018-06-22 18:46:09,903 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 18:46:09,928 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 18:46:09,929 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 18:46:09,929 INFO ]: Interpolant automaton has 8 states [2018-06-22 18:46:09,929 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 18:46:09,929 INFO ]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2018-06-22 18:46:09,930 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 8 states. [2018-06-22 18:46:10,276 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 18:46:10,276 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 18:46:10,277 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 18:46:10,277 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-22 18:46:10,277 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 18:46:10,277 INFO ]: With dead ends: 15 [2018-06-22 18:46:10,277 INFO ]: Without dead ends: 15 [2018-06-22 18:46:10,278 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2018-06-22 18:46:10,278 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 18:46:10,280 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 18:46:10,280 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 18:46:10,280 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 18:46:10,280 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 18:46:10,280 INFO ]: Finished accepts. word is rejected. [2018-06-22 18:46:10,280 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 18:46:10,280 INFO ]: Interpolant automaton has 8 states. [2018-06-22 18:46:10,280 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 18:46:10,281 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 18:46:10,281 INFO ]: Found error trace [2018-06-22 18:46:10,281 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 18:46:10,281 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 18:46:10,281 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 18:46:10,281 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 18:46:10,281 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 18:46:10,282 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:46:10,282 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 18:46:10,282 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 18:46:10,382 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:46:10,910 WARN ]: Spent 158.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 41 [2018-06-22 18:46:11,020 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 18:46:11,021 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 18:46:11,021 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:46:11,038 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 18:46:11,154 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 18:46:11,154 INFO ]: Conjunction of SSA is unsat [2018-06-22 18:46:11,162 INFO ]: Computing forward predicates... [2018-06-22 18:46:11,351 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 18:46:11,351 WARN ]: expecting exponential blowup for input size 16 [2018-06-22 18:46:12,199 WARN ]: Simplifying disjunction of 103680 conjuctions. This might take some time... Received shutdown request... [2018-06-22 18:47:01,069 INFO ]: Timeout while computing interpolants [2018-06-22 18:47:01,270 WARN ]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 18:47:01,270 WARN ]: Verification canceled [2018-06-22 18:47:01,275 WARN ]: Timeout [2018-06-22 18:47:01,275 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 06:47:01 BoogieIcfgContainer [2018-06-22 18:47:01,275 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 18:47:01,276 INFO ]: Toolchain (without parser) took 71336.47 ms. Allocated memory was 302.0 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 244.6 MB in the beginning and 1.1 GB in the end (delta: -904.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 18:47:01,277 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 302.0 MB. Free memory is still 267.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 18:47:01,277 INFO ]: ChcToBoogie took 79.04 ms. Allocated memory is still 302.0 MB. Free memory was 244.6 MB in the beginning and 241.6 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-22 18:47:01,278 INFO ]: Boogie Preprocessor took 84.20 ms. Allocated memory is still 302.0 MB. Free memory was 241.6 MB in the beginning and 240.5 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. [2018-06-22 18:47:01,278 INFO ]: RCFGBuilder took 348.22 ms. Allocated memory is still 302.0 MB. Free memory was 240.5 MB in the beginning and 218.5 MB in the end (delta: 22.0 MB). Peak memory consumption was 22.0 MB. Max. memory is 3.6 GB. [2018-06-22 18:47:01,279 INFO ]: TraceAbstraction took 70817.01 ms. Allocated memory was 302.0 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 218.5 MB in the beginning and 1.1 GB in the end (delta: -930.3 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 18:47:01,281 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 302.0 MB. Free memory is still 267.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 79.04 ms. Allocated memory is still 302.0 MB. Free memory was 244.6 MB in the beginning and 241.6 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 84.20 ms. Allocated memory is still 302.0 MB. Free memory was 241.6 MB in the beginning and 240.5 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 348.22 ms. Allocated memory is still 302.0 MB. Free memory was 240.5 MB in the beginning and 218.5 MB in the end (delta: 22.0 MB). Peak memory consumption was 22.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 70817.01 ms. Allocated memory was 302.0 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 218.5 MB in the beginning and 1.1 GB in the end (delta: -930.3 MB). Peak memory consumption was 1.3 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 103680 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 70.7s OverallTime, 3 OverallIterations, 3 TraceHistogramMax, 0.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 22 SDtfs, 7 SDslu, 47 SDs, 0 SdLazy, 33 SolverSat, 8 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 25 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 1.7s 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.1s SatisfiabilityAnalysisTime, 18.8s InterpolantComputationTime, 35 NumberOfCodeBlocks, 35 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 32 ConstructedInterpolants, 0 QuantifiedInterpolants, 1800 SizeOfPredicates, 31 NumberOfNonLiveVariables, 425 ConjunctsInSsa, 45 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_1.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_18-47-01-300.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/MESI_1.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_18-47-01-300.csv Completed graceful shutdown