21.84/11.02 YES 21.84/11.03 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 21.84/11.03 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 21.84/11.03 21.84/11.03 21.84/11.03 Termination w.r.t. Q of the given QTRS could be proven: 21.84/11.03 21.84/11.03 (0) QTRS 21.84/11.03 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 21.84/11.03 (2) QDP 21.84/11.03 (3) QDPOrderProof [EQUIVALENT, 88 ms] 21.84/11.03 (4) QDP 21.84/11.03 (5) QDPOrderProof [EQUIVALENT, 46 ms] 21.84/11.03 (6) QDP 21.84/11.03 (7) QDPOrderProof [EQUIVALENT, 41 ms] 21.84/11.03 (8) QDP 21.84/11.03 (9) QDPOrderProof [EQUIVALENT, 20 ms] 21.84/11.03 (10) QDP 21.84/11.03 (11) QDPOrderProof [EQUIVALENT, 70 ms] 21.84/11.03 (12) QDP 21.84/11.03 (13) DependencyGraphProof [EQUIVALENT, 0 ms] 21.84/11.03 (14) AND 21.84/11.03 (15) QDP 21.84/11.03 (16) QDPOrderProof [EQUIVALENT, 1381 ms] 21.84/11.03 (17) QDP 21.84/11.03 (18) PisEmptyProof [EQUIVALENT, 0 ms] 21.84/11.03 (19) YES 21.84/11.03 (20) QDP 21.84/11.03 (21) QDPOrderProof [EQUIVALENT, 25 ms] 21.84/11.03 (22) QDP 21.84/11.03 (23) QDPOrderProof [EQUIVALENT, 25 ms] 21.84/11.03 (24) QDP 21.84/11.03 (25) DependencyGraphProof [EQUIVALENT, 0 ms] 21.84/11.03 (26) QDP 21.84/11.03 (27) UsableRulesProof [EQUIVALENT, 0 ms] 21.84/11.03 (28) QDP 21.84/11.03 (29) QReductionProof [EQUIVALENT, 0 ms] 21.84/11.03 (30) QDP 21.84/11.03 (31) QDPSizeChangeProof [EQUIVALENT, 0 ms] 21.84/11.03 (32) YES 21.84/11.03 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (0) 21.84/11.03 Obligation: 21.84/11.03 Q restricted rewrite system: 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (1) DependencyPairsProof (EQUIVALENT) 21.84/11.03 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (2) 21.84/11.03 Obligation: 21.84/11.03 Q DP problem: 21.84/11.03 The TRS P consists of the following rules: 21.84/11.03 21.84/11.03 A__FROM(X) -> MARK(X) 21.84/11.03 A__AFTER(0, XS) -> MARK(XS) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> A__AFTER(mark(N), mark(XS)) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> MARK(N) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> MARK(XS) 21.84/11.03 MARK(from(X)) -> A__FROM(mark(X)) 21.84/11.03 MARK(from(X)) -> MARK(X) 21.84/11.03 MARK(after(X1, X2)) -> A__AFTER(mark(X1), mark(X2)) 21.84/11.03 MARK(after(X1, X2)) -> MARK(X1) 21.84/11.03 MARK(after(X1, X2)) -> MARK(X2) 21.84/11.03 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.03 MARK(s(X)) -> MARK(X) 21.84/11.03 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 We have to consider all minimal (P,Q,R)-chains. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (3) QDPOrderProof (EQUIVALENT) 21.84/11.03 We use the reduction pair processor [LPAR04,JAR06]. 21.84/11.03 21.84/11.03 21.84/11.03 The following pairs can be oriented strictly and are deleted. 21.84/11.03 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> MARK(N) 21.84/11.03 The remaining pairs can at least be oriented weakly. 21.84/11.03 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__AFTER(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(0) = [[0A]] 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(cons(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(from(x_1)) = [[1A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(after(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__from(x_1)) = [[1A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__after(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 21.84/11.03 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 21.84/11.03 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (4) 21.84/11.03 Obligation: 21.84/11.03 Q DP problem: 21.84/11.03 The TRS P consists of the following rules: 21.84/11.03 21.84/11.03 A__FROM(X) -> MARK(X) 21.84/11.03 A__AFTER(0, XS) -> MARK(XS) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> A__AFTER(mark(N), mark(XS)) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> MARK(XS) 21.84/11.03 MARK(from(X)) -> A__FROM(mark(X)) 21.84/11.03 MARK(from(X)) -> MARK(X) 21.84/11.03 MARK(after(X1, X2)) -> A__AFTER(mark(X1), mark(X2)) 21.84/11.03 MARK(after(X1, X2)) -> MARK(X1) 21.84/11.03 MARK(after(X1, X2)) -> MARK(X2) 21.84/11.03 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.03 MARK(s(X)) -> MARK(X) 21.84/11.03 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 We have to consider all minimal (P,Q,R)-chains. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (5) QDPOrderProof (EQUIVALENT) 21.84/11.03 We use the reduction pair processor [LPAR04,JAR06]. 21.84/11.03 21.84/11.03 21.84/11.03 The following pairs can be oriented strictly and are deleted. 21.84/11.03 21.84/11.03 MARK(after(X1, X2)) -> MARK(X1) 21.84/11.03 The remaining pairs can at least be oriented weakly. 21.84/11.03 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__FROM(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__AFTER(x_1, x_2)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(0) = [[0A]] 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(from(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(after(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__from(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__after(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 21.84/11.03 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 21.84/11.03 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (6) 21.84/11.03 Obligation: 21.84/11.03 Q DP problem: 21.84/11.03 The TRS P consists of the following rules: 21.84/11.03 21.84/11.03 A__FROM(X) -> MARK(X) 21.84/11.03 A__AFTER(0, XS) -> MARK(XS) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> A__AFTER(mark(N), mark(XS)) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> MARK(XS) 21.84/11.03 MARK(from(X)) -> A__FROM(mark(X)) 21.84/11.03 MARK(from(X)) -> MARK(X) 21.84/11.03 MARK(after(X1, X2)) -> A__AFTER(mark(X1), mark(X2)) 21.84/11.03 MARK(after(X1, X2)) -> MARK(X2) 21.84/11.03 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.03 MARK(s(X)) -> MARK(X) 21.84/11.03 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 We have to consider all minimal (P,Q,R)-chains. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (7) QDPOrderProof (EQUIVALENT) 21.84/11.03 We use the reduction pair processor [LPAR04,JAR06]. 21.84/11.03 21.84/11.03 21.84/11.03 The following pairs can be oriented strictly and are deleted. 21.84/11.03 21.84/11.03 MARK(after(X1, X2)) -> MARK(X2) 21.84/11.03 The remaining pairs can at least be oriented weakly. 21.84/11.03 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__AFTER(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(0) = [[3A]] 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(from(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(after(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__after(x_1, x_2)) = [[2A]] + [[0A]] * x_1 + [[1A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 21.84/11.03 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 21.84/11.03 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (8) 21.84/11.03 Obligation: 21.84/11.03 Q DP problem: 21.84/11.03 The TRS P consists of the following rules: 21.84/11.03 21.84/11.03 A__FROM(X) -> MARK(X) 21.84/11.03 A__AFTER(0, XS) -> MARK(XS) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> A__AFTER(mark(N), mark(XS)) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> MARK(XS) 21.84/11.03 MARK(from(X)) -> A__FROM(mark(X)) 21.84/11.03 MARK(from(X)) -> MARK(X) 21.84/11.03 MARK(after(X1, X2)) -> A__AFTER(mark(X1), mark(X2)) 21.84/11.03 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.03 MARK(s(X)) -> MARK(X) 21.84/11.03 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 We have to consider all minimal (P,Q,R)-chains. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (9) QDPOrderProof (EQUIVALENT) 21.84/11.03 We use the reduction pair processor [LPAR04,JAR06]. 21.84/11.03 21.84/11.03 21.84/11.03 The following pairs can be oriented strictly and are deleted. 21.84/11.03 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> MARK(XS) 21.84/11.03 The remaining pairs can at least be oriented weakly. 21.84/11.03 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__FROM(x_1)) = [[1A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(MARK(x_1)) = [[1A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__AFTER(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[1A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(0) = [[0A]] 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(s(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(cons(x_1, x_2)) = [[1A]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(from(x_1)) = [[1A]] + [[1A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(after(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[1A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__from(x_1)) = [[1A]] + [[1A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__after(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[1A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 21.84/11.03 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 21.84/11.03 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (10) 21.84/11.03 Obligation: 21.84/11.03 Q DP problem: 21.84/11.03 The TRS P consists of the following rules: 21.84/11.03 21.84/11.03 A__FROM(X) -> MARK(X) 21.84/11.03 A__AFTER(0, XS) -> MARK(XS) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> A__AFTER(mark(N), mark(XS)) 21.84/11.03 MARK(from(X)) -> A__FROM(mark(X)) 21.84/11.03 MARK(from(X)) -> MARK(X) 21.84/11.03 MARK(after(X1, X2)) -> A__AFTER(mark(X1), mark(X2)) 21.84/11.03 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.03 MARK(s(X)) -> MARK(X) 21.84/11.03 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 We have to consider all minimal (P,Q,R)-chains. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (11) QDPOrderProof (EQUIVALENT) 21.84/11.03 We use the reduction pair processor [LPAR04,JAR06]. 21.84/11.03 21.84/11.03 21.84/11.03 The following pairs can be oriented strictly and are deleted. 21.84/11.03 21.84/11.03 A__AFTER(0, XS) -> MARK(XS) 21.84/11.03 The remaining pairs can at least be oriented weakly. 21.84/11.03 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__FROM(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(MARK(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__AFTER(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[1A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(0) = [[0A]] 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(from(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(after(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[1A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__from(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(a__after(x_1, x_2)) = [[1A]] + [[-I]] * x_1 + [[1A]] * x_2 21.84/11.03 >>> 21.84/11.03 21.84/11.03 21.84/11.03 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 21.84/11.03 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (12) 21.84/11.03 Obligation: 21.84/11.03 Q DP problem: 21.84/11.03 The TRS P consists of the following rules: 21.84/11.03 21.84/11.03 A__FROM(X) -> MARK(X) 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> A__AFTER(mark(N), mark(XS)) 21.84/11.03 MARK(from(X)) -> A__FROM(mark(X)) 21.84/11.03 MARK(from(X)) -> MARK(X) 21.84/11.03 MARK(after(X1, X2)) -> A__AFTER(mark(X1), mark(X2)) 21.84/11.03 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.03 MARK(s(X)) -> MARK(X) 21.84/11.03 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 We have to consider all minimal (P,Q,R)-chains. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (13) DependencyGraphProof (EQUIVALENT) 21.84/11.03 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (14) 21.84/11.03 Complex Obligation (AND) 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (15) 21.84/11.03 Obligation: 21.84/11.03 Q DP problem: 21.84/11.03 The TRS P consists of the following rules: 21.84/11.03 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> A__AFTER(mark(N), mark(XS)) 21.84/11.03 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 We have to consider all minimal (P,Q,R)-chains. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (16) QDPOrderProof (EQUIVALENT) 21.84/11.03 We use the reduction pair processor [LPAR04,JAR06]. 21.84/11.03 21.84/11.03 21.84/11.03 The following pairs can be oriented strictly and are deleted. 21.84/11.03 21.84/11.03 A__AFTER(s(N), cons(X, XS)) -> A__AFTER(mark(N), mark(XS)) 21.84/11.03 The remaining pairs can at least be oriented weakly. 21.84/11.03 Used ordering: Combined order from the following AFS and order. 21.84/11.03 A__AFTER(x1, x2) = x1 21.84/11.03 21.84/11.03 s(x1) = s(x1) 21.84/11.03 21.84/11.03 mark(x1) = mark(x1) 21.84/11.03 21.84/11.03 from(x1) = from 21.84/11.03 21.84/11.03 a__from(x1) = a__from 21.84/11.03 21.84/11.03 after(x1, x2) = after(x1, x2) 21.84/11.03 21.84/11.03 a__after(x1, x2) = a__after(x1, x2) 21.84/11.03 21.84/11.03 0 = 0 21.84/11.03 21.84/11.03 cons(x1, x2) = x2 21.84/11.03 21.84/11.03 21.84/11.03 Knuth-Bendix order [KBO] with precedence:mark_1 > s_1 21.84/11.03 mark_1 > a__after_2 > after_2 21.84/11.03 mark_1 > a__from > from 21.84/11.03 mark_1 > 0 21.84/11.03 21.84/11.03 and weight map: 21.84/11.03 21.84/11.03 s_1=1 21.84/11.03 a__after_2=1 21.84/11.03 a__from=1 21.84/11.03 0=2 21.84/11.03 after_2=1 21.84/11.03 from=1 21.84/11.03 mark_1=0 21.84/11.03 21.84/11.03 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 21.84/11.03 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (17) 21.84/11.03 Obligation: 21.84/11.03 Q DP problem: 21.84/11.03 P is empty. 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 We have to consider all minimal (P,Q,R)-chains. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (18) PisEmptyProof (EQUIVALENT) 21.84/11.03 The TRS P is empty. Hence, there is no (P,Q,R) chain. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (19) 21.84/11.03 YES 21.84/11.03 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (20) 21.84/11.03 Obligation: 21.84/11.03 Q DP problem: 21.84/11.03 The TRS P consists of the following rules: 21.84/11.03 21.84/11.03 MARK(from(X)) -> A__FROM(mark(X)) 21.84/11.03 A__FROM(X) -> MARK(X) 21.84/11.03 MARK(from(X)) -> MARK(X) 21.84/11.03 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.03 MARK(s(X)) -> MARK(X) 21.84/11.03 21.84/11.03 The TRS R consists of the following rules: 21.84/11.03 21.84/11.03 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.03 a__after(0, XS) -> mark(XS) 21.84/11.03 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.03 mark(from(X)) -> a__from(mark(X)) 21.84/11.03 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.03 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.03 mark(s(X)) -> s(mark(X)) 21.84/11.03 mark(0) -> 0 21.84/11.03 a__from(X) -> from(X) 21.84/11.03 a__after(X1, X2) -> after(X1, X2) 21.84/11.03 21.84/11.03 The set Q consists of the following terms: 21.84/11.03 21.84/11.03 a__from(x0) 21.84/11.03 mark(from(x0)) 21.84/11.03 mark(after(x0, x1)) 21.84/11.03 mark(cons(x0, x1)) 21.84/11.03 mark(s(x0)) 21.84/11.03 mark(0) 21.84/11.03 a__after(x0, x1) 21.84/11.03 21.84/11.03 We have to consider all minimal (P,Q,R)-chains. 21.84/11.03 ---------------------------------------- 21.84/11.03 21.84/11.03 (21) QDPOrderProof (EQUIVALENT) 21.84/11.03 We use the reduction pair processor [LPAR04,JAR06]. 21.84/11.03 21.84/11.03 21.84/11.03 The following pairs can be oriented strictly and are deleted. 21.84/11.03 21.84/11.03 MARK(from(X)) -> MARK(X) 21.84/11.03 The remaining pairs can at least be oriented weakly. 21.84/11.03 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(MARK(x_1)) = [[2A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(from(x_1)) = [[3A]] + [[3A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(A__FROM(x_1)) = [[2A]] + [[3A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(mark(x_1)) = [[0A]] + [[0A]] * x_1 21.84/11.03 >>> 21.84/11.03 21.84/11.03 <<< 21.84/11.03 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(a__from(x_1)) = [[3A]] + [[3A]] * x_1 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(after(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(a__after(x_1, x_2)) = [[0A]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(0) = [[0A]] 21.84/11.04 >>> 21.84/11.04 21.84/11.04 21.84/11.04 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 21.84/11.04 21.84/11.04 mark(from(X)) -> a__from(mark(X)) 21.84/11.04 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.04 a__after(0, XS) -> mark(XS) 21.84/11.04 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.04 mark(s(X)) -> s(mark(X)) 21.84/11.04 mark(0) -> 0 21.84/11.04 a__from(X) -> from(X) 21.84/11.04 a__after(X1, X2) -> after(X1, X2) 21.84/11.04 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.04 21.84/11.04 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (22) 21.84/11.04 Obligation: 21.84/11.04 Q DP problem: 21.84/11.04 The TRS P consists of the following rules: 21.84/11.04 21.84/11.04 MARK(from(X)) -> A__FROM(mark(X)) 21.84/11.04 A__FROM(X) -> MARK(X) 21.84/11.04 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.04 MARK(s(X)) -> MARK(X) 21.84/11.04 21.84/11.04 The TRS R consists of the following rules: 21.84/11.04 21.84/11.04 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.04 a__after(0, XS) -> mark(XS) 21.84/11.04 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.04 mark(from(X)) -> a__from(mark(X)) 21.84/11.04 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.04 mark(s(X)) -> s(mark(X)) 21.84/11.04 mark(0) -> 0 21.84/11.04 a__from(X) -> from(X) 21.84/11.04 a__after(X1, X2) -> after(X1, X2) 21.84/11.04 21.84/11.04 The set Q consists of the following terms: 21.84/11.04 21.84/11.04 a__from(x0) 21.84/11.04 mark(from(x0)) 21.84/11.04 mark(after(x0, x1)) 21.84/11.04 mark(cons(x0, x1)) 21.84/11.04 mark(s(x0)) 21.84/11.04 mark(0) 21.84/11.04 a__after(x0, x1) 21.84/11.04 21.84/11.04 We have to consider all minimal (P,Q,R)-chains. 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (23) QDPOrderProof (EQUIVALENT) 21.84/11.04 We use the reduction pair processor [LPAR04,JAR06]. 21.84/11.04 21.84/11.04 21.84/11.04 The following pairs can be oriented strictly and are deleted. 21.84/11.04 21.84/11.04 MARK(from(X)) -> A__FROM(mark(X)) 21.84/11.04 The remaining pairs can at least be oriented weakly. 21.84/11.04 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(MARK(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(from(x_1)) = [[0A]] + [[1A]] * x_1 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(A__FROM(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(mark(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(cons(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(s(x_1)) = [[-I]] + [[0A]] * x_1 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(a__from(x_1)) = [[0A]] + [[1A]] * x_1 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(after(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(a__after(x_1, x_2)) = [[-I]] + [[0A]] * x_1 + [[0A]] * x_2 21.84/11.04 >>> 21.84/11.04 21.84/11.04 <<< 21.84/11.04 POL(0) = [[2A]] 21.84/11.04 >>> 21.84/11.04 21.84/11.04 21.84/11.04 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 21.84/11.04 21.84/11.04 mark(from(X)) -> a__from(mark(X)) 21.84/11.04 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.04 a__after(0, XS) -> mark(XS) 21.84/11.04 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.04 mark(s(X)) -> s(mark(X)) 21.84/11.04 mark(0) -> 0 21.84/11.04 a__from(X) -> from(X) 21.84/11.04 a__after(X1, X2) -> after(X1, X2) 21.84/11.04 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.04 21.84/11.04 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (24) 21.84/11.04 Obligation: 21.84/11.04 Q DP problem: 21.84/11.04 The TRS P consists of the following rules: 21.84/11.04 21.84/11.04 A__FROM(X) -> MARK(X) 21.84/11.04 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.04 MARK(s(X)) -> MARK(X) 21.84/11.04 21.84/11.04 The TRS R consists of the following rules: 21.84/11.04 21.84/11.04 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.04 a__after(0, XS) -> mark(XS) 21.84/11.04 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.04 mark(from(X)) -> a__from(mark(X)) 21.84/11.04 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.04 mark(s(X)) -> s(mark(X)) 21.84/11.04 mark(0) -> 0 21.84/11.04 a__from(X) -> from(X) 21.84/11.04 a__after(X1, X2) -> after(X1, X2) 21.84/11.04 21.84/11.04 The set Q consists of the following terms: 21.84/11.04 21.84/11.04 a__from(x0) 21.84/11.04 mark(from(x0)) 21.84/11.04 mark(after(x0, x1)) 21.84/11.04 mark(cons(x0, x1)) 21.84/11.04 mark(s(x0)) 21.84/11.04 mark(0) 21.84/11.04 a__after(x0, x1) 21.84/11.04 21.84/11.04 We have to consider all minimal (P,Q,R)-chains. 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (25) DependencyGraphProof (EQUIVALENT) 21.84/11.04 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (26) 21.84/11.04 Obligation: 21.84/11.04 Q DP problem: 21.84/11.04 The TRS P consists of the following rules: 21.84/11.04 21.84/11.04 MARK(s(X)) -> MARK(X) 21.84/11.04 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.04 21.84/11.04 The TRS R consists of the following rules: 21.84/11.04 21.84/11.04 a__from(X) -> cons(mark(X), from(s(X))) 21.84/11.04 a__after(0, XS) -> mark(XS) 21.84/11.04 a__after(s(N), cons(X, XS)) -> a__after(mark(N), mark(XS)) 21.84/11.04 mark(from(X)) -> a__from(mark(X)) 21.84/11.04 mark(after(X1, X2)) -> a__after(mark(X1), mark(X2)) 21.84/11.04 mark(cons(X1, X2)) -> cons(mark(X1), X2) 21.84/11.04 mark(s(X)) -> s(mark(X)) 21.84/11.04 mark(0) -> 0 21.84/11.04 a__from(X) -> from(X) 21.84/11.04 a__after(X1, X2) -> after(X1, X2) 21.84/11.04 21.84/11.04 The set Q consists of the following terms: 21.84/11.04 21.84/11.04 a__from(x0) 21.84/11.04 mark(from(x0)) 21.84/11.04 mark(after(x0, x1)) 21.84/11.04 mark(cons(x0, x1)) 21.84/11.04 mark(s(x0)) 21.84/11.04 mark(0) 21.84/11.04 a__after(x0, x1) 21.84/11.04 21.84/11.04 We have to consider all minimal (P,Q,R)-chains. 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (27) UsableRulesProof (EQUIVALENT) 21.84/11.04 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (28) 21.84/11.04 Obligation: 21.84/11.04 Q DP problem: 21.84/11.04 The TRS P consists of the following rules: 21.84/11.04 21.84/11.04 MARK(s(X)) -> MARK(X) 21.84/11.04 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.04 21.84/11.04 R is empty. 21.84/11.04 The set Q consists of the following terms: 21.84/11.04 21.84/11.04 a__from(x0) 21.84/11.04 mark(from(x0)) 21.84/11.04 mark(after(x0, x1)) 21.84/11.04 mark(cons(x0, x1)) 21.84/11.04 mark(s(x0)) 21.84/11.04 mark(0) 21.84/11.04 a__after(x0, x1) 21.84/11.04 21.84/11.04 We have to consider all minimal (P,Q,R)-chains. 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (29) QReductionProof (EQUIVALENT) 21.84/11.04 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 21.84/11.04 21.84/11.04 a__from(x0) 21.84/11.04 mark(from(x0)) 21.84/11.04 mark(after(x0, x1)) 21.84/11.04 mark(cons(x0, x1)) 21.84/11.04 mark(s(x0)) 21.84/11.04 mark(0) 21.84/11.04 a__after(x0, x1) 21.84/11.04 21.84/11.04 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (30) 21.84/11.04 Obligation: 21.84/11.04 Q DP problem: 21.84/11.04 The TRS P consists of the following rules: 21.84/11.04 21.84/11.04 MARK(s(X)) -> MARK(X) 21.84/11.04 MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.04 21.84/11.04 R is empty. 21.84/11.04 Q is empty. 21.84/11.04 We have to consider all minimal (P,Q,R)-chains. 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (31) QDPSizeChangeProof (EQUIVALENT) 21.84/11.04 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 21.84/11.04 21.84/11.04 From the DPs we obtained the following set of size-change graphs: 21.84/11.04 *MARK(s(X)) -> MARK(X) 21.84/11.04 The graph contains the following edges 1 > 1 21.84/11.04 21.84/11.04 21.84/11.04 *MARK(cons(X1, X2)) -> MARK(X1) 21.84/11.04 The graph contains the following edges 1 > 1 21.84/11.04 21.84/11.04 21.84/11.04 ---------------------------------------- 21.84/11.04 21.84/11.04 (32) 21.84/11.04 YES 21.96/11.10 EOF