/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 170 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 75 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 32 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 14 ms] (8) QTRS (9) QTRSRRRProof [EQUIVALENT, 52 ms] (10) QTRS (11) QTRSRRRProof [EQUIVALENT, 57 ms] (12) QTRS (13) QTRSRRRProof [EQUIVALENT, 31 ms] (14) QTRS (15) QTRSRRRProof [EQUIVALENT, 0 ms] (16) QTRS (17) QTRSRRRProof [EQUIVALENT, 7 ms] (18) QTRS (19) QTRSRRRProof [EQUIVALENT, 11 ms] (20) QTRS (21) QTRSRRRProof [EQUIVALENT, 12 ms] (22) QTRS (23) QTRSRRRProof [EQUIVALENT, 0 ms] (24) QTRS (25) RisEmptyProof [EQUIVALENT, 0 ms] (26) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U11(tt) -> tt a__U21(tt) -> tt a__U31(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) a__U42(tt) -> tt a__U51(tt, V2) -> a__U52(a__isNatList(V2)) a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(0) -> tt a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNatIList(V) -> a__U31(a__isNatList(V)) a__isNatIList(zeros) -> tt a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) a__isNatList(nil) -> tt a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) a__length(nil) -> 0 a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(isNatIList(X)) -> a__isNatIList(X) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(isNatList(X)) -> a__isNatList(X) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0) -> 0 mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(nil) -> nil a__zeros -> zeros a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__isNatIList(X) -> isNatIList(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__isNat(X) -> isNat(X) a__length(X) -> length(X) Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = x_1 POL(U41(x_1, x_2)) = x_1 + 2*x_2 POL(U42(x_1)) = 2*x_1 POL(U51(x_1, x_2)) = x_1 + 2*x_2 POL(U52(x_1)) = 2*x_1 POL(U61(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U62(x_1, x_2)) = x_1 + x_2 POL(a__U11(x_1)) = x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = x_1 POL(a__U41(x_1, x_2)) = x_1 + 2*x_2 POL(a__U42(x_1)) = 2*x_1 POL(a__U51(x_1, x_2)) = x_1 + 2*x_2 POL(a__U52(x_1)) = 2*x_1 POL(a__U61(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(a__U62(x_1, x_2)) = x_1 + x_2 POL(a__isNat(x_1)) = x_1 POL(a__isNatIList(x_1)) = x_1 POL(a__isNatList(x_1)) = x_1 POL(a__length(x_1)) = x_1 POL(a__zeros) = 0 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(isNat(x_1)) = x_1 POL(isNatIList(x_1)) = x_1 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nil) = 1 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__isNatList(nil) -> tt a__length(nil) -> 0 ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U11(tt) -> tt a__U21(tt) -> tt a__U31(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) a__U42(tt) -> tt a__U51(tt, V2) -> a__U52(a__isNatList(V2)) a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(0) -> tt a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNatIList(V) -> a__U31(a__isNatList(V)) a__isNatIList(zeros) -> tt a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(isNatIList(X)) -> a__isNatIList(X) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(isNatList(X)) -> a__isNatList(X) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0) -> 0 mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(nil) -> nil a__zeros -> zeros a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__isNatIList(X) -> isNatIList(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__isNat(X) -> isNat(X) a__length(X) -> length(X) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = 2*x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = x_1 POL(U41(x_1, x_2)) = x_1 + 2*x_2 POL(U42(x_1)) = 2*x_1 POL(U51(x_1, x_2)) = x_1 + 2*x_2 POL(U52(x_1)) = 2*x_1 POL(U61(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(a__U11(x_1)) = 2*x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = x_1 POL(a__U41(x_1, x_2)) = x_1 + 2*x_2 POL(a__U42(x_1)) = 2*x_1 POL(a__U51(x_1, x_2)) = x_1 + 2*x_2 POL(a__U52(x_1)) = 2*x_1 POL(a__U61(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 POL(a__U62(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(a__isNat(x_1)) = 2*x_1 POL(a__isNatIList(x_1)) = x_1 POL(a__isNatList(x_1)) = x_1 POL(a__length(x_1)) = 1 + 2*x_1 POL(a__zeros) = 0 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(isNat(x_1)) = 2*x_1 POL(isNatIList(x_1)) = x_1 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = 1 + 2*x_1 POL(mark(x_1)) = x_1 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__isNat(length(V1)) -> a__U11(a__isNatList(V1)) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U11(tt) -> tt a__U21(tt) -> tt a__U31(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) a__U42(tt) -> tt a__U51(tt, V2) -> a__U52(a__isNatList(V2)) a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(0) -> tt a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNatIList(V) -> a__U31(a__isNatList(V)) a__isNatIList(zeros) -> tt a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(isNatIList(X)) -> a__isNatIList(X) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(isNatList(X)) -> a__isNatList(X) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0) -> 0 mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(nil) -> nil a__zeros -> zeros a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__isNatIList(X) -> isNatIList(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__isNat(X) -> isNat(X) a__length(X) -> length(X) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = 2*x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = 1 + x_1 POL(U41(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(U42(x_1)) = x_1 POL(U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U52(x_1)) = 2*x_1 POL(U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U11(x_1)) = 2*x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = 1 + x_1 POL(a__U41(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(a__U42(x_1)) = x_1 POL(a__U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U52(x_1)) = 2*x_1 POL(a__U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(a__U62(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__isNat(x_1)) = x_1 POL(a__isNatIList(x_1)) = 1 + x_1 POL(a__isNatList(x_1)) = x_1 POL(a__length(x_1)) = 2*x_1 POL(a__zeros) = 0 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(isNat(x_1)) = x_1 POL(isNatIList(x_1)) = 1 + x_1 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = 2*x_1 POL(mark(x_1)) = x_1 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__U31(tt) -> tt a__isNatIList(zeros) -> tt ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U11(tt) -> tt a__U21(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) a__U42(tt) -> tt a__U51(tt, V2) -> a__U52(a__isNatList(V2)) a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(0) -> tt a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNatIList(V) -> a__U31(a__isNatList(V)) a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(isNatIList(X)) -> a__isNatIList(X) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(isNatList(X)) -> a__isNatList(X) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0) -> 0 mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(nil) -> nil a__zeros -> zeros a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__isNatIList(X) -> isNatIList(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__isNat(X) -> isNat(X) a__length(X) -> length(X) Q is empty. ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = 1 + x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = x_1 POL(U41(x_1, x_2)) = x_1 + 2*x_2 POL(U42(x_1)) = 2*x_1 POL(U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U52(x_1)) = x_1 POL(U61(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2)) = x_1 + 2*x_2 POL(a__U11(x_1)) = 1 + x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = x_1 POL(a__U41(x_1, x_2)) = x_1 + 2*x_2 POL(a__U42(x_1)) = 2*x_1 POL(a__U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U52(x_1)) = x_1 POL(a__U61(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 POL(a__U62(x_1, x_2)) = x_1 + 2*x_2 POL(a__isNat(x_1)) = x_1 POL(a__isNatIList(x_1)) = x_1 POL(a__isNatList(x_1)) = x_1 POL(a__length(x_1)) = 2*x_1 POL(a__zeros) = 0 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(isNat(x_1)) = x_1 POL(isNatIList(x_1)) = x_1 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = 2*x_1 POL(mark(x_1)) = x_1 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__U11(tt) -> tt ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U21(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) a__U42(tt) -> tt a__U51(tt, V2) -> a__U52(a__isNatList(V2)) a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(0) -> tt a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNatIList(V) -> a__U31(a__isNatList(V)) a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(isNatIList(X)) -> a__isNatIList(X) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(isNatList(X)) -> a__isNatList(X) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0) -> 0 mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(nil) -> nil a__zeros -> zeros a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__isNatIList(X) -> isNatIList(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__isNat(X) -> isNat(X) a__length(X) -> length(X) Q is empty. ---------------------------------------- (9) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = x_1 POL(U41(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(U42(x_1)) = x_1 POL(U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U52(x_1)) = x_1 POL(U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U11(x_1)) = x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = x_1 POL(a__U41(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U42(x_1)) = x_1 POL(a__U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U52(x_1)) = x_1 POL(a__U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(a__U62(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__isNat(x_1)) = x_1 POL(a__isNatIList(x_1)) = 1 + x_1 POL(a__isNatList(x_1)) = x_1 POL(a__length(x_1)) = 2*x_1 POL(a__zeros) = 0 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(isNat(x_1)) = x_1 POL(isNatIList(x_1)) = 1 + x_1 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = 2*x_1 POL(mark(x_1)) = x_1 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__isNatIList(V) -> a__U31(a__isNatList(V)) ---------------------------------------- (10) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U21(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) a__U42(tt) -> tt a__U51(tt, V2) -> a__U52(a__isNatList(V2)) a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(0) -> tt a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(isNatIList(X)) -> a__isNatIList(X) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(isNatList(X)) -> a__isNatList(X) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0) -> 0 mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(nil) -> nil a__zeros -> zeros a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__isNatIList(X) -> isNatIList(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__isNat(X) -> isNat(X) a__length(X) -> length(X) Q is empty. ---------------------------------------- (11) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = x_1 POL(U41(x_1, x_2)) = x_1 + 2*x_2 POL(U42(x_1)) = x_1 POL(U51(x_1, x_2)) = x_1 + x_2 POL(U52(x_1)) = x_1 POL(U61(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U62(x_1, x_2)) = 1 + x_1 + x_2 POL(a__U11(x_1)) = x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = x_1 POL(a__U41(x_1, x_2)) = x_1 + 2*x_2 POL(a__U42(x_1)) = x_1 POL(a__U51(x_1, x_2)) = x_1 + x_2 POL(a__U52(x_1)) = x_1 POL(a__U61(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(a__U62(x_1, x_2)) = 1 + x_1 + x_2 POL(a__isNat(x_1)) = x_1 POL(a__isNatIList(x_1)) = x_1 POL(a__isNatList(x_1)) = x_1 POL(a__length(x_1)) = x_1 POL(a__zeros) = 1 POL(cons(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(isNat(x_1)) = x_1 POL(isNatIList(x_1)) = x_1 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = x_1 POL(mark(x_1)) = 1 + x_1 POL(nil) = 1 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__isNatIList(cons(V1, V2)) -> a__U41(a__isNat(V1), V2) a__isNatList(cons(V1, V2)) -> a__U51(a__isNat(V1), V2) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(0) -> 0 mark(tt) -> tt mark(nil) -> nil a__zeros -> zeros ---------------------------------------- (12) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U21(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) a__U42(tt) -> tt a__U51(tt, V2) -> a__U52(a__isNatList(V2)) a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(0) -> tt a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__isNatIList(X) -> isNatIList(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__isNat(X) -> isNat(X) a__length(X) -> length(X) Q is empty. ---------------------------------------- (13) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = 2*x_1 POL(U41(x_1, x_2)) = x_1 + 2*x_2 POL(U42(x_1)) = 2*x_1 POL(U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U52(x_1)) = x_1 POL(U61(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2)) = x_1 + 2*x_2 POL(a__U11(x_1)) = x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = 2*x_1 POL(a__U41(x_1, x_2)) = x_1 + 2*x_2 POL(a__U42(x_1)) = 2*x_1 POL(a__U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U52(x_1)) = x_1 POL(a__U61(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(a__U62(x_1, x_2)) = x_1 + 2*x_2 POL(a__isNat(x_1)) = 2 + 2*x_1 POL(a__isNatIList(x_1)) = x_1 POL(a__isNatList(x_1)) = 2*x_1 POL(a__length(x_1)) = 1 + 2*x_1 POL(a__zeros) = 0 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(isNat(x_1)) = 2 + x_1 POL(isNatIList(x_1)) = x_1 POL(isNatList(x_1)) = 2*x_1 POL(length(x_1)) = 1 + 2*x_1 POL(mark(x_1)) = x_1 POL(s(x_1)) = x_1 POL(tt) = 1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__U41(tt, V2) -> a__U42(a__isNatIList(V2)) a__U42(tt) -> tt a__U51(tt, V2) -> a__U52(a__isNatList(V2)) a__isNat(0) -> tt ---------------------------------------- (14) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U21(tt) -> tt a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__isNatIList(X) -> isNatIList(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__isNat(X) -> isNat(X) a__length(X) -> length(X) Q is empty. ---------------------------------------- (15) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = 2*x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = x_1 POL(U41(x_1, x_2)) = x_1 + 2*x_2 POL(U42(x_1)) = x_1 POL(U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U52(x_1)) = x_1 POL(U61(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U11(x_1)) = 2*x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = x_1 POL(a__U41(x_1, x_2)) = x_1 + 2*x_2 POL(a__U42(x_1)) = x_1 POL(a__U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U52(x_1)) = x_1 POL(a__U61(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 POL(a__U62(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__isNat(x_1)) = x_1 POL(a__isNatIList(x_1)) = 1 + 2*x_1 POL(a__isNatList(x_1)) = x_1 POL(a__length(x_1)) = 2*x_1 POL(a__zeros) = 0 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(isNat(x_1)) = x_1 POL(isNatIList(x_1)) = 2*x_1 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = 2*x_1 POL(mark(x_1)) = x_1 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__isNatIList(X) -> isNatIList(X) ---------------------------------------- (16) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U21(tt) -> tt a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__isNat(X) -> isNat(X) a__length(X) -> length(X) Q is empty. ---------------------------------------- (17) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = 2*x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = x_1 POL(U41(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U42(x_1)) = 2*x_1 POL(U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(U52(x_1)) = 1 + 2*x_1 POL(U61(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U11(x_1)) = 2*x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = x_1 POL(a__U41(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U42(x_1)) = 2*x_1 POL(a__U51(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__U52(x_1)) = 1 + 2*x_1 POL(a__U61(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 POL(a__U62(x_1, x_2)) = 2*x_1 + 2*x_2 POL(a__isNat(x_1)) = 1 + x_1 POL(a__isNatList(x_1)) = x_1 POL(a__length(x_1)) = 2 + 2*x_1 POL(a__zeros) = 0 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(isNat(x_1)) = x_1 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = 2 + 2*x_1 POL(mark(x_1)) = x_1 POL(s(x_1)) = 1 + x_1 POL(tt) = 2 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__U52(tt) -> tt a__U61(tt, L, N) -> a__U62(a__isNat(N), L) a__U62(tt, L) -> s(a__length(mark(L))) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__length(cons(N, L)) -> a__U61(a__isNatList(L), L, N) a__isNat(X) -> isNat(X) ---------------------------------------- (18) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U21(tt) -> tt mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__isNatList(X) -> isNatList(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__length(X) -> length(X) Q is empty. ---------------------------------------- (19) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = x_1 POL(U21(x_1)) = x_1 POL(U31(x_1)) = x_1 POL(U41(x_1, x_2)) = x_1 + x_2 POL(U42(x_1)) = x_1 POL(U51(x_1, x_2)) = x_1 + x_2 POL(U52(x_1)) = x_1 POL(U61(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2)) = x_1 + 2*x_2 POL(a__U11(x_1)) = x_1 POL(a__U21(x_1)) = x_1 POL(a__U31(x_1)) = x_1 POL(a__U41(x_1, x_2)) = x_1 + 2*x_2 POL(a__U42(x_1)) = x_1 POL(a__U51(x_1, x_2)) = x_1 + 2*x_2 POL(a__U52(x_1)) = x_1 POL(a__U61(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 POL(a__U62(x_1, x_2)) = x_1 + 2*x_2 POL(a__isNatList(x_1)) = 1 + x_1 POL(a__length(x_1)) = x_1 POL(a__zeros) = 0 POL(cons(x_1, x_2)) = x_1 + x_2 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = x_1 POL(mark(x_1)) = 2*x_1 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__isNatList(X) -> isNatList(X) ---------------------------------------- (20) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) a__U21(tt) -> tt mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(length(X)) -> a__length(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__length(X) -> length(X) Q is empty. ---------------------------------------- (21) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1)) = 1 + 2*x_1 POL(U21(x_1)) = 1 + 2*x_1 POL(U31(x_1)) = 1 + x_1 POL(U41(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U42(x_1)) = 1 + x_1 POL(U51(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U52(x_1)) = 1 + x_1 POL(U61(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(a__U11(x_1)) = 2 + 2*x_1 POL(a__U21(x_1)) = 2 + 2*x_1 POL(a__U31(x_1)) = 2 + x_1 POL(a__U41(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U42(x_1)) = 2 + x_1 POL(a__U51(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U52(x_1)) = 2 + x_1 POL(a__U61(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U62(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__length(x_1)) = 2 + 2*x_1 POL(a__zeros) = 2 POL(cons(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(length(x_1)) = 1 + 2*x_1 POL(mark(x_1)) = 2*x_1 POL(s(x_1)) = 1 + 2*x_1 POL(tt) = 1 POL(zeros) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__U21(tt) -> tt mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__U11(X) -> U11(X) a__U21(X) -> U21(X) a__U31(X) -> U31(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X1, X2) -> U51(X1, X2) a__U52(X) -> U52(X) a__U61(X1, X2, X3) -> U61(X1, X2, X3) a__U62(X1, X2) -> U62(X1, X2) a__length(X) -> length(X) ---------------------------------------- (22) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__zeros -> cons(0, zeros) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(length(X)) -> a__length(mark(X)) Q is empty. ---------------------------------------- (23) QTRSRRRProof (EQUIVALENT) Used ordering: Knuth-Bendix order [KBO] with precedence:U21_1 > mark_1 > zeros > a__length_1 > length_1 > a__U62_2 > a__U21_1 > U62_2 > U52_1 > a__U51_2 > a__U31_1 > U31_1 > a__U61_3 > U61_3 > a__U52_1 > a__zeros > cons_2 > U51_2 > a__U42_1 > U42_1 > a__U41_2 > U41_2 > a__U11_1 > U11_1 > 0 and weight map: a__zeros=4 0=1 zeros=1 mark_1=3 U11_1=1 a__U11_1=1 U21_1=1 a__U21_1=1 U31_1=1 a__U31_1=1 U42_1=1 a__U42_1=1 U52_1=1 a__U52_1=1 length_1=1 a__length_1=1 cons_2=2 U41_2=0 a__U41_2=0 U51_2=0 a__U51_2=0 U61_3=0 a__U61_3=0 U62_2=0 a__U62_2=0 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__zeros -> cons(0, zeros) mark(zeros) -> a__zeros mark(U11(X)) -> a__U11(mark(X)) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X)) -> a__U31(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X1, X2)) -> a__U51(mark(X1), X2) mark(U52(X)) -> a__U52(mark(X)) mark(U61(X1, X2, X3)) -> a__U61(mark(X1), X2, X3) mark(U62(X1, X2)) -> a__U62(mark(X1), X2) mark(length(X)) -> a__length(mark(X)) ---------------------------------------- (24) Obligation: Q restricted rewrite system: R is empty. Q is empty. ---------------------------------------- (25) RisEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (26) YES