1139.55/291.58 WORST_CASE(Omega(n^2), ?) 1145.50/293.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1145.50/293.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1145.50/293.11 1145.50/293.11 1145.50/293.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1145.50/293.11 1145.50/293.11 (0) CpxTRS 1145.50/293.11 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1145.50/293.11 (2) CpxTRS 1145.50/293.11 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1145.50/293.11 (4) typed CpxTrs 1145.50/293.11 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1145.50/293.11 (6) typed CpxTrs 1145.50/293.11 (7) RewriteLemmaProof [LOWER BOUND(ID), 638 ms] 1145.50/293.11 (8) BEST 1145.50/293.11 (9) proven lower bound 1145.50/293.11 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1145.50/293.11 (11) BOUNDS(n^1, INF) 1145.50/293.11 (12) typed CpxTrs 1145.50/293.11 (13) RewriteLemmaProof [LOWER BOUND(ID), 1329 ms] 1145.50/293.11 (14) BEST 1145.50/293.11 (15) proven lower bound 1145.50/293.11 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1145.50/293.11 (17) BOUNDS(n^2, INF) 1145.50/293.11 (18) typed CpxTrs 1145.50/293.11 (19) RewriteLemmaProof [LOWER BOUND(ID), 5284 ms] 1145.50/293.11 (20) typed CpxTrs 1145.50/293.11 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (0) 1145.50/293.11 Obligation: 1145.50/293.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1145.50/293.11 1145.50/293.11 1145.50/293.11 The TRS R consists of the following rules: 1145.50/293.11 1145.50/293.11 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1145.50/293.11 __(X, nil) -> X 1145.50/293.11 __(nil, X) -> X 1145.50/293.11 U11(tt) -> tt 1145.50/293.11 U21(tt, V2) -> U22(isList(activate(V2))) 1145.50/293.11 U22(tt) -> tt 1145.50/293.11 U31(tt) -> tt 1145.50/293.11 U41(tt, V2) -> U42(isNeList(activate(V2))) 1145.50/293.11 U42(tt) -> tt 1145.50/293.11 U51(tt, V2) -> U52(isList(activate(V2))) 1145.50/293.11 U52(tt) -> tt 1145.50/293.11 U61(tt) -> tt 1145.50/293.11 U71(tt, P) -> U72(isPal(activate(P))) 1145.50/293.11 U72(tt) -> tt 1145.50/293.11 U81(tt) -> tt 1145.50/293.11 isList(V) -> U11(isNeList(activate(V))) 1145.50/293.11 isList(n__nil) -> tt 1145.50/293.11 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(V) -> U31(isQid(activate(V))) 1145.50/293.11 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 1145.50/293.11 isNePal(V) -> U61(isQid(activate(V))) 1145.50/293.11 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) 1145.50/293.11 isPal(V) -> U81(isNePal(activate(V))) 1145.50/293.11 isPal(n__nil) -> tt 1145.50/293.11 isQid(n__a) -> tt 1145.50/293.11 isQid(n__e) -> tt 1145.50/293.11 isQid(n__i) -> tt 1145.50/293.11 isQid(n__o) -> tt 1145.50/293.11 isQid(n__u) -> tt 1145.50/293.11 nil -> n__nil 1145.50/293.11 __(X1, X2) -> n____(X1, X2) 1145.50/293.11 a -> n__a 1145.50/293.11 e -> n__e 1145.50/293.11 i -> n__i 1145.50/293.11 o -> n__o 1145.50/293.11 u -> n__u 1145.50/293.11 activate(n__nil) -> nil 1145.50/293.11 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1145.50/293.11 activate(n__a) -> a 1145.50/293.11 activate(n__e) -> e 1145.50/293.11 activate(n__i) -> i 1145.50/293.11 activate(n__o) -> o 1145.50/293.11 activate(n__u) -> u 1145.50/293.11 activate(X) -> X 1145.50/293.11 1145.50/293.11 S is empty. 1145.50/293.11 Rewrite Strategy: FULL 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1145.50/293.11 Renamed function symbols to avoid clashes with predefined symbol. 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (2) 1145.50/293.11 Obligation: 1145.50/293.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1145.50/293.11 1145.50/293.11 1145.50/293.11 The TRS R consists of the following rules: 1145.50/293.11 1145.50/293.11 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1145.50/293.11 __(X, nil) -> X 1145.50/293.11 __(nil, X) -> X 1145.50/293.11 U11(tt) -> tt 1145.50/293.11 U21(tt, V2) -> U22(isList(activate(V2))) 1145.50/293.11 U22(tt) -> tt 1145.50/293.11 U31(tt) -> tt 1145.50/293.11 U41(tt, V2) -> U42(isNeList(activate(V2))) 1145.50/293.11 U42(tt) -> tt 1145.50/293.11 U51(tt, V2) -> U52(isList(activate(V2))) 1145.50/293.11 U52(tt) -> tt 1145.50/293.11 U61(tt) -> tt 1145.50/293.11 U71(tt, P) -> U72(isPal(activate(P))) 1145.50/293.11 U72(tt) -> tt 1145.50/293.11 U81(tt) -> tt 1145.50/293.11 isList(V) -> U11(isNeList(activate(V))) 1145.50/293.11 isList(n__nil) -> tt 1145.50/293.11 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(V) -> U31(isQid(activate(V))) 1145.50/293.11 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 1145.50/293.11 isNePal(V) -> U61(isQid(activate(V))) 1145.50/293.11 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) 1145.50/293.11 isPal(V) -> U81(isNePal(activate(V))) 1145.50/293.11 isPal(n__nil) -> tt 1145.50/293.11 isQid(n__a) -> tt 1145.50/293.11 isQid(n__e) -> tt 1145.50/293.11 isQid(n__i) -> tt 1145.50/293.11 isQid(n__o) -> tt 1145.50/293.11 isQid(n__u) -> tt 1145.50/293.11 nil -> n__nil 1145.50/293.11 __(X1, X2) -> n____(X1, X2) 1145.50/293.11 a -> n__a 1145.50/293.11 e -> n__e 1145.50/293.11 i -> n__i 1145.50/293.11 o -> n__o 1145.50/293.11 u -> n__u 1145.50/293.11 activate(n__nil) -> nil 1145.50/293.11 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1145.50/293.11 activate(n__a) -> a 1145.50/293.11 activate(n__e) -> e 1145.50/293.11 activate(n__i) -> i 1145.50/293.11 activate(n__o) -> o 1145.50/293.11 activate(n__u) -> u 1145.50/293.11 activate(X) -> X 1145.50/293.11 1145.50/293.11 S is empty. 1145.50/293.11 Rewrite Strategy: FULL 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1145.50/293.11 Infered types. 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (4) 1145.50/293.11 Obligation: 1145.50/293.11 TRS: 1145.50/293.11 Rules: 1145.50/293.11 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1145.50/293.11 __(X, nil) -> X 1145.50/293.11 __(nil, X) -> X 1145.50/293.11 U11(tt) -> tt 1145.50/293.11 U21(tt, V2) -> U22(isList(activate(V2))) 1145.50/293.11 U22(tt) -> tt 1145.50/293.11 U31(tt) -> tt 1145.50/293.11 U41(tt, V2) -> U42(isNeList(activate(V2))) 1145.50/293.11 U42(tt) -> tt 1145.50/293.11 U51(tt, V2) -> U52(isList(activate(V2))) 1145.50/293.11 U52(tt) -> tt 1145.50/293.11 U61(tt) -> tt 1145.50/293.11 U71(tt, P) -> U72(isPal(activate(P))) 1145.50/293.11 U72(tt) -> tt 1145.50/293.11 U81(tt) -> tt 1145.50/293.11 isList(V) -> U11(isNeList(activate(V))) 1145.50/293.11 isList(n__nil) -> tt 1145.50/293.11 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(V) -> U31(isQid(activate(V))) 1145.50/293.11 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 1145.50/293.11 isNePal(V) -> U61(isQid(activate(V))) 1145.50/293.11 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) 1145.50/293.11 isPal(V) -> U81(isNePal(activate(V))) 1145.50/293.11 isPal(n__nil) -> tt 1145.50/293.11 isQid(n__a) -> tt 1145.50/293.11 isQid(n__e) -> tt 1145.50/293.11 isQid(n__i) -> tt 1145.50/293.11 isQid(n__o) -> tt 1145.50/293.11 isQid(n__u) -> tt 1145.50/293.11 nil -> n__nil 1145.50/293.11 __(X1, X2) -> n____(X1, X2) 1145.50/293.11 a -> n__a 1145.50/293.11 e -> n__e 1145.50/293.11 i -> n__i 1145.50/293.11 o -> n__o 1145.50/293.11 u -> n__u 1145.50/293.11 activate(n__nil) -> nil 1145.50/293.11 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1145.50/293.11 activate(n__a) -> a 1145.50/293.11 activate(n__e) -> e 1145.50/293.11 activate(n__i) -> i 1145.50/293.11 activate(n__o) -> o 1145.50/293.11 activate(n__u) -> u 1145.50/293.11 activate(X) -> X 1145.50/293.11 1145.50/293.11 Types: 1145.50/293.11 __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U11 :: tt -> tt 1145.50/293.11 tt :: tt 1145.50/293.11 U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U22 :: tt -> tt 1145.50/293.11 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U31 :: tt -> tt 1145.50/293.11 U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U42 :: tt -> tt 1145.50/293.11 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U52 :: tt -> tt 1145.50/293.11 U61 :: tt -> tt 1145.50/293.11 U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U72 :: tt -> tt 1145.50/293.11 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U81 :: tt -> tt 1145.50/293.11 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_tt2_0 :: tt 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (5) OrderProof (LOWER BOUND(ID)) 1145.50/293.11 Heuristically decided to analyse the following defined symbols: 1145.50/293.11 __, isList, activate, isNeList, isPal, isNePal 1145.50/293.11 1145.50/293.11 They will be analysed ascendingly in the following order: 1145.50/293.11 __ < activate 1145.50/293.11 activate < isList 1145.50/293.11 isList = isNeList 1145.50/293.11 activate < isNeList 1145.50/293.11 activate < isPal 1145.50/293.11 activate < isNePal 1145.50/293.11 isPal = isNePal 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (6) 1145.50/293.11 Obligation: 1145.50/293.11 TRS: 1145.50/293.11 Rules: 1145.50/293.11 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1145.50/293.11 __(X, nil) -> X 1145.50/293.11 __(nil, X) -> X 1145.50/293.11 U11(tt) -> tt 1145.50/293.11 U21(tt, V2) -> U22(isList(activate(V2))) 1145.50/293.11 U22(tt) -> tt 1145.50/293.11 U31(tt) -> tt 1145.50/293.11 U41(tt, V2) -> U42(isNeList(activate(V2))) 1145.50/293.11 U42(tt) -> tt 1145.50/293.11 U51(tt, V2) -> U52(isList(activate(V2))) 1145.50/293.11 U52(tt) -> tt 1145.50/293.11 U61(tt) -> tt 1145.50/293.11 U71(tt, P) -> U72(isPal(activate(P))) 1145.50/293.11 U72(tt) -> tt 1145.50/293.11 U81(tt) -> tt 1145.50/293.11 isList(V) -> U11(isNeList(activate(V))) 1145.50/293.11 isList(n__nil) -> tt 1145.50/293.11 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(V) -> U31(isQid(activate(V))) 1145.50/293.11 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 1145.50/293.11 isNePal(V) -> U61(isQid(activate(V))) 1145.50/293.11 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) 1145.50/293.11 isPal(V) -> U81(isNePal(activate(V))) 1145.50/293.11 isPal(n__nil) -> tt 1145.50/293.11 isQid(n__a) -> tt 1145.50/293.11 isQid(n__e) -> tt 1145.50/293.11 isQid(n__i) -> tt 1145.50/293.11 isQid(n__o) -> tt 1145.50/293.11 isQid(n__u) -> tt 1145.50/293.11 nil -> n__nil 1145.50/293.11 __(X1, X2) -> n____(X1, X2) 1145.50/293.11 a -> n__a 1145.50/293.11 e -> n__e 1145.50/293.11 i -> n__i 1145.50/293.11 o -> n__o 1145.50/293.11 u -> n__u 1145.50/293.11 activate(n__nil) -> nil 1145.50/293.11 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1145.50/293.11 activate(n__a) -> a 1145.50/293.11 activate(n__e) -> e 1145.50/293.11 activate(n__i) -> i 1145.50/293.11 activate(n__o) -> o 1145.50/293.11 activate(n__u) -> u 1145.50/293.11 activate(X) -> X 1145.50/293.11 1145.50/293.11 Types: 1145.50/293.11 __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U11 :: tt -> tt 1145.50/293.11 tt :: tt 1145.50/293.11 U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U22 :: tt -> tt 1145.50/293.11 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U31 :: tt -> tt 1145.50/293.11 U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U42 :: tt -> tt 1145.50/293.11 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U52 :: tt -> tt 1145.50/293.11 U61 :: tt -> tt 1145.50/293.11 U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U72 :: tt -> tt 1145.50/293.11 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U81 :: tt -> tt 1145.50/293.11 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_tt2_0 :: tt 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 1145.50/293.11 1145.50/293.11 Generator Equations: 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) 1145.50/293.11 1145.50/293.11 1145.50/293.11 The following defined symbols remain to be analysed: 1145.50/293.11 __, isList, activate, isNeList, isPal, isNePal 1145.50/293.11 1145.50/293.11 They will be analysed ascendingly in the following order: 1145.50/293.11 __ < activate 1145.50/293.11 activate < isList 1145.50/293.11 isList = isNeList 1145.50/293.11 activate < isNeList 1145.50/293.11 activate < isPal 1145.50/293.11 activate < isNePal 1145.50/293.11 isPal = isNePal 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1145.50/293.11 Proved the following rewrite lemma: 1145.50/293.11 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), rt in Omega(1 + n28_0) 1145.50/293.11 1145.50/293.11 Induction Base: 1145.50/293.11 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) 1145.50/293.11 1145.50/293.11 Induction Step: 1145.50/293.11 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n28_0, 1))) ->_R^Omega(1) 1145.50/293.11 __(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)), activate(n__nil)) ->_IH 1145.50/293.11 __(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(c29_0), activate(n__nil)) ->_R^Omega(1) 1145.50/293.11 __(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), n__nil) ->_R^Omega(1) 1145.50/293.11 n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), n__nil) 1145.50/293.11 1145.50/293.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (8) 1145.50/293.11 Complex Obligation (BEST) 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (9) 1145.50/293.11 Obligation: 1145.50/293.11 Proved the lower bound n^1 for the following obligation: 1145.50/293.11 1145.50/293.11 TRS: 1145.50/293.11 Rules: 1145.50/293.11 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1145.50/293.11 __(X, nil) -> X 1145.50/293.11 __(nil, X) -> X 1145.50/293.11 U11(tt) -> tt 1145.50/293.11 U21(tt, V2) -> U22(isList(activate(V2))) 1145.50/293.11 U22(tt) -> tt 1145.50/293.11 U31(tt) -> tt 1145.50/293.11 U41(tt, V2) -> U42(isNeList(activate(V2))) 1145.50/293.11 U42(tt) -> tt 1145.50/293.11 U51(tt, V2) -> U52(isList(activate(V2))) 1145.50/293.11 U52(tt) -> tt 1145.50/293.11 U61(tt) -> tt 1145.50/293.11 U71(tt, P) -> U72(isPal(activate(P))) 1145.50/293.11 U72(tt) -> tt 1145.50/293.11 U81(tt) -> tt 1145.50/293.11 isList(V) -> U11(isNeList(activate(V))) 1145.50/293.11 isList(n__nil) -> tt 1145.50/293.11 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(V) -> U31(isQid(activate(V))) 1145.50/293.11 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 1145.50/293.11 isNePal(V) -> U61(isQid(activate(V))) 1145.50/293.11 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) 1145.50/293.11 isPal(V) -> U81(isNePal(activate(V))) 1145.50/293.11 isPal(n__nil) -> tt 1145.50/293.11 isQid(n__a) -> tt 1145.50/293.11 isQid(n__e) -> tt 1145.50/293.11 isQid(n__i) -> tt 1145.50/293.11 isQid(n__o) -> tt 1145.50/293.11 isQid(n__u) -> tt 1145.50/293.11 nil -> n__nil 1145.50/293.11 __(X1, X2) -> n____(X1, X2) 1145.50/293.11 a -> n__a 1145.50/293.11 e -> n__e 1145.50/293.11 i -> n__i 1145.50/293.11 o -> n__o 1145.50/293.11 u -> n__u 1145.50/293.11 activate(n__nil) -> nil 1145.50/293.11 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1145.50/293.11 activate(n__a) -> a 1145.50/293.11 activate(n__e) -> e 1145.50/293.11 activate(n__i) -> i 1145.50/293.11 activate(n__o) -> o 1145.50/293.11 activate(n__u) -> u 1145.50/293.11 activate(X) -> X 1145.50/293.11 1145.50/293.11 Types: 1145.50/293.11 __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U11 :: tt -> tt 1145.50/293.11 tt :: tt 1145.50/293.11 U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U22 :: tt -> tt 1145.50/293.11 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U31 :: tt -> tt 1145.50/293.11 U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U42 :: tt -> tt 1145.50/293.11 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U52 :: tt -> tt 1145.50/293.11 U61 :: tt -> tt 1145.50/293.11 U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U72 :: tt -> tt 1145.50/293.11 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U81 :: tt -> tt 1145.50/293.11 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_tt2_0 :: tt 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 1145.50/293.11 1145.50/293.11 Generator Equations: 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) 1145.50/293.11 1145.50/293.11 1145.50/293.11 The following defined symbols remain to be analysed: 1145.50/293.11 activate, isList, isNeList, isPal, isNePal 1145.50/293.11 1145.50/293.11 They will be analysed ascendingly in the following order: 1145.50/293.11 activate < isList 1145.50/293.11 isList = isNeList 1145.50/293.11 activate < isNeList 1145.50/293.11 activate < isPal 1145.50/293.11 activate < isNePal 1145.50/293.11 isPal = isNePal 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (10) LowerBoundPropagationProof (FINISHED) 1145.50/293.11 Propagated lower bound. 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (11) 1145.50/293.11 BOUNDS(n^1, INF) 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (12) 1145.50/293.11 Obligation: 1145.50/293.11 TRS: 1145.50/293.11 Rules: 1145.50/293.11 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1145.50/293.11 __(X, nil) -> X 1145.50/293.11 __(nil, X) -> X 1145.50/293.11 U11(tt) -> tt 1145.50/293.11 U21(tt, V2) -> U22(isList(activate(V2))) 1145.50/293.11 U22(tt) -> tt 1145.50/293.11 U31(tt) -> tt 1145.50/293.11 U41(tt, V2) -> U42(isNeList(activate(V2))) 1145.50/293.11 U42(tt) -> tt 1145.50/293.11 U51(tt, V2) -> U52(isList(activate(V2))) 1145.50/293.11 U52(tt) -> tt 1145.50/293.11 U61(tt) -> tt 1145.50/293.11 U71(tt, P) -> U72(isPal(activate(P))) 1145.50/293.11 U72(tt) -> tt 1145.50/293.11 U81(tt) -> tt 1145.50/293.11 isList(V) -> U11(isNeList(activate(V))) 1145.50/293.11 isList(n__nil) -> tt 1145.50/293.11 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(V) -> U31(isQid(activate(V))) 1145.50/293.11 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 1145.50/293.11 isNePal(V) -> U61(isQid(activate(V))) 1145.50/293.11 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) 1145.50/293.11 isPal(V) -> U81(isNePal(activate(V))) 1145.50/293.11 isPal(n__nil) -> tt 1145.50/293.11 isQid(n__a) -> tt 1145.50/293.11 isQid(n__e) -> tt 1145.50/293.11 isQid(n__i) -> tt 1145.50/293.11 isQid(n__o) -> tt 1145.50/293.11 isQid(n__u) -> tt 1145.50/293.11 nil -> n__nil 1145.50/293.11 __(X1, X2) -> n____(X1, X2) 1145.50/293.11 a -> n__a 1145.50/293.11 e -> n__e 1145.50/293.11 i -> n__i 1145.50/293.11 o -> n__o 1145.50/293.11 u -> n__u 1145.50/293.11 activate(n__nil) -> nil 1145.50/293.11 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1145.50/293.11 activate(n__a) -> a 1145.50/293.11 activate(n__e) -> e 1145.50/293.11 activate(n__i) -> i 1145.50/293.11 activate(n__o) -> o 1145.50/293.11 activate(n__u) -> u 1145.50/293.11 activate(X) -> X 1145.50/293.11 1145.50/293.11 Types: 1145.50/293.11 __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U11 :: tt -> tt 1145.50/293.11 tt :: tt 1145.50/293.11 U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U22 :: tt -> tt 1145.50/293.11 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U31 :: tt -> tt 1145.50/293.11 U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U42 :: tt -> tt 1145.50/293.11 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U52 :: tt -> tt 1145.50/293.11 U61 :: tt -> tt 1145.50/293.11 U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U72 :: tt -> tt 1145.50/293.11 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U81 :: tt -> tt 1145.50/293.11 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_tt2_0 :: tt 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 1145.50/293.11 1145.50/293.11 Lemmas: 1145.50/293.11 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), rt in Omega(1 + n28_0) 1145.50/293.11 1145.50/293.11 1145.50/293.11 Generator Equations: 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) 1145.50/293.11 1145.50/293.11 1145.50/293.11 The following defined symbols remain to be analysed: 1145.50/293.11 isNePal, isList, isNeList, isPal 1145.50/293.11 1145.50/293.11 They will be analysed ascendingly in the following order: 1145.50/293.11 isList = isNeList 1145.50/293.11 isPal = isNePal 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1145.50/293.11 Proved the following rewrite lemma: 1145.50/293.11 isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0)) -> *4_0, rt in Omega(n9819_0 + n9819_0^2) 1145.50/293.11 1145.50/293.11 Induction Base: 1145.50/293.11 isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) 1145.50/293.11 1145.50/293.11 Induction Step: 1145.50/293.11 isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n9819_0, 1))) ->_R^Omega(1) 1145.50/293.11 U51(isNeList(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0))), activate(n__nil)) ->_L^Omega(1 + n9819_0) 1145.50/293.11 U51(isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0)), activate(n__nil)) ->_IH 1145.50/293.11 U51(*4_0, activate(n__nil)) ->_L^Omega(1) 1145.50/293.11 U51(*4_0, gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) 1145.50/293.11 1145.50/293.11 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (14) 1145.50/293.11 Complex Obligation (BEST) 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (15) 1145.50/293.11 Obligation: 1145.50/293.11 Proved the lower bound n^2 for the following obligation: 1145.50/293.11 1145.50/293.11 TRS: 1145.50/293.11 Rules: 1145.50/293.11 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1145.50/293.11 __(X, nil) -> X 1145.50/293.11 __(nil, X) -> X 1145.50/293.11 U11(tt) -> tt 1145.50/293.11 U21(tt, V2) -> U22(isList(activate(V2))) 1145.50/293.11 U22(tt) -> tt 1145.50/293.11 U31(tt) -> tt 1145.50/293.11 U41(tt, V2) -> U42(isNeList(activate(V2))) 1145.50/293.11 U42(tt) -> tt 1145.50/293.11 U51(tt, V2) -> U52(isList(activate(V2))) 1145.50/293.11 U52(tt) -> tt 1145.50/293.11 U61(tt) -> tt 1145.50/293.11 U71(tt, P) -> U72(isPal(activate(P))) 1145.50/293.11 U72(tt) -> tt 1145.50/293.11 U81(tt) -> tt 1145.50/293.11 isList(V) -> U11(isNeList(activate(V))) 1145.50/293.11 isList(n__nil) -> tt 1145.50/293.11 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(V) -> U31(isQid(activate(V))) 1145.50/293.11 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 1145.50/293.11 isNePal(V) -> U61(isQid(activate(V))) 1145.50/293.11 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) 1145.50/293.11 isPal(V) -> U81(isNePal(activate(V))) 1145.50/293.11 isPal(n__nil) -> tt 1145.50/293.11 isQid(n__a) -> tt 1145.50/293.11 isQid(n__e) -> tt 1145.50/293.11 isQid(n__i) -> tt 1145.50/293.11 isQid(n__o) -> tt 1145.50/293.11 isQid(n__u) -> tt 1145.50/293.11 nil -> n__nil 1145.50/293.11 __(X1, X2) -> n____(X1, X2) 1145.50/293.11 a -> n__a 1145.50/293.11 e -> n__e 1145.50/293.11 i -> n__i 1145.50/293.11 o -> n__o 1145.50/293.11 u -> n__u 1145.50/293.11 activate(n__nil) -> nil 1145.50/293.11 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1145.50/293.11 activate(n__a) -> a 1145.50/293.11 activate(n__e) -> e 1145.50/293.11 activate(n__i) -> i 1145.50/293.11 activate(n__o) -> o 1145.50/293.11 activate(n__u) -> u 1145.50/293.11 activate(X) -> X 1145.50/293.11 1145.50/293.11 Types: 1145.50/293.11 __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U11 :: tt -> tt 1145.50/293.11 tt :: tt 1145.50/293.11 U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U22 :: tt -> tt 1145.50/293.11 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U31 :: tt -> tt 1145.50/293.11 U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U42 :: tt -> tt 1145.50/293.11 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U52 :: tt -> tt 1145.50/293.11 U61 :: tt -> tt 1145.50/293.11 U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U72 :: tt -> tt 1145.50/293.11 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U81 :: tt -> tt 1145.50/293.11 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_tt2_0 :: tt 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 1145.50/293.11 1145.50/293.11 Lemmas: 1145.50/293.11 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), rt in Omega(1 + n28_0) 1145.50/293.11 1145.50/293.11 1145.50/293.11 Generator Equations: 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) 1145.50/293.11 1145.50/293.11 1145.50/293.11 The following defined symbols remain to be analysed: 1145.50/293.11 isNeList, isList 1145.50/293.11 1145.50/293.11 They will be analysed ascendingly in the following order: 1145.50/293.11 isList = isNeList 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (16) LowerBoundPropagationProof (FINISHED) 1145.50/293.11 Propagated lower bound. 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (17) 1145.50/293.11 BOUNDS(n^2, INF) 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (18) 1145.50/293.11 Obligation: 1145.50/293.11 TRS: 1145.50/293.11 Rules: 1145.50/293.11 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1145.50/293.11 __(X, nil) -> X 1145.50/293.11 __(nil, X) -> X 1145.50/293.11 U11(tt) -> tt 1145.50/293.11 U21(tt, V2) -> U22(isList(activate(V2))) 1145.50/293.11 U22(tt) -> tt 1145.50/293.11 U31(tt) -> tt 1145.50/293.11 U41(tt, V2) -> U42(isNeList(activate(V2))) 1145.50/293.11 U42(tt) -> tt 1145.50/293.11 U51(tt, V2) -> U52(isList(activate(V2))) 1145.50/293.11 U52(tt) -> tt 1145.50/293.11 U61(tt) -> tt 1145.50/293.11 U71(tt, P) -> U72(isPal(activate(P))) 1145.50/293.11 U72(tt) -> tt 1145.50/293.11 U81(tt) -> tt 1145.50/293.11 isList(V) -> U11(isNeList(activate(V))) 1145.50/293.11 isList(n__nil) -> tt 1145.50/293.11 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(V) -> U31(isQid(activate(V))) 1145.50/293.11 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 1145.50/293.11 isNePal(V) -> U61(isQid(activate(V))) 1145.50/293.11 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) 1145.50/293.11 isPal(V) -> U81(isNePal(activate(V))) 1145.50/293.11 isPal(n__nil) -> tt 1145.50/293.11 isQid(n__a) -> tt 1145.50/293.11 isQid(n__e) -> tt 1145.50/293.11 isQid(n__i) -> tt 1145.50/293.11 isQid(n__o) -> tt 1145.50/293.11 isQid(n__u) -> tt 1145.50/293.11 nil -> n__nil 1145.50/293.11 __(X1, X2) -> n____(X1, X2) 1145.50/293.11 a -> n__a 1145.50/293.11 e -> n__e 1145.50/293.11 i -> n__i 1145.50/293.11 o -> n__o 1145.50/293.11 u -> n__u 1145.50/293.11 activate(n__nil) -> nil 1145.50/293.11 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1145.50/293.11 activate(n__a) -> a 1145.50/293.11 activate(n__e) -> e 1145.50/293.11 activate(n__i) -> i 1145.50/293.11 activate(n__o) -> o 1145.50/293.11 activate(n__u) -> u 1145.50/293.11 activate(X) -> X 1145.50/293.11 1145.50/293.11 Types: 1145.50/293.11 __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U11 :: tt -> tt 1145.50/293.11 tt :: tt 1145.50/293.11 U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U22 :: tt -> tt 1145.50/293.11 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U31 :: tt -> tt 1145.50/293.11 U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U42 :: tt -> tt 1145.50/293.11 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U52 :: tt -> tt 1145.50/293.11 U61 :: tt -> tt 1145.50/293.11 U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U72 :: tt -> tt 1145.50/293.11 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U81 :: tt -> tt 1145.50/293.11 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_tt2_0 :: tt 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 1145.50/293.11 1145.50/293.11 Lemmas: 1145.50/293.11 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), rt in Omega(1 + n28_0) 1145.50/293.11 isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0)) -> *4_0, rt in Omega(n9819_0 + n9819_0^2) 1145.50/293.11 1145.50/293.11 1145.50/293.11 Generator Equations: 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) 1145.50/293.11 1145.50/293.11 1145.50/293.11 The following defined symbols remain to be analysed: 1145.50/293.11 isList 1145.50/293.11 1145.50/293.11 They will be analysed ascendingly in the following order: 1145.50/293.11 isList = isNeList 1145.50/293.11 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1145.50/293.11 Proved the following rewrite lemma: 1145.50/293.11 isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n25345_0)) -> tt, rt in Omega(1 + n25345_0 + n25345_0^2) 1145.50/293.11 1145.50/293.11 Induction Base: 1145.50/293.11 isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) 1145.50/293.11 tt 1145.50/293.11 1145.50/293.11 Induction Step: 1145.50/293.11 isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(n25345_0, 1))) ->_R^Omega(1) 1145.50/293.11 U21(isList(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n25345_0))), activate(n__nil)) ->_L^Omega(1 + n25345_0) 1145.50/293.11 U21(isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n25345_0)), activate(n__nil)) ->_IH 1145.50/293.11 U21(tt, activate(n__nil)) ->_L^Omega(1) 1145.50/293.11 U21(tt, gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)) ->_R^Omega(1) 1145.50/293.11 U22(isList(activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0)))) ->_L^Omega(1) 1145.50/293.11 U22(isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0))) ->_R^Omega(1) 1145.50/293.11 U22(tt) ->_R^Omega(1) 1145.50/293.11 tt 1145.50/293.11 1145.50/293.11 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1145.50/293.11 ---------------------------------------- 1145.50/293.11 1145.50/293.11 (20) 1145.50/293.11 Obligation: 1145.50/293.11 TRS: 1145.50/293.11 Rules: 1145.50/293.11 __(__(X, Y), Z) -> __(X, __(Y, Z)) 1145.50/293.11 __(X, nil) -> X 1145.50/293.11 __(nil, X) -> X 1145.50/293.11 U11(tt) -> tt 1145.50/293.11 U21(tt, V2) -> U22(isList(activate(V2))) 1145.50/293.11 U22(tt) -> tt 1145.50/293.11 U31(tt) -> tt 1145.50/293.11 U41(tt, V2) -> U42(isNeList(activate(V2))) 1145.50/293.11 U42(tt) -> tt 1145.50/293.11 U51(tt, V2) -> U52(isList(activate(V2))) 1145.50/293.11 U52(tt) -> tt 1145.50/293.11 U61(tt) -> tt 1145.50/293.11 U71(tt, P) -> U72(isPal(activate(P))) 1145.50/293.11 U72(tt) -> tt 1145.50/293.11 U81(tt) -> tt 1145.50/293.11 isList(V) -> U11(isNeList(activate(V))) 1145.50/293.11 isList(n__nil) -> tt 1145.50/293.11 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(V) -> U31(isQid(activate(V))) 1145.50/293.11 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 1145.50/293.11 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 1145.50/293.11 isNePal(V) -> U61(isQid(activate(V))) 1145.50/293.11 isNePal(n____(I, n____(P, I))) -> U71(isQid(activate(I)), activate(P)) 1145.50/293.11 isPal(V) -> U81(isNePal(activate(V))) 1145.50/293.11 isPal(n__nil) -> tt 1145.50/293.11 isQid(n__a) -> tt 1145.50/293.11 isQid(n__e) -> tt 1145.50/293.11 isQid(n__i) -> tt 1145.50/293.11 isQid(n__o) -> tt 1145.50/293.11 isQid(n__u) -> tt 1145.50/293.11 nil -> n__nil 1145.50/293.11 __(X1, X2) -> n____(X1, X2) 1145.50/293.11 a -> n__a 1145.50/293.11 e -> n__e 1145.50/293.11 i -> n__i 1145.50/293.11 o -> n__o 1145.50/293.11 u -> n__u 1145.50/293.11 activate(n__nil) -> nil 1145.50/293.11 activate(n____(X1, X2)) -> __(activate(X1), activate(X2)) 1145.50/293.11 activate(n__a) -> a 1145.50/293.11 activate(n__e) -> e 1145.50/293.11 activate(n__i) -> i 1145.50/293.11 activate(n__o) -> o 1145.50/293.11 activate(n__u) -> u 1145.50/293.11 activate(X) -> X 1145.50/293.11 1145.50/293.11 Types: 1145.50/293.11 __ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U11 :: tt -> tt 1145.50/293.11 tt :: tt 1145.50/293.11 U21 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U22 :: tt -> tt 1145.50/293.11 isList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 activate :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 U31 :: tt -> tt 1145.50/293.11 U41 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U42 :: tt -> tt 1145.50/293.11 isNeList :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U51 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U52 :: tt -> tt 1145.50/293.11 U61 :: tt -> tt 1145.50/293.11 U71 :: tt -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U72 :: tt -> tt 1145.50/293.11 isPal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 U81 :: tt -> tt 1145.50/293.11 n__nil :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n____ :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 isQid :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 isNePal :: n__nil:n____:n__a:n__e:n__i:n__o:n__u -> tt 1145.50/293.11 n__a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 n__u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 a :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 e :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 i :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 o :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 u :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_n__nil:n____:n__a:n__e:n__i:n__o:n__u1_0 :: n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 hole_tt2_0 :: tt 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0 :: Nat -> n__nil:n____:n__a:n__e:n__i:n__o:n__u 1145.50/293.11 1145.50/293.11 1145.50/293.11 Lemmas: 1145.50/293.11 activate(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0)) -> gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n28_0), rt in Omega(1 + n28_0) 1145.50/293.11 isNeList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n9819_0)) -> *4_0, rt in Omega(n9819_0 + n9819_0^2) 1145.50/293.11 isList(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(n25345_0)) -> tt, rt in Omega(1 + n25345_0 + n25345_0^2) 1145.50/293.11 1145.50/293.11 1145.50/293.11 Generator Equations: 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(0) <=> n__nil 1145.50/293.11 gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(+(x, 1)) <=> n____(gen_n__nil:n____:n__a:n__e:n__i:n__o:n__u3_0(x), n__nil) 1145.50/293.11 1145.50/293.11 1145.50/293.11 The following defined symbols remain to be analysed: 1145.50/293.11 isNeList 1145.50/293.11 1145.50/293.11 They will be analysed ascendingly in the following order: 1145.50/293.11 isList = isNeList 1145.86/293.20 EOF