632.46/291.52 WORST_CASE(Omega(n^1), O(n^2)) 632.62/291.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 632.62/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 632.62/291.53 632.62/291.53 632.62/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 632.62/291.53 632.62/291.53 (0) CpxTRS 632.62/291.53 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 5 ms] 632.62/291.53 (2) CpxTRS 632.62/291.53 (3) NonCtorToCtorProof [UPPER BOUND(ID), 4 ms] 632.62/291.53 (4) CpxRelTRS 632.62/291.53 (5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 632.62/291.53 (6) CpxRelTRS 632.62/291.53 (7) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 632.62/291.53 (8) CdtProblem 632.62/291.53 (9) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 632.62/291.53 (10) CdtProblem 632.62/291.53 (11) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 632.62/291.53 (12) CdtProblem 632.62/291.53 (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 2 ms] 632.62/291.53 (14) CdtProblem 632.62/291.53 (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 1442 ms] 632.62/291.53 (16) CdtProblem 632.62/291.53 (17) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 632.62/291.53 (18) CdtProblem 632.62/291.53 (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 90 ms] 632.62/291.53 (20) CdtProblem 632.62/291.53 (21) CdtKnowledgeProof [FINISHED, 0 ms] 632.62/291.53 (22) BOUNDS(1, 1) 632.62/291.53 (23) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 632.62/291.53 (24) TRS for Loop Detection 632.62/291.53 (25) DecreasingLoopProof [LOWER BOUND(ID), 50 ms] 632.62/291.53 (26) BEST 632.62/291.53 (27) proven lower bound 632.62/291.53 (28) LowerBoundPropagationProof [FINISHED, 0 ms] 632.62/291.53 (29) BOUNDS(n^1, INF) 632.62/291.53 (30) TRS for Loop Detection 632.62/291.53 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (0) 632.62/291.53 Obligation: 632.62/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 632.62/291.53 632.62/291.53 632.62/291.53 The TRS R consists of the following rules: 632.62/291.53 632.62/291.53 __(__(X, Y), Z) -> __(X, __(Y, Z)) 632.62/291.53 __(X, nil) -> X 632.62/291.53 __(nil, X) -> X 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, V2) -> U22(isList(activate(V2))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, V2) -> U42(isNeList(activate(V2))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, V2) -> U52(isList(activate(V2))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, P) -> U72(isPal(activate(P))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(V) -> U11(isNeList(activate(V))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(V) -> U31(isQid(activate(V))) 632.62/291.53 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 632.62/291.53 isNePal(V) -> U61(isQid(activate(V))) 632.62/291.53 isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P)) 632.62/291.53 isPal(V) -> U81(isNePal(activate(V))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 __(X1, X2) -> n____(X1, X2) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(X1, X2)) -> __(X1, X2) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(X) -> X 632.62/291.53 632.62/291.53 S is empty. 632.62/291.53 Rewrite Strategy: FULL 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 632.62/291.53 The following defined symbols can occur below the 0th argument of U31: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of isQid: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of activate: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of U22: a, U31, U52, U11, U41, isQid, isPal, __, U61, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U71, U22, o, isNeList, i, U51 632.62/291.53 The following defined symbols can occur below the 0th argument of isList: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of U41: a, U31, U52, U11, U41, isQid, isPal, __, U61, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U71, U22, o, isNeList, i, U51 632.62/291.53 The following defined symbols can occur below the 1th argument of U41: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of U42: a, U31, U52, U11, U41, isQid, isPal, __, U61, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U71, U22, o, isNeList, i, U51 632.62/291.53 The following defined symbols can occur below the 0th argument of isNeList: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of U51: a, U31, U52, U11, U41, isQid, isPal, __, U61, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U71, U22, o, isNeList, i, U51 632.62/291.53 The following defined symbols can occur below the 1th argument of U51: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of U72: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of isPal: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of U52: a, U31, U52, U11, U41, isQid, isPal, __, U61, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U71, U22, o, isNeList, i, U51 632.62/291.53 The following defined symbols can occur below the 0th argument of U11: a, U31, U52, U11, U41, isQid, isPal, __, U61, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U71, U22, o, isNeList, i, U51 632.62/291.53 The following defined symbols can occur below the 0th argument of U21: a, U31, U52, U11, U41, isQid, isPal, __, U61, e, isList, U42, U72, isNePal, U81, U21, activate, u, nil, U71, U22, o, isNeList, i, U51 632.62/291.53 The following defined symbols can occur below the 1th argument of U21: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of U61: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of U81: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of isNePal: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 0th argument of U71: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 The following defined symbols can occur below the 1th argument of U71: a, U72, isNePal, U81, activate, u, nil, isQid, U71, o, i, isPal, __, U61, e 632.62/291.53 632.62/291.53 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 632.62/291.53 __(__(X, Y), Z) -> __(X, __(Y, Z)) 632.62/291.53 __(X, nil) -> X 632.62/291.53 __(nil, X) -> X 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (2) 632.62/291.53 Obligation: 632.62/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 632.62/291.53 632.62/291.53 632.62/291.53 The TRS R consists of the following rules: 632.62/291.53 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, V2) -> U22(isList(activate(V2))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, V2) -> U42(isNeList(activate(V2))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, V2) -> U52(isList(activate(V2))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, P) -> U72(isPal(activate(P))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(V) -> U11(isNeList(activate(V))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(V) -> U31(isQid(activate(V))) 632.62/291.53 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 632.62/291.53 isNePal(V) -> U61(isQid(activate(V))) 632.62/291.53 isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P)) 632.62/291.53 isPal(V) -> U81(isNePal(activate(V))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 __(X1, X2) -> n____(X1, X2) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(X1, X2)) -> __(X1, X2) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(X) -> X 632.62/291.53 632.62/291.53 S is empty. 632.62/291.53 Rewrite Strategy: FULL 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (3) NonCtorToCtorProof (UPPER BOUND(ID)) 632.62/291.53 transformed non-ctor to ctor-system 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (4) 632.62/291.53 Obligation: 632.62/291.53 The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2). 632.62/291.53 632.62/291.53 632.62/291.53 The TRS R consists of the following rules: 632.62/291.53 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, V2) -> U22(isList(activate(V2))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, V2) -> U42(isNeList(activate(V2))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, V2) -> U52(isList(activate(V2))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, P) -> U72(isPal(activate(P))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(V) -> U11(isNeList(activate(V))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(V) -> U31(isQid(activate(V))) 632.62/291.53 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 632.62/291.53 isNePal(V) -> U61(isQid(activate(V))) 632.62/291.53 isPal(V) -> U81(isNePal(activate(V))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 __(X1, X2) -> n____(X1, X2) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(X1, X2)) -> __(X1, X2) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(X) -> X 632.62/291.53 isNePal(n____(I, c___(P, I))) -> U71(isQid(activate(I)), activate(P)) 632.62/291.53 632.62/291.53 The (relative) TRS S consists of the following rules: 632.62/291.53 632.62/291.53 __(x0, x1) -> c___(x0, x1) 632.62/291.53 632.62/291.53 Rewrite Strategy: FULL 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (5) RcToIrcProof (BOTH BOUNDS(ID, ID)) 632.62/291.53 Converted rc-obligation to irc-obligation. 632.62/291.53 632.62/291.53 As the TRS is a non-duplicating overlay system, we have rc = irc. 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (6) 632.62/291.53 Obligation: 632.62/291.53 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2). 632.62/291.53 632.62/291.53 632.62/291.53 The TRS R consists of the following rules: 632.62/291.53 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, V2) -> U22(isList(activate(V2))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, V2) -> U42(isNeList(activate(V2))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, V2) -> U52(isList(activate(V2))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, P) -> U72(isPal(activate(P))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(V) -> U11(isNeList(activate(V))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(V) -> U31(isQid(activate(V))) 632.62/291.53 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 632.62/291.53 isNePal(V) -> U61(isQid(activate(V))) 632.62/291.53 isPal(V) -> U81(isNePal(activate(V))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 __(X1, X2) -> n____(X1, X2) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(X1, X2)) -> __(X1, X2) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(X) -> X 632.62/291.53 isNePal(n____(I, c___(P, I))) -> U71(isQid(activate(I)), activate(P)) 632.62/291.53 632.62/291.53 The (relative) TRS S consists of the following rules: 632.62/291.53 632.62/291.53 __(x0, x1) -> c___(x0, x1) 632.62/291.53 632.62/291.53 Rewrite Strategy: INNERMOST 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (7) CpxTrsToCdtProof (UPPER BOUND(ID)) 632.62/291.53 Converted Cpx (relative) TRS to CDT 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (8) 632.62/291.53 Obligation: 632.62/291.53 Complexity Dependency Tuples Problem 632.62/291.53 632.62/291.53 Rules: 632.62/291.53 __(z0, z1) -> c___(z0, z1) 632.62/291.53 __(z0, z1) -> n____(z0, z1) 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, z0) -> U22(isList(activate(z0))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, z0) -> U42(isNeList(activate(z0))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, z0) -> U52(isList(activate(z0))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, z0) -> U72(isPal(activate(z0))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(z0) -> U11(isNeList(activate(z0))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(z0) -> U31(isQid(activate(z0))) 632.62/291.53 isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1)) 632.62/291.53 isNePal(z0) -> U61(isQid(activate(z0))) 632.62/291.53 isNePal(n____(z0, c___(z1, z0))) -> U71(isQid(activate(z0)), activate(z1)) 632.62/291.53 isPal(z0) -> U81(isNePal(activate(z0))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(z0, z1)) -> __(z0, z1) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(z0) -> z0 632.62/291.53 Tuples: 632.62/291.53 __'(z0, z1) -> c 632.62/291.53 __'(z0, z1) -> c1 632.62/291.53 U11'(tt) -> c2 632.62/291.53 U21'(tt, z0) -> c3(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U22'(tt) -> c4 632.62/291.53 U31'(tt) -> c5 632.62/291.53 U41'(tt, z0) -> c6(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U42'(tt) -> c7 632.62/291.53 U51'(tt, z0) -> c8(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U52'(tt) -> c9 632.62/291.53 U61'(tt) -> c10 632.62/291.53 U71'(tt, z0) -> c11(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U72'(tt) -> c12 632.62/291.53 U81'(tt) -> c13 632.62/291.53 ISLIST(z0) -> c14(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISLIST(n__nil) -> c15 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNELIST(z0) -> c17(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNEPAL(z0) -> c20(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISPAL(z0) -> c22(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISPAL(n__nil) -> c23 632.62/291.53 ISQID(n__a) -> c24 632.62/291.53 ISQID(n__e) -> c25 632.62/291.53 ISQID(n__i) -> c26 632.62/291.53 ISQID(n__o) -> c27 632.62/291.53 ISQID(n__u) -> c28 632.62/291.53 NIL -> c29 632.62/291.53 A -> c30 632.62/291.53 E -> c31 632.62/291.53 I -> c32 632.62/291.53 O -> c33 632.62/291.53 U -> c34 632.62/291.53 ACTIVATE(n__nil) -> c35(NIL) 632.62/291.53 ACTIVATE(n____(z0, z1)) -> c36(__'(z0, z1)) 632.62/291.53 ACTIVATE(n__a) -> c37(A) 632.62/291.53 ACTIVATE(n__e) -> c38(E) 632.62/291.53 ACTIVATE(n__i) -> c39(I) 632.62/291.53 ACTIVATE(n__o) -> c40(O) 632.62/291.53 ACTIVATE(n__u) -> c41(U) 632.62/291.53 ACTIVATE(z0) -> c42 632.62/291.53 S tuples: 632.62/291.53 __'(z0, z1) -> c1 632.62/291.53 U11'(tt) -> c2 632.62/291.53 U21'(tt, z0) -> c3(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U22'(tt) -> c4 632.62/291.53 U31'(tt) -> c5 632.62/291.53 U41'(tt, z0) -> c6(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U42'(tt) -> c7 632.62/291.53 U51'(tt, z0) -> c8(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U52'(tt) -> c9 632.62/291.53 U61'(tt) -> c10 632.62/291.53 U71'(tt, z0) -> c11(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U72'(tt) -> c12 632.62/291.53 U81'(tt) -> c13 632.62/291.53 ISLIST(z0) -> c14(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISLIST(n__nil) -> c15 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNELIST(z0) -> c17(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNEPAL(z0) -> c20(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISPAL(z0) -> c22(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISPAL(n__nil) -> c23 632.62/291.53 ISQID(n__a) -> c24 632.62/291.53 ISQID(n__e) -> c25 632.62/291.53 ISQID(n__i) -> c26 632.62/291.53 ISQID(n__o) -> c27 632.62/291.53 ISQID(n__u) -> c28 632.62/291.53 NIL -> c29 632.62/291.53 A -> c30 632.62/291.53 E -> c31 632.62/291.53 I -> c32 632.62/291.53 O -> c33 632.62/291.53 U -> c34 632.62/291.53 ACTIVATE(n__nil) -> c35(NIL) 632.62/291.53 ACTIVATE(n____(z0, z1)) -> c36(__'(z0, z1)) 632.62/291.53 ACTIVATE(n__a) -> c37(A) 632.62/291.53 ACTIVATE(n__e) -> c38(E) 632.62/291.53 ACTIVATE(n__i) -> c39(I) 632.62/291.53 ACTIVATE(n__o) -> c40(O) 632.62/291.53 ACTIVATE(n__u) -> c41(U) 632.62/291.53 ACTIVATE(z0) -> c42 632.62/291.53 K tuples:none 632.62/291.53 Defined Rule Symbols: U11_1, U21_2, U22_1, U31_1, U41_2, U42_1, U51_2, U52_1, U61_1, U71_2, U72_1, U81_1, isList_1, isNeList_1, isNePal_1, isPal_1, isQid_1, nil, ___2, a, e, i, o, u, activate_1 632.62/291.53 632.62/291.53 Defined Pair Symbols: __'_2, U11'_1, U21'_2, U22'_1, U31'_1, U41'_2, U42'_1, U51'_2, U52'_1, U61'_1, U71'_2, U72'_1, U81'_1, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1, ISQID_1, NIL, A, E, I, O, U, ACTIVATE_1 632.62/291.53 632.62/291.53 Compound Symbols: c, c1, c2, c3_3, c4, c5, c6_3, c7, c8_3, c9, c10, c11_3, c12, c13, c14_3, c15, c16_4, c17_3, c18_4, c19_4, c20_3, c21_4, c22_3, c23, c24, c25, c26, c27, c28, c29, c30, c31, c32, c33, c34, c35_1, c36_1, c37_1, c38_1, c39_1, c40_1, c41_1, c42 632.62/291.53 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (9) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 632.62/291.53 Removed 33 trailing nodes: 632.62/291.53 ISQID(n__o) -> c27 632.62/291.53 ACTIVATE(n__u) -> c41(U) 632.62/291.53 ISQID(n__u) -> c28 632.62/291.53 ACTIVATE(n__nil) -> c35(NIL) 632.62/291.53 U11'(tt) -> c2 632.62/291.53 ISQID(n__a) -> c24 632.62/291.53 ISNELIST(z0) -> c17(U31'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ACTIVATE(n__a) -> c37(A) 632.62/291.53 U42'(tt) -> c7 632.62/291.53 ISNEPAL(z0) -> c20(U61'(isQid(activate(z0))), ISQID(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U31'(tt) -> c5 632.62/291.53 U -> c34 632.62/291.53 O -> c33 632.62/291.53 I -> c32 632.62/291.53 __'(z0, z1) -> c1 632.62/291.53 ACTIVATE(n__o) -> c40(O) 632.62/291.53 ISQID(n__e) -> c25 632.62/291.53 E -> c31 632.62/291.53 A -> c30 632.62/291.53 NIL -> c29 632.62/291.53 U52'(tt) -> c9 632.62/291.53 ACTIVATE(n__i) -> c39(I) 632.62/291.53 ISLIST(n__nil) -> c15 632.62/291.53 U22'(tt) -> c4 632.62/291.53 ISPAL(n__nil) -> c23 632.62/291.53 __'(z0, z1) -> c 632.62/291.53 ACTIVATE(n____(z0, z1)) -> c36(__'(z0, z1)) 632.62/291.53 ACTIVATE(z0) -> c42 632.62/291.53 U72'(tt) -> c12 632.62/291.53 ISQID(n__i) -> c26 632.62/291.53 ACTIVATE(n__e) -> c38(E) 632.62/291.53 U81'(tt) -> c13 632.62/291.53 U61'(tt) -> c10 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (10) 632.62/291.53 Obligation: 632.62/291.53 Complexity Dependency Tuples Problem 632.62/291.53 632.62/291.53 Rules: 632.62/291.53 __(z0, z1) -> c___(z0, z1) 632.62/291.53 __(z0, z1) -> n____(z0, z1) 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, z0) -> U22(isList(activate(z0))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, z0) -> U42(isNeList(activate(z0))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, z0) -> U52(isList(activate(z0))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, z0) -> U72(isPal(activate(z0))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(z0) -> U11(isNeList(activate(z0))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(z0) -> U31(isQid(activate(z0))) 632.62/291.53 isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1)) 632.62/291.53 isNePal(z0) -> U61(isQid(activate(z0))) 632.62/291.53 isNePal(n____(z0, c___(z1, z0))) -> U71(isQid(activate(z0)), activate(z1)) 632.62/291.53 isPal(z0) -> U81(isNePal(activate(z0))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(z0, z1)) -> __(z0, z1) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(z0) -> z0 632.62/291.53 Tuples: 632.62/291.53 U21'(tt, z0) -> c3(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U41'(tt, z0) -> c6(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U51'(tt, z0) -> c8(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U71'(tt, z0) -> c11(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISLIST(z0) -> c14(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISPAL(z0) -> c22(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0)) 632.62/291.53 S tuples: 632.62/291.53 U21'(tt, z0) -> c3(U22'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U41'(tt, z0) -> c6(U42'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U51'(tt, z0) -> c8(U52'(isList(activate(z0))), ISLIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 U71'(tt, z0) -> c11(U72'(isPal(activate(z0))), ISPAL(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISLIST(z0) -> c14(U11'(isNeList(activate(z0))), ISNELIST(activate(z0)), ACTIVATE(z0)) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1)), ISQID(activate(z0)), ACTIVATE(z0), ACTIVATE(z1)) 632.62/291.53 ISPAL(z0) -> c22(U81'(isNePal(activate(z0))), ISNEPAL(activate(z0)), ACTIVATE(z0)) 632.62/291.53 K tuples:none 632.62/291.53 Defined Rule Symbols: U11_1, U21_2, U22_1, U31_1, U41_2, U42_1, U51_2, U52_1, U61_1, U71_2, U72_1, U81_1, isList_1, isNeList_1, isNePal_1, isPal_1, isQid_1, nil, ___2, a, e, i, o, u, activate_1 632.62/291.53 632.62/291.53 Defined Pair Symbols: U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1 632.62/291.53 632.62/291.53 Compound Symbols: c3_3, c6_3, c8_3, c11_3, c14_3, c16_4, c18_4, c19_4, c21_4, c22_3 632.62/291.53 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (11) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 632.62/291.53 Removed 21 trailing tuple parts 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (12) 632.62/291.53 Obligation: 632.62/291.53 Complexity Dependency Tuples Problem 632.62/291.53 632.62/291.53 Rules: 632.62/291.53 __(z0, z1) -> c___(z0, z1) 632.62/291.53 __(z0, z1) -> n____(z0, z1) 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, z0) -> U22(isList(activate(z0))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, z0) -> U42(isNeList(activate(z0))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, z0) -> U52(isList(activate(z0))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, z0) -> U72(isPal(activate(z0))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(z0) -> U11(isNeList(activate(z0))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(z0) -> U31(isQid(activate(z0))) 632.62/291.53 isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1)) 632.62/291.53 isNePal(z0) -> U61(isQid(activate(z0))) 632.62/291.53 isNePal(n____(z0, c___(z1, z0))) -> U71(isQid(activate(z0)), activate(z1)) 632.62/291.53 isPal(z0) -> U81(isNePal(activate(z0))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(z0, z1)) -> __(z0, z1) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(z0) -> z0 632.62/291.53 Tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 S tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 K tuples:none 632.62/291.53 Defined Rule Symbols: U11_1, U21_2, U22_1, U31_1, U41_2, U42_1, U51_2, U52_1, U61_1, U71_2, U72_1, U81_1, isList_1, isNeList_1, isNePal_1, isPal_1, isQid_1, nil, ___2, a, e, i, o, u, activate_1 632.62/291.53 632.62/291.53 Defined Pair Symbols: U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1 632.62/291.53 632.62/291.53 Compound Symbols: c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1 632.62/291.53 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (13) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 632.62/291.53 The following rules are not usable and were removed: 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, z0) -> U72(isPal(activate(z0))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isNePal(z0) -> U61(isQid(activate(z0))) 632.62/291.53 isNePal(n____(z0, c___(z1, z0))) -> U71(isQid(activate(z0)), activate(z1)) 632.62/291.53 isPal(z0) -> U81(isNePal(activate(z0))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (14) 632.62/291.53 Obligation: 632.62/291.53 Complexity Dependency Tuples Problem 632.62/291.53 632.62/291.53 Rules: 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(z0, z1)) -> __(z0, z1) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(z0) -> z0 632.62/291.53 nil -> n__nil 632.62/291.53 __(z0, z1) -> c___(z0, z1) 632.62/291.53 __(z0, z1) -> n____(z0, z1) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 isList(z0) -> U11(isNeList(activate(z0))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1)) 632.62/291.53 U11(tt) -> tt 632.62/291.53 isNeList(z0) -> U31(isQid(activate(z0))) 632.62/291.53 isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1)) 632.62/291.53 U31(tt) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 U41(tt, z0) -> U42(isNeList(activate(z0))) 632.62/291.53 U21(tt, z0) -> U22(isList(activate(z0))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, z0) -> U52(isList(activate(z0))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 Tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 S tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 K tuples:none 632.62/291.53 Defined Rule Symbols: activate_1, nil, ___2, a, e, i, o, u, isList_1, U11_1, isNeList_1, U31_1, isQid_1, U41_2, U21_2, U22_1, U42_1, U51_2, U52_1 632.62/291.53 632.62/291.53 Defined Pair Symbols: U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1 632.62/291.53 632.62/291.53 Compound Symbols: c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1 632.62/291.53 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 632.62/291.53 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 We considered the (Usable) Rules: 632.62/291.53 activate(n__u) -> u 632.62/291.53 __(z0, z1) -> c___(z0, z1) 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(z0) -> z0 632.62/291.53 i -> n__i 632.62/291.53 nil -> n__nil 632.62/291.53 u -> n__u 632.62/291.53 o -> n__o 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 __(z0, z1) -> n____(z0, z1) 632.62/291.53 activate(n__e) -> e 632.62/291.53 e -> n__e 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n____(z0, z1)) -> __(z0, z1) 632.62/291.53 a -> n__a 632.62/291.53 And the Tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 The order we found is given by the following interpretation: 632.62/291.53 632.62/291.53 Polynomial interpretation : 632.62/291.53 632.62/291.53 POL(ISLIST(x_1)) = 0 632.62/291.53 POL(ISNELIST(x_1)) = 0 632.62/291.53 POL(ISNEPAL(x_1)) = [2]x_1^2 632.62/291.53 POL(ISPAL(x_1)) = [2]x_1^2 632.62/291.53 POL(U11(x_1)) = [1] 632.62/291.53 POL(U21(x_1, x_2)) = [1] 632.62/291.53 POL(U21'(x_1, x_2)) = 0 632.62/291.53 POL(U22(x_1)) = [1] 632.62/291.53 POL(U31(x_1)) = [1] 632.62/291.53 POL(U41(x_1, x_2)) = [1] 632.62/291.53 POL(U41'(x_1, x_2)) = 0 632.62/291.53 POL(U42(x_1)) = [1] 632.62/291.53 POL(U51(x_1, x_2)) = [1] 632.62/291.53 POL(U51'(x_1, x_2)) = 0 632.62/291.53 POL(U52(x_1)) = [1] 632.62/291.53 POL(U71'(x_1, x_2)) = [2]x_2^2 632.62/291.53 POL(__(x_1, x_2)) = [2] + x_1 + x_2 632.62/291.53 POL(a) = 0 632.62/291.53 POL(activate(x_1)) = x_1 632.62/291.53 POL(c11(x_1)) = x_1 632.62/291.53 POL(c14(x_1)) = x_1 632.62/291.53 POL(c16(x_1, x_2)) = x_1 + x_2 632.62/291.53 POL(c18(x_1, x_2)) = x_1 + x_2 632.62/291.53 POL(c19(x_1, x_2)) = x_1 + x_2 632.62/291.53 POL(c21(x_1)) = x_1 632.62/291.53 POL(c22(x_1)) = x_1 632.62/291.53 POL(c3(x_1)) = x_1 632.62/291.53 POL(c6(x_1)) = x_1 632.62/291.53 POL(c8(x_1)) = x_1 632.62/291.53 POL(c___(x_1, x_2)) = [2] + x_1 632.62/291.53 POL(e) = 0 632.62/291.53 POL(i) = 0 632.62/291.53 POL(isList(x_1)) = 0 632.62/291.53 POL(isNeList(x_1)) = 0 632.62/291.53 POL(isQid(x_1)) = 0 632.62/291.53 POL(n____(x_1, x_2)) = [2] + x_1 + x_2 632.62/291.53 POL(n__a) = 0 632.62/291.53 POL(n__e) = 0 632.62/291.53 POL(n__i) = 0 632.62/291.53 POL(n__nil) = 0 632.62/291.53 POL(n__o) = 0 632.62/291.53 POL(n__u) = 0 632.62/291.53 POL(nil) = 0 632.62/291.53 POL(o) = 0 632.62/291.53 POL(tt) = 0 632.62/291.53 POL(u) = 0 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (16) 632.62/291.53 Obligation: 632.62/291.53 Complexity Dependency Tuples Problem 632.62/291.53 632.62/291.53 Rules: 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(z0, z1)) -> __(z0, z1) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(z0) -> z0 632.62/291.53 nil -> n__nil 632.62/291.53 __(z0, z1) -> c___(z0, z1) 632.62/291.53 __(z0, z1) -> n____(z0, z1) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 isList(z0) -> U11(isNeList(activate(z0))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1)) 632.62/291.53 U11(tt) -> tt 632.62/291.53 isNeList(z0) -> U31(isQid(activate(z0))) 632.62/291.53 isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1)) 632.62/291.53 U31(tt) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 U41(tt, z0) -> U42(isNeList(activate(z0))) 632.62/291.53 U21(tt, z0) -> U22(isList(activate(z0))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, z0) -> U52(isList(activate(z0))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 Tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 S tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 K tuples: 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 Defined Rule Symbols: activate_1, nil, ___2, a, e, i, o, u, isList_1, U11_1, isNeList_1, U31_1, isQid_1, U41_2, U21_2, U22_1, U42_1, U51_2, U52_1 632.62/291.53 632.62/291.53 Defined Pair Symbols: U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1 632.62/291.53 632.62/291.53 Compound Symbols: c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1 632.62/291.53 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (17) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 632.62/291.53 The following tuples could be moved from S to K by knowledge propagation: 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (18) 632.62/291.53 Obligation: 632.62/291.53 Complexity Dependency Tuples Problem 632.62/291.53 632.62/291.53 Rules: 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(z0, z1)) -> __(z0, z1) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(z0) -> z0 632.62/291.53 nil -> n__nil 632.62/291.53 __(z0, z1) -> c___(z0, z1) 632.62/291.53 __(z0, z1) -> n____(z0, z1) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 isList(z0) -> U11(isNeList(activate(z0))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1)) 632.62/291.53 U11(tt) -> tt 632.62/291.53 isNeList(z0) -> U31(isQid(activate(z0))) 632.62/291.53 isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1)) 632.62/291.53 U31(tt) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 U41(tt, z0) -> U42(isNeList(activate(z0))) 632.62/291.53 U21(tt, z0) -> U22(isList(activate(z0))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, z0) -> U52(isList(activate(z0))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 Tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 S tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 K tuples: 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 Defined Rule Symbols: activate_1, nil, ___2, a, e, i, o, u, isList_1, U11_1, isNeList_1, U31_1, isQid_1, U41_2, U21_2, U22_1, U42_1, U51_2, U52_1 632.62/291.53 632.62/291.53 Defined Pair Symbols: U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1 632.62/291.53 632.62/291.53 Compound Symbols: c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1 632.62/291.53 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 632.62/291.53 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 We considered the (Usable) Rules: 632.62/291.53 activate(n__u) -> u 632.62/291.53 __(z0, z1) -> c___(z0, z1) 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(z0) -> z0 632.62/291.53 i -> n__i 632.62/291.53 nil -> n__nil 632.62/291.53 u -> n__u 632.62/291.53 o -> n__o 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 __(z0, z1) -> n____(z0, z1) 632.62/291.53 activate(n__e) -> e 632.62/291.53 e -> n__e 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n____(z0, z1)) -> __(z0, z1) 632.62/291.53 a -> n__a 632.62/291.53 And the Tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 The order we found is given by the following interpretation: 632.62/291.53 632.62/291.53 Polynomial interpretation : 632.62/291.53 632.62/291.53 POL(ISLIST(x_1)) = x_1 632.62/291.53 POL(ISNELIST(x_1)) = x_1 632.62/291.53 POL(ISNEPAL(x_1)) = 0 632.62/291.53 POL(ISPAL(x_1)) = 0 632.62/291.53 POL(U11(x_1)) = [1] + x_1 632.62/291.53 POL(U21(x_1, x_2)) = [1] + x_1 + x_2 632.62/291.53 POL(U21'(x_1, x_2)) = x_2 632.62/291.53 POL(U22(x_1)) = [1] 632.62/291.53 POL(U31(x_1)) = [1] + x_1 632.62/291.53 POL(U41(x_1, x_2)) = [1] + x_1 + x_2 632.62/291.53 POL(U41'(x_1, x_2)) = x_2 632.62/291.53 POL(U42(x_1)) = [1] 632.62/291.53 POL(U51(x_1, x_2)) = [1] + x_1 + x_2 632.62/291.53 POL(U51'(x_1, x_2)) = x_2 632.62/291.53 POL(U52(x_1)) = [1] 632.62/291.53 POL(U71'(x_1, x_2)) = 0 632.62/291.53 POL(__(x_1, x_2)) = [1] + x_1 + x_2 632.62/291.53 POL(a) = [1] 632.62/291.53 POL(activate(x_1)) = x_1 632.62/291.53 POL(c11(x_1)) = x_1 632.62/291.53 POL(c14(x_1)) = x_1 632.62/291.53 POL(c16(x_1, x_2)) = x_1 + x_2 632.62/291.53 POL(c18(x_1, x_2)) = x_1 + x_2 632.62/291.53 POL(c19(x_1, x_2)) = x_1 + x_2 632.62/291.53 POL(c21(x_1)) = x_1 632.62/291.53 POL(c22(x_1)) = x_1 632.62/291.53 POL(c3(x_1)) = x_1 632.62/291.53 POL(c6(x_1)) = x_1 632.62/291.53 POL(c8(x_1)) = x_1 632.62/291.53 POL(c___(x_1, x_2)) = [1] + x_1 + x_2 632.62/291.53 POL(e) = [1] 632.62/291.53 POL(i) = [1] 632.62/291.53 POL(isList(x_1)) = 0 632.62/291.53 POL(isNeList(x_1)) = [1] 632.62/291.53 POL(isQid(x_1)) = [1] 632.62/291.53 POL(n____(x_1, x_2)) = [1] + x_1 + x_2 632.62/291.53 POL(n__a) = [1] 632.62/291.53 POL(n__e) = [1] 632.62/291.53 POL(n__i) = [1] 632.62/291.53 POL(n__nil) = [1] 632.62/291.53 POL(n__o) = [1] 632.62/291.53 POL(n__u) = [1] 632.62/291.53 POL(nil) = [1] 632.62/291.53 POL(o) = [1] 632.62/291.53 POL(tt) = 0 632.62/291.53 POL(u) = [1] 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (20) 632.62/291.53 Obligation: 632.62/291.53 Complexity Dependency Tuples Problem 632.62/291.53 632.62/291.53 Rules: 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(z0, z1)) -> __(z0, z1) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(z0) -> z0 632.62/291.53 nil -> n__nil 632.62/291.53 __(z0, z1) -> c___(z0, z1) 632.62/291.53 __(z0, z1) -> n____(z0, z1) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 isList(z0) -> U11(isNeList(activate(z0))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(z0, z1)) -> U21(isList(activate(z0)), activate(z1)) 632.62/291.53 U11(tt) -> tt 632.62/291.53 isNeList(z0) -> U31(isQid(activate(z0))) 632.62/291.53 isNeList(n____(z0, z1)) -> U41(isList(activate(z0)), activate(z1)) 632.62/291.53 isNeList(n____(z0, z1)) -> U51(isNeList(activate(z0)), activate(z1)) 632.62/291.53 U31(tt) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 U41(tt, z0) -> U42(isNeList(activate(z0))) 632.62/291.53 U21(tt, z0) -> U22(isList(activate(z0))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, z0) -> U52(isList(activate(z0))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 Tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 S tuples: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 K tuples: 632.62/291.53 ISNEPAL(n____(z0, c___(z1, z0))) -> c21(U71'(isQid(activate(z0)), activate(z1))) 632.62/291.53 U71'(tt, z0) -> c11(ISPAL(activate(z0))) 632.62/291.53 ISPAL(z0) -> c22(ISNEPAL(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 Defined Rule Symbols: activate_1, nil, ___2, a, e, i, o, u, isList_1, U11_1, isNeList_1, U31_1, isQid_1, U41_2, U21_2, U22_1, U42_1, U51_2, U52_1 632.62/291.53 632.62/291.53 Defined Pair Symbols: U21'_2, U41'_2, U51'_2, U71'_2, ISLIST_1, ISNELIST_1, ISNEPAL_1, ISPAL_1 632.62/291.53 632.62/291.53 Compound Symbols: c3_1, c6_1, c8_1, c11_1, c14_1, c16_2, c18_2, c19_2, c21_1, c22_1 632.62/291.53 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (21) CdtKnowledgeProof (FINISHED) 632.62/291.53 The following tuples could be moved from S to K by knowledge propagation: 632.62/291.53 U21'(tt, z0) -> c3(ISLIST(activate(z0))) 632.62/291.53 U41'(tt, z0) -> c6(ISNELIST(activate(z0))) 632.62/291.53 U51'(tt, z0) -> c8(ISLIST(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 ISLIST(z0) -> c14(ISNELIST(activate(z0))) 632.62/291.53 ISLIST(n____(z0, z1)) -> c16(U21'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c18(U41'(isList(activate(z0)), activate(z1)), ISLIST(activate(z0))) 632.62/291.53 ISNELIST(n____(z0, z1)) -> c19(U51'(isNeList(activate(z0)), activate(z1)), ISNELIST(activate(z0))) 632.62/291.53 Now S is empty 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (22) 632.62/291.53 BOUNDS(1, 1) 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (23) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 632.62/291.53 Transformed a relative TRS into a decreasing-loop problem. 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (24) 632.62/291.53 Obligation: 632.62/291.53 Analyzing the following TRS for decreasing loops: 632.62/291.53 632.62/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 632.62/291.53 632.62/291.53 632.62/291.53 The TRS R consists of the following rules: 632.62/291.53 632.62/291.53 __(__(X, Y), Z) -> __(X, __(Y, Z)) 632.62/291.53 __(X, nil) -> X 632.62/291.53 __(nil, X) -> X 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, V2) -> U22(isList(activate(V2))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, V2) -> U42(isNeList(activate(V2))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, V2) -> U52(isList(activate(V2))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, P) -> U72(isPal(activate(P))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(V) -> U11(isNeList(activate(V))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(V) -> U31(isQid(activate(V))) 632.62/291.53 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 632.62/291.53 isNePal(V) -> U61(isQid(activate(V))) 632.62/291.53 isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P)) 632.62/291.53 isPal(V) -> U81(isNePal(activate(V))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 __(X1, X2) -> n____(X1, X2) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(X1, X2)) -> __(X1, X2) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(X) -> X 632.62/291.53 632.62/291.53 S is empty. 632.62/291.53 Rewrite Strategy: FULL 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (25) DecreasingLoopProof (LOWER BOUND(ID)) 632.62/291.53 The following loop(s) give(s) rise to the lower bound Omega(n^1): 632.62/291.53 632.62/291.53 The rewrite sequence 632.62/291.53 632.62/291.53 isList(n____(V1, V2)) ->^+ U21(isList(V1), activate(V2)) 632.62/291.53 632.62/291.53 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 632.62/291.53 632.62/291.53 The pumping substitution is [V1 / n____(V1, V2)]. 632.62/291.53 632.62/291.53 The result substitution is [ ]. 632.62/291.53 632.62/291.53 632.62/291.53 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (26) 632.62/291.53 Complex Obligation (BEST) 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (27) 632.62/291.53 Obligation: 632.62/291.53 Proved the lower bound n^1 for the following obligation: 632.62/291.53 632.62/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 632.62/291.53 632.62/291.53 632.62/291.53 The TRS R consists of the following rules: 632.62/291.53 632.62/291.53 __(__(X, Y), Z) -> __(X, __(Y, Z)) 632.62/291.53 __(X, nil) -> X 632.62/291.53 __(nil, X) -> X 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, V2) -> U22(isList(activate(V2))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, V2) -> U42(isNeList(activate(V2))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, V2) -> U52(isList(activate(V2))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, P) -> U72(isPal(activate(P))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(V) -> U11(isNeList(activate(V))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(V) -> U31(isQid(activate(V))) 632.62/291.53 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 632.62/291.53 isNePal(V) -> U61(isQid(activate(V))) 632.62/291.53 isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P)) 632.62/291.53 isPal(V) -> U81(isNePal(activate(V))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 __(X1, X2) -> n____(X1, X2) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(X1, X2)) -> __(X1, X2) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(X) -> X 632.62/291.53 632.62/291.53 S is empty. 632.62/291.53 Rewrite Strategy: FULL 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (28) LowerBoundPropagationProof (FINISHED) 632.62/291.53 Propagated lower bound. 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (29) 632.62/291.53 BOUNDS(n^1, INF) 632.62/291.53 632.62/291.53 ---------------------------------------- 632.62/291.53 632.62/291.53 (30) 632.62/291.53 Obligation: 632.62/291.53 Analyzing the following TRS for decreasing loops: 632.62/291.53 632.62/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 632.62/291.53 632.62/291.53 632.62/291.53 The TRS R consists of the following rules: 632.62/291.53 632.62/291.53 __(__(X, Y), Z) -> __(X, __(Y, Z)) 632.62/291.53 __(X, nil) -> X 632.62/291.53 __(nil, X) -> X 632.62/291.53 U11(tt) -> tt 632.62/291.53 U21(tt, V2) -> U22(isList(activate(V2))) 632.62/291.53 U22(tt) -> tt 632.62/291.53 U31(tt) -> tt 632.62/291.53 U41(tt, V2) -> U42(isNeList(activate(V2))) 632.62/291.53 U42(tt) -> tt 632.62/291.53 U51(tt, V2) -> U52(isList(activate(V2))) 632.62/291.53 U52(tt) -> tt 632.62/291.53 U61(tt) -> tt 632.62/291.53 U71(tt, P) -> U72(isPal(activate(P))) 632.62/291.53 U72(tt) -> tt 632.62/291.53 U81(tt) -> tt 632.62/291.53 isList(V) -> U11(isNeList(activate(V))) 632.62/291.53 isList(n__nil) -> tt 632.62/291.53 isList(n____(V1, V2)) -> U21(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(V) -> U31(isQid(activate(V))) 632.62/291.53 isNeList(n____(V1, V2)) -> U41(isList(activate(V1)), activate(V2)) 632.62/291.53 isNeList(n____(V1, V2)) -> U51(isNeList(activate(V1)), activate(V2)) 632.62/291.53 isNePal(V) -> U61(isQid(activate(V))) 632.62/291.53 isNePal(n____(I, __(P, I))) -> U71(isQid(activate(I)), activate(P)) 632.62/291.53 isPal(V) -> U81(isNePal(activate(V))) 632.62/291.53 isPal(n__nil) -> tt 632.62/291.53 isQid(n__a) -> tt 632.62/291.53 isQid(n__e) -> tt 632.62/291.53 isQid(n__i) -> tt 632.62/291.53 isQid(n__o) -> tt 632.62/291.53 isQid(n__u) -> tt 632.62/291.53 nil -> n__nil 632.62/291.53 __(X1, X2) -> n____(X1, X2) 632.62/291.53 a -> n__a 632.62/291.53 e -> n__e 632.62/291.53 i -> n__i 632.62/291.53 o -> n__o 632.62/291.53 u -> n__u 632.62/291.53 activate(n__nil) -> nil 632.62/291.53 activate(n____(X1, X2)) -> __(X1, X2) 632.62/291.53 activate(n__a) -> a 632.62/291.53 activate(n__e) -> e 632.62/291.53 activate(n__i) -> i 632.62/291.53 activate(n__o) -> o 632.62/291.53 activate(n__u) -> u 632.62/291.53 activate(X) -> X 632.62/291.53 632.62/291.53 S is empty. 632.62/291.53 Rewrite Strategy: FULL 632.68/291.59 EOF