Certification Problem

Input (TPDB TRS_Standard/Transformed_CSR_04/PALINDROME_nokinds-noand_FR)

The rewrite relation of the following TRS is considered.

__(__(X,Y),Z) → __(X,__(Y,Z)) (1)
__(X,nil) → X (2)
__(nil,X) → X (3)
U11(tt) → tt (4)
U21(tt,V2) → U22(isList(activate(V2))) (5)
U22(tt) → tt (6)
U31(tt) → tt (7)
U41(tt,V2) → U42(isNeList(activate(V2))) (8)
U42(tt) → tt (9)
U51(tt,V2) → U52(isList(activate(V2))) (10)
U52(tt) → tt (11)
U61(tt) → tt (12)
U71(tt,P) → U72(isPal(activate(P))) (13)
U72(tt) → tt (14)
U81(tt) → tt (15)
isList(V) → U11(isNeList(activate(V))) (16)
isList(n__nil) → tt (17)
isList(n____(V1,V2)) → U21(isList(activate(V1)),activate(V2)) (18)
isNeList(V) → U31(isQid(activate(V))) (19)
isNeList(n____(V1,V2)) → U41(isList(activate(V1)),activate(V2)) (20)
isNeList(n____(V1,V2)) → U51(isNeList(activate(V1)),activate(V2)) (21)
isNePal(V) → U61(isQid(activate(V))) (22)
isNePal(n____(I,n____(P,I))) → U71(isQid(activate(I)),activate(P)) (23)
isPal(V) → U81(isNePal(activate(V))) (24)
isPal(n__nil) → tt (25)
isQid(n__a) → tt (26)
isQid(n__e) → tt (27)
isQid(n__i) → tt (28)
isQid(n__o) → tt (29)
isQid(n__u) → tt (30)
nil → n__nil (31)
__(X1,X2) → n____(X1,X2) (32)
a → n__a (33)
e → n__e (34)
i → n__i (35)
o → n__o (36)
u → n__u (37)
activate(n__nil) → nil (38)
activate(n____(X1,X2)) → __(activate(X1),activate(X2)) (39)
activate(n__a) → a (40)
activate(n__e) → e (41)
activate(n__i) → i (42)
activate(n__o) → o (43)
activate(n__u) → u (44)
activate(X) → X (45)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by AProVE @ termCOMP 2023)

1 Rule Removal

Using the Knuth Bendix order with w0 = 1 and the following precedence and weight functions
prec(nil) = 12 weight(nil) = 1
prec(tt) = 3 weight(tt) = 8
prec(n__nil) = 11 weight(n__nil) = 1
prec(n__a) = 28 weight(n__a) = 3
prec(n__e) = 29 weight(n__e) = 3
prec(n__i) = 18 weight(n__i) = 3
prec(n__o) = 23 weight(n__o) = 3
prec(n__u) = 24 weight(n__u) = 3
prec(a) = 30 weight(a) = 3
prec(e) = 31 weight(e) = 3
prec(i) = 20 weight(i) = 3
prec(o) = 25 weight(o) = 3
prec(u) = 26 weight(u) = 3
prec(U11) = 4 weight(U11) = 1
prec(U22) = 0 weight(U22) = 2
prec(isList) = 5 weight(isList) = 7
prec(activate) = 32 weight(activate) = 0
prec(U31) = 15 weight(U31) = 1
prec(U42) = 2 weight(U42) = 2
prec(isNeList) = 27 weight(isNeList) = 6
prec(U52) = 21 weight(U52) = 1
prec(U61) = 13 weight(U61) = 1
prec(U72) = 6 weight(U72) = 5
prec(isPal) = 10 weight(isPal) = 7
prec(U81) = 9 weight(U81) = 1
prec(isQid) = 16 weight(isQid) = 5
prec(isNePal) = 17 weight(isNePal) = 6
prec(__) = 19 weight(__) = 1
prec(U21) = 1 weight(U21) = 1
prec(U41) = 8 weight(U41) = 0
prec(U51) = 22 weight(U51) = 1
prec(U71) = 7 weight(U71) = 4
prec(n____) = 14 weight(n____) = 1
all of the following rules can be deleted.
__(__(X,Y),Z) → __(X,__(Y,Z)) (1)
__(X,nil) → X (2)
__(nil,X) → X (3)
U11(tt) → tt (4)
U21(tt,V2) → U22(isList(activate(V2))) (5)
U22(tt) → tt (6)
U31(tt) → tt (7)
U41(tt,V2) → U42(isNeList(activate(V2))) (8)
U42(tt) → tt (9)
U51(tt,V2) → U52(isList(activate(V2))) (10)
U52(tt) → tt (11)
U61(tt) → tt (12)
U71(tt,P) → U72(isPal(activate(P))) (13)
U72(tt) → tt (14)
U81(tt) → tt (15)
isList(V) → U11(isNeList(activate(V))) (16)
isList(n__nil) → tt (17)
isList(n____(V1,V2)) → U21(isList(activate(V1)),activate(V2)) (18)
isNeList(V) → U31(isQid(activate(V))) (19)
isNeList(n____(V1,V2)) → U41(isList(activate(V1)),activate(V2)) (20)
isNeList(n____(V1,V2)) → U51(isNeList(activate(V1)),activate(V2)) (21)
isNePal(V) → U61(isQid(activate(V))) (22)
isNePal(n____(I,n____(P,I))) → U71(isQid(activate(I)),activate(P)) (23)
isPal(V) → U81(isNePal(activate(V))) (24)
isPal(n__nil) → tt (25)
isQid(n__a) → tt (26)
isQid(n__e) → tt (27)
isQid(n__i) → tt (28)
isQid(n__o) → tt (29)
isQid(n__u) → tt (30)
nil → n__nil (31)
__(X1,X2) → n____(X1,X2) (32)
a → n__a (33)
e → n__e (34)
i → n__i (35)
o → n__o (36)
u → n__u (37)
activate(n__nil) → nil (38)
activate(n____(X1,X2)) → __(activate(X1),activate(X2)) (39)
activate(n__a) → a (40)
activate(n__e) → e (41)
activate(n__i) → i (42)
activate(n__o) → o (43)
activate(n__u) → u (44)
activate(X) → X (45)

1.1 R is empty

There are no rules in the TRS. Hence, it is terminating.