3.28/1.59 WORST_CASE(NON_POLY, ?) 3.28/1.60 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.28/1.60 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.28/1.60 3.28/1.60 3.28/1.60 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 3.28/1.60 3.28/1.60 (0) CpxTRS 3.28/1.60 (1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 3.28/1.60 (2) TRS for Loop Detection 3.28/1.60 (3) InfiniteLowerBoundProof [FINISHED, 0 ms] 3.28/1.60 (4) BOUNDS(INF, INF) 3.28/1.60 3.28/1.60 3.28/1.60 ---------------------------------------- 3.28/1.60 3.28/1.60 (0) 3.28/1.60 Obligation: 3.28/1.60 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 3.28/1.60 3.28/1.60 3.28/1.60 The TRS R consists of the following rules: 3.28/1.60 3.28/1.60 __(__(X, Y), Z) -> __(X, __(Y, Z)) 3.28/1.60 __(X, nil) -> X 3.28/1.60 __(nil, X) -> X 3.28/1.60 U11(tt) -> U12(isPalListKind) 3.28/1.60 U12(tt) -> U13(isNeList) 3.28/1.60 U13(tt) -> tt 3.28/1.60 U21(tt) -> U22(isPalListKind) 3.28/1.60 U22(tt) -> U23(isPalListKind) 3.28/1.60 U23(tt) -> U24(isPalListKind) 3.28/1.60 U24(tt) -> U25(isList) 3.28/1.60 U25(tt) -> U26(isList) 3.28/1.60 U26(tt) -> tt 3.28/1.60 U31(tt) -> U32(isPalListKind) 3.28/1.60 U32(tt) -> U33(isQid) 3.28/1.60 U33(tt) -> tt 3.28/1.60 U41(tt) -> U42(isPalListKind) 3.28/1.60 U42(tt) -> U43(isPalListKind) 3.28/1.60 U43(tt) -> U44(isPalListKind) 3.28/1.60 U44(tt) -> U45(isList) 3.28/1.60 U45(tt) -> U46(isNeList) 3.28/1.60 U46(tt) -> tt 3.28/1.60 U51(tt) -> U52(isPalListKind) 3.28/1.60 U52(tt) -> U53(isPalListKind) 3.28/1.60 U53(tt) -> U54(isPalListKind) 3.28/1.60 U54(tt) -> U55(isNeList) 3.28/1.60 U55(tt) -> U56(isList) 3.28/1.60 U56(tt) -> tt 3.28/1.60 U61(tt) -> U62(isPalListKind) 3.28/1.60 U62(tt) -> U63(isQid) 3.28/1.60 U63(tt) -> tt 3.28/1.60 U71(tt) -> U72(isPalListKind) 3.28/1.60 U72(tt) -> U73(isPal) 3.28/1.60 U73(tt) -> U74(isPalListKind) 3.28/1.60 U74(tt) -> tt 3.28/1.60 U81(tt) -> U82(isPalListKind) 3.28/1.60 U82(tt) -> U83(isNePal) 3.28/1.60 U83(tt) -> tt 3.28/1.60 U91(tt) -> U92(isPalListKind) 3.28/1.60 U92(tt) -> tt 3.28/1.60 isList -> U11(isPalListKind) 3.28/1.60 isList -> tt 3.28/1.60 isList -> U21(isPalListKind) 3.28/1.60 isNeList -> U31(isPalListKind) 3.28/1.60 isNeList -> U41(isPalListKind) 3.28/1.60 isNeList -> U51(isPalListKind) 3.28/1.60 isNePal -> U61(isPalListKind) 3.28/1.60 isNePal -> U71(isQid) 3.28/1.60 isPal -> U81(isPalListKind) 3.28/1.60 isPal -> tt 3.28/1.60 isPalListKind -> tt 3.28/1.60 isPalListKind -> U91(isPalListKind) 3.28/1.60 isQid -> tt 3.28/1.60 3.28/1.60 S is empty. 3.28/1.60 Rewrite Strategy: FULL 3.28/1.60 ---------------------------------------- 3.28/1.60 3.28/1.60 (1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 3.28/1.60 Transformed a relative TRS into a decreasing-loop problem. 3.28/1.60 ---------------------------------------- 3.28/1.60 3.28/1.60 (2) 3.28/1.60 Obligation: 3.28/1.60 Analyzing the following TRS for decreasing loops: 3.28/1.60 3.28/1.60 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(INF, INF). 3.28/1.60 3.28/1.60 3.28/1.60 The TRS R consists of the following rules: 3.28/1.60 3.28/1.60 __(__(X, Y), Z) -> __(X, __(Y, Z)) 3.28/1.60 __(X, nil) -> X 3.28/1.60 __(nil, X) -> X 3.28/1.60 U11(tt) -> U12(isPalListKind) 3.28/1.60 U12(tt) -> U13(isNeList) 3.28/1.60 U13(tt) -> tt 3.28/1.60 U21(tt) -> U22(isPalListKind) 3.28/1.60 U22(tt) -> U23(isPalListKind) 3.28/1.60 U23(tt) -> U24(isPalListKind) 3.28/1.60 U24(tt) -> U25(isList) 3.28/1.60 U25(tt) -> U26(isList) 3.28/1.60 U26(tt) -> tt 3.28/1.60 U31(tt) -> U32(isPalListKind) 3.28/1.60 U32(tt) -> U33(isQid) 3.28/1.60 U33(tt) -> tt 3.28/1.60 U41(tt) -> U42(isPalListKind) 3.28/1.60 U42(tt) -> U43(isPalListKind) 3.28/1.60 U43(tt) -> U44(isPalListKind) 3.28/1.60 U44(tt) -> U45(isList) 3.28/1.60 U45(tt) -> U46(isNeList) 3.28/1.60 U46(tt) -> tt 3.28/1.60 U51(tt) -> U52(isPalListKind) 3.28/1.60 U52(tt) -> U53(isPalListKind) 3.28/1.60 U53(tt) -> U54(isPalListKind) 3.28/1.60 U54(tt) -> U55(isNeList) 3.28/1.60 U55(tt) -> U56(isList) 3.28/1.60 U56(tt) -> tt 3.28/1.60 U61(tt) -> U62(isPalListKind) 3.28/1.60 U62(tt) -> U63(isQid) 3.28/1.60 U63(tt) -> tt 3.28/1.60 U71(tt) -> U72(isPalListKind) 3.28/1.60 U72(tt) -> U73(isPal) 3.28/1.60 U73(tt) -> U74(isPalListKind) 3.28/1.60 U74(tt) -> tt 3.28/1.60 U81(tt) -> U82(isPalListKind) 3.28/1.60 U82(tt) -> U83(isNePal) 3.28/1.60 U83(tt) -> tt 3.28/1.60 U91(tt) -> U92(isPalListKind) 3.28/1.60 U92(tt) -> tt 3.28/1.60 isList -> U11(isPalListKind) 3.28/1.60 isList -> tt 3.28/1.60 isList -> U21(isPalListKind) 3.28/1.60 isNeList -> U31(isPalListKind) 3.28/1.60 isNeList -> U41(isPalListKind) 3.28/1.60 isNeList -> U51(isPalListKind) 3.28/1.60 isNePal -> U61(isPalListKind) 3.28/1.60 isNePal -> U71(isQid) 3.28/1.60 isPal -> U81(isPalListKind) 3.28/1.60 isPal -> tt 3.28/1.60 isPalListKind -> tt 3.28/1.60 isPalListKind -> U91(isPalListKind) 3.28/1.60 isQid -> tt 3.28/1.60 3.28/1.60 S is empty. 3.28/1.60 Rewrite Strategy: FULL 3.28/1.60 ---------------------------------------- 3.28/1.60 3.28/1.60 (3) InfiniteLowerBoundProof (FINISHED) 3.28/1.60 The following loop proves infinite runtime complexity: 3.28/1.60 3.28/1.60 The rewrite sequence 3.28/1.60 3.28/1.60 isPalListKind ->^+ U91(isPalListKind) 3.28/1.60 3.28/1.60 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 3.28/1.60 3.28/1.60 The pumping substitution is [ ]. 3.28/1.60 3.28/1.60 The result substitution is [ ]. 3.28/1.60 3.28/1.60 3.28/1.60 3.28/1.60 3.28/1.60 ---------------------------------------- 3.28/1.60 3.28/1.60 (4) 3.28/1.60 BOUNDS(INF, INF) 3.34/1.64 EOF