15.38/4.86 WORST_CASE(Omega(n^1), O(n^1)) 15.71/4.87 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 15.71/4.87 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 15.71/4.87 15.71/4.87 15.71/4.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 15.71/4.87 15.71/4.87 (0) CpxTRS 15.71/4.87 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 15.71/4.87 (2) CdtProblem 15.71/4.87 (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 15.71/4.87 (4) CdtProblem 15.71/4.87 (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 15.71/4.87 (6) CdtProblem 15.71/4.87 (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 15.71/4.87 (8) CdtProblem 15.71/4.87 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 76 ms] 15.71/4.87 (10) CdtProblem 15.71/4.87 (11) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 15.71/4.87 (12) BOUNDS(1, 1) 15.71/4.87 (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 15.71/4.87 (14) TRS for Loop Detection 15.71/4.87 (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 15.71/4.87 (16) BEST 15.71/4.87 (17) proven lower bound 15.71/4.87 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 15.71/4.87 (19) BOUNDS(n^1, INF) 15.71/4.87 (20) TRS for Loop Detection 15.71/4.87 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (0) 15.71/4.87 Obligation: 15.71/4.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 15.71/4.87 15.71/4.87 15.71/4.87 The TRS R consists of the following rules: 15.71/4.87 15.71/4.87 foldl(x, Cons(S(0), xs)) -> foldl(S(x), xs) 15.71/4.87 foldl(S(0), Cons(x, xs)) -> foldl(S(x), xs) 15.71/4.87 foldr(a, Cons(x, xs)) -> op(x, foldr(a, xs)) 15.71/4.87 foldr(a, Nil) -> a 15.71/4.87 foldl(a, Nil) -> a 15.71/4.87 notEmpty(Cons(x, xs)) -> True 15.71/4.87 notEmpty(Nil) -> False 15.71/4.87 op(x, S(0)) -> S(x) 15.71/4.87 op(S(0), y) -> S(y) 15.71/4.87 fold(a, xs) -> Cons(foldl(a, xs), Cons(foldr(a, xs), Nil)) 15.71/4.87 15.71/4.87 S is empty. 15.71/4.87 Rewrite Strategy: INNERMOST 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 15.71/4.87 Converted Cpx (relative) TRS to CDT 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (2) 15.71/4.87 Obligation: 15.71/4.87 Complexity Dependency Tuples Problem 15.71/4.87 15.71/4.87 Rules: 15.71/4.87 foldl(z0, Cons(S(0), z1)) -> foldl(S(z0), z1) 15.71/4.87 foldl(S(0), Cons(z0, z1)) -> foldl(S(z0), z1) 15.71/4.87 foldl(z0, Nil) -> z0 15.71/4.87 foldr(z0, Cons(z1, z2)) -> op(z1, foldr(z0, z2)) 15.71/4.87 foldr(z0, Nil) -> z0 15.71/4.87 notEmpty(Cons(z0, z1)) -> True 15.71/4.87 notEmpty(Nil) -> False 15.71/4.87 op(z0, S(0)) -> S(z0) 15.71/4.87 op(S(0), z0) -> S(z0) 15.71/4.87 fold(z0, z1) -> Cons(foldl(z0, z1), Cons(foldr(z0, z1), Nil)) 15.71/4.87 Tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(z0, Nil) -> c2 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(OP(z1, foldr(z0, z2)), FOLDR(z0, z2)) 15.71/4.87 FOLDR(z0, Nil) -> c4 15.71/4.87 NOTEMPTY(Cons(z0, z1)) -> c5 15.71/4.87 NOTEMPTY(Nil) -> c6 15.71/4.87 OP(z0, S(0)) -> c7 15.71/4.87 OP(S(0), z0) -> c8 15.71/4.87 FOLD(z0, z1) -> c9(FOLDL(z0, z1), FOLDR(z0, z1)) 15.71/4.87 S tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(z0, Nil) -> c2 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(OP(z1, foldr(z0, z2)), FOLDR(z0, z2)) 15.71/4.87 FOLDR(z0, Nil) -> c4 15.71/4.87 NOTEMPTY(Cons(z0, z1)) -> c5 15.71/4.87 NOTEMPTY(Nil) -> c6 15.71/4.87 OP(z0, S(0)) -> c7 15.71/4.87 OP(S(0), z0) -> c8 15.71/4.87 FOLD(z0, z1) -> c9(FOLDL(z0, z1), FOLDR(z0, z1)) 15.71/4.87 K tuples:none 15.71/4.87 Defined Rule Symbols: foldl_2, foldr_2, notEmpty_1, op_2, fold_2 15.71/4.87 15.71/4.87 Defined Pair Symbols: FOLDL_2, FOLDR_2, NOTEMPTY_1, OP_2, FOLD_2 15.71/4.87 15.71/4.87 Compound Symbols: c_1, c1_1, c2, c3_2, c4, c5, c6, c7, c8, c9_2 15.71/4.87 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (3) CdtLeafRemovalProof (ComplexityIfPolyImplication) 15.71/4.87 Removed 1 leading nodes: 15.71/4.87 FOLD(z0, z1) -> c9(FOLDL(z0, z1), FOLDR(z0, z1)) 15.71/4.87 Removed 6 trailing nodes: 15.71/4.87 NOTEMPTY(Cons(z0, z1)) -> c5 15.71/4.87 FOLDL(z0, Nil) -> c2 15.71/4.87 NOTEMPTY(Nil) -> c6 15.71/4.87 OP(z0, S(0)) -> c7 15.71/4.87 FOLDR(z0, Nil) -> c4 15.71/4.87 OP(S(0), z0) -> c8 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (4) 15.71/4.87 Obligation: 15.71/4.87 Complexity Dependency Tuples Problem 15.71/4.87 15.71/4.87 Rules: 15.71/4.87 foldl(z0, Cons(S(0), z1)) -> foldl(S(z0), z1) 15.71/4.87 foldl(S(0), Cons(z0, z1)) -> foldl(S(z0), z1) 15.71/4.87 foldl(z0, Nil) -> z0 15.71/4.87 foldr(z0, Cons(z1, z2)) -> op(z1, foldr(z0, z2)) 15.71/4.87 foldr(z0, Nil) -> z0 15.71/4.87 notEmpty(Cons(z0, z1)) -> True 15.71/4.87 notEmpty(Nil) -> False 15.71/4.87 op(z0, S(0)) -> S(z0) 15.71/4.87 op(S(0), z0) -> S(z0) 15.71/4.87 fold(z0, z1) -> Cons(foldl(z0, z1), Cons(foldr(z0, z1), Nil)) 15.71/4.87 Tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(OP(z1, foldr(z0, z2)), FOLDR(z0, z2)) 15.71/4.87 S tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(OP(z1, foldr(z0, z2)), FOLDR(z0, z2)) 15.71/4.87 K tuples:none 15.71/4.87 Defined Rule Symbols: foldl_2, foldr_2, notEmpty_1, op_2, fold_2 15.71/4.87 15.71/4.87 Defined Pair Symbols: FOLDL_2, FOLDR_2 15.71/4.87 15.71/4.87 Compound Symbols: c_1, c1_1, c3_2 15.71/4.87 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 15.71/4.87 Removed 1 trailing tuple parts 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (6) 15.71/4.87 Obligation: 15.71/4.87 Complexity Dependency Tuples Problem 15.71/4.87 15.71/4.87 Rules: 15.71/4.87 foldl(z0, Cons(S(0), z1)) -> foldl(S(z0), z1) 15.71/4.87 foldl(S(0), Cons(z0, z1)) -> foldl(S(z0), z1) 15.71/4.87 foldl(z0, Nil) -> z0 15.71/4.87 foldr(z0, Cons(z1, z2)) -> op(z1, foldr(z0, z2)) 15.71/4.87 foldr(z0, Nil) -> z0 15.71/4.87 notEmpty(Cons(z0, z1)) -> True 15.71/4.87 notEmpty(Nil) -> False 15.71/4.87 op(z0, S(0)) -> S(z0) 15.71/4.87 op(S(0), z0) -> S(z0) 15.71/4.87 fold(z0, z1) -> Cons(foldl(z0, z1), Cons(foldr(z0, z1), Nil)) 15.71/4.87 Tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(FOLDR(z0, z2)) 15.71/4.87 S tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(FOLDR(z0, z2)) 15.71/4.87 K tuples:none 15.71/4.87 Defined Rule Symbols: foldl_2, foldr_2, notEmpty_1, op_2, fold_2 15.71/4.87 15.71/4.87 Defined Pair Symbols: FOLDL_2, FOLDR_2 15.71/4.87 15.71/4.87 Compound Symbols: c_1, c1_1, c3_1 15.71/4.87 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 15.71/4.87 The following rules are not usable and were removed: 15.71/4.87 foldl(z0, Cons(S(0), z1)) -> foldl(S(z0), z1) 15.71/4.87 foldl(S(0), Cons(z0, z1)) -> foldl(S(z0), z1) 15.71/4.87 foldl(z0, Nil) -> z0 15.71/4.87 foldr(z0, Cons(z1, z2)) -> op(z1, foldr(z0, z2)) 15.71/4.87 foldr(z0, Nil) -> z0 15.71/4.87 notEmpty(Cons(z0, z1)) -> True 15.71/4.87 notEmpty(Nil) -> False 15.71/4.87 op(z0, S(0)) -> S(z0) 15.71/4.87 op(S(0), z0) -> S(z0) 15.71/4.87 fold(z0, z1) -> Cons(foldl(z0, z1), Cons(foldr(z0, z1), Nil)) 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (8) 15.71/4.87 Obligation: 15.71/4.87 Complexity Dependency Tuples Problem 15.71/4.87 15.71/4.87 Rules:none 15.71/4.87 Tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(FOLDR(z0, z2)) 15.71/4.87 S tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(FOLDR(z0, z2)) 15.71/4.87 K tuples:none 15.71/4.87 Defined Rule Symbols:none 15.71/4.87 15.71/4.87 Defined Pair Symbols: FOLDL_2, FOLDR_2 15.71/4.87 15.71/4.87 Compound Symbols: c_1, c1_1, c3_1 15.71/4.87 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 15.71/4.87 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(FOLDR(z0, z2)) 15.71/4.87 We considered the (Usable) Rules:none 15.71/4.87 And the Tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(FOLDR(z0, z2)) 15.71/4.87 The order we found is given by the following interpretation: 15.71/4.87 15.71/4.87 Polynomial interpretation : 15.71/4.87 15.71/4.87 POL(0) = [1] 15.71/4.87 POL(Cons(x_1, x_2)) = [1] + x_1 + x_2 15.71/4.87 POL(FOLDL(x_1, x_2)) = x_1 + x_2 15.71/4.87 POL(FOLDR(x_1, x_2)) = x_2 15.71/4.87 POL(S(x_1)) = x_1 15.71/4.87 POL(c(x_1)) = x_1 15.71/4.87 POL(c1(x_1)) = x_1 15.71/4.87 POL(c3(x_1)) = x_1 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (10) 15.71/4.87 Obligation: 15.71/4.87 Complexity Dependency Tuples Problem 15.71/4.87 15.71/4.87 Rules:none 15.71/4.87 Tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(FOLDR(z0, z2)) 15.71/4.87 S tuples:none 15.71/4.87 K tuples: 15.71/4.87 FOLDL(z0, Cons(S(0), z1)) -> c(FOLDL(S(z0), z1)) 15.71/4.87 FOLDL(S(0), Cons(z0, z1)) -> c1(FOLDL(S(z0), z1)) 15.71/4.87 FOLDR(z0, Cons(z1, z2)) -> c3(FOLDR(z0, z2)) 15.71/4.87 Defined Rule Symbols:none 15.71/4.87 15.71/4.87 Defined Pair Symbols: FOLDL_2, FOLDR_2 15.71/4.87 15.71/4.87 Compound Symbols: c_1, c1_1, c3_1 15.71/4.87 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (11) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 15.71/4.87 The set S is empty 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (12) 15.71/4.87 BOUNDS(1, 1) 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 15.71/4.87 Transformed a relative TRS into a decreasing-loop problem. 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (14) 15.71/4.87 Obligation: 15.71/4.87 Analyzing the following TRS for decreasing loops: 15.71/4.87 15.71/4.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 15.71/4.87 15.71/4.87 15.71/4.87 The TRS R consists of the following rules: 15.71/4.87 15.71/4.87 foldl(x, Cons(S(0), xs)) -> foldl(S(x), xs) 15.71/4.87 foldl(S(0), Cons(x, xs)) -> foldl(S(x), xs) 15.71/4.87 foldr(a, Cons(x, xs)) -> op(x, foldr(a, xs)) 15.71/4.87 foldr(a, Nil) -> a 15.71/4.87 foldl(a, Nil) -> a 15.71/4.87 notEmpty(Cons(x, xs)) -> True 15.71/4.87 notEmpty(Nil) -> False 15.71/4.87 op(x, S(0)) -> S(x) 15.71/4.87 op(S(0), y) -> S(y) 15.71/4.87 fold(a, xs) -> Cons(foldl(a, xs), Cons(foldr(a, xs), Nil)) 15.71/4.87 15.71/4.87 S is empty. 15.71/4.87 Rewrite Strategy: INNERMOST 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (15) DecreasingLoopProof (LOWER BOUND(ID)) 15.71/4.87 The following loop(s) give(s) rise to the lower bound Omega(n^1): 15.71/4.87 15.71/4.87 The rewrite sequence 15.71/4.87 15.71/4.87 foldl(x, Cons(S(0), xs)) ->^+ foldl(S(x), xs) 15.71/4.87 15.71/4.87 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 15.71/4.87 15.71/4.87 The pumping substitution is [xs / Cons(S(0), xs)]. 15.71/4.87 15.71/4.87 The result substitution is [x / S(x)]. 15.71/4.87 15.71/4.87 15.71/4.87 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (16) 15.71/4.87 Complex Obligation (BEST) 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (17) 15.71/4.87 Obligation: 15.71/4.87 Proved the lower bound n^1 for the following obligation: 15.71/4.87 15.71/4.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 15.71/4.87 15.71/4.87 15.71/4.87 The TRS R consists of the following rules: 15.71/4.87 15.71/4.87 foldl(x, Cons(S(0), xs)) -> foldl(S(x), xs) 15.71/4.87 foldl(S(0), Cons(x, xs)) -> foldl(S(x), xs) 15.71/4.87 foldr(a, Cons(x, xs)) -> op(x, foldr(a, xs)) 15.71/4.87 foldr(a, Nil) -> a 15.71/4.87 foldl(a, Nil) -> a 15.71/4.87 notEmpty(Cons(x, xs)) -> True 15.71/4.87 notEmpty(Nil) -> False 15.71/4.87 op(x, S(0)) -> S(x) 15.71/4.87 op(S(0), y) -> S(y) 15.71/4.87 fold(a, xs) -> Cons(foldl(a, xs), Cons(foldr(a, xs), Nil)) 15.71/4.87 15.71/4.87 S is empty. 15.71/4.87 Rewrite Strategy: INNERMOST 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (18) LowerBoundPropagationProof (FINISHED) 15.71/4.87 Propagated lower bound. 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (19) 15.71/4.87 BOUNDS(n^1, INF) 15.71/4.87 15.71/4.87 ---------------------------------------- 15.71/4.87 15.71/4.87 (20) 15.71/4.87 Obligation: 15.71/4.87 Analyzing the following TRS for decreasing loops: 15.71/4.87 15.71/4.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 15.71/4.87 15.71/4.87 15.71/4.87 The TRS R consists of the following rules: 15.71/4.87 15.71/4.87 foldl(x, Cons(S(0), xs)) -> foldl(S(x), xs) 15.71/4.87 foldl(S(0), Cons(x, xs)) -> foldl(S(x), xs) 15.71/4.87 foldr(a, Cons(x, xs)) -> op(x, foldr(a, xs)) 15.71/4.87 foldr(a, Nil) -> a 15.71/4.87 foldl(a, Nil) -> a 15.71/4.87 notEmpty(Cons(x, xs)) -> True 15.71/4.87 notEmpty(Nil) -> False 15.71/4.87 op(x, S(0)) -> S(x) 15.71/4.87 op(S(0), y) -> S(y) 15.71/4.87 fold(a, xs) -> Cons(foldl(a, xs), Cons(foldr(a, xs), Nil)) 15.71/4.87 15.71/4.87 S is empty. 15.71/4.87 Rewrite Strategy: INNERMOST 15.79/5.00 EOF