3.92/1.83 YES 3.92/1.84 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.92/1.84 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.92/1.84 3.92/1.84 3.92/1.84 Termination w.r.t. Q of the given QTRS could be proven: 3.92/1.84 3.92/1.84 (0) QTRS 3.92/1.84 (1) QTRSToCSRProof [SOUND, 0 ms] 3.92/1.84 (2) CSR 3.92/1.84 (3) CSRRRRProof [EQUIVALENT, 25 ms] 3.92/1.84 (4) CSR 3.92/1.84 (5) CSRRRRProof [EQUIVALENT, 9 ms] 3.92/1.84 (6) CSR 3.92/1.84 (7) CSRRRRProof [EQUIVALENT, 0 ms] 3.92/1.84 (8) CSR 3.92/1.84 (9) CSRRRRProof [EQUIVALENT, 0 ms] 3.92/1.84 (10) CSR 3.92/1.84 (11) CSRRRRProof [EQUIVALENT, 0 ms] 3.92/1.84 (12) CSR 3.92/1.84 (13) CSRRRRProof [EQUIVALENT, 0 ms] 3.92/1.84 (14) CSR 3.92/1.84 (15) RisEmptyProof [EQUIVALENT, 0 ms] 3.92/1.84 (16) YES 3.92/1.84 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (0) 3.92/1.84 Obligation: 3.92/1.84 Q restricted rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 3.92/1.84 active(__(X, nil)) -> mark(X) 3.92/1.84 active(__(nil, X)) -> mark(X) 3.92/1.84 active(and(tt, X)) -> mark(X) 3.92/1.84 active(isList(V)) -> mark(isNeList(V)) 3.92/1.84 active(isList(nil)) -> mark(tt) 3.92/1.84 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 3.92/1.84 active(isNeList(V)) -> mark(isQid(V)) 3.92/1.84 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 3.92/1.84 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 3.92/1.84 active(isNePal(V)) -> mark(isQid(V)) 3.92/1.84 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 3.92/1.84 active(isPal(V)) -> mark(isNePal(V)) 3.92/1.84 active(isPal(nil)) -> mark(tt) 3.92/1.84 active(isQid(a)) -> mark(tt) 3.92/1.84 active(isQid(e)) -> mark(tt) 3.92/1.84 active(isQid(i)) -> mark(tt) 3.92/1.84 active(isQid(o)) -> mark(tt) 3.92/1.84 active(isQid(u)) -> mark(tt) 3.92/1.84 active(__(X1, X2)) -> __(active(X1), X2) 3.92/1.84 active(__(X1, X2)) -> __(X1, active(X2)) 3.92/1.84 active(and(X1, X2)) -> and(active(X1), X2) 3.92/1.84 __(mark(X1), X2) -> mark(__(X1, X2)) 3.92/1.84 __(X1, mark(X2)) -> mark(__(X1, X2)) 3.92/1.84 and(mark(X1), X2) -> mark(and(X1, X2)) 3.92/1.84 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 3.92/1.84 proper(nil) -> ok(nil) 3.92/1.84 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 3.92/1.84 proper(tt) -> ok(tt) 3.92/1.84 proper(isList(X)) -> isList(proper(X)) 3.92/1.84 proper(isNeList(X)) -> isNeList(proper(X)) 3.92/1.84 proper(isQid(X)) -> isQid(proper(X)) 3.92/1.84 proper(isNePal(X)) -> isNePal(proper(X)) 3.92/1.84 proper(isPal(X)) -> isPal(proper(X)) 3.92/1.84 proper(a) -> ok(a) 3.92/1.84 proper(e) -> ok(e) 3.92/1.84 proper(i) -> ok(i) 3.92/1.84 proper(o) -> ok(o) 3.92/1.84 proper(u) -> ok(u) 3.92/1.84 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 3.92/1.84 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 3.92/1.84 isList(ok(X)) -> ok(isList(X)) 3.92/1.84 isNeList(ok(X)) -> ok(isNeList(X)) 3.92/1.84 isQid(ok(X)) -> ok(isQid(X)) 3.92/1.84 isNePal(ok(X)) -> ok(isNePal(X)) 3.92/1.84 isPal(ok(X)) -> ok(isPal(X)) 3.92/1.84 top(mark(X)) -> top(proper(X)) 3.92/1.84 top(ok(X)) -> top(active(X)) 3.92/1.84 3.92/1.84 The set Q consists of the following terms: 3.92/1.84 3.92/1.84 active(isList(x0)) 3.92/1.84 active(isNeList(x0)) 3.92/1.84 active(isNePal(x0)) 3.92/1.84 active(isPal(x0)) 3.92/1.84 active(isQid(a)) 3.92/1.84 active(isQid(e)) 3.92/1.84 active(isQid(i)) 3.92/1.84 active(isQid(o)) 3.92/1.84 active(isQid(u)) 3.92/1.84 active(__(x0, x1)) 3.92/1.84 active(and(x0, x1)) 3.92/1.84 __(mark(x0), x1) 3.92/1.84 __(x0, mark(x1)) 3.92/1.84 and(mark(x0), x1) 3.92/1.84 proper(__(x0, x1)) 3.92/1.84 proper(nil) 3.92/1.84 proper(and(x0, x1)) 3.92/1.84 proper(tt) 3.92/1.84 proper(isList(x0)) 3.92/1.84 proper(isNeList(x0)) 3.92/1.84 proper(isQid(x0)) 3.92/1.84 proper(isNePal(x0)) 3.92/1.84 proper(isPal(x0)) 3.92/1.84 proper(a) 3.92/1.84 proper(e) 3.92/1.84 proper(i) 3.92/1.84 proper(o) 3.92/1.84 proper(u) 3.92/1.84 __(ok(x0), ok(x1)) 3.92/1.84 and(ok(x0), ok(x1)) 3.92/1.84 isList(ok(x0)) 3.92/1.84 isNeList(ok(x0)) 3.92/1.84 isQid(ok(x0)) 3.92/1.84 isNePal(ok(x0)) 3.92/1.84 isPal(ok(x0)) 3.92/1.84 top(mark(x0)) 3.92/1.84 top(ok(x0)) 3.92/1.84 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (1) QTRSToCSRProof (SOUND) 3.92/1.84 The following Q TRS is given: Q restricted rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 3.92/1.84 active(__(X, nil)) -> mark(X) 3.92/1.84 active(__(nil, X)) -> mark(X) 3.92/1.84 active(and(tt, X)) -> mark(X) 3.92/1.84 active(isList(V)) -> mark(isNeList(V)) 3.92/1.84 active(isList(nil)) -> mark(tt) 3.92/1.84 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 3.92/1.84 active(isNeList(V)) -> mark(isQid(V)) 3.92/1.84 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 3.92/1.84 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 3.92/1.84 active(isNePal(V)) -> mark(isQid(V)) 3.92/1.84 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 3.92/1.84 active(isPal(V)) -> mark(isNePal(V)) 3.92/1.84 active(isPal(nil)) -> mark(tt) 3.92/1.84 active(isQid(a)) -> mark(tt) 3.92/1.84 active(isQid(e)) -> mark(tt) 3.92/1.84 active(isQid(i)) -> mark(tt) 3.92/1.84 active(isQid(o)) -> mark(tt) 3.92/1.84 active(isQid(u)) -> mark(tt) 3.92/1.84 active(__(X1, X2)) -> __(active(X1), X2) 3.92/1.84 active(__(X1, X2)) -> __(X1, active(X2)) 3.92/1.84 active(and(X1, X2)) -> and(active(X1), X2) 3.92/1.84 __(mark(X1), X2) -> mark(__(X1, X2)) 3.92/1.84 __(X1, mark(X2)) -> mark(__(X1, X2)) 3.92/1.84 and(mark(X1), X2) -> mark(and(X1, X2)) 3.92/1.84 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 3.92/1.84 proper(nil) -> ok(nil) 3.92/1.84 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 3.92/1.84 proper(tt) -> ok(tt) 3.92/1.84 proper(isList(X)) -> isList(proper(X)) 3.92/1.84 proper(isNeList(X)) -> isNeList(proper(X)) 3.92/1.84 proper(isQid(X)) -> isQid(proper(X)) 3.92/1.84 proper(isNePal(X)) -> isNePal(proper(X)) 3.92/1.84 proper(isPal(X)) -> isPal(proper(X)) 3.92/1.84 proper(a) -> ok(a) 3.92/1.84 proper(e) -> ok(e) 3.92/1.84 proper(i) -> ok(i) 3.92/1.84 proper(o) -> ok(o) 3.92/1.84 proper(u) -> ok(u) 3.92/1.84 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 3.92/1.84 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 3.92/1.84 isList(ok(X)) -> ok(isList(X)) 3.92/1.84 isNeList(ok(X)) -> ok(isNeList(X)) 3.92/1.84 isQid(ok(X)) -> ok(isQid(X)) 3.92/1.84 isNePal(ok(X)) -> ok(isNePal(X)) 3.92/1.84 isPal(ok(X)) -> ok(isPal(X)) 3.92/1.84 top(mark(X)) -> top(proper(X)) 3.92/1.84 top(ok(X)) -> top(active(X)) 3.92/1.84 3.92/1.84 The set Q consists of the following terms: 3.92/1.84 3.92/1.84 active(isList(x0)) 3.92/1.84 active(isNeList(x0)) 3.92/1.84 active(isNePal(x0)) 3.92/1.84 active(isPal(x0)) 3.92/1.84 active(isQid(a)) 3.92/1.84 active(isQid(e)) 3.92/1.84 active(isQid(i)) 3.92/1.84 active(isQid(o)) 3.92/1.84 active(isQid(u)) 3.92/1.84 active(__(x0, x1)) 3.92/1.84 active(and(x0, x1)) 3.92/1.84 __(mark(x0), x1) 3.92/1.84 __(x0, mark(x1)) 3.92/1.84 and(mark(x0), x1) 3.92/1.84 proper(__(x0, x1)) 3.92/1.84 proper(nil) 3.92/1.84 proper(and(x0, x1)) 3.92/1.84 proper(tt) 3.92/1.84 proper(isList(x0)) 3.92/1.84 proper(isNeList(x0)) 3.92/1.84 proper(isQid(x0)) 3.92/1.84 proper(isNePal(x0)) 3.92/1.84 proper(isPal(x0)) 3.92/1.84 proper(a) 3.92/1.84 proper(e) 3.92/1.84 proper(i) 3.92/1.84 proper(o) 3.92/1.84 proper(u) 3.92/1.84 __(ok(x0), ok(x1)) 3.92/1.84 and(ok(x0), ok(x1)) 3.92/1.84 isList(ok(x0)) 3.92/1.84 isNeList(ok(x0)) 3.92/1.84 isQid(ok(x0)) 3.92/1.84 isNePal(ok(x0)) 3.92/1.84 isPal(ok(x0)) 3.92/1.84 top(mark(x0)) 3.92/1.84 top(ok(x0)) 3.92/1.84 3.92/1.84 Special symbols used for the transformation (see [GM04]): 3.92/1.84 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 __: {1, 2} 3.92/1.84 nil: empty set 3.92/1.84 and: {1} 3.92/1.84 tt: empty set 3.92/1.84 isList: empty set 3.92/1.84 isNeList: empty set 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 a: empty set 3.92/1.84 e: empty set 3.92/1.84 i: empty set 3.92/1.84 o: empty set 3.92/1.84 u: empty set 3.92/1.84 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.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (2) 3.92/1.84 Obligation: 3.92/1.84 Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 __(__(X, Y), Z) -> __(X, __(Y, Z)) 3.92/1.84 __(X, nil) -> X 3.92/1.84 __(nil, X) -> X 3.92/1.84 and(tt, X) -> X 3.92/1.84 isList(V) -> isNeList(V) 3.92/1.84 isList(nil) -> tt 3.92/1.84 isList(__(V1, V2)) -> and(isList(V1), isList(V2)) 3.92/1.84 isNeList(V) -> isQid(V) 3.92/1.84 isNeList(__(V1, V2)) -> and(isList(V1), isNeList(V2)) 3.92/1.84 isNeList(__(V1, V2)) -> and(isNeList(V1), isList(V2)) 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isNePal(__(I, __(P, I))) -> and(isQid(I), isPal(P)) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 isPal(nil) -> tt 3.92/1.84 isQid(a) -> tt 3.92/1.84 isQid(e) -> tt 3.92/1.84 isQid(i) -> tt 3.92/1.84 isQid(o) -> tt 3.92/1.84 isQid(u) -> tt 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 __: {1, 2} 3.92/1.84 nil: empty set 3.92/1.84 and: {1} 3.92/1.84 tt: empty set 3.92/1.84 isList: empty set 3.92/1.84 isNeList: empty set 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 a: empty set 3.92/1.84 e: empty set 3.92/1.84 i: empty set 3.92/1.84 o: empty set 3.92/1.84 u: empty set 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (3) CSRRRRProof (EQUIVALENT) 3.92/1.84 The following CSR is given: Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 __(__(X, Y), Z) -> __(X, __(Y, Z)) 3.92/1.84 __(X, nil) -> X 3.92/1.84 __(nil, X) -> X 3.92/1.84 and(tt, X) -> X 3.92/1.84 isList(V) -> isNeList(V) 3.92/1.84 isList(nil) -> tt 3.92/1.84 isList(__(V1, V2)) -> and(isList(V1), isList(V2)) 3.92/1.84 isNeList(V) -> isQid(V) 3.92/1.84 isNeList(__(V1, V2)) -> and(isList(V1), isNeList(V2)) 3.92/1.84 isNeList(__(V1, V2)) -> and(isNeList(V1), isList(V2)) 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isNePal(__(I, __(P, I))) -> and(isQid(I), isPal(P)) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 isPal(nil) -> tt 3.92/1.84 isQid(a) -> tt 3.92/1.84 isQid(e) -> tt 3.92/1.84 isQid(i) -> tt 3.92/1.84 isQid(o) -> tt 3.92/1.84 isQid(u) -> tt 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 __: {1, 2} 3.92/1.84 nil: empty set 3.92/1.84 and: {1} 3.92/1.84 tt: empty set 3.92/1.84 isList: empty set 3.92/1.84 isNeList: empty set 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 a: empty set 3.92/1.84 e: empty set 3.92/1.84 i: empty set 3.92/1.84 o: empty set 3.92/1.84 u: empty set 3.92/1.84 Used ordering: 3.92/1.84 Polynomial interpretation [POLO]: 3.92/1.84 3.92/1.84 POL(__(x_1, x_2)) = 1 + x_1 + x_2 3.92/1.84 POL(a) = 0 3.92/1.84 POL(and(x_1, x_2)) = x_1 + x_2 3.92/1.84 POL(e) = 0 3.92/1.84 POL(i) = 1 3.92/1.84 POL(isList(x_1)) = 1 + x_1 3.92/1.84 POL(isNeList(x_1)) = 1 + x_1 3.92/1.84 POL(isNePal(x_1)) = 1 + x_1 3.92/1.84 POL(isPal(x_1)) = 1 + x_1 3.92/1.84 POL(isQid(x_1)) = 1 + x_1 3.92/1.84 POL(nil) = 0 3.92/1.84 POL(o) = 1 3.92/1.84 POL(tt) = 1 3.92/1.84 POL(u) = 0 3.92/1.84 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.92/1.84 3.92/1.84 __(X, nil) -> X 3.92/1.84 __(nil, X) -> X 3.92/1.84 and(tt, X) -> X 3.92/1.84 isNePal(__(I, __(P, I))) -> and(isQid(I), isPal(P)) 3.92/1.84 isQid(i) -> tt 3.92/1.84 isQid(o) -> tt 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (4) 3.92/1.84 Obligation: 3.92/1.84 Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 __(__(X, Y), Z) -> __(X, __(Y, Z)) 3.92/1.84 isList(V) -> isNeList(V) 3.92/1.84 isList(nil) -> tt 3.92/1.84 isList(__(V1, V2)) -> and(isList(V1), isList(V2)) 3.92/1.84 isNeList(V) -> isQid(V) 3.92/1.84 isNeList(__(V1, V2)) -> and(isList(V1), isNeList(V2)) 3.92/1.84 isNeList(__(V1, V2)) -> and(isNeList(V1), isList(V2)) 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 isPal(nil) -> tt 3.92/1.84 isQid(a) -> tt 3.92/1.84 isQid(e) -> tt 3.92/1.84 isQid(u) -> tt 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 __: {1, 2} 3.92/1.84 nil: empty set 3.92/1.84 and: {1} 3.92/1.84 tt: empty set 3.92/1.84 isList: empty set 3.92/1.84 isNeList: empty set 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 a: empty set 3.92/1.84 e: empty set 3.92/1.84 u: empty set 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (5) CSRRRRProof (EQUIVALENT) 3.92/1.84 The following CSR is given: Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 __(__(X, Y), Z) -> __(X, __(Y, Z)) 3.92/1.84 isList(V) -> isNeList(V) 3.92/1.84 isList(nil) -> tt 3.92/1.84 isList(__(V1, V2)) -> and(isList(V1), isList(V2)) 3.92/1.84 isNeList(V) -> isQid(V) 3.92/1.84 isNeList(__(V1, V2)) -> and(isList(V1), isNeList(V2)) 3.92/1.84 isNeList(__(V1, V2)) -> and(isNeList(V1), isList(V2)) 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 isPal(nil) -> tt 3.92/1.84 isQid(a) -> tt 3.92/1.84 isQid(e) -> tt 3.92/1.84 isQid(u) -> tt 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 __: {1, 2} 3.92/1.84 nil: empty set 3.92/1.84 and: {1} 3.92/1.84 tt: empty set 3.92/1.84 isList: empty set 3.92/1.84 isNeList: empty set 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 a: empty set 3.92/1.84 e: empty set 3.92/1.84 u: empty set 3.92/1.84 Used ordering: 3.92/1.84 Polynomial interpretation [POLO]: 3.92/1.84 3.92/1.84 POL(__(x_1, x_2)) = 1 + 2*x_1 + x_2 3.92/1.84 POL(a) = 0 3.92/1.84 POL(and(x_1, x_2)) = 1 + x_1 3.92/1.84 POL(e) = 0 3.92/1.84 POL(isList(x_1)) = 2 + 2*x_1 3.92/1.84 POL(isNeList(x_1)) = 2 + 2*x_1 3.92/1.84 POL(isNePal(x_1)) = 2 + 2*x_1 3.92/1.84 POL(isPal(x_1)) = 2 + 2*x_1 3.92/1.84 POL(isQid(x_1)) = 2 + 2*x_1 3.92/1.84 POL(nil) = 0 3.92/1.84 POL(tt) = 1 3.92/1.84 POL(u) = 2 3.92/1.84 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.92/1.84 3.92/1.84 __(__(X, Y), Z) -> __(X, __(Y, Z)) 3.92/1.84 isList(nil) -> tt 3.92/1.84 isList(__(V1, V2)) -> and(isList(V1), isList(V2)) 3.92/1.84 isNeList(__(V1, V2)) -> and(isList(V1), isNeList(V2)) 3.92/1.84 isNeList(__(V1, V2)) -> and(isNeList(V1), isList(V2)) 3.92/1.84 isPal(nil) -> tt 3.92/1.84 isQid(a) -> tt 3.92/1.84 isQid(e) -> tt 3.92/1.84 isQid(u) -> tt 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (6) 3.92/1.84 Obligation: 3.92/1.84 Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 isList(V) -> isNeList(V) 3.92/1.84 isNeList(V) -> isQid(V) 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 isList: empty set 3.92/1.84 isNeList: empty set 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (7) CSRRRRProof (EQUIVALENT) 3.92/1.84 The following CSR is given: Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 isList(V) -> isNeList(V) 3.92/1.84 isNeList(V) -> isQid(V) 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 isList: empty set 3.92/1.84 isNeList: empty set 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 Used ordering: 3.92/1.84 Polynomial interpretation [POLO]: 3.92/1.84 3.92/1.84 POL(isList(x_1)) = 1 + x_1 3.92/1.84 POL(isNeList(x_1)) = 1 + x_1 3.92/1.84 POL(isNePal(x_1)) = x_1 3.92/1.84 POL(isPal(x_1)) = x_1 3.92/1.84 POL(isQid(x_1)) = x_1 3.92/1.84 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.92/1.84 3.92/1.84 isNeList(V) -> isQid(V) 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (8) 3.92/1.84 Obligation: 3.92/1.84 Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 isList(V) -> isNeList(V) 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 isList: empty set 3.92/1.84 isNeList: empty set 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (9) CSRRRRProof (EQUIVALENT) 3.92/1.84 The following CSR is given: Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 isList(V) -> isNeList(V) 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 isList: empty set 3.92/1.84 isNeList: empty set 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 Used ordering: 3.92/1.84 Polynomial interpretation [POLO]: 3.92/1.84 3.92/1.84 POL(isList(x_1)) = 1 + x_1 3.92/1.84 POL(isNeList(x_1)) = x_1 3.92/1.84 POL(isNePal(x_1)) = 1 + x_1 3.92/1.84 POL(isPal(x_1)) = 1 + x_1 3.92/1.84 POL(isQid(x_1)) = 1 + x_1 3.92/1.84 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.92/1.84 3.92/1.84 isList(V) -> isNeList(V) 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (10) 3.92/1.84 Obligation: 3.92/1.84 Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (11) CSRRRRProof (EQUIVALENT) 3.92/1.84 The following CSR is given: Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 isQid: empty set 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 Used ordering: 3.92/1.84 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 3.92/1.84 3.92/1.84 <<< 3.92/1.84 POL(isNePal(x_1)) = [[1]] + [[1, 1]] * x_1 3.92/1.84 >>> 3.92/1.84 3.92/1.84 <<< 3.92/1.84 POL(isQid(x_1)) = [[0]] + [[1, 1]] * x_1 3.92/1.84 >>> 3.92/1.84 3.92/1.84 <<< 3.92/1.84 POL(isPal(x_1)) = [[1]] + [[1, 1]] * x_1 3.92/1.84 >>> 3.92/1.84 3.92/1.84 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.92/1.84 3.92/1.84 isNePal(V) -> isQid(V) 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (12) 3.92/1.84 Obligation: 3.92/1.84 Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (13) CSRRRRProof (EQUIVALENT) 3.92/1.84 The following CSR is given: Context-sensitive rewrite system: 3.92/1.84 The TRS R consists of the following rules: 3.92/1.84 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 3.92/1.84 The replacement map contains the following entries: 3.92/1.84 3.92/1.84 isNePal: empty set 3.92/1.84 isPal: empty set 3.92/1.84 Used ordering: 3.92/1.84 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 3.92/1.84 3.92/1.84 <<< 3.92/1.84 POL(isPal(x_1)) = [[1]] + [[1, 1]] * x_1 3.92/1.84 >>> 3.92/1.84 3.92/1.84 <<< 3.92/1.84 POL(isNePal(x_1)) = [[0]] + [[1, 1]] * x_1 3.92/1.84 >>> 3.92/1.84 3.92/1.84 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.92/1.84 3.92/1.84 isPal(V) -> isNePal(V) 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (14) 3.92/1.84 Obligation: 3.92/1.84 Context-sensitive rewrite system: 3.92/1.84 R is empty. 3.92/1.84 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (15) RisEmptyProof (EQUIVALENT) 3.92/1.84 The CSR R is empty. Hence, termination is trivially proven. 3.92/1.84 ---------------------------------------- 3.92/1.84 3.92/1.84 (16) 3.92/1.84 YES 4.04/1.87 EOF