/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, 374 ms]
(2) QTRS
(3) QTRSRRRProof [EQUIVALENT, 16 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, n____(P, I))) -> and(and(isQid(activate(I)), n__isPalListKind(activate(I))), n__and(n__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)
   isPal(X) -> n__isPal(X)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(X1, X2)) -> __(activate(X1), activate(X2))
   activate(n__isPalListKind(X)) -> isPalListKind(X)
   activate(n__and(X1, X2)) -> and(activate(X1), X2)
   activate(n__isPal(X)) -> isPal(X)
   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)
n__isPal/1(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, U52_2] > [U11_2, isNeList_1] > U31_2 > isQid_1 > tt
[___2, n_____2] > U21_3 > U22_2 > [isList_1, U52_2] > U53_1 > tt
[___2, n_____2] > U21_3 > U22_2 > U23_1 > tt
[___2, n_____2] > U41_3 > [isList_1, U52_2] > [U11_2, isNeList_1] > U31_2 > isQid_1 > tt
[___2, n_____2] > U41_3 > [isList_1, U52_2] > U53_1 > tt
[___2, n_____2] > U41_3 > U42_2 > [U11_2, isNeList_1] > U31_2 > isQid_1 > tt
[___2, n_____2] > U41_3 > U42_2 > U43_1 > tt
[___2, n_____2] > U51_3 > [isList_1, U52_2] > [U11_2, isNeList_1] > U31_2 > isQid_1 > tt
[___2, n_____2] > U51_3 > [isList_1, U52_2] > U53_1 > tt
[___2, n_____2] > [and_2, n__and_2]
[___2, n_____2] > [n__isPal_1, isPal_1] > [U71_2, isNePal_1] > U61_2 > isQid_1 > tt
[___2, n_____2] > [n__isPal_1, isPal_1] > [U71_2, isNePal_1] > U61_2 > U62_1 > tt
[nil, n__nil] > tt
[n__a, a] > tt
[n__e, e] > tt
[n__i, i] > tt
[n__o, o] > tt
[n__u, u] > tt


Status:
___2: [1,2]
nil: multiset status
U11_2: multiset status
tt: multiset status
isNeList_1: multiset status
U21_3: [3,2,1]
U22_2: multiset status
isList_1: multiset status
U23_1: multiset status
U31_2: [2,1]
isQid_1: multiset status
U41_3: multiset status
U42_2: multiset status
U43_1: multiset status
U51_3: multiset status
U52_2: multiset status
U53_1: multiset status
U61_2: multiset status
U62_1: [1]
U71_2: multiset status
isNePal_1: multiset status
and_2: multiset status
n__nil: multiset status
n_____2: [1,2]
n__and_2: multiset status
n__isPal_1: 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)))
   U23(tt) -> tt
   U31(tt, V) -> U32(isQid(activate(V)))
   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)))
   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, n____(P, I))) -> and(and(isQid(activate(I)), n__isPalListKind(activate(I))), n__and(n__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




----------------------------------------

(2)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   U12(tt) -> tt
   U32(tt) -> tt
   U72(tt) -> tt
   nil -> n__nil
   __(X1, X2) -> n____(X1, X2)
   isPalListKind(X) -> n__isPalListKind(X)
   and(X1, X2) -> n__and(X1, X2)
   isPal(X) -> n__isPal(X)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(X1, X2)) -> __(activate(X1), activate(X2))
   activate(n__isPalListKind(X)) -> isPalListKind(X)
   activate(n__and(X1, X2)) -> and(activate(X1), X2)
   activate(n__isPal(X)) -> isPal(X)
   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.

----------------------------------------

(3) QTRSRRRProof (EQUIVALENT)
Used ordering:
Knuth-Bendix order [KBO] with precedence:activate_1 > o > U32_1 > u > n__u > n__o > ___2 > nil > n__nil > isPalListKind_1 > tt > n__isPalListKind_1 > a > n__a > isPal_1 > n_____2 > i > n__i > e > n__e > U12_1 > U72_1 > and_2 > n__and_2 > n__isPal_1

and weight map:

   tt=1
   nil=1
   n__nil=1
   a=1
   n__a=1
   e=1
   n__e=1
   i=1
   n__i=1
   o=1
   n__o=1
   u=2
   n__u=2
   U12_1=1
   U32_1=1
   U72_1=1
   isPalListKind_1=1
   n__isPalListKind_1=1
   isPal_1=2
   n__isPal_1=2
   activate_1=0
   ___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
   U32(tt) -> tt
   U72(tt) -> tt
   nil -> n__nil
   __(X1, X2) -> n____(X1, X2)
   isPalListKind(X) -> n__isPalListKind(X)
   and(X1, X2) -> n__and(X1, X2)
   isPal(X) -> n__isPal(X)
   a -> n__a
   e -> n__e
   i -> n__i
   o -> n__o
   u -> n__u
   activate(n__nil) -> nil
   activate(n____(X1, X2)) -> __(activate(X1), activate(X2))
   activate(n__isPalListKind(X)) -> isPalListKind(X)
   activate(n__and(X1, X2)) -> and(activate(X1), X2)
   activate(n__isPal(X)) -> isPal(X)
   activate(n__a) -> a
   activate(n__e) -> e
   activate(n__i) -> i
   activate(n__o) -> o
   activate(n__u) -> u
   activate(X) -> X




----------------------------------------

(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