3.57/1.78 YES 3.57/1.79 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.57/1.79 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.57/1.79 3.57/1.79 3.57/1.79 Termination w.r.t. Q of the given QTRS could be proven: 3.57/1.79 3.57/1.79 (0) QTRS 3.57/1.79 (1) QTRSToCSRProof [SOUND, 0 ms] 3.57/1.79 (2) CSR 3.57/1.79 (3) CSDependencyPairsProof [EQUIVALENT, 0 ms] 3.57/1.79 (4) QCSDP 3.57/1.79 (5) QCSDPForwardInstantiationProcessor [EQUIVALENT, 0 ms] 3.57/1.79 (6) QCSDP 3.57/1.79 (7) PIsEmptyProof [EQUIVALENT, 0 ms] 3.57/1.79 (8) YES 3.57/1.79 3.57/1.79 3.57/1.79 ---------------------------------------- 3.57/1.79 3.57/1.79 (0) 3.57/1.79 Obligation: 3.57/1.79 Q restricted rewrite system: 3.57/1.79 The TRS R consists of the following rules: 3.57/1.79 3.57/1.79 active(f(a, b, X)) -> mark(f(X, X, X)) 3.57/1.79 active(c) -> mark(a) 3.57/1.79 active(c) -> mark(b) 3.57/1.79 active(f(X1, X2, X3)) -> f(active(X1), X2, X3) 3.57/1.79 active(f(X1, X2, X3)) -> f(X1, X2, active(X3)) 3.57/1.79 f(mark(X1), X2, X3) -> mark(f(X1, X2, X3)) 3.57/1.79 f(X1, X2, mark(X3)) -> mark(f(X1, X2, X3)) 3.57/1.79 proper(f(X1, X2, X3)) -> f(proper(X1), proper(X2), proper(X3)) 3.57/1.79 proper(a) -> ok(a) 3.57/1.79 proper(b) -> ok(b) 3.57/1.79 proper(c) -> ok(c) 3.57/1.79 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 3.57/1.79 top(mark(X)) -> top(proper(X)) 3.57/1.79 top(ok(X)) -> top(active(X)) 3.57/1.79 3.57/1.79 The set Q consists of the following terms: 3.57/1.79 3.57/1.79 active(c) 3.57/1.79 active(f(x0, x1, x2)) 3.57/1.79 f(mark(x0), x1, x2) 3.57/1.79 f(x0, x1, mark(x2)) 3.57/1.79 proper(f(x0, x1, x2)) 3.57/1.79 proper(a) 3.57/1.79 proper(b) 3.57/1.79 proper(c) 3.57/1.79 f(ok(x0), ok(x1), ok(x2)) 3.57/1.79 top(mark(x0)) 3.57/1.79 top(ok(x0)) 3.57/1.79 3.57/1.79 3.57/1.79 ---------------------------------------- 3.57/1.79 3.57/1.79 (1) QTRSToCSRProof (SOUND) 3.57/1.79 The following Q TRS is given: Q restricted rewrite system: 3.57/1.79 The TRS R consists of the following rules: 3.57/1.79 3.57/1.79 active(f(a, b, X)) -> mark(f(X, X, X)) 3.57/1.79 active(c) -> mark(a) 3.57/1.79 active(c) -> mark(b) 3.57/1.79 active(f(X1, X2, X3)) -> f(active(X1), X2, X3) 3.57/1.79 active(f(X1, X2, X3)) -> f(X1, X2, active(X3)) 3.57/1.79 f(mark(X1), X2, X3) -> mark(f(X1, X2, X3)) 3.57/1.79 f(X1, X2, mark(X3)) -> mark(f(X1, X2, X3)) 3.57/1.79 proper(f(X1, X2, X3)) -> f(proper(X1), proper(X2), proper(X3)) 3.57/1.79 proper(a) -> ok(a) 3.57/1.79 proper(b) -> ok(b) 3.57/1.79 proper(c) -> ok(c) 3.57/1.79 f(ok(X1), ok(X2), ok(X3)) -> ok(f(X1, X2, X3)) 3.57/1.79 top(mark(X)) -> top(proper(X)) 3.57/1.79 top(ok(X)) -> top(active(X)) 3.57/1.79 3.57/1.79 The set Q consists of the following terms: 3.57/1.79 3.57/1.79 active(c) 3.57/1.79 active(f(x0, x1, x2)) 3.57/1.79 f(mark(x0), x1, x2) 3.57/1.79 f(x0, x1, mark(x2)) 3.57/1.79 proper(f(x0, x1, x2)) 3.57/1.79 proper(a) 3.57/1.79 proper(b) 3.57/1.79 proper(c) 3.57/1.79 f(ok(x0), ok(x1), ok(x2)) 3.57/1.79 top(mark(x0)) 3.57/1.79 top(ok(x0)) 3.57/1.79 3.57/1.79 Special symbols used for the transformation (see [GM04]): 3.57/1.79 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 3.57/1.79 The replacement map contains the following entries: 3.57/1.79 3.57/1.79 f: {1, 3} 3.57/1.79 a: empty set 3.57/1.79 b: empty set 3.57/1.79 c: empty set 3.57/1.79 The QTRS contained just a subset of rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is sound, but not necessarily complete. 3.57/1.79 ---------------------------------------- 3.57/1.79 3.57/1.79 (2) 3.57/1.79 Obligation: 3.57/1.79 Context-sensitive rewrite system: 3.57/1.79 The TRS R consists of the following rules: 3.57/1.79 3.57/1.79 f(a, b, X) -> f(X, X, X) 3.57/1.79 c -> a 3.57/1.79 c -> b 3.57/1.79 3.57/1.79 The replacement map contains the following entries: 3.57/1.79 3.57/1.79 f: {1, 3} 3.57/1.79 a: empty set 3.57/1.79 b: empty set 3.57/1.79 c: empty set 3.57/1.79 3.57/1.79 ---------------------------------------- 3.57/1.79 3.57/1.79 (3) CSDependencyPairsProof (EQUIVALENT) 3.57/1.79 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 3.57/1.79 ---------------------------------------- 3.57/1.79 3.57/1.79 (4) 3.57/1.79 Obligation: 3.57/1.79 Q-restricted context-sensitive dependency pair problem: 3.57/1.79 For all symbols f in {f_3, F_3} we have mu(f) = {1, 3}. 3.57/1.79 3.57/1.79 The ordinary context-sensitive dependency pairs DP_o are: 3.57/1.79 F(a, b, X) -> F(X, X, X) 3.57/1.79 3.57/1.79 The TRS R consists of the following rules: 3.57/1.79 3.57/1.79 f(a, b, X) -> f(X, X, X) 3.57/1.79 c -> a 3.57/1.79 c -> b 3.57/1.79 3.57/1.79 Q is empty. 3.57/1.79 3.57/1.79 ---------------------------------------- 3.57/1.79 3.57/1.79 (5) QCSDPForwardInstantiationProcessor (EQUIVALENT) 3.57/1.79 Using the Context-Sensitive Forward Instantiation[DA_EMMES] Processor 3.57/1.79 3.57/1.79 the pair F(a, b, X) -> F(X, X, X) 3.57/1.79 3.57/1.79 was transformed to the following new pairs: 3.57/1.79 F(a, b, b) -> F(b, b, b) 3.57/1.79 3.57/1.79 3.57/1.79 3.57/1.79 ---------------------------------------- 3.57/1.79 3.57/1.79 (6) 3.57/1.79 Obligation: 3.57/1.79 Q-restricted context-sensitive dependency pair problem: 3.57/1.79 For all symbols f in {f_3} we have mu(f) = {1, 3}. 3.57/1.79 3.57/1.79 The TRS P consists of the following rules: 3.57/1.79 none 3.57/1.79 3.57/1.79 The TRS R consists of the following rules: 3.57/1.79 3.57/1.79 f(a, b, X) -> f(X, X, X) 3.57/1.79 c -> a 3.57/1.79 c -> b 3.57/1.79 3.57/1.79 Q is empty. 3.57/1.79 3.57/1.79 ---------------------------------------- 3.57/1.79 3.57/1.79 (7) PIsEmptyProof (EQUIVALENT) 3.57/1.79 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 3.57/1.79 ---------------------------------------- 3.57/1.79 3.57/1.79 (8) 3.57/1.79 YES 3.62/1.82 EOF