YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 370 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 2 ms] (4) QTRS (5) RisEmptyProof [EQUIVALENT, 0 ms] (6) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt, V) -> U12(isNeList(activate(V))) U12(tt) -> tt U21(tt, V1, V2) -> U22(isList(activate(V1)), activate(V2)) U22(tt, V2) -> U23(isList(activate(V2))) U23(tt) -> tt U31(tt, V) -> U32(isQid(activate(V))) U32(tt) -> tt U41(tt, V1, V2) -> U42(isList(activate(V1)), activate(V2)) U42(tt, V2) -> U43(isNeList(activate(V2))) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNeList(activate(V1)), activate(V2)) U52(tt, V2) -> U53(isList(activate(V2))) U53(tt) -> tt U61(tt, V) -> U62(isQid(activate(V))) U62(tt) -> tt U71(tt, V) -> U72(isNePal(activate(V))) U72(tt) -> tt and(tt, X) -> activate(X) isList(V) -> U11(isPalListKind(activate(V)), activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))), activate(V1), activate(V2)) isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) isNeList(n____(V1, V2)) -> U41(and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))), activate(V1), activate(V2)) isNeList(n____(V1, V2)) -> U51(and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))), activate(V1), activate(V2)) isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) isNePal(n____(I, __(P, I))) -> and(and(isQid(activate(I)), n__isPalListKind(activate(I))), n__and(isPal(activate(P)), n__isPalListKind(activate(P)))) isPal(V) -> U71(isPalListKind(activate(V)), activate(V)) isPal(n__nil) -> tt isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(n____(V1, V2)) -> and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))) isQid(n__a) -> tt isQid(n__e) -> tt isQid(n__i) -> tt isQid(n__o) -> tt isQid(n__u) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) isPalListKind(X) -> n__isPalListKind(X) and(X1, X2) -> n__and(X1, X2) a -> n__a e -> n__e i -> n__i o -> n__o u -> n__u activate(n__nil) -> nil activate(n____(X1, X2)) -> __(X1, X2) activate(n__isPalListKind(X)) -> isPalListKind(X) activate(n__and(X1, X2)) -> and(X1, X2) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: __/2(YES,YES) nil/0) U11/2(YES,YES) tt/0) U12/1)YES( isNeList/1(YES) activate/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) and/2(YES,YES) isPalListKind/1(YES) n__nil/0) n____/2(YES,YES) n__isPalListKind/1(YES) n__and/2(YES,YES) isPal/1(YES) n__a/0) n__e/0) n__i/0) n__o/0) n__u/0) a/0) e/0) i/0) o/0) u/0) Quasi precedence: [___2, n_____2] > U21_3 > U22_2 > isList_1 > U11_2 > isNeList_1 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__isPalListKind_1 [___2, n_____2] > U21_3 > U22_2 > isList_1 > U11_2 > isNeList_1 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__e > [tt, U62_1, n__a, n__i] [___2, n_____2] > U41_3 > isList_1 > U11_2 > isNeList_1 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__isPalListKind_1 [___2, n_____2] > U41_3 > isList_1 > U11_2 > isNeList_1 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__e > [tt, U62_1, n__a, n__i] [___2, n_____2] > U41_3 > U42_2 > isNeList_1 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__isPalListKind_1 [___2, n_____2] > U41_3 > U42_2 > isNeList_1 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__e > [tt, U62_1, n__a, n__i] [___2, n_____2] > U51_3 > U52_2 > isList_1 > U11_2 > isNeList_1 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__isPalListKind_1 [___2, n_____2] > U51_3 > U52_2 > isList_1 > U11_2 > isNeList_1 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__e > [tt, U62_1, n__a, n__i] [___2, n_____2] > [and_2, n__and_2] > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__isPalListKind_1 [___2, n_____2] > [and_2, n__and_2] > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__e > [tt, U62_1, n__a, n__i] [___2, n_____2] > isPal_1 > U71_2 > isNePal_1 > U61_2 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__isPalListKind_1 [___2, n_____2] > isPal_1 > U71_2 > isNePal_1 > U61_2 > [activate_1, U31_2, isPalListKind_1, a, e, i] > n__e > [tt, U62_1, n__a, n__i] [nil, n__nil] > [tt, U62_1, n__a, n__i] [n__o, o] > [tt, U62_1, n__a, n__i] [n__u, u] > [tt, U62_1, n__a, n__i] Status: ___2: [1,2] nil: multiset status U11_2: [2,1] tt: multiset status isNeList_1: multiset status activate_1: multiset status U21_3: [3,2,1] U22_2: [2,1] isList_1: [1] U31_2: multiset status U41_3: [1,3,2] U42_2: multiset status U51_3: multiset status U52_2: multiset status U61_2: [2,1] U62_1: [1] U71_2: [2,1] isNePal_1: multiset status and_2: multiset status isPalListKind_1: multiset status n__nil: multiset status n_____2: [1,2] n__isPalListKind_1: multiset status n__and_2: multiset status isPal_1: multiset status n__a: multiset status n__e: multiset status n__i: multiset status n__o: multiset status n__u: multiset status a: multiset status e: multiset status i: multiset status o: multiset status u: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: __(__(X, Y), Z) -> __(X, __(Y, Z)) __(X, nil) -> X __(nil, X) -> X U11(tt, V) -> U12(isNeList(activate(V))) U21(tt, V1, V2) -> U22(isList(activate(V1)), activate(V2)) U22(tt, V2) -> U23(isList(activate(V2))) U31(tt, V) -> U32(isQid(activate(V))) U41(tt, V1, V2) -> U42(isList(activate(V1)), activate(V2)) U42(tt, V2) -> U43(isNeList(activate(V2))) U51(tt, V1, V2) -> U52(isNeList(activate(V1)), activate(V2)) U52(tt, V2) -> U53(isList(activate(V2))) U61(tt, V) -> U62(isQid(activate(V))) U62(tt) -> tt U71(tt, V) -> U72(isNePal(activate(V))) and(tt, X) -> activate(X) isList(V) -> U11(isPalListKind(activate(V)), activate(V)) isList(n__nil) -> tt isList(n____(V1, V2)) -> U21(and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))), activate(V1), activate(V2)) isNeList(V) -> U31(isPalListKind(activate(V)), activate(V)) isNeList(n____(V1, V2)) -> U41(and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))), activate(V1), activate(V2)) isNeList(n____(V1, V2)) -> U51(and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))), activate(V1), activate(V2)) isNePal(V) -> U61(isPalListKind(activate(V)), activate(V)) isNePal(n____(I, __(P, I))) -> and(and(isQid(activate(I)), n__isPalListKind(activate(I))), n__and(isPal(activate(P)), n__isPalListKind(activate(P)))) isPal(V) -> U71(isPalListKind(activate(V)), activate(V)) isPal(n__nil) -> tt isPalListKind(n__a) -> tt isPalListKind(n__e) -> tt isPalListKind(n__i) -> tt isPalListKind(n__nil) -> tt isPalListKind(n__o) -> tt isPalListKind(n__u) -> tt isPalListKind(n____(V1, V2)) -> and(isPalListKind(activate(V1)), n__isPalListKind(activate(V2))) isQid(n__e) -> tt isQid(n__o) -> tt isQid(n__u) -> tt isPalListKind(X) -> n__isPalListKind(X) a -> n__a e -> n__e i -> n__i activate(n__nil) -> nil activate(n____(X1, X2)) -> __(X1, X2) activate(n__isPalListKind(X)) -> isPalListKind(X) activate(n__and(X1, X2)) -> and(X1, X2) activate(n__a) -> a activate(n__e) -> e activate(n__i) -> i activate(n__o) -> o activate(n__u) -> u activate(X) -> X ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: U12(tt) -> tt U23(tt) -> tt U32(tt) -> tt U43(tt) -> tt U53(tt) -> tt U72(tt) -> tt isQid(n__a) -> tt isQid(n__i) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) and(X1, X2) -> n__and(X1, X2) o -> n__o u -> n__u Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Knuth-Bendix order [KBO] with precedence:U72_1 > u > n__u > o > n__o > and_2 > n__and_2 > ___2 > n_____2 > nil > n__nil > n__i > n__a > U12_1 > isQid_1 > U53_1 > U43_1 > U32_1 > U23_1 > tt and weight map: tt=2 n__a=1 n__i=1 nil=1 n__nil=1 o=1 n__o=1 u=1 n__u=1 U12_1=1 U23_1=1 U32_1=1 U43_1=1 U53_1=1 U72_1=0 isQid_1=1 ___2=0 n_____2=0 and_2=0 n__and_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: U12(tt) -> tt U23(tt) -> tt U32(tt) -> tt U43(tt) -> tt U53(tt) -> tt U72(tt) -> tt isQid(n__a) -> tt isQid(n__i) -> tt nil -> n__nil __(X1, X2) -> n____(X1, X2) and(X1, X2) -> n__and(X1, X2) o -> n__o u -> n__u ---------------------------------------- (4) Obligation: Q restricted rewrite system: R is empty. Q is empty. ---------------------------------------- (5) RisEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (6) YES