1129.42/291.57 WORST_CASE(Omega(n^2), ?) 1129.42/291.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1129.42/291.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1129.42/291.61 1129.42/291.61 1129.42/291.61 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1129.42/291.61 1129.42/291.61 (0) CpxTRS 1129.42/291.61 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1129.42/291.61 (2) CpxTRS 1129.42/291.61 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1129.42/291.61 (4) typed CpxTrs 1129.42/291.61 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1129.42/291.61 (6) typed CpxTrs 1129.42/291.61 (7) RewriteLemmaProof [LOWER BOUND(ID), 1487 ms] 1129.42/291.61 (8) BEST 1129.42/291.61 (9) proven lower bound 1129.42/291.61 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1129.42/291.61 (11) BOUNDS(n^1, INF) 1129.42/291.61 (12) typed CpxTrs 1129.42/291.61 (13) RewriteLemmaProof [LOWER BOUND(ID), 3503 ms] 1129.42/291.61 (14) BEST 1129.42/291.61 (15) proven lower bound 1129.42/291.61 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1129.42/291.61 (17) BOUNDS(n^2, INF) 1129.42/291.61 (18) typed CpxTrs 1129.42/291.61 (19) RewriteLemmaProof [LOWER BOUND(ID), 751 ms] 1129.42/291.61 (20) BOUNDS(1, INF) 1129.42/291.61 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (0) 1129.42/291.61 Obligation: 1129.42/291.61 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1129.42/291.61 1129.42/291.61 1129.42/291.61 The TRS R consists of the following rules: 1129.42/291.61 1129.42/291.61 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1129.42/291.61 __(X, nil) -> X 1129.42/291.61 __(nil, X) -> X 1129.42/291.61 and(tt, X) -> activate(X) 1129.42/291.61 isList(V) -> isNeList(activate(V)) 1129.42/291.61 isList(n__nil) -> tt 1129.42/291.61 isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNeList(V) -> isQid(activate(V)) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNePal(V) -> isQid(activate(V)) 1129.42/291.61 isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) 1129.42/291.61 isPal(V) -> isNePal(activate(V)) 1129.42/291.61 isPal(n__nil) -> tt 1129.42/291.61 isQid(n__a) -> tt 1129.42/291.61 isQid(n__e) -> tt 1129.42/291.61 isQid(n__i) -> tt 1129.42/291.61 isQid(n__o) -> tt 1129.42/291.61 isQid(n__u) -> tt 1129.42/291.61 nil -> n__nil 1129.42/291.61 __(X1, X2) -> n____(X1, X2) 1129.42/291.61 isList(X) -> n__isList(X) 1129.42/291.61 isNeList(X) -> n__isNeList(X) 1129.42/291.61 isPal(X) -> n__isPal(X) 1129.42/291.61 a -> n__a 1129.42/291.61 e -> n__e 1129.42/291.61 i -> n__i 1129.42/291.61 o -> n__o 1129.42/291.61 u -> n__u 1129.42/291.61 activate(n__nil) -> nil 1129.42/291.61 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1129.42/291.61 activate(n__isList(X)) -> isList(X) 1129.42/291.61 activate(n__isNeList(X)) -> isNeList(X) 1129.42/291.61 activate(n__isPal(X)) -> isPal(X) 1129.42/291.61 activate(n__a) -> a 1129.42/291.61 activate(n__e) -> e 1129.42/291.61 activate(n__i) -> i 1129.42/291.61 activate(n__o) -> o 1129.42/291.61 activate(n__u) -> u 1129.42/291.61 activate(X) -> X 1129.42/291.61 1129.42/291.61 S is empty. 1129.42/291.61 Rewrite Strategy: FULL 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1129.42/291.61 Renamed function symbols to avoid clashes with predefined symbol. 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (2) 1129.42/291.61 Obligation: 1129.42/291.61 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1129.42/291.61 1129.42/291.61 1129.42/291.61 The TRS R consists of the following rules: 1129.42/291.61 1129.42/291.61 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1129.42/291.61 __(X, nil) -> X 1129.42/291.61 __(nil, X) -> X 1129.42/291.61 and(tt, X) -> activate(X) 1129.42/291.61 isList(V) -> isNeList(activate(V)) 1129.42/291.61 isList(n__nil) -> tt 1129.42/291.61 isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNeList(V) -> isQid(activate(V)) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNePal(V) -> isQid(activate(V)) 1129.42/291.61 isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) 1129.42/291.61 isPal(V) -> isNePal(activate(V)) 1129.42/291.61 isPal(n__nil) -> tt 1129.42/291.61 isQid(n__a) -> tt 1129.42/291.61 isQid(n__e) -> tt 1129.42/291.61 isQid(n__i) -> tt 1129.42/291.61 isQid(n__o) -> tt 1129.42/291.61 isQid(n__u) -> tt 1129.42/291.61 nil -> n__nil 1129.42/291.61 __(X1, X2) -> n____(X1, X2) 1129.42/291.61 isList(X) -> n__isList(X) 1129.42/291.61 isNeList(X) -> n__isNeList(X) 1129.42/291.61 isPal(X) -> n__isPal(X) 1129.42/291.61 a -> n__a 1129.42/291.61 e -> n__e 1129.42/291.61 i -> n__i 1129.42/291.61 o -> n__o 1129.42/291.61 u -> n__u 1129.42/291.61 activate(n__nil) -> nil 1129.42/291.61 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1129.42/291.61 activate(n__isList(X)) -> isList(X) 1129.42/291.61 activate(n__isNeList(X)) -> isNeList(X) 1129.42/291.61 activate(n__isPal(X)) -> isPal(X) 1129.42/291.61 activate(n__a) -> a 1129.42/291.61 activate(n__e) -> e 1129.42/291.61 activate(n__i) -> i 1129.42/291.61 activate(n__o) -> o 1129.42/291.61 activate(n__u) -> u 1129.42/291.61 activate(X) -> X 1129.42/291.61 1129.42/291.61 S is empty. 1129.42/291.61 Rewrite Strategy: FULL 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1129.42/291.61 Infered types. 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (4) 1129.42/291.61 Obligation: 1129.42/291.61 TRS: 1129.42/291.61 Rules: 1129.42/291.61 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1129.42/291.61 __(X, nil) -> X 1129.42/291.61 __(nil, X) -> X 1129.42/291.61 and(tt, X) -> activate(X) 1129.42/291.61 isList(V) -> isNeList(activate(V)) 1129.42/291.61 isList(n__nil) -> tt 1129.42/291.61 isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNeList(V) -> isQid(activate(V)) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNePal(V) -> isQid(activate(V)) 1129.42/291.61 isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) 1129.42/291.61 isPal(V) -> isNePal(activate(V)) 1129.42/291.61 isPal(n__nil) -> tt 1129.42/291.61 isQid(n__a) -> tt 1129.42/291.61 isQid(n__e) -> tt 1129.42/291.61 isQid(n__i) -> tt 1129.42/291.61 isQid(n__o) -> tt 1129.42/291.61 isQid(n__u) -> tt 1129.42/291.61 nil -> n__nil 1129.42/291.61 __(X1, X2) -> n____(X1, X2) 1129.42/291.61 isList(X) -> n__isList(X) 1129.42/291.61 isNeList(X) -> n__isNeList(X) 1129.42/291.61 isPal(X) -> n__isPal(X) 1129.42/291.61 a -> n__a 1129.42/291.61 e -> n__e 1129.42/291.61 i -> n__i 1129.42/291.61 o -> n__o 1129.42/291.61 u -> n__u 1129.42/291.61 activate(n__nil) -> nil 1129.42/291.61 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1129.42/291.61 activate(n__isList(X)) -> isList(X) 1129.42/291.61 activate(n__isNeList(X)) -> isNeList(X) 1129.42/291.61 activate(n__isPal(X)) -> isPal(X) 1129.42/291.61 activate(n__a) -> a 1129.42/291.61 activate(n__e) -> e 1129.42/291.61 activate(n__i) -> i 1129.42/291.61 activate(n__o) -> o 1129.42/291.61 activate(n__u) -> u 1129.42/291.61 activate(X) -> X 1129.42/291.61 1129.42/291.61 Types: 1129.42/291.61 __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (5) OrderProof (LOWER BOUND(ID)) 1129.42/291.61 Heuristically decided to analyse the following defined symbols: 1129.42/291.61 __, and, activate, isList, isNeList, isNePal, isPal 1129.42/291.61 1129.42/291.61 They will be analysed ascendingly in the following order: 1129.42/291.61 __ < activate 1129.42/291.61 and = activate 1129.42/291.61 and = isList 1129.42/291.61 and = isNeList 1129.42/291.61 and = isNePal 1129.42/291.61 and = isPal 1129.42/291.61 activate = isList 1129.42/291.61 activate = isNeList 1129.42/291.61 activate = isNePal 1129.42/291.61 activate = isPal 1129.42/291.61 isList = isNeList 1129.42/291.61 isList = isNePal 1129.42/291.61 isList = isPal 1129.42/291.61 isNeList = isNePal 1129.42/291.61 isNeList = isPal 1129.42/291.61 isNePal = isPal 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (6) 1129.42/291.61 Obligation: 1129.42/291.61 TRS: 1129.42/291.61 Rules: 1129.42/291.61 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1129.42/291.61 __(X, nil) -> X 1129.42/291.61 __(nil, X) -> X 1129.42/291.61 and(tt, X) -> activate(X) 1129.42/291.61 isList(V) -> isNeList(activate(V)) 1129.42/291.61 isList(n__nil) -> tt 1129.42/291.61 isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNeList(V) -> isQid(activate(V)) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNePal(V) -> isQid(activate(V)) 1129.42/291.61 isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) 1129.42/291.61 isPal(V) -> isNePal(activate(V)) 1129.42/291.61 isPal(n__nil) -> tt 1129.42/291.61 isQid(n__a) -> tt 1129.42/291.61 isQid(n__e) -> tt 1129.42/291.61 isQid(n__i) -> tt 1129.42/291.61 isQid(n__o) -> tt 1129.42/291.61 isQid(n__u) -> tt 1129.42/291.61 nil -> n__nil 1129.42/291.61 __(X1, X2) -> n____(X1, X2) 1129.42/291.61 isList(X) -> n__isList(X) 1129.42/291.61 isNeList(X) -> n__isNeList(X) 1129.42/291.61 isPal(X) -> n__isPal(X) 1129.42/291.61 a -> n__a 1129.42/291.61 e -> n__e 1129.42/291.61 i -> n__i 1129.42/291.61 o -> n__o 1129.42/291.61 u -> n__u 1129.42/291.61 activate(n__nil) -> nil 1129.42/291.61 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1129.42/291.61 activate(n__isList(X)) -> isList(X) 1129.42/291.61 activate(n__isNeList(X)) -> isNeList(X) 1129.42/291.61 activate(n__isPal(X)) -> isPal(X) 1129.42/291.61 activate(n__a) -> a 1129.42/291.61 activate(n__e) -> e 1129.42/291.61 activate(n__i) -> i 1129.42/291.61 activate(n__o) -> o 1129.42/291.61 activate(n__u) -> u 1129.42/291.61 activate(X) -> X 1129.42/291.61 1129.42/291.61 Types: 1129.42/291.61 __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 1129.42/291.61 1129.42/291.61 Generator Equations: 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) 1129.42/291.61 1129.42/291.61 1129.42/291.61 The following defined symbols remain to be analysed: 1129.42/291.61 __, and, activate, isList, isNeList, isNePal, isPal 1129.42/291.61 1129.42/291.61 They will be analysed ascendingly in the following order: 1129.42/291.61 __ < activate 1129.42/291.61 and = activate 1129.42/291.61 and = isList 1129.42/291.61 and = isNeList 1129.42/291.61 and = isNePal 1129.42/291.61 and = isPal 1129.42/291.61 activate = isList 1129.42/291.61 activate = isNeList 1129.42/291.61 activate = isNePal 1129.42/291.61 activate = isPal 1129.42/291.61 isList = isNeList 1129.42/291.61 isList = isNePal 1129.42/291.61 isList = isPal 1129.42/291.61 isNeList = isNePal 1129.42/291.61 isNeList = isPal 1129.42/291.61 isNePal = isPal 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1129.42/291.61 Proved the following rewrite lemma: 1129.42/291.61 activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), rt in Omega(1 + n27_0) 1129.42/291.61 1129.42/291.61 Induction Base: 1129.42/291.61 activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0)) ->_R^Omega(1) 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) 1129.42/291.61 1129.42/291.61 Induction Step: 1129.42/291.61 activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(n27_0, 1))) ->_R^Omega(1) 1129.42/291.61 __(activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)), activate(n__nil)) ->_IH 1129.42/291.61 __(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(c28_0), activate(n__nil)) ->_R^Omega(1) 1129.42/291.61 __(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), n__nil) ->_R^Omega(1) 1129.42/291.61 n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), n__nil) 1129.42/291.61 1129.42/291.61 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (8) 1129.42/291.61 Complex Obligation (BEST) 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (9) 1129.42/291.61 Obligation: 1129.42/291.61 Proved the lower bound n^1 for the following obligation: 1129.42/291.61 1129.42/291.61 TRS: 1129.42/291.61 Rules: 1129.42/291.61 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1129.42/291.61 __(X, nil) -> X 1129.42/291.61 __(nil, X) -> X 1129.42/291.61 and(tt, X) -> activate(X) 1129.42/291.61 isList(V) -> isNeList(activate(V)) 1129.42/291.61 isList(n__nil) -> tt 1129.42/291.61 isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNeList(V) -> isQid(activate(V)) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNePal(V) -> isQid(activate(V)) 1129.42/291.61 isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) 1129.42/291.61 isPal(V) -> isNePal(activate(V)) 1129.42/291.61 isPal(n__nil) -> tt 1129.42/291.61 isQid(n__a) -> tt 1129.42/291.61 isQid(n__e) -> tt 1129.42/291.61 isQid(n__i) -> tt 1129.42/291.61 isQid(n__o) -> tt 1129.42/291.61 isQid(n__u) -> tt 1129.42/291.61 nil -> n__nil 1129.42/291.61 __(X1, X2) -> n____(X1, X2) 1129.42/291.61 isList(X) -> n__isList(X) 1129.42/291.61 isNeList(X) -> n__isNeList(X) 1129.42/291.61 isPal(X) -> n__isPal(X) 1129.42/291.61 a -> n__a 1129.42/291.61 e -> n__e 1129.42/291.61 i -> n__i 1129.42/291.61 o -> n__o 1129.42/291.61 u -> n__u 1129.42/291.61 activate(n__nil) -> nil 1129.42/291.61 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1129.42/291.61 activate(n__isList(X)) -> isList(X) 1129.42/291.61 activate(n__isNeList(X)) -> isNeList(X) 1129.42/291.61 activate(n__isPal(X)) -> isPal(X) 1129.42/291.61 activate(n__a) -> a 1129.42/291.61 activate(n__e) -> e 1129.42/291.61 activate(n__i) -> i 1129.42/291.61 activate(n__o) -> o 1129.42/291.61 activate(n__u) -> u 1129.42/291.61 activate(X) -> X 1129.42/291.61 1129.42/291.61 Types: 1129.42/291.61 __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 1129.42/291.61 1129.42/291.61 Generator Equations: 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) 1129.42/291.61 1129.42/291.61 1129.42/291.61 The following defined symbols remain to be analysed: 1129.42/291.61 activate, and, isList, isNeList, isNePal, isPal 1129.42/291.61 1129.42/291.61 They will be analysed ascendingly in the following order: 1129.42/291.61 and = activate 1129.42/291.61 and = isList 1129.42/291.61 and = isNeList 1129.42/291.61 and = isNePal 1129.42/291.61 and = isPal 1129.42/291.61 activate = isList 1129.42/291.61 activate = isNeList 1129.42/291.61 activate = isNePal 1129.42/291.61 activate = isPal 1129.42/291.61 isList = isNeList 1129.42/291.61 isList = isNePal 1129.42/291.61 isList = isPal 1129.42/291.61 isNeList = isNePal 1129.42/291.61 isNeList = isPal 1129.42/291.61 isNePal = isPal 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (10) LowerBoundPropagationProof (FINISHED) 1129.42/291.61 Propagated lower bound. 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (11) 1129.42/291.61 BOUNDS(n^1, INF) 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (12) 1129.42/291.61 Obligation: 1129.42/291.61 TRS: 1129.42/291.61 Rules: 1129.42/291.61 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1129.42/291.61 __(X, nil) -> X 1129.42/291.61 __(nil, X) -> X 1129.42/291.61 and(tt, X) -> activate(X) 1129.42/291.61 isList(V) -> isNeList(activate(V)) 1129.42/291.61 isList(n__nil) -> tt 1129.42/291.61 isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNeList(V) -> isQid(activate(V)) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNePal(V) -> isQid(activate(V)) 1129.42/291.61 isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) 1129.42/291.61 isPal(V) -> isNePal(activate(V)) 1129.42/291.61 isPal(n__nil) -> tt 1129.42/291.61 isQid(n__a) -> tt 1129.42/291.61 isQid(n__e) -> tt 1129.42/291.61 isQid(n__i) -> tt 1129.42/291.61 isQid(n__o) -> tt 1129.42/291.61 isQid(n__u) -> tt 1129.42/291.61 nil -> n__nil 1129.42/291.61 __(X1, X2) -> n____(X1, X2) 1129.42/291.61 isList(X) -> n__isList(X) 1129.42/291.61 isNeList(X) -> n__isNeList(X) 1129.42/291.61 isPal(X) -> n__isPal(X) 1129.42/291.61 a -> n__a 1129.42/291.61 e -> n__e 1129.42/291.61 i -> n__i 1129.42/291.61 o -> n__o 1129.42/291.61 u -> n__u 1129.42/291.61 activate(n__nil) -> nil 1129.42/291.61 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1129.42/291.61 activate(n__isList(X)) -> isList(X) 1129.42/291.61 activate(n__isNeList(X)) -> isNeList(X) 1129.42/291.61 activate(n__isPal(X)) -> isPal(X) 1129.42/291.61 activate(n__a) -> a 1129.42/291.61 activate(n__e) -> e 1129.42/291.61 activate(n__i) -> i 1129.42/291.61 activate(n__o) -> o 1129.42/291.61 activate(n__u) -> u 1129.42/291.61 activate(X) -> X 1129.42/291.61 1129.42/291.61 Types: 1129.42/291.61 __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 1129.42/291.61 1129.42/291.61 Lemmas: 1129.42/291.61 activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), rt in Omega(1 + n27_0) 1129.42/291.61 1129.42/291.61 1129.42/291.61 Generator Equations: 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) 1129.42/291.61 1129.42/291.61 1129.42/291.61 The following defined symbols remain to be analysed: 1129.42/291.61 isList, and, isNeList, isNePal, isPal 1129.42/291.61 1129.42/291.61 They will be analysed ascendingly in the following order: 1129.42/291.61 and = activate 1129.42/291.61 and = isList 1129.42/291.61 and = isNeList 1129.42/291.61 and = isNePal 1129.42/291.61 and = isPal 1129.42/291.61 activate = isList 1129.42/291.61 activate = isNeList 1129.42/291.61 activate = isNePal 1129.42/291.61 activate = isPal 1129.42/291.61 isList = isNeList 1129.42/291.61 isList = isNePal 1129.42/291.61 isList = isPal 1129.42/291.61 isNeList = isNePal 1129.42/291.61 isNeList = isPal 1129.42/291.61 isNePal = isPal 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1129.42/291.61 Proved the following rewrite lemma: 1129.42/291.61 isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n65578_0)) -> tt, rt in Omega(1 + n65578_0 + n65578_0^2) 1129.42/291.61 1129.42/291.61 Induction Base: 1129.42/291.61 isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0)) ->_R^Omega(1) 1129.42/291.61 tt 1129.42/291.61 1129.42/291.61 Induction Step: 1129.42/291.61 isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(n65578_0, 1))) ->_R^Omega(1) 1129.42/291.61 and(isList(activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n65578_0))), n__isList(activate(n__nil))) ->_L^Omega(1 + n65578_0) 1129.42/291.61 and(isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n65578_0)), n__isList(activate(n__nil))) ->_IH 1129.42/291.61 and(tt, n__isList(activate(n__nil))) ->_L^Omega(1) 1129.42/291.61 and(tt, n__isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0))) ->_R^Omega(1) 1129.42/291.61 activate(n__isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0))) ->_R^Omega(1) 1129.42/291.61 isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0)) ->_R^Omega(1) 1129.42/291.61 tt 1129.42/291.61 1129.42/291.61 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (14) 1129.42/291.61 Complex Obligation (BEST) 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (15) 1129.42/291.61 Obligation: 1129.42/291.61 Proved the lower bound n^2 for the following obligation: 1129.42/291.61 1129.42/291.61 TRS: 1129.42/291.61 Rules: 1129.42/291.61 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1129.42/291.61 __(X, nil) -> X 1129.42/291.61 __(nil, X) -> X 1129.42/291.61 and(tt, X) -> activate(X) 1129.42/291.61 isList(V) -> isNeList(activate(V)) 1129.42/291.61 isList(n__nil) -> tt 1129.42/291.61 isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNeList(V) -> isQid(activate(V)) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNePal(V) -> isQid(activate(V)) 1129.42/291.61 isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) 1129.42/291.61 isPal(V) -> isNePal(activate(V)) 1129.42/291.61 isPal(n__nil) -> tt 1129.42/291.61 isQid(n__a) -> tt 1129.42/291.61 isQid(n__e) -> tt 1129.42/291.61 isQid(n__i) -> tt 1129.42/291.61 isQid(n__o) -> tt 1129.42/291.61 isQid(n__u) -> tt 1129.42/291.61 nil -> n__nil 1129.42/291.61 __(X1, X2) -> n____(X1, X2) 1129.42/291.61 isList(X) -> n__isList(X) 1129.42/291.61 isNeList(X) -> n__isNeList(X) 1129.42/291.61 isPal(X) -> n__isPal(X) 1129.42/291.61 a -> n__a 1129.42/291.61 e -> n__e 1129.42/291.61 i -> n__i 1129.42/291.61 o -> n__o 1129.42/291.61 u -> n__u 1129.42/291.61 activate(n__nil) -> nil 1129.42/291.61 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1129.42/291.61 activate(n__isList(X)) -> isList(X) 1129.42/291.61 activate(n__isNeList(X)) -> isNeList(X) 1129.42/291.61 activate(n__isPal(X)) -> isPal(X) 1129.42/291.61 activate(n__a) -> a 1129.42/291.61 activate(n__e) -> e 1129.42/291.61 activate(n__i) -> i 1129.42/291.61 activate(n__o) -> o 1129.42/291.61 activate(n__u) -> u 1129.42/291.61 activate(X) -> X 1129.42/291.61 1129.42/291.61 Types: 1129.42/291.61 __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 1129.42/291.61 1129.42/291.61 Lemmas: 1129.42/291.61 activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), rt in Omega(1 + n27_0) 1129.42/291.61 1129.42/291.61 1129.42/291.61 Generator Equations: 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) 1129.42/291.61 1129.42/291.61 1129.42/291.61 The following defined symbols remain to be analysed: 1129.42/291.61 isList, and, isNeList, isNePal, isPal 1129.42/291.61 1129.42/291.61 They will be analysed ascendingly in the following order: 1129.42/291.61 and = activate 1129.42/291.61 and = isList 1129.42/291.61 and = isNeList 1129.42/291.61 and = isNePal 1129.42/291.61 and = isPal 1129.42/291.61 activate = isList 1129.42/291.61 activate = isNeList 1129.42/291.61 activate = isNePal 1129.42/291.61 activate = isPal 1129.42/291.61 isList = isNeList 1129.42/291.61 isList = isNePal 1129.42/291.61 isList = isPal 1129.42/291.61 isNeList = isNePal 1129.42/291.61 isNeList = isPal 1129.42/291.61 isNePal = isPal 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (16) LowerBoundPropagationProof (FINISHED) 1129.42/291.61 Propagated lower bound. 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (17) 1129.42/291.61 BOUNDS(n^2, INF) 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (18) 1129.42/291.61 Obligation: 1129.42/291.61 TRS: 1129.42/291.61 Rules: 1129.42/291.61 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1129.42/291.61 __(X, nil) -> X 1129.42/291.61 __(nil, X) -> X 1129.42/291.61 and(tt, X) -> activate(X) 1129.42/291.61 isList(V) -> isNeList(activate(V)) 1129.42/291.61 isList(n__nil) -> tt 1129.42/291.61 isList(n____(V1, V2)) -> and(isList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNeList(V) -> isQid(activate(V)) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isList(activate(V1)), n__isNeList(activate(V2))) 1129.42/291.61 isNeList(n____(V1, V2)) -> and(isNeList(activate(V1)), n__isList(activate(V2))) 1129.42/291.61 isNePal(V) -> isQid(activate(V)) 1129.42/291.61 isNePal(n____(I, n____(P, I))) -> and(isQid(activate(I)), n__isPal(activate(P))) 1129.42/291.61 isPal(V) -> isNePal(activate(V)) 1129.42/291.61 isPal(n__nil) -> tt 1129.42/291.61 isQid(n__a) -> tt 1129.42/291.61 isQid(n__e) -> tt 1129.42/291.61 isQid(n__i) -> tt 1129.42/291.61 isQid(n__o) -> tt 1129.42/291.61 isQid(n__u) -> tt 1129.42/291.61 nil -> n__nil 1129.42/291.61 __(X1, X2) -> n____(X1, X2) 1129.42/291.61 isList(X) -> n__isList(X) 1129.42/291.61 isNeList(X) -> n__isNeList(X) 1129.42/291.61 isPal(X) -> n__isPal(X) 1129.42/291.61 a -> n__a 1129.42/291.61 e -> n__e 1129.42/291.61 i -> n__i 1129.42/291.61 o -> n__o 1129.42/291.61 u -> n__u 1129.42/291.61 activate(n__nil) -> nil 1129.42/291.61 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1129.42/291.61 activate(n__isList(X)) -> isList(X) 1129.42/291.61 activate(n__isNeList(X)) -> isNeList(X) 1129.42/291.61 activate(n__isPal(X)) -> isPal(X) 1129.42/291.61 activate(n__a) -> a 1129.42/291.61 activate(n__e) -> e 1129.42/291.61 activate(n__i) -> i 1129.42/291.61 activate(n__o) -> o 1129.42/291.61 activate(n__u) -> u 1129.42/291.61 activate(X) -> X 1129.42/291.61 1129.42/291.61 Types: 1129.42/291.61 __ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 and :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 tt :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 activate :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__nil :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n____ :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isQid :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isNeList :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isNePal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 isPal :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 n__u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 a :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 e :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 i :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 o :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 u :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 hole_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u1_0 :: tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0 :: Nat -> tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u 1129.42/291.61 1129.42/291.61 1129.42/291.61 Lemmas: 1129.42/291.61 activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n27_0), rt in Omega(1 + n27_0) 1129.42/291.61 isList(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n65578_0)) -> tt, rt in Omega(1 + n65578_0 + n65578_0^2) 1129.42/291.61 1129.42/291.61 1129.42/291.61 Generator Equations: 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) <=> n__nil 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(x, 1)) <=> n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(x), n__nil) 1129.42/291.61 1129.42/291.61 1129.42/291.61 The following defined symbols remain to be analysed: 1129.42/291.61 isNeList, and, activate, isNePal, isPal 1129.42/291.61 1129.42/291.61 They will be analysed ascendingly in the following order: 1129.42/291.61 and = activate 1129.42/291.61 and = isList 1129.42/291.61 and = isNeList 1129.42/291.61 and = isNePal 1129.42/291.61 and = isPal 1129.42/291.61 activate = isList 1129.42/291.61 activate = isNeList 1129.42/291.61 activate = isNePal 1129.42/291.61 activate = isPal 1129.42/291.61 isList = isNeList 1129.42/291.61 isList = isNePal 1129.42/291.61 isList = isPal 1129.42/291.61 isNeList = isNePal 1129.42/291.61 isNeList = isPal 1129.42/291.61 isNePal = isPal 1129.42/291.61 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1129.42/291.61 Proved the following rewrite lemma: 1129.42/291.61 activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0)) -> gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0), rt in Omega(1 + n153552_0) 1129.42/291.61 1129.42/291.61 Induction Base: 1129.42/291.61 activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0)) ->_R^Omega(1) 1129.42/291.61 gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(0) 1129.42/291.61 1129.42/291.61 Induction Step: 1129.42/291.61 activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(+(n153552_0, 1))) ->_R^Omega(1) 1129.42/291.61 __(activate(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0)), activate(n__nil)) ->_IH 1129.42/291.61 __(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(c153553_0), activate(n__nil)) ->_R^Omega(1) 1129.42/291.61 __(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0), n__nil) ->_R^Omega(1) 1129.42/291.61 n____(gen_tt:n__nil:n____:n__isList:n__isNeList:n__isPal:n__a:n__e:n__i:n__o:n__u2_0(n153552_0), n__nil) 1129.42/291.61 1129.42/291.61 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1129.42/291.61 ---------------------------------------- 1129.42/291.61 1129.42/291.61 (20) 1129.42/291.61 BOUNDS(1, INF) 1129.67/291.71 EOF