/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/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, 534 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 62 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 38 ms] (6) QTRS (7) RisEmptyProof [EQUIVALENT, 0 ms] (8) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a____(__(X, Y), Z) -> a____(mark(X), a____(mark(Y), mark(Z))) a____(X, nil) -> mark(X) a____(nil, X) -> mark(X) a__U11(tt, V) -> a__U12(a__isNeList(V)) a__U12(tt) -> tt a__U21(tt, V1, V2) -> a__U22(a__isList(V1), V2) a__U22(tt, V2) -> a__U23(a__isList(V2)) a__U23(tt) -> tt a__U31(tt, V) -> a__U32(a__isQid(V)) a__U32(tt) -> tt a__U41(tt, V1, V2) -> a__U42(a__isList(V1), V2) a__U42(tt, V2) -> a__U43(a__isNeList(V2)) a__U43(tt) -> tt a__U51(tt, V1, V2) -> a__U52(a__isNeList(V1), V2) a__U52(tt, V2) -> a__U53(a__isList(V2)) a__U53(tt) -> tt a__U61(tt, V) -> a__U62(a__isQid(V)) a__U62(tt) -> tt a__U71(tt, V) -> a__U72(a__isNePal(V)) a__U72(tt) -> tt a__and(tt, X) -> mark(X) a__isList(V) -> a__U11(a__isPalListKind(V), V) a__isList(nil) -> tt a__isList(__(V1, V2)) -> a__U21(a__and(a__isPalListKind(V1), isPalListKind(V2)), V1, V2) a__isNeList(V) -> a__U31(a__isPalListKind(V), V) a__isNeList(__(V1, V2)) -> a__U41(a__and(a__isPalListKind(V1), isPalListKind(V2)), V1, V2) a__isNeList(__(V1, V2)) -> a__U51(a__and(a__isPalListKind(V1), isPalListKind(V2)), V1, V2) a__isNePal(V) -> a__U61(a__isPalListKind(V), V) a__isNePal(__(I, __(P, I))) -> a__and(a__and(a__isQid(I), isPalListKind(I)), and(isPal(P), isPalListKind(P))) a__isPal(V) -> a__U71(a__isPalListKind(V), V) a__isPal(nil) -> tt a__isPalListKind(a) -> tt a__isPalListKind(e) -> tt a__isPalListKind(i) -> tt a__isPalListKind(nil) -> tt a__isPalListKind(o) -> tt a__isPalListKind(u) -> tt a__isPalListKind(__(V1, V2)) -> a__and(a__isPalListKind(V1), isPalListKind(V2)) a__isQid(a) -> tt a__isQid(e) -> tt a__isQid(i) -> tt a__isQid(o) -> tt a__isQid(u) -> tt mark(__(X1, X2)) -> a____(mark(X1), mark(X2)) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNeList(X)) -> a__isNeList(X) mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(isList(X)) -> a__isList(X) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(isQid(X)) -> a__isQid(X) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(U42(X1, X2)) -> a__U42(mark(X1), X2) mark(U43(X)) -> a__U43(mark(X)) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2)) -> a__U52(mark(X1), X2) mark(U53(X)) -> a__U53(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X)) -> a__U72(mark(X)) mark(isNePal(X)) -> a__isNePal(X) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(isPalListKind(X)) -> a__isPalListKind(X) mark(isPal(X)) -> a__isPal(X) mark(nil) -> nil mark(tt) -> tt mark(a) -> a mark(e) -> e mark(i) -> i mark(o) -> o mark(u) -> u a____(X1, X2) -> __(X1, X2) a__U11(X1, X2) -> U11(X1, X2) a__U12(X) -> U12(X) a__isNeList(X) -> isNeList(X) a__U21(X1, X2, X3) -> U21(X1, X2, X3) a__U22(X1, X2) -> U22(X1, X2) a__isList(X) -> isList(X) a__U23(X) -> U23(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X) -> U32(X) a__isQid(X) -> isQid(X) a__U41(X1, X2, X3) -> U41(X1, X2, X3) a__U42(X1, X2) -> U42(X1, X2) a__U43(X) -> U43(X) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2) -> U52(X1, X2) a__U53(X) -> U53(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X) -> U72(X) a__isNePal(X) -> isNePal(X) a__and(X1, X2) -> and(X1, X2) a__isPalListKind(X) -> isPalListKind(X) a__isPal(X) -> isPal(X) Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: a____/2(YES,YES) __/2(YES,YES) mark/1)YES( nil/0) a__U11/2(YES,YES) tt/0) a__U12/1)YES( a__isNeList/1(YES) a__U21/3(YES,YES,YES) a__U22/2(YES,YES) a__isList/1(YES) a__U23/1)YES( a__U31/2(YES,YES) a__U32/1)YES( a__isQid/1)YES( a__U41/3(YES,YES,YES) a__U42/2(YES,YES) a__U43/1)YES( a__U51/3(YES,YES,YES) a__U52/2(YES,YES) a__U53/1)YES( a__U61/2(YES,YES) a__U62/1)YES( a__U71/2(YES,YES) a__U72/1)YES( a__isNePal/1(YES) a__and/2(YES,YES) a__isPalListKind/1(YES) isPalListKind/1(YES) and/2(YES,YES) isPal/1(YES) a__isPal/1(YES) a/0) e/0) i/0) o/0) u/0) U11/2(YES,YES) U12/1)YES( isNeList/1(YES) U21/3(YES,YES,YES) U22/2(YES,YES) isList/1(YES) U23/1)YES( U31/2(YES,YES) U32/1)YES( isQid/1)YES( U41/3(YES,YES,YES) U42/2(YES,YES) U43/1)YES( U51/3(YES,YES,YES) U52/2(YES,YES) U53/1)YES( U61/2(YES,YES) U62/1)YES( U71/2(YES,YES) U72/1)YES( isNePal/1(YES) Quasi precedence: [a_____2, ___2] > [a__U21_3, U21_3] > [a__U22_2, U22_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] [a_____2, ___2] > [a__U21_3, U21_3] > [a__U22_2, U22_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] [a_____2, ___2] > [a__U41_3, U41_3] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] [a_____2, ___2] > [a__U41_3, U41_3] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] [a_____2, ___2] > [a__U41_3, U41_3] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] [a_____2, ___2] > [a__U41_3, U41_3] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] [a_____2, ___2] > [a__U51_3, U51_3] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] [a_____2, ___2] > [a__U51_3, U51_3] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] [a_____2, ___2] > [isPal_1, a__isPal_1] > [a__U71_2, U71_2] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] [a_____2, ___2] > [isPal_1, a__isPal_1] > [a__U71_2, U71_2] > [a__isNePal_1, isNePal_1] > [a__and_2, and_2] [a_____2, ___2] > [isPal_1, a__isPal_1] > [a__U71_2, U71_2] > [a__isNePal_1, isNePal_1] > [a__isPalListKind_1, isPalListKind_1] nil > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] nil > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] nil > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] nil > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] nil > [tt, i] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] nil > [tt, i] > [a__isNePal_1, isNePal_1] > [a__and_2, and_2] nil > [tt, i] > [a__isNePal_1, isNePal_1] > [a__isPalListKind_1, isPalListKind_1] a > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] a > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] a > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] a > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] a > [tt, i] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] a > [tt, i] > [a__isNePal_1, isNePal_1] > [a__and_2, and_2] a > [tt, i] > [a__isNePal_1, isNePal_1] > [a__isPalListKind_1, isPalListKind_1] e > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] e > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] e > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] e > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] e > [tt, i] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] e > [tt, i] > [a__isNePal_1, isNePal_1] > [a__and_2, and_2] e > [tt, i] > [a__isNePal_1, isNePal_1] > [a__isPalListKind_1, isPalListKind_1] o > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] o > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] o > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] o > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] o > [tt, i] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] o > [tt, i] > [a__isNePal_1, isNePal_1] > [a__and_2, and_2] o > [tt, i] > [a__isNePal_1, isNePal_1] > [a__isPalListKind_1, isPalListKind_1] u > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] u > [tt, i] > [a__U42_2, U42_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] u > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__U31_2, U31_2] u > [tt, i] > [a__U52_2, U52_2] > [a__isList_1, isList_1] > [a__U11_2, U11_2] > [a__isNeList_1, isNeList_1] > [a__isPalListKind_1, isPalListKind_1] u > [tt, i] > [a__isNePal_1, isNePal_1] > [a__U61_2, U61_2] u > [tt, i] > [a__isNePal_1, isNePal_1] > [a__and_2, and_2] u > [tt, i] > [a__isNePal_1, isNePal_1] > [a__isPalListKind_1, isPalListKind_1] Status: a_____2: [1,2] ___2: [1,2] nil: multiset status a__U11_2: multiset status tt: multiset status a__isNeList_1: multiset status a__U21_3: multiset status a__U22_2: multiset status a__isList_1: multiset status a__U31_2: multiset status a__U41_3: multiset status a__U42_2: multiset status a__U51_3: multiset status a__U52_2: multiset status a__U61_2: multiset status a__U71_2: [1,2] a__isNePal_1: multiset status a__and_2: multiset status a__isPalListKind_1: multiset status isPalListKind_1: multiset status and_2: multiset status isPal_1: multiset status a__isPal_1: multiset status a: multiset status e: multiset status i: multiset status o: multiset status u: multiset status U11_2: multiset status isNeList_1: multiset status U21_3: multiset status U22_2: multiset status isList_1: multiset status U31_2: multiset status U41_3: multiset status U42_2: multiset status U51_3: multiset status U52_2: multiset status U61_2: multiset status U71_2: [1,2] isNePal_1: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a____(__(X, Y), Z) -> a____(mark(X), a____(mark(Y), mark(Z))) a____(X, nil) -> mark(X) a____(nil, X) -> mark(X) a__U11(tt, V) -> a__U12(a__isNeList(V)) a__U21(tt, V1, V2) -> a__U22(a__isList(V1), V2) a__U22(tt, V2) -> a__U23(a__isList(V2)) a__U31(tt, V) -> a__U32(a__isQid(V)) a__U41(tt, V1, V2) -> a__U42(a__isList(V1), V2) a__U42(tt, V2) -> a__U43(a__isNeList(V2)) a__U51(tt, V1, V2) -> a__U52(a__isNeList(V1), V2) a__U52(tt, V2) -> a__U53(a__isList(V2)) a__U61(tt, V) -> a__U62(a__isQid(V)) a__U71(tt, V) -> a__U72(a__isNePal(V)) a__and(tt, X) -> mark(X) a__isList(V) -> a__U11(a__isPalListKind(V), V) a__isList(nil) -> tt a__isList(__(V1, V2)) -> a__U21(a__and(a__isPalListKind(V1), isPalListKind(V2)), V1, V2) a__isNeList(V) -> a__U31(a__isPalListKind(V), V) a__isNeList(__(V1, V2)) -> a__U41(a__and(a__isPalListKind(V1), isPalListKind(V2)), V1, V2) a__isNeList(__(V1, V2)) -> a__U51(a__and(a__isPalListKind(V1), isPalListKind(V2)), V1, V2) a__isNePal(V) -> a__U61(a__isPalListKind(V), V) a__isNePal(__(I, __(P, I))) -> a__and(a__and(a__isQid(I), isPalListKind(I)), and(isPal(P), isPalListKind(P))) a__isPal(V) -> a__U71(a__isPalListKind(V), V) a__isPal(nil) -> tt a__isPalListKind(a) -> tt a__isPalListKind(e) -> tt a__isPalListKind(i) -> tt a__isPalListKind(nil) -> tt a__isPalListKind(o) -> tt a__isPalListKind(u) -> tt a__isPalListKind(__(V1, V2)) -> a__and(a__isPalListKind(V1), isPalListKind(V2)) a__isQid(a) -> tt a__isQid(e) -> tt a__isQid(o) -> tt a__isQid(u) -> tt ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__U12(tt) -> tt a__U23(tt) -> tt a__U32(tt) -> tt a__U43(tt) -> tt a__U53(tt) -> tt a__U62(tt) -> tt a__U72(tt) -> tt a__isQid(i) -> tt mark(__(X1, X2)) -> a____(mark(X1), mark(X2)) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNeList(X)) -> a__isNeList(X) mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(isList(X)) -> a__isList(X) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(isQid(X)) -> a__isQid(X) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(U42(X1, X2)) -> a__U42(mark(X1), X2) mark(U43(X)) -> a__U43(mark(X)) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2)) -> a__U52(mark(X1), X2) mark(U53(X)) -> a__U53(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X)) -> a__U72(mark(X)) mark(isNePal(X)) -> a__isNePal(X) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(isPalListKind(X)) -> a__isPalListKind(X) mark(isPal(X)) -> a__isPal(X) mark(nil) -> nil mark(tt) -> tt mark(a) -> a mark(e) -> e mark(i) -> i mark(o) -> o mark(u) -> u a____(X1, X2) -> __(X1, X2) a__U11(X1, X2) -> U11(X1, X2) a__U12(X) -> U12(X) a__isNeList(X) -> isNeList(X) a__U21(X1, X2, X3) -> U21(X1, X2, X3) a__U22(X1, X2) -> U22(X1, X2) a__isList(X) -> isList(X) a__U23(X) -> U23(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X) -> U32(X) a__isQid(X) -> isQid(X) a__U41(X1, X2, X3) -> U41(X1, X2, X3) a__U42(X1, X2) -> U42(X1, X2) a__U43(X) -> U43(X) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2) -> U52(X1, X2) a__U53(X) -> U53(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X) -> U72(X) a__isNePal(X) -> isNePal(X) a__and(X1, X2) -> and(X1, X2) a__isPalListKind(X) -> isPalListKind(X) a__isPal(X) -> isPal(X) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U12(x_1)) = 1 + 2*x_1 POL(U21(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3 POL(U22(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U23(x_1)) = 1 + 2*x_1 POL(U31(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U32(x_1)) = 1 + 2*x_1 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U42(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U43(x_1)) = 1 + 2*x_1 POL(U51(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U52(x_1, x_2)) = 1 + x_1 + x_2 POL(U53(x_1)) = 1 + 2*x_1 POL(U61(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U62(x_1)) = 1 + 2*x_1 POL(U71(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(U72(x_1)) = 1 + 2*x_1 POL(__(x_1, x_2)) = 1 + x_1 + x_2 POL(a) = 1 POL(a__U11(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U12(x_1)) = 2 + 2*x_1 POL(a__U21(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U22(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U23(x_1)) = 2 + 2*x_1 POL(a__U31(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U32(x_1)) = 2 + 2*x_1 POL(a__U41(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U42(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U43(x_1)) = 2 + 2*x_1 POL(a__U51(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(a__U52(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U53(x_1)) = 2 + 2*x_1 POL(a__U61(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U62(x_1)) = 2 + 2*x_1 POL(a__U71(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__U72(x_1)) = 2 + 2*x_1 POL(a____(x_1, x_2)) = 2 + x_1 + x_2 POL(a__and(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(a__isList(x_1)) = 2 + 2*x_1 POL(a__isNeList(x_1)) = 2 + 2*x_1 POL(a__isNePal(x_1)) = 2 + 2*x_1 POL(a__isPal(x_1)) = 2 + 2*x_1 POL(a__isPalListKind(x_1)) = 2 + 2*x_1 POL(a__isQid(x_1)) = 2 + 2*x_1 POL(and(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(e) = 1 POL(i) = 1 POL(isList(x_1)) = 1 + x_1 POL(isNeList(x_1)) = 1 + x_1 POL(isNePal(x_1)) = 1 + x_1 POL(isPal(x_1)) = 1 + 2*x_1 POL(isPalListKind(x_1)) = 1 + x_1 POL(isQid(x_1)) = 1 + 2*x_1 POL(mark(x_1)) = 2*x_1 POL(nil) = 1 POL(o) = 1 POL(tt) = 1 POL(u) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a__U12(tt) -> tt a__U23(tt) -> tt a__U32(tt) -> tt a__U43(tt) -> tt a__U53(tt) -> tt a__U62(tt) -> tt a__U72(tt) -> tt a__isQid(i) -> tt mark(nil) -> nil mark(tt) -> tt mark(a) -> a mark(e) -> e mark(i) -> i mark(o) -> o mark(u) -> u a____(X1, X2) -> __(X1, X2) a__U11(X1, X2) -> U11(X1, X2) a__U12(X) -> U12(X) a__isNeList(X) -> isNeList(X) a__U21(X1, X2, X3) -> U21(X1, X2, X3) a__U22(X1, X2) -> U22(X1, X2) a__isList(X) -> isList(X) a__U23(X) -> U23(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X) -> U32(X) a__isQid(X) -> isQid(X) a__U41(X1, X2, X3) -> U41(X1, X2, X3) a__U42(X1, X2) -> U42(X1, X2) a__U43(X) -> U43(X) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2) -> U52(X1, X2) a__U53(X) -> U53(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X) -> U72(X) a__isNePal(X) -> isNePal(X) a__and(X1, X2) -> and(X1, X2) a__isPalListKind(X) -> isPalListKind(X) a__isPal(X) -> isPal(X) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: mark(__(X1, X2)) -> a____(mark(X1), mark(X2)) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNeList(X)) -> a__isNeList(X) mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(isList(X)) -> a__isList(X) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(isQid(X)) -> a__isQid(X) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(U42(X1, X2)) -> a__U42(mark(X1), X2) mark(U43(X)) -> a__U43(mark(X)) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2)) -> a__U52(mark(X1), X2) mark(U53(X)) -> a__U53(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X)) -> a__U72(mark(X)) mark(isNePal(X)) -> a__isNePal(X) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(isPalListKind(X)) -> a__isPalListKind(X) mark(isPal(X)) -> a__isPal(X) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U11(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(U12(x_1)) = 2 + 2*x_1 POL(U21(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3 POL(U22(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(U23(x_1)) = 1 + 2*x_1 POL(U31(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(U32(x_1)) = 2 + 2*x_1 POL(U41(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3 POL(U42(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(U43(x_1)) = 1 + 2*x_1 POL(U51(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 POL(U52(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(U53(x_1)) = 2 + 2*x_1 POL(U61(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(U62(x_1)) = 1 + 2*x_1 POL(U71(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(U72(x_1)) = 2 + 2*x_1 POL(__(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(a__U11(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U12(x_1)) = 1 + 2*x_1 POL(a__U21(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 POL(a__U22(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(a__U23(x_1)) = 1 + x_1 POL(a__U31(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U32(x_1)) = 1 + 2*x_1 POL(a__U41(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 POL(a__U42(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U43(x_1)) = 1 + x_1 POL(a__U51(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(a__U52(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U53(x_1)) = 1 + 2*x_1 POL(a__U61(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__U62(x_1)) = 1 + x_1 POL(a__U71(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(a__U72(x_1)) = 1 + 2*x_1 POL(a____(x_1, x_2)) = 1 + x_1 + x_2 POL(a__and(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(a__isList(x_1)) = 1 + 2*x_1 POL(a__isNeList(x_1)) = 1 + 2*x_1 POL(a__isNePal(x_1)) = 2*x_1 POL(a__isPal(x_1)) = 1 + 2*x_1 POL(a__isPalListKind(x_1)) = 2*x_1 POL(a__isQid(x_1)) = 1 + 2*x_1 POL(and(x_1, x_2)) = 2 + 2*x_1 + x_2 POL(isList(x_1)) = 2*x_1 POL(isNeList(x_1)) = 2*x_1 POL(isNePal(x_1)) = 1 + 2*x_1 POL(isPal(x_1)) = x_1 POL(isPalListKind(x_1)) = 1 + 2*x_1 POL(isQid(x_1)) = x_1 POL(mark(x_1)) = 2 + 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: mark(__(X1, X2)) -> a____(mark(X1), mark(X2)) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNeList(X)) -> a__isNeList(X) mark(U21(X1, X2, X3)) -> a__U21(mark(X1), X2, X3) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(isList(X)) -> a__isList(X) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(isQid(X)) -> a__isQid(X) mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) mark(U42(X1, X2)) -> a__U42(mark(X1), X2) mark(U43(X)) -> a__U43(mark(X)) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2)) -> a__U52(mark(X1), X2) mark(U53(X)) -> a__U53(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X)) -> a__U72(mark(X)) mark(isNePal(X)) -> a__isNePal(X) mark(and(X1, X2)) -> a__and(mark(X1), X2) mark(isPalListKind(X)) -> a__isPalListKind(X) mark(isPal(X)) -> a__isPal(X) ---------------------------------------- (6) Obligation: Q restricted rewrite system: R is empty. Q is empty. ---------------------------------------- (7) RisEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (8) YES