8.64/3.06 YES 8.64/3.07 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.64/3.07 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.64/3.07 8.64/3.07 8.64/3.07 Termination w.r.t. Q of the given QTRS could be proven: 8.64/3.07 8.64/3.07 (0) QTRS 8.64/3.07 (1) QTRSRRRProof [EQUIVALENT, 840 ms] 8.64/3.07 (2) QTRS 8.64/3.07 (3) QTRSRRRProof [EQUIVALENT, 134 ms] 8.64/3.07 (4) QTRS 8.64/3.07 (5) QTRSRRRProof [EQUIVALENT, 5 ms] 8.64/3.07 (6) QTRS 8.64/3.07 (7) RisEmptyProof [EQUIVALENT, 0 ms] 8.64/3.07 (8) YES 8.64/3.07 8.64/3.07 8.64/3.07 ---------------------------------------- 8.64/3.07 8.64/3.07 (0) 8.64/3.07 Obligation: 8.64/3.07 Q restricted rewrite system: 8.64/3.07 The TRS R consists of the following rules: 8.64/3.07 8.64/3.07 active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2)) 8.64/3.07 active(U12(tt, V2)) -> mark(U13(isNat(V2))) 8.64/3.07 active(U13(tt)) -> mark(tt) 8.64/3.07 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 8.64/3.07 active(U22(tt)) -> mark(tt) 8.64/3.07 active(U31(tt, V1, V2)) -> mark(U32(isNat(V1), V2)) 8.64/3.07 active(U32(tt, V2)) -> mark(U33(isNat(V2))) 8.64/3.07 active(U33(tt)) -> mark(tt) 8.64/3.07 active(U41(tt, N)) -> mark(N) 8.64/3.07 active(U51(tt, M, N)) -> mark(s(plus(N, M))) 8.64/3.07 active(U61(tt)) -> mark(0) 8.64/3.07 active(U71(tt, M, N)) -> mark(plus(x(N, M), N)) 8.64/3.07 active(and(tt, X)) -> mark(X) 8.64/3.07 active(isNat(0)) -> mark(tt) 8.64/3.07 active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 8.64/3.07 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 8.64/3.07 active(isNat(x(V1, V2))) -> mark(U31(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 8.64/3.07 active(isNatKind(0)) -> mark(tt) 8.64/3.07 active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 8.64/3.07 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 8.64/3.07 active(isNatKind(x(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 8.64/3.07 active(plus(N, 0)) -> mark(U41(and(isNat(N), isNatKind(N)), N)) 8.64/3.07 active(plus(N, s(M))) -> mark(U51(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 8.64/3.07 active(x(N, 0)) -> mark(U61(and(isNat(N), isNatKind(N)))) 8.64/3.07 active(x(N, s(M))) -> mark(U71(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 8.64/3.07 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 8.64/3.07 mark(tt) -> active(tt) 8.64/3.07 mark(U12(X1, X2)) -> active(U12(mark(X1), X2)) 8.64/3.07 mark(isNat(X)) -> active(isNat(X)) 8.64/3.07 mark(U13(X)) -> active(U13(mark(X))) 8.64/3.07 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 8.64/3.07 mark(U22(X)) -> active(U22(mark(X))) 8.64/3.07 mark(U31(X1, X2, X3)) -> active(U31(mark(X1), X2, X3)) 8.64/3.07 mark(U32(X1, X2)) -> active(U32(mark(X1), X2)) 8.64/3.07 mark(U33(X)) -> active(U33(mark(X))) 8.64/3.07 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 8.64/3.07 mark(U51(X1, X2, X3)) -> active(U51(mark(X1), X2, X3)) 8.64/3.07 mark(s(X)) -> active(s(mark(X))) 8.64/3.07 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 8.64/3.07 mark(U61(X)) -> active(U61(mark(X))) 8.64/3.07 mark(0) -> active(0) 8.64/3.07 mark(U71(X1, X2, X3)) -> active(U71(mark(X1), X2, X3)) 8.64/3.07 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 8.64/3.07 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.64/3.07 mark(isNatKind(X)) -> active(isNatKind(X)) 8.64/3.07 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 8.64/3.07 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 8.64/3.07 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 8.64/3.07 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 8.64/3.07 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 8.64/3.07 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 8.64/3.07 U12(mark(X1), X2) -> U12(X1, X2) 8.64/3.07 U12(X1, mark(X2)) -> U12(X1, X2) 8.64/3.07 U12(active(X1), X2) -> U12(X1, X2) 8.64/3.07 U12(X1, active(X2)) -> U12(X1, X2) 8.64/3.07 isNat(mark(X)) -> isNat(X) 8.64/3.07 isNat(active(X)) -> isNat(X) 8.64/3.07 U13(mark(X)) -> U13(X) 8.64/3.07 U13(active(X)) -> U13(X) 8.64/3.07 U21(mark(X1), X2) -> U21(X1, X2) 8.64/3.07 U21(X1, mark(X2)) -> U21(X1, X2) 8.64/3.07 U21(active(X1), X2) -> U21(X1, X2) 8.64/3.07 U21(X1, active(X2)) -> U21(X1, X2) 8.64/3.07 U22(mark(X)) -> U22(X) 8.64/3.07 U22(active(X)) -> U22(X) 8.64/3.07 U31(mark(X1), X2, X3) -> U31(X1, X2, X3) 8.64/3.07 U31(X1, mark(X2), X3) -> U31(X1, X2, X3) 8.64/3.07 U31(X1, X2, mark(X3)) -> U31(X1, X2, X3) 8.64/3.07 U31(active(X1), X2, X3) -> U31(X1, X2, X3) 8.64/3.07 U31(X1, active(X2), X3) -> U31(X1, X2, X3) 8.64/3.07 U31(X1, X2, active(X3)) -> U31(X1, X2, X3) 8.64/3.07 U32(mark(X1), X2) -> U32(X1, X2) 8.64/3.07 U32(X1, mark(X2)) -> U32(X1, X2) 8.64/3.07 U32(active(X1), X2) -> U32(X1, X2) 8.64/3.07 U32(X1, active(X2)) -> U32(X1, X2) 8.64/3.07 U33(mark(X)) -> U33(X) 8.64/3.07 U33(active(X)) -> U33(X) 8.64/3.07 U41(mark(X1), X2) -> U41(X1, X2) 8.64/3.07 U41(X1, mark(X2)) -> U41(X1, X2) 8.64/3.07 U41(active(X1), X2) -> U41(X1, X2) 8.64/3.07 U41(X1, active(X2)) -> U41(X1, X2) 8.64/3.07 U51(mark(X1), X2, X3) -> U51(X1, X2, X3) 8.64/3.07 U51(X1, mark(X2), X3) -> U51(X1, X2, X3) 8.64/3.07 U51(X1, X2, mark(X3)) -> U51(X1, X2, X3) 8.64/3.07 U51(active(X1), X2, X3) -> U51(X1, X2, X3) 8.64/3.07 U51(X1, active(X2), X3) -> U51(X1, X2, X3) 8.64/3.07 U51(X1, X2, active(X3)) -> U51(X1, X2, X3) 8.64/3.07 s(mark(X)) -> s(X) 8.64/3.07 s(active(X)) -> s(X) 8.64/3.07 plus(mark(X1), X2) -> plus(X1, X2) 8.64/3.07 plus(X1, mark(X2)) -> plus(X1, X2) 8.64/3.07 plus(active(X1), X2) -> plus(X1, X2) 8.64/3.07 plus(X1, active(X2)) -> plus(X1, X2) 8.64/3.07 U61(mark(X)) -> U61(X) 8.64/3.07 U61(active(X)) -> U61(X) 8.64/3.07 U71(mark(X1), X2, X3) -> U71(X1, X2, X3) 8.64/3.07 U71(X1, mark(X2), X3) -> U71(X1, X2, X3) 8.64/3.07 U71(X1, X2, mark(X3)) -> U71(X1, X2, X3) 8.64/3.07 U71(active(X1), X2, X3) -> U71(X1, X2, X3) 8.64/3.07 U71(X1, active(X2), X3) -> U71(X1, X2, X3) 8.64/3.07 U71(X1, X2, active(X3)) -> U71(X1, X2, X3) 8.64/3.07 x(mark(X1), X2) -> x(X1, X2) 8.64/3.07 x(X1, mark(X2)) -> x(X1, X2) 8.64/3.07 x(active(X1), X2) -> x(X1, X2) 8.64/3.07 x(X1, active(X2)) -> x(X1, X2) 8.64/3.07 and(mark(X1), X2) -> and(X1, X2) 8.64/3.07 and(X1, mark(X2)) -> and(X1, X2) 8.64/3.07 and(active(X1), X2) -> and(X1, X2) 8.64/3.07 and(X1, active(X2)) -> and(X1, X2) 8.64/3.07 isNatKind(mark(X)) -> isNatKind(X) 8.64/3.07 isNatKind(active(X)) -> isNatKind(X) 8.64/3.07 8.64/3.07 The set Q consists of the following terms: 8.64/3.07 8.64/3.07 active(U11(tt, x0, x1)) 8.64/3.07 active(U12(tt, x0)) 8.64/3.07 active(U13(tt)) 8.64/3.07 active(U21(tt, x0)) 8.64/3.07 active(U22(tt)) 8.64/3.07 active(U31(tt, x0, x1)) 8.64/3.07 active(U32(tt, x0)) 8.64/3.07 active(U33(tt)) 8.64/3.07 active(U41(tt, x0)) 8.64/3.07 active(U51(tt, x0, x1)) 8.64/3.07 active(U61(tt)) 8.64/3.07 active(U71(tt, x0, x1)) 8.64/3.07 active(and(tt, x0)) 8.64/3.07 active(isNat(0)) 8.64/3.07 active(isNat(plus(x0, x1))) 8.64/3.07 active(isNat(s(x0))) 8.64/3.07 active(isNat(x(x0, x1))) 8.64/3.07 active(isNatKind(0)) 8.64/3.07 active(isNatKind(plus(x0, x1))) 8.64/3.07 active(isNatKind(s(x0))) 8.64/3.07 active(isNatKind(x(x0, x1))) 8.64/3.07 active(plus(x0, 0)) 8.64/3.07 active(plus(x0, s(x1))) 8.64/3.07 active(x(x0, 0)) 8.64/3.07 active(x(x0, s(x1))) 8.64/3.07 mark(U11(x0, x1, x2)) 8.64/3.07 mark(tt) 8.64/3.07 mark(U12(x0, x1)) 8.64/3.07 mark(isNat(x0)) 8.64/3.07 mark(U13(x0)) 8.64/3.07 mark(U21(x0, x1)) 8.64/3.07 mark(U22(x0)) 8.64/3.07 mark(U31(x0, x1, x2)) 8.64/3.07 mark(U32(x0, x1)) 8.64/3.07 mark(U33(x0)) 8.64/3.07 mark(U41(x0, x1)) 8.64/3.07 mark(U51(x0, x1, x2)) 8.64/3.07 mark(s(x0)) 8.64/3.07 mark(plus(x0, x1)) 8.64/3.07 mark(U61(x0)) 8.64/3.07 mark(0) 8.64/3.07 mark(U71(x0, x1, x2)) 8.64/3.07 mark(x(x0, x1)) 8.64/3.07 mark(and(x0, x1)) 8.64/3.07 mark(isNatKind(x0)) 8.64/3.07 U11(mark(x0), x1, x2) 8.64/3.07 U11(x0, mark(x1), x2) 8.64/3.07 U11(x0, x1, mark(x2)) 8.64/3.07 U11(active(x0), x1, x2) 8.64/3.07 U11(x0, active(x1), x2) 8.64/3.07 U11(x0, x1, active(x2)) 8.64/3.07 U12(mark(x0), x1) 8.64/3.07 U12(x0, mark(x1)) 8.64/3.07 U12(active(x0), x1) 8.64/3.07 U12(x0, active(x1)) 8.64/3.07 isNat(mark(x0)) 8.64/3.07 isNat(active(x0)) 8.64/3.07 U13(mark(x0)) 8.64/3.07 U13(active(x0)) 8.64/3.07 U21(mark(x0), x1) 8.64/3.07 U21(x0, mark(x1)) 8.64/3.07 U21(active(x0), x1) 8.64/3.07 U21(x0, active(x1)) 8.64/3.07 U22(mark(x0)) 8.64/3.07 U22(active(x0)) 8.64/3.07 U31(mark(x0), x1, x2) 8.64/3.07 U31(x0, mark(x1), x2) 8.64/3.07 U31(x0, x1, mark(x2)) 8.64/3.07 U31(active(x0), x1, x2) 8.64/3.07 U31(x0, active(x1), x2) 8.64/3.07 U31(x0, x1, active(x2)) 8.64/3.07 U32(mark(x0), x1) 8.64/3.07 U32(x0, mark(x1)) 8.64/3.07 U32(active(x0), x1) 8.64/3.07 U32(x0, active(x1)) 8.64/3.07 U33(mark(x0)) 8.64/3.07 U33(active(x0)) 8.64/3.07 U41(mark(x0), x1) 8.64/3.07 U41(x0, mark(x1)) 8.64/3.07 U41(active(x0), x1) 8.64/3.07 U41(x0, active(x1)) 8.64/3.07 U51(mark(x0), x1, x2) 8.64/3.07 U51(x0, mark(x1), x2) 8.64/3.07 U51(x0, x1, mark(x2)) 8.64/3.07 U51(active(x0), x1, x2) 8.64/3.07 U51(x0, active(x1), x2) 8.64/3.07 U51(x0, x1, active(x2)) 8.64/3.07 s(mark(x0)) 8.64/3.07 s(active(x0)) 8.64/3.07 plus(mark(x0), x1) 8.64/3.07 plus(x0, mark(x1)) 8.64/3.07 plus(active(x0), x1) 8.64/3.07 plus(x0, active(x1)) 8.64/3.07 U61(mark(x0)) 8.64/3.07 U61(active(x0)) 8.64/3.07 U71(mark(x0), x1, x2) 8.64/3.07 U71(x0, mark(x1), x2) 8.64/3.07 U71(x0, x1, mark(x2)) 8.64/3.07 U71(active(x0), x1, x2) 8.64/3.07 U71(x0, active(x1), x2) 8.64/3.07 U71(x0, x1, active(x2)) 8.64/3.07 x(mark(x0), x1) 8.64/3.07 x(x0, mark(x1)) 8.64/3.07 x(active(x0), x1) 8.64/3.07 x(x0, active(x1)) 8.64/3.07 and(mark(x0), x1) 8.64/3.07 and(x0, mark(x1)) 8.64/3.07 and(active(x0), x1) 8.64/3.07 and(x0, active(x1)) 8.64/3.07 isNatKind(mark(x0)) 8.64/3.07 isNatKind(active(x0)) 8.64/3.07 8.64/3.07 8.64/3.07 ---------------------------------------- 8.64/3.07 8.64/3.07 (1) QTRSRRRProof (EQUIVALENT) 8.64/3.07 Used ordering: 8.64/3.07 active/1)YES( 8.64/3.07 U11/3(YES,YES,YES) 8.64/3.07 tt/0) 8.64/3.07 mark/1)YES( 8.64/3.07 U12/2(YES,YES) 8.64/3.07 isNat/1)YES( 8.64/3.07 U13/1)YES( 8.64/3.07 U21/2(YES,YES) 8.64/3.07 U22/1(YES) 8.64/3.07 U31/3(YES,YES,YES) 8.64/3.07 U32/2(YES,YES) 8.64/3.07 U33/1(YES) 8.64/3.07 U41/2(YES,YES) 8.64/3.07 U51/3(YES,YES,YES) 8.64/3.07 s/1(YES) 8.64/3.07 plus/2(YES,YES) 8.64/3.07 U61/1(YES) 8.64/3.07 0/0) 8.64/3.07 U71/3(YES,YES,YES) 8.64/3.07 x/2(YES,YES) 8.64/3.07 and/2(YES,YES) 8.64/3.07 isNatKind/1)YES( 8.64/3.07 8.64/3.07 Quasi precedence: 8.64/3.07 [U71_3, x_2] > U31_3 > U32_2 > U33_1 > tt 8.64/3.07 [U71_3, x_2] > [U51_3, plus_2] > U11_3 > U12_2 8.64/3.07 [U71_3, x_2] > [U51_3, plus_2] > U41_2 8.64/3.07 [U71_3, x_2] > [U51_3, plus_2] > s_1 > U21_2 > U22_1 > tt 8.64/3.07 [U71_3, x_2] > [U51_3, plus_2] > and_2 8.64/3.07 [U71_3, x_2] > [U61_1, 0] > tt 8.64/3.07 8.64/3.07 8.64/3.07 Status: 8.64/3.07 U11_3: [1,2,3] 8.64/3.07 tt: multiset status 8.64/3.07 U12_2: multiset status 8.64/3.07 U21_2: [1,2] 8.64/3.07 U22_1: multiset status 8.64/3.07 U31_3: [3,1,2] 8.64/3.07 U32_2: multiset status 8.64/3.07 U33_1: multiset status 8.64/3.07 U41_2: multiset status 8.64/3.07 U51_3: [2,3,1] 8.64/3.07 s_1: multiset status 8.64/3.07 plus_2: [2,1] 8.64/3.07 U61_1: multiset status 8.64/3.07 0: multiset status 8.64/3.07 U71_3: [3,2,1] 8.64/3.07 x_2: [1,2] 8.64/3.07 and_2: multiset status 8.64/3.07 8.64/3.07 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.64/3.07 8.64/3.07 active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2)) 8.64/3.07 active(U12(tt, V2)) -> mark(U13(isNat(V2))) 8.64/3.07 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 8.64/3.07 active(U22(tt)) -> mark(tt) 8.64/3.07 active(U31(tt, V1, V2)) -> mark(U32(isNat(V1), V2)) 8.64/3.07 active(U32(tt, V2)) -> mark(U33(isNat(V2))) 8.64/3.07 active(U33(tt)) -> mark(tt) 8.64/3.07 active(U41(tt, N)) -> mark(N) 8.64/3.07 active(U51(tt, M, N)) -> mark(s(plus(N, M))) 8.64/3.07 active(U61(tt)) -> mark(0) 8.64/3.07 active(U71(tt, M, N)) -> mark(plus(x(N, M), N)) 8.64/3.07 active(and(tt, X)) -> mark(X) 8.64/3.07 active(isNat(0)) -> mark(tt) 8.64/3.07 active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 8.64/3.07 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 8.64/3.07 active(isNat(x(V1, V2))) -> mark(U31(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 8.64/3.07 active(isNatKind(0)) -> mark(tt) 8.64/3.07 active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 8.64/3.07 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 8.64/3.07 active(isNatKind(x(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 8.64/3.07 active(plus(N, 0)) -> mark(U41(and(isNat(N), isNatKind(N)), N)) 8.64/3.07 active(plus(N, s(M))) -> mark(U51(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 8.64/3.07 active(x(N, 0)) -> mark(U61(and(isNat(N), isNatKind(N)))) 8.64/3.07 active(x(N, s(M))) -> mark(U71(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 8.64/3.07 8.64/3.07 8.64/3.07 8.64/3.07 8.64/3.07 ---------------------------------------- 8.64/3.07 8.64/3.07 (2) 8.64/3.07 Obligation: 8.64/3.07 Q restricted rewrite system: 8.64/3.07 The TRS R consists of the following rules: 8.64/3.07 8.64/3.07 active(U13(tt)) -> mark(tt) 8.64/3.07 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 8.64/3.07 mark(tt) -> active(tt) 8.64/3.07 mark(U12(X1, X2)) -> active(U12(mark(X1), X2)) 8.64/3.07 mark(isNat(X)) -> active(isNat(X)) 8.64/3.07 mark(U13(X)) -> active(U13(mark(X))) 8.64/3.07 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 8.64/3.07 mark(U22(X)) -> active(U22(mark(X))) 8.64/3.07 mark(U31(X1, X2, X3)) -> active(U31(mark(X1), X2, X3)) 8.64/3.07 mark(U32(X1, X2)) -> active(U32(mark(X1), X2)) 8.64/3.07 mark(U33(X)) -> active(U33(mark(X))) 8.64/3.07 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 8.64/3.07 mark(U51(X1, X2, X3)) -> active(U51(mark(X1), X2, X3)) 8.64/3.07 mark(s(X)) -> active(s(mark(X))) 8.64/3.07 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 8.64/3.07 mark(U61(X)) -> active(U61(mark(X))) 8.64/3.07 mark(0) -> active(0) 8.64/3.07 mark(U71(X1, X2, X3)) -> active(U71(mark(X1), X2, X3)) 8.64/3.07 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 8.64/3.07 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.64/3.07 mark(isNatKind(X)) -> active(isNatKind(X)) 8.64/3.07 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 8.64/3.07 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 8.64/3.07 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 8.64/3.07 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 8.64/3.07 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 8.64/3.07 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 8.64/3.07 U12(mark(X1), X2) -> U12(X1, X2) 8.64/3.07 U12(X1, mark(X2)) -> U12(X1, X2) 8.64/3.07 U12(active(X1), X2) -> U12(X1, X2) 8.64/3.07 U12(X1, active(X2)) -> U12(X1, X2) 8.64/3.07 isNat(mark(X)) -> isNat(X) 8.64/3.07 isNat(active(X)) -> isNat(X) 8.64/3.07 U13(mark(X)) -> U13(X) 8.64/3.07 U13(active(X)) -> U13(X) 8.64/3.07 U21(mark(X1), X2) -> U21(X1, X2) 8.64/3.07 U21(X1, mark(X2)) -> U21(X1, X2) 8.64/3.07 U21(active(X1), X2) -> U21(X1, X2) 8.64/3.07 U21(X1, active(X2)) -> U21(X1, X2) 8.64/3.07 U22(mark(X)) -> U22(X) 8.64/3.07 U22(active(X)) -> U22(X) 8.64/3.07 U31(mark(X1), X2, X3) -> U31(X1, X2, X3) 8.64/3.07 U31(X1, mark(X2), X3) -> U31(X1, X2, X3) 8.64/3.07 U31(X1, X2, mark(X3)) -> U31(X1, X2, X3) 8.64/3.07 U31(active(X1), X2, X3) -> U31(X1, X2, X3) 8.64/3.07 U31(X1, active(X2), X3) -> U31(X1, X2, X3) 8.64/3.07 U31(X1, X2, active(X3)) -> U31(X1, X2, X3) 8.64/3.07 U32(mark(X1), X2) -> U32(X1, X2) 8.64/3.07 U32(X1, mark(X2)) -> U32(X1, X2) 8.64/3.07 U32(active(X1), X2) -> U32(X1, X2) 8.64/3.07 U32(X1, active(X2)) -> U32(X1, X2) 8.64/3.07 U33(mark(X)) -> U33(X) 8.64/3.07 U33(active(X)) -> U33(X) 8.64/3.07 U41(mark(X1), X2) -> U41(X1, X2) 8.64/3.07 U41(X1, mark(X2)) -> U41(X1, X2) 8.64/3.07 U41(active(X1), X2) -> U41(X1, X2) 8.64/3.07 U41(X1, active(X2)) -> U41(X1, X2) 8.64/3.07 U51(mark(X1), X2, X3) -> U51(X1, X2, X3) 8.64/3.07 U51(X1, mark(X2), X3) -> U51(X1, X2, X3) 8.64/3.07 U51(X1, X2, mark(X3)) -> U51(X1, X2, X3) 8.64/3.07 U51(active(X1), X2, X3) -> U51(X1, X2, X3) 8.64/3.07 U51(X1, active(X2), X3) -> U51(X1, X2, X3) 8.64/3.07 U51(X1, X2, active(X3)) -> U51(X1, X2, X3) 8.64/3.07 s(mark(X)) -> s(X) 8.64/3.07 s(active(X)) -> s(X) 8.64/3.07 plus(mark(X1), X2) -> plus(X1, X2) 8.64/3.07 plus(X1, mark(X2)) -> plus(X1, X2) 8.64/3.07 plus(active(X1), X2) -> plus(X1, X2) 8.64/3.07 plus(X1, active(X2)) -> plus(X1, X2) 8.64/3.07 U61(mark(X)) -> U61(X) 8.64/3.07 U61(active(X)) -> U61(X) 8.64/3.07 U71(mark(X1), X2, X3) -> U71(X1, X2, X3) 8.64/3.07 U71(X1, mark(X2), X3) -> U71(X1, X2, X3) 8.64/3.07 U71(X1, X2, mark(X3)) -> U71(X1, X2, X3) 8.64/3.07 U71(active(X1), X2, X3) -> U71(X1, X2, X3) 8.64/3.07 U71(X1, active(X2), X3) -> U71(X1, X2, X3) 8.64/3.07 U71(X1, X2, active(X3)) -> U71(X1, X2, X3) 8.64/3.07 x(mark(X1), X2) -> x(X1, X2) 8.64/3.07 x(X1, mark(X2)) -> x(X1, X2) 8.64/3.07 x(active(X1), X2) -> x(X1, X2) 8.64/3.07 x(X1, active(X2)) -> x(X1, X2) 8.64/3.07 and(mark(X1), X2) -> and(X1, X2) 8.64/3.07 and(X1, mark(X2)) -> and(X1, X2) 8.64/3.07 and(active(X1), X2) -> and(X1, X2) 8.64/3.07 and(X1, active(X2)) -> and(X1, X2) 8.64/3.07 isNatKind(mark(X)) -> isNatKind(X) 8.64/3.07 isNatKind(active(X)) -> isNatKind(X) 8.64/3.07 8.64/3.07 The set Q consists of the following terms: 8.64/3.07 8.64/3.07 active(U11(tt, x0, x1)) 8.64/3.07 active(U12(tt, x0)) 8.64/3.07 active(U13(tt)) 8.64/3.07 active(U21(tt, x0)) 8.64/3.07 active(U22(tt)) 8.64/3.07 active(U31(tt, x0, x1)) 8.64/3.07 active(U32(tt, x0)) 8.64/3.07 active(U33(tt)) 8.64/3.07 active(U41(tt, x0)) 8.64/3.07 active(U51(tt, x0, x1)) 8.64/3.07 active(U61(tt)) 8.64/3.07 active(U71(tt, x0, x1)) 8.64/3.07 active(and(tt, x0)) 8.64/3.07 active(isNat(0)) 8.64/3.07 active(isNat(plus(x0, x1))) 8.64/3.07 active(isNat(s(x0))) 8.64/3.07 active(isNat(x(x0, x1))) 8.64/3.07 active(isNatKind(0)) 8.64/3.07 active(isNatKind(plus(x0, x1))) 8.64/3.07 active(isNatKind(s(x0))) 8.64/3.07 active(isNatKind(x(x0, x1))) 8.64/3.07 active(plus(x0, 0)) 8.64/3.07 active(plus(x0, s(x1))) 8.64/3.07 active(x(x0, 0)) 8.64/3.07 active(x(x0, s(x1))) 8.64/3.07 mark(U11(x0, x1, x2)) 8.64/3.07 mark(tt) 8.64/3.07 mark(U12(x0, x1)) 8.64/3.07 mark(isNat(x0)) 8.64/3.07 mark(U13(x0)) 8.64/3.07 mark(U21(x0, x1)) 8.64/3.07 mark(U22(x0)) 8.64/3.07 mark(U31(x0, x1, x2)) 8.64/3.07 mark(U32(x0, x1)) 8.64/3.07 mark(U33(x0)) 8.64/3.07 mark(U41(x0, x1)) 8.64/3.07 mark(U51(x0, x1, x2)) 8.64/3.07 mark(s(x0)) 8.64/3.07 mark(plus(x0, x1)) 8.64/3.07 mark(U61(x0)) 8.64/3.07 mark(0) 8.64/3.07 mark(U71(x0, x1, x2)) 8.64/3.07 mark(x(x0, x1)) 8.64/3.07 mark(and(x0, x1)) 8.64/3.07 mark(isNatKind(x0)) 8.64/3.07 U11(mark(x0), x1, x2) 8.64/3.07 U11(x0, mark(x1), x2) 8.64/3.07 U11(x0, x1, mark(x2)) 8.64/3.07 U11(active(x0), x1, x2) 8.64/3.07 U11(x0, active(x1), x2) 8.64/3.07 U11(x0, x1, active(x2)) 8.64/3.07 U12(mark(x0), x1) 8.64/3.07 U12(x0, mark(x1)) 8.64/3.07 U12(active(x0), x1) 8.64/3.07 U12(x0, active(x1)) 8.64/3.07 isNat(mark(x0)) 8.64/3.07 isNat(active(x0)) 8.64/3.07 U13(mark(x0)) 8.64/3.07 U13(active(x0)) 8.64/3.07 U21(mark(x0), x1) 8.64/3.07 U21(x0, mark(x1)) 8.64/3.07 U21(active(x0), x1) 8.64/3.07 U21(x0, active(x1)) 8.64/3.07 U22(mark(x0)) 8.64/3.07 U22(active(x0)) 8.64/3.07 U31(mark(x0), x1, x2) 8.64/3.07 U31(x0, mark(x1), x2) 8.64/3.07 U31(x0, x1, mark(x2)) 8.64/3.07 U31(active(x0), x1, x2) 8.64/3.07 U31(x0, active(x1), x2) 8.64/3.07 U31(x0, x1, active(x2)) 8.64/3.07 U32(mark(x0), x1) 8.64/3.07 U32(x0, mark(x1)) 8.64/3.07 U32(active(x0), x1) 8.64/3.07 U32(x0, active(x1)) 8.64/3.07 U33(mark(x0)) 8.64/3.07 U33(active(x0)) 8.64/3.07 U41(mark(x0), x1) 8.64/3.07 U41(x0, mark(x1)) 8.64/3.07 U41(active(x0), x1) 8.64/3.07 U41(x0, active(x1)) 8.64/3.07 U51(mark(x0), x1, x2) 8.64/3.07 U51(x0, mark(x1), x2) 8.64/3.07 U51(x0, x1, mark(x2)) 8.64/3.07 U51(active(x0), x1, x2) 8.64/3.07 U51(x0, active(x1), x2) 8.64/3.07 U51(x0, x1, active(x2)) 8.64/3.07 s(mark(x0)) 8.64/3.07 s(active(x0)) 8.64/3.07 plus(mark(x0), x1) 8.64/3.07 plus(x0, mark(x1)) 8.64/3.07 plus(active(x0), x1) 8.64/3.07 plus(x0, active(x1)) 8.64/3.07 U61(mark(x0)) 8.64/3.07 U61(active(x0)) 8.64/3.07 U71(mark(x0), x1, x2) 8.64/3.07 U71(x0, mark(x1), x2) 8.64/3.07 U71(x0, x1, mark(x2)) 8.64/3.07 U71(active(x0), x1, x2) 8.64/3.07 U71(x0, active(x1), x2) 8.64/3.07 U71(x0, x1, active(x2)) 8.64/3.07 x(mark(x0), x1) 8.64/3.07 x(x0, mark(x1)) 8.64/3.07 x(active(x0), x1) 8.64/3.07 x(x0, active(x1)) 8.64/3.08 and(mark(x0), x1) 8.64/3.08 and(x0, mark(x1)) 8.64/3.08 and(active(x0), x1) 8.64/3.08 and(x0, active(x1)) 8.64/3.08 isNatKind(mark(x0)) 8.64/3.08 isNatKind(active(x0)) 8.64/3.08 8.64/3.08 8.64/3.08 ---------------------------------------- 8.64/3.08 8.64/3.08 (3) QTRSRRRProof (EQUIVALENT) 8.64/3.08 Used ordering: 8.64/3.08 Polynomial interpretation [POLO]: 8.64/3.08 8.64/3.08 POL(0) = 2 8.64/3.08 POL(U11(x_1, x_2, x_3)) = 2 + x_1 + x_2 + x_3 8.64/3.08 POL(U12(x_1, x_2)) = 2 + x_1 + x_2 8.64/3.08 POL(U13(x_1)) = 2 + x_1 8.64/3.08 POL(U21(x_1, x_2)) = 2 + x_1 + x_2 8.64/3.08 POL(U22(x_1)) = 2 + x_1 8.64/3.08 POL(U31(x_1, x_2, x_3)) = 2 + x_1 + x_2 + x_3 8.64/3.08 POL(U32(x_1, x_2)) = 2 + x_1 + x_2 8.64/3.08 POL(U33(x_1)) = 2 + x_1 8.64/3.08 POL(U41(x_1, x_2)) = 2 + x_1 + x_2 8.64/3.08 POL(U51(x_1, x_2, x_3)) = 2 + x_1 + x_2 + x_3 8.64/3.08 POL(U61(x_1)) = 2 + x_1 8.64/3.08 POL(U71(x_1, x_2, x_3)) = 2 + x_1 + x_2 + 2*x_3 8.64/3.08 POL(active(x_1)) = 1 + x_1 8.64/3.08 POL(and(x_1, x_2)) = 2 + 2*x_1 + x_2 8.64/3.08 POL(isNat(x_1)) = 2 + x_1 8.64/3.08 POL(isNatKind(x_1)) = 2 + x_1 8.64/3.08 POL(mark(x_1)) = 2*x_1 8.64/3.08 POL(plus(x_1, x_2)) = 2 + x_1 + x_2 8.64/3.08 POL(s(x_1)) = 2 + x_1 8.64/3.08 POL(tt) = 2 8.64/3.08 POL(x(x_1, x_2)) = 2 + x_1 + x_2 8.64/3.08 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.64/3.08 8.64/3.08 active(U13(tt)) -> mark(tt) 8.64/3.08 mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3)) 8.64/3.08 mark(tt) -> active(tt) 8.64/3.08 mark(U12(X1, X2)) -> active(U12(mark(X1), X2)) 8.64/3.08 mark(isNat(X)) -> active(isNat(X)) 8.64/3.08 mark(U13(X)) -> active(U13(mark(X))) 8.64/3.08 mark(U21(X1, X2)) -> active(U21(mark(X1), X2)) 8.64/3.08 mark(U22(X)) -> active(U22(mark(X))) 8.64/3.08 mark(U31(X1, X2, X3)) -> active(U31(mark(X1), X2, X3)) 8.64/3.08 mark(U32(X1, X2)) -> active(U32(mark(X1), X2)) 8.64/3.08 mark(U33(X)) -> active(U33(mark(X))) 8.64/3.08 mark(U41(X1, X2)) -> active(U41(mark(X1), X2)) 8.64/3.08 mark(U51(X1, X2, X3)) -> active(U51(mark(X1), X2, X3)) 8.64/3.08 mark(s(X)) -> active(s(mark(X))) 8.64/3.08 mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) 8.64/3.08 mark(U61(X)) -> active(U61(mark(X))) 8.64/3.08 mark(0) -> active(0) 8.64/3.08 mark(U71(X1, X2, X3)) -> active(U71(mark(X1), X2, X3)) 8.64/3.08 mark(x(X1, X2)) -> active(x(mark(X1), mark(X2))) 8.64/3.08 mark(and(X1, X2)) -> active(and(mark(X1), X2)) 8.64/3.08 mark(isNatKind(X)) -> active(isNatKind(X)) 8.64/3.08 U11(active(X1), X2, X3) -> U11(X1, X2, X3) 8.64/3.08 U11(X1, active(X2), X3) -> U11(X1, X2, X3) 8.64/3.08 U11(X1, X2, active(X3)) -> U11(X1, X2, X3) 8.64/3.08 U12(active(X1), X2) -> U12(X1, X2) 8.64/3.08 U12(X1, active(X2)) -> U12(X1, X2) 8.64/3.08 isNat(active(X)) -> isNat(X) 8.64/3.08 U13(active(X)) -> U13(X) 8.64/3.08 U21(active(X1), X2) -> U21(X1, X2) 8.64/3.08 U21(X1, active(X2)) -> U21(X1, X2) 8.64/3.08 U22(active(X)) -> U22(X) 8.64/3.08 U31(active(X1), X2, X3) -> U31(X1, X2, X3) 8.64/3.08 U31(X1, active(X2), X3) -> U31(X1, X2, X3) 8.64/3.08 U31(X1, X2, active(X3)) -> U31(X1, X2, X3) 8.64/3.08 U32(active(X1), X2) -> U32(X1, X2) 8.64/3.08 U32(X1, active(X2)) -> U32(X1, X2) 8.64/3.08 U33(active(X)) -> U33(X) 8.64/3.08 U41(active(X1), X2) -> U41(X1, X2) 8.64/3.08 U41(X1, active(X2)) -> U41(X1, X2) 8.64/3.08 U51(active(X1), X2, X3) -> U51(X1, X2, X3) 8.64/3.08 U51(X1, active(X2), X3) -> U51(X1, X2, X3) 8.64/3.08 U51(X1, X2, active(X3)) -> U51(X1, X2, X3) 8.64/3.08 s(active(X)) -> s(X) 8.64/3.08 plus(active(X1), X2) -> plus(X1, X2) 8.64/3.08 plus(X1, active(X2)) -> plus(X1, X2) 8.64/3.08 U61(active(X)) -> U61(X) 8.64/3.08 U71(active(X1), X2, X3) -> U71(X1, X2, X3) 8.64/3.08 U71(X1, active(X2), X3) -> U71(X1, X2, X3) 8.64/3.08 U71(X1, X2, active(X3)) -> U71(X1, X2, X3) 8.64/3.08 x(active(X1), X2) -> x(X1, X2) 8.64/3.08 x(X1, active(X2)) -> x(X1, X2) 8.64/3.08 and(active(X1), X2) -> and(X1, X2) 8.64/3.08 and(X1, active(X2)) -> and(X1, X2) 8.64/3.08 isNatKind(active(X)) -> isNatKind(X) 8.64/3.08 8.64/3.08 8.64/3.08 8.64/3.08 8.64/3.08 ---------------------------------------- 8.64/3.08 8.64/3.08 (4) 8.64/3.08 Obligation: 8.64/3.08 Q restricted rewrite system: 8.64/3.08 The TRS R consists of the following rules: 8.64/3.08 8.64/3.08 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 8.64/3.08 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 8.64/3.08 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 8.64/3.08 U12(mark(X1), X2) -> U12(X1, X2) 8.64/3.08 U12(X1, mark(X2)) -> U12(X1, X2) 8.64/3.08 isNat(mark(X)) -> isNat(X) 8.64/3.08 U13(mark(X)) -> U13(X) 8.64/3.08 U21(mark(X1), X2) -> U21(X1, X2) 8.64/3.08 U21(X1, mark(X2)) -> U21(X1, X2) 8.64/3.08 U22(mark(X)) -> U22(X) 8.64/3.08 U31(mark(X1), X2, X3) -> U31(X1, X2, X3) 8.64/3.08 U31(X1, mark(X2), X3) -> U31(X1, X2, X3) 8.64/3.08 U31(X1, X2, mark(X3)) -> U31(X1, X2, X3) 8.64/3.08 U32(mark(X1), X2) -> U32(X1, X2) 8.64/3.08 U32(X1, mark(X2)) -> U32(X1, X2) 8.64/3.08 U33(mark(X)) -> U33(X) 8.64/3.08 U41(mark(X1), X2) -> U41(X1, X2) 8.64/3.08 U41(X1, mark(X2)) -> U41(X1, X2) 8.64/3.08 U51(mark(X1), X2, X3) -> U51(X1, X2, X3) 8.64/3.08 U51(X1, mark(X2), X3) -> U51(X1, X2, X3) 8.64/3.08 U51(X1, X2, mark(X3)) -> U51(X1, X2, X3) 8.64/3.08 s(mark(X)) -> s(X) 8.64/3.08 plus(mark(X1), X2) -> plus(X1, X2) 8.64/3.08 plus(X1, mark(X2)) -> plus(X1, X2) 8.64/3.08 U61(mark(X)) -> U61(X) 8.64/3.08 U71(mark(X1), X2, X3) -> U71(X1, X2, X3) 8.64/3.08 U71(X1, mark(X2), X3) -> U71(X1, X2, X3) 8.64/3.08 U71(X1, X2, mark(X3)) -> U71(X1, X2, X3) 8.64/3.08 x(mark(X1), X2) -> x(X1, X2) 8.64/3.08 x(X1, mark(X2)) -> x(X1, X2) 8.64/3.08 and(mark(X1), X2) -> and(X1, X2) 8.64/3.08 and(X1, mark(X2)) -> and(X1, X2) 8.64/3.08 isNatKind(mark(X)) -> isNatKind(X) 8.64/3.08 8.64/3.08 The set Q consists of the following terms: 8.64/3.08 8.64/3.08 active(U11(tt, x0, x1)) 8.64/3.08 active(U12(tt, x0)) 8.64/3.08 active(U13(tt)) 8.64/3.08 active(U21(tt, x0)) 8.64/3.08 active(U22(tt)) 8.64/3.08 active(U31(tt, x0, x1)) 8.64/3.08 active(U32(tt, x0)) 8.64/3.08 active(U33(tt)) 8.64/3.08 active(U41(tt, x0)) 8.64/3.08 active(U51(tt, x0, x1)) 8.64/3.08 active(U61(tt)) 8.64/3.08 active(U71(tt, x0, x1)) 8.64/3.08 active(and(tt, x0)) 8.64/3.08 active(isNat(0)) 8.64/3.08 active(isNat(plus(x0, x1))) 8.64/3.08 active(isNat(s(x0))) 8.64/3.08 active(isNat(x(x0, x1))) 8.64/3.08 active(isNatKind(0)) 8.64/3.08 active(isNatKind(plus(x0, x1))) 8.64/3.08 active(isNatKind(s(x0))) 8.64/3.08 active(isNatKind(x(x0, x1))) 8.64/3.08 active(plus(x0, 0)) 8.64/3.08 active(plus(x0, s(x1))) 8.64/3.08 active(x(x0, 0)) 8.64/3.08 active(x(x0, s(x1))) 8.64/3.08 mark(U11(x0, x1, x2)) 8.64/3.08 mark(tt) 8.64/3.08 mark(U12(x0, x1)) 8.64/3.08 mark(isNat(x0)) 8.64/3.08 mark(U13(x0)) 8.64/3.08 mark(U21(x0, x1)) 8.64/3.08 mark(U22(x0)) 8.64/3.08 mark(U31(x0, x1, x2)) 8.64/3.08 mark(U32(x0, x1)) 8.64/3.08 mark(U33(x0)) 8.64/3.08 mark(U41(x0, x1)) 8.64/3.08 mark(U51(x0, x1, x2)) 8.64/3.08 mark(s(x0)) 8.64/3.08 mark(plus(x0, x1)) 8.64/3.08 mark(U61(x0)) 8.64/3.08 mark(0) 8.64/3.08 mark(U71(x0, x1, x2)) 8.64/3.08 mark(x(x0, x1)) 8.64/3.08 mark(and(x0, x1)) 8.64/3.08 mark(isNatKind(x0)) 8.64/3.08 U11(mark(x0), x1, x2) 8.64/3.08 U11(x0, mark(x1), x2) 8.64/3.08 U11(x0, x1, mark(x2)) 8.64/3.08 U11(active(x0), x1, x2) 8.64/3.08 U11(x0, active(x1), x2) 8.64/3.08 U11(x0, x1, active(x2)) 8.64/3.08 U12(mark(x0), x1) 8.64/3.08 U12(x0, mark(x1)) 8.64/3.08 U12(active(x0), x1) 8.64/3.08 U12(x0, active(x1)) 8.64/3.08 isNat(mark(x0)) 8.64/3.08 isNat(active(x0)) 8.64/3.08 U13(mark(x0)) 8.64/3.08 U13(active(x0)) 8.64/3.08 U21(mark(x0), x1) 8.64/3.08 U21(x0, mark(x1)) 8.64/3.08 U21(active(x0), x1) 8.64/3.08 U21(x0, active(x1)) 8.64/3.08 U22(mark(x0)) 8.64/3.08 U22(active(x0)) 8.64/3.08 U31(mark(x0), x1, x2) 8.64/3.08 U31(x0, mark(x1), x2) 8.64/3.08 U31(x0, x1, mark(x2)) 8.64/3.08 U31(active(x0), x1, x2) 8.64/3.08 U31(x0, active(x1), x2) 8.64/3.08 U31(x0, x1, active(x2)) 8.64/3.08 U32(mark(x0), x1) 8.64/3.08 U32(x0, mark(x1)) 8.64/3.08 U32(active(x0), x1) 8.64/3.08 U32(x0, active(x1)) 8.64/3.08 U33(mark(x0)) 8.64/3.08 U33(active(x0)) 8.64/3.08 U41(mark(x0), x1) 8.64/3.08 U41(x0, mark(x1)) 8.64/3.08 U41(active(x0), x1) 8.64/3.08 U41(x0, active(x1)) 8.64/3.08 U51(mark(x0), x1, x2) 8.64/3.08 U51(x0, mark(x1), x2) 8.64/3.08 U51(x0, x1, mark(x2)) 8.64/3.08 U51(active(x0), x1, x2) 8.64/3.08 U51(x0, active(x1), x2) 8.64/3.08 U51(x0, x1, active(x2)) 8.64/3.08 s(mark(x0)) 8.64/3.08 s(active(x0)) 8.64/3.08 plus(mark(x0), x1) 8.64/3.08 plus(x0, mark(x1)) 8.64/3.08 plus(active(x0), x1) 8.64/3.08 plus(x0, active(x1)) 8.64/3.08 U61(mark(x0)) 8.64/3.08 U61(active(x0)) 8.64/3.08 U71(mark(x0), x1, x2) 8.64/3.08 U71(x0, mark(x1), x2) 8.64/3.08 U71(x0, x1, mark(x2)) 8.64/3.08 U71(active(x0), x1, x2) 8.64/3.08 U71(x0, active(x1), x2) 8.64/3.08 U71(x0, x1, active(x2)) 8.64/3.08 x(mark(x0), x1) 8.64/3.08 x(x0, mark(x1)) 8.64/3.08 x(active(x0), x1) 8.64/3.08 x(x0, active(x1)) 8.64/3.08 and(mark(x0), x1) 8.64/3.08 and(x0, mark(x1)) 8.64/3.08 and(active(x0), x1) 8.64/3.08 and(x0, active(x1)) 8.64/3.08 isNatKind(mark(x0)) 8.64/3.08 isNatKind(active(x0)) 8.64/3.08 8.64/3.08 8.64/3.08 ---------------------------------------- 8.64/3.08 8.64/3.08 (5) QTRSRRRProof (EQUIVALENT) 8.64/3.08 Used ordering: 8.64/3.08 Knuth-Bendix order [KBO] with precedence:mark_1 > isNatKind_1 > and_2 > x_2 > U11_3 > U71_3 > U61_1 > plus_2 > s_1 > U51_3 > U41_2 > U33_1 > U32_2 > U31_3 > U22_1 > U21_2 > U13_1 > isNat_1 > U12_2 8.64/3.08 8.64/3.08 and weight map: 8.64/3.08 8.64/3.08 mark_1=0 8.64/3.08 isNat_1=1 8.64/3.08 U13_1=1 8.64/3.08 U22_1=1 8.64/3.08 U33_1=1 8.64/3.08 s_1=1 8.64/3.08 U61_1=1 8.64/3.08 isNatKind_1=1 8.64/3.08 U11_3=0 8.64/3.08 U12_2=0 8.64/3.08 U21_2=0 8.64/3.08 U31_3=0 8.64/3.08 U32_2=0 8.64/3.08 U41_2=0 8.64/3.08 U51_3=0 8.64/3.08 plus_2=0 8.64/3.08 U71_3=0 8.64/3.08 x_2=0 8.64/3.08 and_2=0 8.64/3.08 8.64/3.08 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.64/3.08 8.64/3.08 U11(mark(X1), X2, X3) -> U11(X1, X2, X3) 8.64/3.08 U11(X1, mark(X2), X3) -> U11(X1, X2, X3) 8.64/3.08 U11(X1, X2, mark(X3)) -> U11(X1, X2, X3) 8.64/3.08 U12(mark(X1), X2) -> U12(X1, X2) 8.64/3.08 U12(X1, mark(X2)) -> U12(X1, X2) 8.64/3.08 isNat(mark(X)) -> isNat(X) 8.64/3.08 U13(mark(X)) -> U13(X) 8.64/3.08 U21(mark(X1), X2) -> U21(X1, X2) 8.64/3.08 U21(X1, mark(X2)) -> U21(X1, X2) 8.64/3.08 U22(mark(X)) -> U22(X) 8.64/3.08 U31(mark(X1), X2, X3) -> U31(X1, X2, X3) 8.64/3.08 U31(X1, mark(X2), X3) -> U31(X1, X2, X3) 8.64/3.08 U31(X1, X2, mark(X3)) -> U31(X1, X2, X3) 8.64/3.08 U32(mark(X1), X2) -> U32(X1, X2) 8.64/3.08 U32(X1, mark(X2)) -> U32(X1, X2) 8.64/3.08 U33(mark(X)) -> U33(X) 8.64/3.08 U41(mark(X1), X2) -> U41(X1, X2) 8.64/3.08 U41(X1, mark(X2)) -> U41(X1, X2) 8.64/3.08 U51(mark(X1), X2, X3) -> U51(X1, X2, X3) 8.64/3.08 U51(X1, mark(X2), X3) -> U51(X1, X2, X3) 8.64/3.08 U51(X1, X2, mark(X3)) -> U51(X1, X2, X3) 8.64/3.08 s(mark(X)) -> s(X) 8.64/3.08 plus(mark(X1), X2) -> plus(X1, X2) 8.64/3.08 plus(X1, mark(X2)) -> plus(X1, X2) 8.64/3.08 U61(mark(X)) -> U61(X) 8.64/3.08 U71(mark(X1), X2, X3) -> U71(X1, X2, X3) 8.64/3.08 U71(X1, mark(X2), X3) -> U71(X1, X2, X3) 8.64/3.08 U71(X1, X2, mark(X3)) -> U71(X1, X2, X3) 8.64/3.08 x(mark(X1), X2) -> x(X1, X2) 8.64/3.08 x(X1, mark(X2)) -> x(X1, X2) 8.64/3.08 and(mark(X1), X2) -> and(X1, X2) 8.64/3.08 and(X1, mark(X2)) -> and(X1, X2) 8.64/3.08 isNatKind(mark(X)) -> isNatKind(X) 8.64/3.08 8.64/3.08 8.64/3.08 8.64/3.08 8.64/3.08 ---------------------------------------- 8.64/3.08 8.64/3.08 (6) 8.64/3.08 Obligation: 8.64/3.08 Q restricted rewrite system: 8.64/3.08 R is empty. 8.64/3.08 The set Q consists of the following terms: 8.64/3.08 8.64/3.08 active(U11(tt, x0, x1)) 8.64/3.08 active(U12(tt, x0)) 8.64/3.08 active(U13(tt)) 8.64/3.08 active(U21(tt, x0)) 8.64/3.08 active(U22(tt)) 8.64/3.08 active(U31(tt, x0, x1)) 8.64/3.08 active(U32(tt, x0)) 8.64/3.08 active(U33(tt)) 8.64/3.08 active(U41(tt, x0)) 8.64/3.08 active(U51(tt, x0, x1)) 8.64/3.08 active(U61(tt)) 8.64/3.08 active(U71(tt, x0, x1)) 8.64/3.08 active(and(tt, x0)) 8.64/3.08 active(isNat(0)) 8.64/3.08 active(isNat(plus(x0, x1))) 8.64/3.08 active(isNat(s(x0))) 8.64/3.08 active(isNat(x(x0, x1))) 8.64/3.08 active(isNatKind(0)) 8.64/3.08 active(isNatKind(plus(x0, x1))) 8.64/3.08 active(isNatKind(s(x0))) 8.64/3.08 active(isNatKind(x(x0, x1))) 8.64/3.08 active(plus(x0, 0)) 8.64/3.08 active(plus(x0, s(x1))) 8.64/3.08 active(x(x0, 0)) 8.64/3.08 active(x(x0, s(x1))) 8.64/3.08 mark(U11(x0, x1, x2)) 8.64/3.08 mark(tt) 8.64/3.08 mark(U12(x0, x1)) 8.64/3.08 mark(isNat(x0)) 8.64/3.08 mark(U13(x0)) 8.64/3.08 mark(U21(x0, x1)) 8.64/3.08 mark(U22(x0)) 8.64/3.08 mark(U31(x0, x1, x2)) 8.64/3.08 mark(U32(x0, x1)) 8.64/3.08 mark(U33(x0)) 8.64/3.08 mark(U41(x0, x1)) 8.64/3.08 mark(U51(x0, x1, x2)) 8.64/3.08 mark(s(x0)) 8.64/3.08 mark(plus(x0, x1)) 8.64/3.08 mark(U61(x0)) 8.64/3.08 mark(0) 8.64/3.08 mark(U71(x0, x1, x2)) 8.64/3.08 mark(x(x0, x1)) 8.64/3.08 mark(and(x0, x1)) 8.64/3.08 mark(isNatKind(x0)) 8.64/3.08 U11(mark(x0), x1, x2) 8.64/3.08 U11(x0, mark(x1), x2) 8.64/3.08 U11(x0, x1, mark(x2)) 8.64/3.08 U11(active(x0), x1, x2) 8.64/3.08 U11(x0, active(x1), x2) 8.64/3.08 U11(x0, x1, active(x2)) 8.64/3.08 U12(mark(x0), x1) 8.64/3.08 U12(x0, mark(x1)) 8.64/3.08 U12(active(x0), x1) 8.64/3.08 U12(x0, active(x1)) 8.64/3.08 isNat(mark(x0)) 8.64/3.08 isNat(active(x0)) 8.64/3.08 U13(mark(x0)) 8.64/3.08 U13(active(x0)) 8.64/3.08 U21(mark(x0), x1) 8.64/3.08 U21(x0, mark(x1)) 8.64/3.08 U21(active(x0), x1) 8.64/3.08 U21(x0, active(x1)) 8.64/3.08 U22(mark(x0)) 8.64/3.08 U22(active(x0)) 8.64/3.08 U31(mark(x0), x1, x2) 8.64/3.08 U31(x0, mark(x1), x2) 8.64/3.08 U31(x0, x1, mark(x2)) 8.64/3.08 U31(active(x0), x1, x2) 8.64/3.08 U31(x0, active(x1), x2) 8.64/3.08 U31(x0, x1, active(x2)) 8.64/3.08 U32(mark(x0), x1) 8.64/3.08 U32(x0, mark(x1)) 8.64/3.08 U32(active(x0), x1) 8.64/3.08 U32(x0, active(x1)) 8.64/3.08 U33(mark(x0)) 8.64/3.08 U33(active(x0)) 8.64/3.08 U41(mark(x0), x1) 8.64/3.08 U41(x0, mark(x1)) 8.64/3.08 U41(active(x0), x1) 8.64/3.08 U41(x0, active(x1)) 8.64/3.08 U51(mark(x0), x1, x2) 8.64/3.08 U51(x0, mark(x1), x2) 8.64/3.08 U51(x0, x1, mark(x2)) 8.64/3.08 U51(active(x0), x1, x2) 8.64/3.08 U51(x0, active(x1), x2) 8.64/3.08 U51(x0, x1, active(x2)) 8.64/3.08 s(mark(x0)) 8.64/3.08 s(active(x0)) 8.64/3.08 plus(mark(x0), x1) 8.64/3.08 plus(x0, mark(x1)) 8.64/3.08 plus(active(x0), x1) 8.64/3.08 plus(x0, active(x1)) 8.64/3.08 U61(mark(x0)) 8.64/3.08 U61(active(x0)) 8.64/3.08 U71(mark(x0), x1, x2) 8.64/3.08 U71(x0, mark(x1), x2) 8.64/3.08 U71(x0, x1, mark(x2)) 8.64/3.08 U71(active(x0), x1, x2) 8.64/3.08 U71(x0, active(x1), x2) 8.64/3.08 U71(x0, x1, active(x2)) 8.64/3.08 x(mark(x0), x1) 8.64/3.08 x(x0, mark(x1)) 8.64/3.08 x(active(x0), x1) 8.64/3.08 x(x0, active(x1)) 8.64/3.08 and(mark(x0), x1) 8.64/3.08 and(x0, mark(x1)) 8.64/3.08 and(active(x0), x1) 8.64/3.08 and(x0, active(x1)) 8.64/3.08 isNatKind(mark(x0)) 8.64/3.08 isNatKind(active(x0)) 8.64/3.08 8.64/3.08 8.64/3.08 ---------------------------------------- 8.64/3.08 8.64/3.08 (7) RisEmptyProof (EQUIVALENT) 8.64/3.08 The TRS R is empty. Hence, termination is trivially proven. 8.64/3.08 ---------------------------------------- 8.64/3.08 8.64/3.08 (8) 8.64/3.08 YES 8.86/3.12 EOF