java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_i3_e1_447_e7_2194.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 08:51:34,106 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 08:51:34,108 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 08:51:34,125 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 08:51:34,125 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 08:51:34,128 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 08:51:34,129 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 08:51:34,131 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 08:51:34,133 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 08:51:34,135 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 08:51:34,136 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 08:51:34,136 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 08:51:34,137 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 08:51:34,138 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 08:51:34,138 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 08:51:34,143 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 08:51:34,145 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 08:51:34,157 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 08:51:34,159 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 08:51:34,160 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 08:51:34,161 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 08:51:34,163 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 08:51:34,163 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 08:51:34,164 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 08:51:34,164 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 08:51:34,169 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 08:51:34,170 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 08:51:34,170 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 08:51:34,171 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 08:51:34,176 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 08:51:34,177 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 08:51:34,177 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 08:51:34,177 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 08:51:34,178 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 08:51:34,179 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 08:51:34,179 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 08:51:34,201 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 08:51:34,201 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 08:51:34,201 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 08:51:34,201 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 08:51:34,203 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 08:51:34,203 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 08:51:34,203 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 08:51:34,203 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 08:51:34,204 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 08:51:34,204 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 08:51:34,204 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 08:51:34,204 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 08:51:34,204 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 08:51:34,205 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 08:51:34,205 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 08:51:34,205 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 08:51:34,205 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 08:51:34,207 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 08:51:34,207 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 08:51:34,250 INFO ]: Repository-Root is: /tmp [2018-06-22 08:51:34,264 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 08:51:34,270 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 08:51:34,272 INFO ]: Initializing SmtParser... [2018-06-22 08:51:34,273 INFO ]: SmtParser initialized [2018-06-22 08:51:34,273 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_i3_e1_447_e7_2194.smt2 [2018-06-22 08:51:34,275 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 08:51:34,364 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_i3_e1_447_e7_2194.smt2 unknown [2018-06-22 08:51:34,714 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/MESI_i3_e1_447_e7_2194.smt2 [2018-06-22 08:51:34,719 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 08:51:34,735 INFO ]: Walking toolchain with 4 elements. [2018-06-22 08:51:34,736 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 08:51:34,736 INFO ]: Initializing ChcToBoogie... [2018-06-22 08:51:34,736 INFO ]: ChcToBoogie initialized [2018-06-22 08:51:34,739 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 08:51:34" (1/1) ... [2018-06-22 08:51:34,844 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34 Unit [2018-06-22 08:51:34,844 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 08:51:34,852 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 08:51:34,852 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 08:51:34,852 INFO ]: Boogie Preprocessor initialized [2018-06-22 08:51:34,893 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34" (1/1) ... [2018-06-22 08:51:34,893 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34" (1/1) ... [2018-06-22 08:51:34,909 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34" (1/1) ... [2018-06-22 08:51:34,909 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34" (1/1) ... [2018-06-22 08:51:34,926 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34" (1/1) ... [2018-06-22 08:51:34,928 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34" (1/1) ... [2018-06-22 08:51:34,930 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34" (1/1) ... [2018-06-22 08:51:34,935 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 08:51:34,936 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 08:51:34,936 INFO ]: Initializing RCFGBuilder... [2018-06-22 08:51:34,936 INFO ]: RCFGBuilder initialized [2018-06-22 08:51:34,937 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34" (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) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 08:51:34,991 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 08:51:34,991 INFO ]: Found specification of procedure gotoProc [2018-06-22 08:51:34,991 INFO ]: Found implementation of procedure gotoProc [2018-06-22 08:51:34,991 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 08:51:34,991 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 08:51:34,991 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 08:51:35,410 INFO ]: Using library mode [2018-06-22 08:51:35,410 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 08:51:35 BoogieIcfgContainer [2018-06-22 08:51:35,410 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 08:51:35,411 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 08:51:35,411 INFO ]: Initializing TraceAbstraction... [2018-06-22 08:51:35,417 INFO ]: TraceAbstraction initialized [2018-06-22 08:51:35,418 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 08:51:34" (1/3) ... [2018-06-22 08:51:35,419 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11b35977 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 08:51:35, skipping insertion in model container [2018-06-22 08:51:35,419 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 08:51:34" (2/3) ... [2018-06-22 08:51:35,419 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11b35977 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 08:51:35, skipping insertion in model container [2018-06-22 08:51:35,419 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 08:51:35" (3/3) ... [2018-06-22 08:51:35,421 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 08:51:35,431 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 08:51:35,440 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 08:51:35,486 INFO ]: Using default assertion order modulation [2018-06-22 08:51:35,486 INFO ]: Interprodecural is true [2018-06-22 08:51:35,486 INFO ]: Hoare is false [2018-06-22 08:51:35,487 INFO ]: Compute interpolants for FPandBP [2018-06-22 08:51:35,487 INFO ]: Backedges is TWOTRACK [2018-06-22 08:51:35,487 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 08:51:35,487 INFO ]: Difference is false [2018-06-22 08:51:35,487 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 08:51:35,487 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 08:51:35,500 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 08:51:35,507 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 08:51:35,507 INFO ]: Found error trace [2018-06-22 08:51:35,508 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 08:51:35,508 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 08:51:35,514 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-22 08:51:35,516 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 08:51:35,517 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 08:51:35,553 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:51:35,553 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 08:51:35,553 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:51:35,665 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:51:35,806 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:51:35,808 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 08:51:35,808 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 08:51:35,810 INFO ]: Interpolant automaton has 3 states [2018-06-22 08:51:35,821 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 08:51:35,822 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 08:51:35,823 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 08:51:35,902 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 08:51:35,902 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 08:51:35,903 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 08:51:35,904 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 08:51:35,904 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 08:51:35,914 INFO ]: With dead ends: 9 [2018-06-22 08:51:35,914 INFO ]: Without dead ends: 9 [2018-06-22 08:51:35,917 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 08:51:35,932 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 08:51:35,958 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 08:51:35,959 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 08:51:35,960 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 08:51:35,961 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 08:51:35,962 INFO ]: Finished accepts. word is rejected. [2018-06-22 08:51:35,962 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 08:51:35,962 INFO ]: Interpolant automaton has 3 states. [2018-06-22 08:51:35,962 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 08:51:35,962 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 08:51:35,962 INFO ]: Found error trace [2018-06-22 08:51:35,962 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 08:51:35,962 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 08:51:35,962 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-22 08:51:35,963 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 08:51:35,963 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 08:51:35,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:51:35,963 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 08:51:35,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:51:36,098 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:51:36,421 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:51:36,421 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 08:51:36,421 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 08:51:36,430 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 08:51:36,578 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:51:36,590 INFO ]: Computing forward predicates... [2018-06-22 08:51:37,275 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:37,281 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:37,290 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:37,293 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 08:51:37,331 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:37,383 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:37,439 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:37,489 WARN ]: expecting exponential blowup for input size 11 [2018-06-22 08:51:37,592 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:37,594 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 08:51:37,596 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:37,610 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:37,650 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:37,658 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:37,660 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:37,663 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:48,358 WARN ]: Spent 457.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 14 [2018-06-22 08:51:48,369 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:51:48,402 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 08:51:48,402 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 08:51:48,402 INFO ]: Interpolant automaton has 5 states [2018-06-22 08:51:48,402 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 08:51:48,403 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 08:51:48,403 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 08:51:48,440 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 08:51:48,440 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 08:51:48,441 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 08:51:48,441 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 08:51:48,441 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 08:51:48,441 INFO ]: With dead ends: 10 [2018-06-22 08:51:48,441 INFO ]: Without dead ends: 10 [2018-06-22 08:51:48,442 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 08:51:48,442 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 08:51:48,443 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 08:51:48,443 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 08:51:48,443 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 08:51:48,444 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 08:51:48,444 INFO ]: Finished accepts. word is rejected. [2018-06-22 08:51:48,444 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 08:51:48,444 INFO ]: Interpolant automaton has 5 states. [2018-06-22 08:51:48,444 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 08:51:48,444 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 08:51:48,444 INFO ]: Found error trace [2018-06-22 08:51:48,444 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 08:51:48,444 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 08:51:48,444 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-22 08:51:48,444 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 08:51:48,444 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 08:51:48,445 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:51:48,445 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 08:51:48,445 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 08:51:48,567 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:51:48,932 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 95 DAG size of output: 56 [2018-06-22 08:51:48,952 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 08:51:48,952 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 08:51:48,952 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 08:51:48,959 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 08:51:49,074 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 08:51:49,074 INFO ]: Conjunction of SSA is unsat [2018-06-22 08:51:49,082 INFO ]: Computing forward predicates... [2018-06-22 08:51:49,437 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,456 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,471 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,472 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,477 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 08:51:49,535 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,538 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,541 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,558 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 08:51:49,613 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,613 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,615 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,616 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 08:51:49,625 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,662 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,663 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,664 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,692 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,693 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,693 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 08:51:49,695 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,707 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 08:51:49,710 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,713 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 08:51:49,752 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,764 WARN ]: expecting exponential blowup for input size 9 [2018-06-22 08:51:49,795 WARN ]: expecting exponential blowup for input size 10 [2018-06-22 08:51:49,819 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 08:51:49,820 WARN ]: expecting exponential blowup for input size 8 [2018-06-22 08:51:49,942 WARN ]: Simplifying disjunction of 36624 conjuctions. This might take some time... Received shutdown request... [2018-06-22 08:52:48,033 INFO ]: Timeout while computing interpolants [2018-06-22 08:52:48,234 WARN ]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 08:52:48,234 WARN ]: Verification canceled [2018-06-22 08:52:48,238 WARN ]: Timeout [2018-06-22 08:52:48,238 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 08:52:48 BoogieIcfgContainer [2018-06-22 08:52:48,238 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 08:52:48,239 INFO ]: Toolchain (without parser) took 73519.26 ms. Allocated memory was 308.8 MB in the beginning and 1.3 GB in the end (delta: 1.0 GB). Free memory was 251.2 MB in the beginning and 842.9 MB in the end (delta: -591.7 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 08:52:48,240 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 308.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 08:52:48,240 INFO ]: ChcToBoogie took 108.91 ms. Allocated memory is still 308.8 MB. Free memory was 251.2 MB in the beginning and 248.2 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-22 08:52:48,240 INFO ]: Boogie Preprocessor took 82.94 ms. Allocated memory is still 308.8 MB. Free memory was 248.2 MB in the beginning and 246.2 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 3.6 GB. [2018-06-22 08:52:48,241 INFO ]: RCFGBuilder took 474.74 ms. Allocated memory is still 308.8 MB. Free memory was 246.2 MB in the beginning and 219.1 MB in the end (delta: 27.0 MB). Peak memory consumption was 27.0 MB. Max. memory is 3.6 GB. [2018-06-22 08:52:48,241 INFO ]: TraceAbstraction took 72826.71 ms. Allocated memory was 308.8 MB in the beginning and 1.3 GB in the end (delta: 1.0 GB). Free memory was 219.1 MB in the beginning and 842.9 MB in the end (delta: -623.8 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 08:52:48,244 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 308.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 108.91 ms. Allocated memory is still 308.8 MB. Free memory was 251.2 MB in the beginning and 248.2 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 82.94 ms. Allocated memory is still 308.8 MB. Free memory was 248.2 MB in the beginning and 246.2 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 474.74 ms. Allocated memory is still 308.8 MB. Free memory was 246.2 MB in the beginning and 219.1 MB in the end (delta: 27.0 MB). Peak memory consumption was 27.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 72826.71 ms. Allocated memory was 308.8 MB in the beginning and 1.3 GB in the end (delta: 1.0 GB). Free memory was 219.1 MB in the beginning and 842.9 MB in the end (delta: -623.8 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 10 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was XNF transformer was simplifying 36624 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 72.7s OverallTime, 3 OverallIterations, 2 TraceHistogramMax, 0.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 14 SDtfs, 0 SDslu, 20 SDs, 0 SdLazy, 14 SolverSat, 0 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 14 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=10occurred in iteration=0, 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.3s SatisfiabilityAnalysisTime, 12.2s InterpolantComputationTime, 23 NumberOfCodeBlocks, 23 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 20 ConstructedInterpolants, 0 QuantifiedInterpolants, 413 SizeOfPredicates, 4 NumberOfNonLiveVariables, 521 ConjunctsInSsa, 45 ConjunctsInUnsatCore, 3 InterpolantComputations, 1 PerfectInterpolantSequences, 0/2 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_i3_e1_447_e7_2194.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_08-52-48-255.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/MESI_i3_e1_447_e7_2194.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_08-52-48-255.csv Completed graceful shutdown