7.10/2.73 YES 7.10/2.74 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 7.10/2.74 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.10/2.74 7.10/2.74 7.10/2.74 Termination w.r.t. Q of the given QTRS could be proven: 7.10/2.74 7.10/2.74 (0) QTRS 7.10/2.74 (1) QTRSRRRProof [EQUIVALENT, 534 ms] 7.10/2.74 (2) QTRS 7.10/2.74 (3) QTRSRRRProof [EQUIVALENT, 73 ms] 7.10/2.74 (4) QTRS 7.10/2.74 (5) QTRSRRRProof [EQUIVALENT, 34 ms] 7.10/2.74 (6) QTRS 7.10/2.74 (7) QTRSRRRProof [EQUIVALENT, 0 ms] 7.10/2.74 (8) QTRS 7.10/2.74 (9) QTRSRRRProof [EQUIVALENT, 1 ms] 7.10/2.74 (10) QTRS 7.10/2.74 (11) RisEmptyProof [EQUIVALENT, 0 ms] 7.10/2.74 (12) YES 7.10/2.74 7.10/2.74 7.10/2.74 ---------------------------------------- 7.10/2.74 7.10/2.74 (0) 7.10/2.74 Obligation: 7.10/2.74 Q restricted rewrite system: 7.10/2.74 The TRS R consists of the following rules: 7.10/2.74 7.10/2.74 a__U11(tt, V1, V2) -> a__U12(a__isNat(V1), V2) 7.10/2.74 a__U12(tt, V2) -> a__U13(a__isNat(V2)) 7.10/2.74 a__U13(tt) -> tt 7.10/2.74 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 7.10/2.74 a__U22(tt) -> tt 7.10/2.74 a__U31(tt, V1, V2) -> a__U32(a__isNat(V1), V2) 7.10/2.74 a__U32(tt, V2) -> a__U33(a__isNat(V2)) 7.10/2.74 a__U33(tt) -> tt 7.10/2.74 a__U41(tt, N) -> mark(N) 7.10/2.74 a__U51(tt, M, N) -> s(a__plus(mark(N), mark(M))) 7.10/2.74 a__U61(tt) -> 0 7.10/2.74 a__U71(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 7.10/2.74 a__and(tt, X) -> mark(X) 7.10/2.74 a__isNat(0) -> tt 7.10/2.74 a__isNat(plus(V1, V2)) -> a__U11(a__and(a__isNatKind(V1), isNatKind(V2)), V1, V2) 7.10/2.74 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 7.10/2.74 a__isNat(x(V1, V2)) -> a__U31(a__and(a__isNatKind(V1), isNatKind(V2)), V1, V2) 7.10/2.74 a__isNatKind(0) -> tt 7.10/2.74 a__isNatKind(plus(V1, V2)) -> a__and(a__isNatKind(V1), isNatKind(V2)) 7.10/2.74 a__isNatKind(s(V1)) -> a__isNatKind(V1) 7.10/2.74 a__isNatKind(x(V1, V2)) -> a__and(a__isNatKind(V1), isNatKind(V2)) 7.10/2.74 a__plus(N, 0) -> a__U41(a__and(a__isNat(N), isNatKind(N)), N) 7.10/2.74 a__plus(N, s(M)) -> a__U51(a__and(a__and(a__isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 7.10/2.74 a__x(N, 0) -> a__U61(a__and(a__isNat(N), isNatKind(N))) 7.10/2.74 a__x(N, s(M)) -> a__U71(a__and(a__and(a__isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 7.10/2.74 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 7.10/2.74 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 7.10/2.74 mark(isNat(X)) -> a__isNat(X) 7.10/2.74 mark(U13(X)) -> a__U13(mark(X)) 7.10/2.74 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 7.10/2.74 mark(U22(X)) -> a__U22(mark(X)) 7.10/2.74 mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) 7.10/2.74 mark(U32(X1, X2)) -> a__U32(mark(X1), X2) 7.10/2.74 mark(U33(X)) -> a__U33(mark(X)) 7.10/2.74 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 7.10/2.74 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 7.10/2.74 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 7.10/2.74 mark(U61(X)) -> a__U61(mark(X)) 7.10/2.74 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 7.10/2.74 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 7.10/2.74 mark(and(X1, X2)) -> a__and(mark(X1), X2) 7.10/2.74 mark(isNatKind(X)) -> a__isNatKind(X) 7.10/2.74 mark(tt) -> tt 7.10/2.74 mark(s(X)) -> s(mark(X)) 7.10/2.74 mark(0) -> 0 7.10/2.74 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 7.10/2.74 a__U12(X1, X2) -> U12(X1, X2) 7.10/2.74 a__isNat(X) -> isNat(X) 7.10/2.74 a__U13(X) -> U13(X) 7.10/2.74 a__U21(X1, X2) -> U21(X1, X2) 7.10/2.74 a__U22(X) -> U22(X) 7.10/2.74 a__U31(X1, X2, X3) -> U31(X1, X2, X3) 7.10/2.74 a__U32(X1, X2) -> U32(X1, X2) 7.10/2.74 a__U33(X) -> U33(X) 7.10/2.74 a__U41(X1, X2) -> U41(X1, X2) 7.10/2.74 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 7.10/2.74 a__plus(X1, X2) -> plus(X1, X2) 7.10/2.74 a__U61(X) -> U61(X) 7.10/2.74 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 7.10/2.74 a__x(X1, X2) -> x(X1, X2) 7.10/2.74 a__and(X1, X2) -> and(X1, X2) 7.10/2.74 a__isNatKind(X) -> isNatKind(X) 7.10/2.74 7.10/2.74 The set Q consists of the following terms: 7.10/2.74 7.10/2.74 mark(U11(x0, x1, x2)) 7.10/2.74 mark(U12(x0, x1)) 7.10/2.74 mark(isNat(x0)) 7.10/2.74 mark(U13(x0)) 7.10/2.74 mark(U21(x0, x1)) 7.10/2.74 mark(U22(x0)) 7.10/2.74 mark(U31(x0, x1, x2)) 7.10/2.74 mark(U32(x0, x1)) 7.10/2.74 mark(U33(x0)) 7.10/2.74 mark(U41(x0, x1)) 7.10/2.74 mark(U51(x0, x1, x2)) 7.10/2.74 mark(plus(x0, x1)) 7.10/2.74 mark(U61(x0)) 7.10/2.74 mark(U71(x0, x1, x2)) 7.10/2.74 mark(x(x0, x1)) 7.10/2.74 mark(and(x0, x1)) 7.10/2.74 mark(isNatKind(x0)) 7.10/2.74 mark(tt) 7.10/2.74 mark(s(x0)) 7.10/2.74 mark(0) 7.10/2.74 a__U11(x0, x1, x2) 7.10/2.74 a__U12(x0, x1) 7.10/2.74 a__isNat(x0) 7.10/2.74 a__U13(x0) 7.10/2.74 a__U21(x0, x1) 7.10/2.74 a__U22(x0) 7.10/2.74 a__U31(x0, x1, x2) 7.10/2.74 a__U32(x0, x1) 7.10/2.74 a__U33(x0) 7.10/2.74 a__U41(x0, x1) 7.10/2.74 a__U51(x0, x1, x2) 7.10/2.74 a__plus(x0, x1) 7.10/2.74 a__U61(x0) 7.10/2.74 a__U71(x0, x1, x2) 7.10/2.74 a__x(x0, x1) 7.10/2.74 a__and(x0, x1) 7.10/2.74 a__isNatKind(x0) 7.10/2.74 7.10/2.74 7.10/2.74 ---------------------------------------- 7.10/2.74 7.10/2.74 (1) QTRSRRRProof (EQUIVALENT) 7.10/2.74 Used ordering: 7.10/2.74 a__U11/3(YES,YES,YES) 7.10/2.74 tt/0) 7.10/2.74 a__U12/2(YES,YES) 7.10/2.74 a__isNat/1)YES( 7.10/2.74 a__U13/1)YES( 7.10/2.74 a__U21/2(YES,YES) 7.10/2.74 a__U22/1(YES) 7.10/2.74 a__U31/3(YES,YES,YES) 7.10/2.74 a__U32/2(YES,YES) 7.10/2.74 a__U33/1)YES( 7.10/2.74 a__U41/2(YES,YES) 7.10/2.74 mark/1)YES( 7.10/2.74 a__U51/3(YES,YES,YES) 7.10/2.74 s/1(YES) 7.10/2.74 a__plus/2(YES,YES) 7.10/2.74 a__U61/1)YES( 7.10/2.74 0/0) 7.10/2.74 a__U71/3(YES,YES,YES) 7.10/2.74 a__x/2(YES,YES) 7.10/2.74 a__and/2(YES,YES) 7.10/2.74 plus/2(YES,YES) 7.10/2.74 a__isNatKind/1)YES( 7.10/2.74 isNatKind/1)YES( 7.10/2.74 x/2(YES,YES) 7.10/2.74 and/2(YES,YES) 7.10/2.74 isNat/1)YES( 7.10/2.74 U11/3(YES,YES,YES) 7.10/2.74 U12/2(YES,YES) 7.10/2.74 U13/1)YES( 7.10/2.74 U21/2(YES,YES) 7.10/2.74 U22/1(YES) 7.10/2.74 U31/3(YES,YES,YES) 7.10/2.74 U32/2(YES,YES) 7.10/2.74 U33/1)YES( 7.10/2.74 U41/2(YES,YES) 7.10/2.74 U51/3(YES,YES,YES) 7.10/2.74 U61/1)YES( 7.10/2.74 U71/3(YES,YES,YES) 7.10/2.74 7.10/2.74 Quasi precedence: 7.10/2.74 [tt, 0] > [a__U22_1, U22_1] 7.10/2.74 [tt, 0] > [a__U32_2, U32_2] 7.10/2.74 [tt, 0] > [a__U41_2, U41_2] 7.10/2.74 [a__U71_3, a__x_2, x_2, U71_3] > [a__U31_3, U31_3] > [a__U32_2, U32_2] 7.10/2.74 [a__U71_3, a__x_2, x_2, U71_3] > [a__U51_3, a__plus_2, plus_2, U51_3] > [a__U11_3, a__U12_2, U11_3, U12_2] 7.10/2.74 [a__U71_3, a__x_2, x_2, U71_3] > [a__U51_3, a__plus_2, plus_2, U51_3] > [a__U41_2, U41_2] 7.10/2.74 [a__U71_3, a__x_2, x_2, U71_3] > [a__U51_3, a__plus_2, plus_2, U51_3] > [s_1, a__and_2, and_2] > [a__U21_2, U21_2] > [a__U22_1, U22_1] 7.10/2.74 7.10/2.74 7.10/2.74 Status: 7.10/2.74 a__U11_3: multiset status 7.10/2.74 tt: multiset status 7.10/2.74 a__U12_2: multiset status 7.10/2.74 a__U21_2: multiset status 7.10/2.74 a__U22_1: multiset status 7.10/2.74 a__U31_3: multiset status 7.10/2.74 a__U32_2: multiset status 7.10/2.74 a__U41_2: multiset status 7.10/2.74 a__U51_3: [3,2,1] 7.10/2.74 s_1: multiset status 7.10/2.74 a__plus_2: [1,2] 7.10/2.74 0: multiset status 7.10/2.74 a__U71_3: [2,3,1] 7.10/2.74 a__x_2: [2,1] 7.10/2.74 a__and_2: multiset status 7.10/2.74 plus_2: [1,2] 7.10/2.74 x_2: [2,1] 7.10/2.74 and_2: multiset status 7.10/2.74 U11_3: multiset status 7.10/2.74 U12_2: multiset status 7.10/2.74 U21_2: multiset status 7.10/2.74 U22_1: multiset status 7.10/2.74 U31_3: multiset status 7.10/2.74 U32_2: multiset status 7.10/2.74 U41_2: multiset status 7.10/2.74 U51_3: [3,2,1] 7.10/2.74 U71_3: [2,3,1] 7.10/2.74 7.10/2.74 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.10/2.74 7.10/2.74 a__U11(tt, V1, V2) -> a__U12(a__isNat(V1), V2) 7.10/2.74 a__U12(tt, V2) -> a__U13(a__isNat(V2)) 7.10/2.74 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 7.10/2.74 a__U22(tt) -> tt 7.10/2.74 a__U31(tt, V1, V2) -> a__U32(a__isNat(V1), V2) 7.10/2.74 a__U32(tt, V2) -> a__U33(a__isNat(V2)) 7.10/2.74 a__U41(tt, N) -> mark(N) 7.10/2.74 a__U51(tt, M, N) -> s(a__plus(mark(N), mark(M))) 7.10/2.74 a__U71(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 7.10/2.74 a__and(tt, X) -> mark(X) 7.10/2.74 a__isNat(plus(V1, V2)) -> a__U11(a__and(a__isNatKind(V1), isNatKind(V2)), V1, V2) 7.10/2.74 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 7.10/2.74 a__isNat(x(V1, V2)) -> a__U31(a__and(a__isNatKind(V1), isNatKind(V2)), V1, V2) 7.10/2.74 a__isNatKind(plus(V1, V2)) -> a__and(a__isNatKind(V1), isNatKind(V2)) 7.10/2.74 a__isNatKind(s(V1)) -> a__isNatKind(V1) 7.10/2.74 a__isNatKind(x(V1, V2)) -> a__and(a__isNatKind(V1), isNatKind(V2)) 7.10/2.74 a__plus(N, 0) -> a__U41(a__and(a__isNat(N), isNatKind(N)), N) 7.10/2.74 a__plus(N, s(M)) -> a__U51(a__and(a__and(a__isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 7.10/2.74 a__x(N, 0) -> a__U61(a__and(a__isNat(N), isNatKind(N))) 7.10/2.74 a__x(N, s(M)) -> a__U71(a__and(a__and(a__isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 7.10/2.74 7.10/2.74 7.10/2.74 7.10/2.74 7.10/2.74 ---------------------------------------- 7.10/2.74 7.10/2.74 (2) 7.10/2.74 Obligation: 7.10/2.74 Q restricted rewrite system: 7.10/2.74 The TRS R consists of the following rules: 7.10/2.75 7.10/2.75 a__U13(tt) -> tt 7.10/2.75 a__U33(tt) -> tt 7.10/2.75 a__U61(tt) -> 0 7.10/2.75 a__isNat(0) -> tt 7.10/2.75 a__isNatKind(0) -> tt 7.10/2.75 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 7.10/2.75 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 7.10/2.75 mark(isNat(X)) -> a__isNat(X) 7.10/2.75 mark(U13(X)) -> a__U13(mark(X)) 7.10/2.75 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 7.10/2.75 mark(U22(X)) -> a__U22(mark(X)) 7.10/2.75 mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) 7.10/2.75 mark(U32(X1, X2)) -> a__U32(mark(X1), X2) 7.10/2.75 mark(U33(X)) -> a__U33(mark(X)) 7.10/2.75 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 7.10/2.75 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 7.10/2.75 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 7.10/2.75 mark(U61(X)) -> a__U61(mark(X)) 7.10/2.75 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 7.10/2.75 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 7.10/2.75 mark(and(X1, X2)) -> a__and(mark(X1), X2) 7.10/2.75 mark(isNatKind(X)) -> a__isNatKind(X) 7.10/2.75 mark(tt) -> tt 7.10/2.75 mark(s(X)) -> s(mark(X)) 7.10/2.75 mark(0) -> 0 7.10/2.75 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 7.10/2.75 a__U12(X1, X2) -> U12(X1, X2) 7.10/2.75 a__isNat(X) -> isNat(X) 7.10/2.75 a__U13(X) -> U13(X) 7.10/2.75 a__U21(X1, X2) -> U21(X1, X2) 7.10/2.75 a__U22(X) -> U22(X) 7.10/2.75 a__U31(X1, X2, X3) -> U31(X1, X2, X3) 7.10/2.75 a__U32(X1, X2) -> U32(X1, X2) 7.10/2.75 a__U33(X) -> U33(X) 7.10/2.75 a__U41(X1, X2) -> U41(X1, X2) 7.10/2.75 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 7.10/2.75 a__plus(X1, X2) -> plus(X1, X2) 7.10/2.75 a__U61(X) -> U61(X) 7.10/2.75 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 7.10/2.75 a__x(X1, X2) -> x(X1, X2) 7.10/2.75 a__and(X1, X2) -> and(X1, X2) 7.10/2.75 a__isNatKind(X) -> isNatKind(X) 7.10/2.75 7.10/2.75 The set Q consists of the following terms: 7.10/2.75 7.10/2.75 mark(U11(x0, x1, x2)) 7.10/2.75 mark(U12(x0, x1)) 7.10/2.75 mark(isNat(x0)) 7.10/2.75 mark(U13(x0)) 7.10/2.75 mark(U21(x0, x1)) 7.10/2.75 mark(U22(x0)) 7.10/2.75 mark(U31(x0, x1, x2)) 7.10/2.75 mark(U32(x0, x1)) 7.10/2.75 mark(U33(x0)) 7.10/2.75 mark(U41(x0, x1)) 7.10/2.75 mark(U51(x0, x1, x2)) 7.10/2.75 mark(plus(x0, x1)) 7.10/2.75 mark(U61(x0)) 7.10/2.75 mark(U71(x0, x1, x2)) 7.10/2.75 mark(x(x0, x1)) 7.10/2.75 mark(and(x0, x1)) 7.10/2.75 mark(isNatKind(x0)) 7.10/2.75 mark(tt) 7.10/2.75 mark(s(x0)) 7.10/2.75 mark(0) 7.10/2.75 a__U11(x0, x1, x2) 7.10/2.75 a__U12(x0, x1) 7.10/2.75 a__isNat(x0) 7.10/2.75 a__U13(x0) 7.10/2.75 a__U21(x0, x1) 7.10/2.75 a__U22(x0) 7.10/2.75 a__U31(x0, x1, x2) 7.10/2.75 a__U32(x0, x1) 7.10/2.75 a__U33(x0) 7.10/2.75 a__U41(x0, x1) 7.10/2.75 a__U51(x0, x1, x2) 7.10/2.75 a__plus(x0, x1) 7.10/2.75 a__U61(x0) 7.10/2.75 a__U71(x0, x1, x2) 7.10/2.75 a__x(x0, x1) 7.10/2.75 a__and(x0, x1) 7.10/2.75 a__isNatKind(x0) 7.10/2.75 7.10/2.75 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (3) QTRSRRRProof (EQUIVALENT) 7.10/2.75 Used ordering: 7.10/2.75 Polynomial interpretation [POLO]: 7.10/2.75 7.10/2.75 POL(0) = 1 7.10/2.75 POL(U11(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(U12(x_1, x_2)) = 1 + x_1 + x_2 7.10/2.75 POL(U13(x_1)) = 1 + 2*x_1 7.10/2.75 POL(U21(x_1, x_2)) = 1 + x_1 + 2*x_2 7.10/2.75 POL(U22(x_1)) = 1 + x_1 7.10/2.75 POL(U31(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(U32(x_1, x_2)) = 1 + x_1 + 2*x_2 7.10/2.75 POL(U33(x_1)) = 1 + 2*x_1 7.10/2.75 POL(U41(x_1, x_2)) = 1 + x_1 + 2*x_2 7.10/2.75 POL(U51(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 7.10/2.75 POL(U61(x_1)) = 1 + 2*x_1 7.10/2.75 POL(U71(x_1, x_2, x_3)) = 1 + x_1 + x_2 + 2*x_3 7.10/2.75 POL(a__U11(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(a__U12(x_1, x_2)) = 2 + x_1 + 2*x_2 7.10/2.75 POL(a__U13(x_1)) = 2 + 2*x_1 7.10/2.75 POL(a__U21(x_1, x_2)) = 2 + x_1 + 2*x_2 7.10/2.75 POL(a__U22(x_1)) = 2 + x_1 7.10/2.75 POL(a__U31(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(a__U32(x_1, x_2)) = 2 + x_1 + 2*x_2 7.10/2.75 POL(a__U33(x_1)) = 2 + 2*x_1 7.10/2.75 POL(a__U41(x_1, x_2)) = 2 + x_1 + 2*x_2 7.10/2.75 POL(a__U51(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(a__U61(x_1)) = 2 + 2*x_1 7.10/2.75 POL(a__U71(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(a__and(x_1, x_2)) = 2 + x_1 + 2*x_2 7.10/2.75 POL(a__isNat(x_1)) = 2 + 2*x_1 7.10/2.75 POL(a__isNatKind(x_1)) = 2 + 2*x_1 7.10/2.75 POL(a__plus(x_1, x_2)) = 2 + x_1 + x_2 7.10/2.75 POL(a__x(x_1, x_2)) = 2 + x_1 + x_2 7.10/2.75 POL(and(x_1, x_2)) = 1 + x_1 + 2*x_2 7.10/2.75 POL(isNat(x_1)) = 1 + 2*x_1 7.10/2.75 POL(isNatKind(x_1)) = 1 + 2*x_1 7.10/2.75 POL(mark(x_1)) = 2*x_1 7.10/2.75 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 7.10/2.75 POL(s(x_1)) = 1 + x_1 7.10/2.75 POL(tt) = 1 7.10/2.75 POL(x(x_1, x_2)) = 1 + x_1 + x_2 7.10/2.75 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.10/2.75 7.10/2.75 a__U13(tt) -> tt 7.10/2.75 a__U33(tt) -> tt 7.10/2.75 a__U61(tt) -> 0 7.10/2.75 a__isNat(0) -> tt 7.10/2.75 a__isNatKind(0) -> tt 7.10/2.75 mark(tt) -> tt 7.10/2.75 mark(s(X)) -> s(mark(X)) 7.10/2.75 mark(0) -> 0 7.10/2.75 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 7.10/2.75 a__U12(X1, X2) -> U12(X1, X2) 7.10/2.75 a__isNat(X) -> isNat(X) 7.10/2.75 a__U13(X) -> U13(X) 7.10/2.75 a__U21(X1, X2) -> U21(X1, X2) 7.10/2.75 a__U22(X) -> U22(X) 7.10/2.75 a__U31(X1, X2, X3) -> U31(X1, X2, X3) 7.10/2.75 a__U32(X1, X2) -> U32(X1, X2) 7.10/2.75 a__U33(X) -> U33(X) 7.10/2.75 a__U41(X1, X2) -> U41(X1, X2) 7.10/2.75 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 7.10/2.75 a__plus(X1, X2) -> plus(X1, X2) 7.10/2.75 a__U61(X) -> U61(X) 7.10/2.75 a__U71(X1, X2, X3) -> U71(X1, X2, X3) 7.10/2.75 a__x(X1, X2) -> x(X1, X2) 7.10/2.75 a__and(X1, X2) -> and(X1, X2) 7.10/2.75 a__isNatKind(X) -> isNatKind(X) 7.10/2.75 7.10/2.75 7.10/2.75 7.10/2.75 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (4) 7.10/2.75 Obligation: 7.10/2.75 Q restricted rewrite system: 7.10/2.75 The TRS R consists of the following rules: 7.10/2.75 7.10/2.75 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 7.10/2.75 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 7.10/2.75 mark(isNat(X)) -> a__isNat(X) 7.10/2.75 mark(U13(X)) -> a__U13(mark(X)) 7.10/2.75 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 7.10/2.75 mark(U22(X)) -> a__U22(mark(X)) 7.10/2.75 mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) 7.10/2.75 mark(U32(X1, X2)) -> a__U32(mark(X1), X2) 7.10/2.75 mark(U33(X)) -> a__U33(mark(X)) 7.10/2.75 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 7.10/2.75 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 7.10/2.75 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 7.10/2.75 mark(U61(X)) -> a__U61(mark(X)) 7.10/2.75 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 7.10/2.75 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 7.10/2.75 mark(and(X1, X2)) -> a__and(mark(X1), X2) 7.10/2.75 mark(isNatKind(X)) -> a__isNatKind(X) 7.10/2.75 7.10/2.75 The set Q consists of the following terms: 7.10/2.75 7.10/2.75 mark(U11(x0, x1, x2)) 7.10/2.75 mark(U12(x0, x1)) 7.10/2.75 mark(isNat(x0)) 7.10/2.75 mark(U13(x0)) 7.10/2.75 mark(U21(x0, x1)) 7.10/2.75 mark(U22(x0)) 7.10/2.75 mark(U31(x0, x1, x2)) 7.10/2.75 mark(U32(x0, x1)) 7.10/2.75 mark(U33(x0)) 7.10/2.75 mark(U41(x0, x1)) 7.10/2.75 mark(U51(x0, x1, x2)) 7.10/2.75 mark(plus(x0, x1)) 7.10/2.75 mark(U61(x0)) 7.10/2.75 mark(U71(x0, x1, x2)) 7.10/2.75 mark(x(x0, x1)) 7.10/2.75 mark(and(x0, x1)) 7.10/2.75 mark(isNatKind(x0)) 7.10/2.75 mark(tt) 7.10/2.75 mark(s(x0)) 7.10/2.75 mark(0) 7.10/2.75 a__U11(x0, x1, x2) 7.10/2.75 a__U12(x0, x1) 7.10/2.75 a__isNat(x0) 7.10/2.75 a__U13(x0) 7.10/2.75 a__U21(x0, x1) 7.10/2.75 a__U22(x0) 7.10/2.75 a__U31(x0, x1, x2) 7.10/2.75 a__U32(x0, x1) 7.10/2.75 a__U33(x0) 7.10/2.75 a__U41(x0, x1) 7.10/2.75 a__U51(x0, x1, x2) 7.10/2.75 a__plus(x0, x1) 7.10/2.75 a__U61(x0) 7.10/2.75 a__U71(x0, x1, x2) 7.10/2.75 a__x(x0, x1) 7.10/2.75 a__and(x0, x1) 7.10/2.75 a__isNatKind(x0) 7.10/2.75 7.10/2.75 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (5) QTRSRRRProof (EQUIVALENT) 7.10/2.75 Used ordering: 7.10/2.75 Polynomial interpretation [POLO]: 7.10/2.75 7.10/2.75 POL(U11(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + x_3 7.10/2.75 POL(U12(x_1, x_2)) = 2*x_1 + 2*x_2 7.10/2.75 POL(U13(x_1)) = 2 + 2*x_1 7.10/2.75 POL(U21(x_1, x_2)) = 2 + 2*x_1 + x_2 7.10/2.75 POL(U22(x_1)) = 1 + 2*x_1 7.10/2.75 POL(U31(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(U32(x_1, x_2)) = 2*x_1 + 2*x_2 7.10/2.75 POL(U33(x_1)) = 2*x_1 7.10/2.75 POL(U41(x_1, x_2)) = 2*x_1 + x_2 7.10/2.75 POL(U51(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(U61(x_1)) = 2*x_1 7.10/2.75 POL(U71(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 7.10/2.75 POL(a__U11(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 7.10/2.75 POL(a__U13(x_1)) = 2 + 2*x_1 7.10/2.75 POL(a__U21(x_1, x_2)) = 2*x_1 + 2*x_2 7.10/2.75 POL(a__U22(x_1)) = 1 + 2*x_1 7.10/2.75 POL(a__U31(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(a__U32(x_1, x_2)) = x_1 + 2*x_2 7.10/2.75 POL(a__U33(x_1)) = x_1 7.10/2.75 POL(a__U41(x_1, x_2)) = x_1 + 2*x_2 7.10/2.75 POL(a__U51(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(a__U61(x_1)) = x_1 7.10/2.75 POL(a__U71(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(a__and(x_1, x_2)) = 2*x_1 + 2*x_2 7.10/2.75 POL(a__isNat(x_1)) = 1 + 2*x_1 7.10/2.75 POL(a__isNatKind(x_1)) = 1 + 2*x_1 7.10/2.75 POL(a__plus(x_1, x_2)) = x_1 + 2*x_2 7.10/2.75 POL(a__x(x_1, x_2)) = x_1 + x_2 7.10/2.75 POL(and(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 7.10/2.75 POL(isNat(x_1)) = x_1 7.10/2.75 POL(isNatKind(x_1)) = x_1 7.10/2.75 POL(mark(x_1)) = 1 + 2*x_1 7.10/2.75 POL(plus(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 7.10/2.75 POL(x(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 7.10/2.75 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.10/2.75 7.10/2.75 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 7.10/2.75 mark(U13(X)) -> a__U13(mark(X)) 7.10/2.75 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 7.10/2.75 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 7.10/2.75 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 7.10/2.75 mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) 7.10/2.75 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 7.10/2.75 mark(and(X1, X2)) -> a__and(mark(X1), X2) 7.10/2.75 7.10/2.75 7.10/2.75 7.10/2.75 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (6) 7.10/2.75 Obligation: 7.10/2.75 Q restricted rewrite system: 7.10/2.75 The TRS R consists of the following rules: 7.10/2.75 7.10/2.75 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 7.10/2.75 mark(isNat(X)) -> a__isNat(X) 7.10/2.75 mark(U22(X)) -> a__U22(mark(X)) 7.10/2.75 mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) 7.10/2.75 mark(U32(X1, X2)) -> a__U32(mark(X1), X2) 7.10/2.75 mark(U33(X)) -> a__U33(mark(X)) 7.10/2.75 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 7.10/2.75 mark(U61(X)) -> a__U61(mark(X)) 7.10/2.75 mark(isNatKind(X)) -> a__isNatKind(X) 7.10/2.75 7.10/2.75 The set Q consists of the following terms: 7.10/2.75 7.10/2.75 mark(U11(x0, x1, x2)) 7.10/2.75 mark(U12(x0, x1)) 7.10/2.75 mark(isNat(x0)) 7.10/2.75 mark(U13(x0)) 7.10/2.75 mark(U21(x0, x1)) 7.10/2.75 mark(U22(x0)) 7.10/2.75 mark(U31(x0, x1, x2)) 7.10/2.75 mark(U32(x0, x1)) 7.10/2.75 mark(U33(x0)) 7.10/2.75 mark(U41(x0, x1)) 7.10/2.75 mark(U51(x0, x1, x2)) 7.10/2.75 mark(plus(x0, x1)) 7.10/2.75 mark(U61(x0)) 7.10/2.75 mark(U71(x0, x1, x2)) 7.10/2.75 mark(x(x0, x1)) 7.10/2.75 mark(and(x0, x1)) 7.10/2.75 mark(isNatKind(x0)) 7.10/2.75 mark(tt) 7.10/2.75 mark(s(x0)) 7.10/2.75 mark(0) 7.10/2.75 a__U11(x0, x1, x2) 7.10/2.75 a__U12(x0, x1) 7.10/2.75 a__isNat(x0) 7.10/2.75 a__U13(x0) 7.10/2.75 a__U21(x0, x1) 7.10/2.75 a__U22(x0) 7.10/2.75 a__U31(x0, x1, x2) 7.10/2.75 a__U32(x0, x1) 7.10/2.75 a__U33(x0) 7.10/2.75 a__U41(x0, x1) 7.10/2.75 a__U51(x0, x1, x2) 7.10/2.75 a__plus(x0, x1) 7.10/2.75 a__U61(x0) 7.10/2.75 a__U71(x0, x1, x2) 7.10/2.75 a__x(x0, x1) 7.10/2.75 a__and(x0, x1) 7.10/2.75 a__isNatKind(x0) 7.10/2.75 7.10/2.75 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (7) QTRSRRRProof (EQUIVALENT) 7.10/2.75 Used ordering: 7.10/2.75 Polynomial interpretation [POLO]: 7.10/2.75 7.10/2.75 POL(U12(x_1, x_2)) = 2 + 2*x_1 + x_2 7.10/2.75 POL(U22(x_1)) = 2 + 2*x_1 7.10/2.75 POL(U31(x_1, x_2, x_3)) = 2 + 2*x_1 + x_2 + 2*x_3 7.10/2.75 POL(U32(x_1, x_2)) = 1 + 2*x_1 + x_2 7.10/2.75 POL(U33(x_1)) = 2 + 2*x_1 7.10/2.75 POL(U41(x_1, x_2)) = 2 + 2*x_1 + x_2 7.10/2.75 POL(U61(x_1)) = 2 + 2*x_1 7.10/2.75 POL(a__U12(x_1, x_2)) = 2*x_1 + 2*x_2 7.10/2.75 POL(a__U22(x_1)) = 2*x_1 7.10/2.75 POL(a__U31(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 7.10/2.75 POL(a__U32(x_1, x_2)) = x_1 + 2*x_2 7.10/2.75 POL(a__U33(x_1)) = 1 + x_1 7.10/2.75 POL(a__U41(x_1, x_2)) = 2*x_1 + 2*x_2 7.10/2.75 POL(a__U61(x_1)) = 2*x_1 7.10/2.75 POL(a__isNat(x_1)) = 1 + 2*x_1 7.10/2.75 POL(a__isNatKind(x_1)) = 1 + 2*x_1 7.10/2.75 POL(isNat(x_1)) = 2*x_1 7.10/2.75 POL(isNatKind(x_1)) = x_1 7.10/2.75 POL(mark(x_1)) = 1 + 2*x_1 7.10/2.75 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.10/2.75 7.10/2.75 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 7.10/2.75 mark(U22(X)) -> a__U22(mark(X)) 7.10/2.75 mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) 7.10/2.75 mark(U32(X1, X2)) -> a__U32(mark(X1), X2) 7.10/2.75 mark(U33(X)) -> a__U33(mark(X)) 7.10/2.75 mark(U41(X1, X2)) -> a__U41(mark(X1), X2) 7.10/2.75 mark(U61(X)) -> a__U61(mark(X)) 7.10/2.75 7.10/2.75 7.10/2.75 7.10/2.75 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (8) 7.10/2.75 Obligation: 7.10/2.75 Q restricted rewrite system: 7.10/2.75 The TRS R consists of the following rules: 7.10/2.75 7.10/2.75 mark(isNat(X)) -> a__isNat(X) 7.10/2.75 mark(isNatKind(X)) -> a__isNatKind(X) 7.10/2.75 7.10/2.75 The set Q consists of the following terms: 7.10/2.75 7.10/2.75 mark(U11(x0, x1, x2)) 7.10/2.75 mark(U12(x0, x1)) 7.10/2.75 mark(isNat(x0)) 7.10/2.75 mark(U13(x0)) 7.10/2.75 mark(U21(x0, x1)) 7.10/2.75 mark(U22(x0)) 7.10/2.75 mark(U31(x0, x1, x2)) 7.10/2.75 mark(U32(x0, x1)) 7.10/2.75 mark(U33(x0)) 7.10/2.75 mark(U41(x0, x1)) 7.10/2.75 mark(U51(x0, x1, x2)) 7.10/2.75 mark(plus(x0, x1)) 7.10/2.75 mark(U61(x0)) 7.10/2.75 mark(U71(x0, x1, x2)) 7.10/2.75 mark(x(x0, x1)) 7.10/2.75 mark(and(x0, x1)) 7.10/2.75 mark(isNatKind(x0)) 7.10/2.75 mark(tt) 7.10/2.75 mark(s(x0)) 7.10/2.75 mark(0) 7.10/2.75 a__U11(x0, x1, x2) 7.10/2.75 a__U12(x0, x1) 7.10/2.75 a__isNat(x0) 7.10/2.75 a__U13(x0) 7.10/2.75 a__U21(x0, x1) 7.10/2.75 a__U22(x0) 7.10/2.75 a__U31(x0, x1, x2) 7.10/2.75 a__U32(x0, x1) 7.10/2.75 a__U33(x0) 7.10/2.75 a__U41(x0, x1) 7.10/2.75 a__U51(x0, x1, x2) 7.10/2.75 a__plus(x0, x1) 7.10/2.75 a__U61(x0) 7.10/2.75 a__U71(x0, x1, x2) 7.10/2.75 a__x(x0, x1) 7.10/2.75 a__and(x0, x1) 7.10/2.75 a__isNatKind(x0) 7.10/2.75 7.10/2.75 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (9) QTRSRRRProof (EQUIVALENT) 7.10/2.75 Used ordering: 7.10/2.75 Knuth-Bendix order [KBO] with precedence:a__isNatKind_1 > isNatKind_1 > isNat_1 > mark_1 > a__isNat_1 7.10/2.75 7.10/2.75 and weight map: 7.10/2.75 7.10/2.75 mark_1=1 7.10/2.75 isNat_1=1 7.10/2.75 a__isNat_1=2 7.10/2.75 isNatKind_1=1 7.10/2.75 a__isNatKind_1=1 7.10/2.75 7.10/2.75 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.10/2.75 7.10/2.75 mark(isNat(X)) -> a__isNat(X) 7.10/2.75 mark(isNatKind(X)) -> a__isNatKind(X) 7.10/2.75 7.10/2.75 7.10/2.75 7.10/2.75 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (10) 7.10/2.75 Obligation: 7.10/2.75 Q restricted rewrite system: 7.10/2.75 R is empty. 7.10/2.75 The set Q consists of the following terms: 7.10/2.75 7.10/2.75 mark(U11(x0, x1, x2)) 7.10/2.75 mark(U12(x0, x1)) 7.10/2.75 mark(isNat(x0)) 7.10/2.75 mark(U13(x0)) 7.10/2.75 mark(U21(x0, x1)) 7.10/2.75 mark(U22(x0)) 7.10/2.75 mark(U31(x0, x1, x2)) 7.10/2.75 mark(U32(x0, x1)) 7.10/2.75 mark(U33(x0)) 7.10/2.75 mark(U41(x0, x1)) 7.10/2.75 mark(U51(x0, x1, x2)) 7.10/2.75 mark(plus(x0, x1)) 7.10/2.75 mark(U61(x0)) 7.10/2.75 mark(U71(x0, x1, x2)) 7.10/2.75 mark(x(x0, x1)) 7.10/2.75 mark(and(x0, x1)) 7.10/2.75 mark(isNatKind(x0)) 7.10/2.75 mark(tt) 7.10/2.75 mark(s(x0)) 7.10/2.75 mark(0) 7.10/2.75 a__U11(x0, x1, x2) 7.10/2.75 a__U12(x0, x1) 7.10/2.75 a__isNat(x0) 7.10/2.75 a__U13(x0) 7.10/2.75 a__U21(x0, x1) 7.10/2.75 a__U22(x0) 7.10/2.75 a__U31(x0, x1, x2) 7.10/2.75 a__U32(x0, x1) 7.10/2.75 a__U33(x0) 7.10/2.75 a__U41(x0, x1) 7.10/2.75 a__U51(x0, x1, x2) 7.10/2.75 a__plus(x0, x1) 7.10/2.75 a__U61(x0) 7.10/2.75 a__U71(x0, x1, x2) 7.10/2.75 a__x(x0, x1) 7.10/2.75 a__and(x0, x1) 7.10/2.75 a__isNatKind(x0) 7.10/2.75 7.10/2.75 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (11) RisEmptyProof (EQUIVALENT) 7.10/2.75 The TRS R is empty. Hence, termination is trivially proven. 7.10/2.75 ---------------------------------------- 7.10/2.75 7.10/2.75 (12) 7.10/2.75 YES 7.27/2.83 EOF