343.61/291.46 WORST_CASE(Omega(n^1), O(n^2)) 343.61/291.47 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 343.61/291.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 343.61/291.47 343.61/291.47 343.61/291.47 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 343.61/291.47 343.61/291.47 (0) CpxRelTRS 343.61/291.47 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 250 ms] 343.61/291.47 (2) CpxRelTRS 343.61/291.47 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 343.61/291.47 (4) CdtProblem 343.61/291.47 (5) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 343.61/291.47 (6) CdtProblem 343.61/291.47 (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 343.61/291.47 (8) CdtProblem 343.61/291.47 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 33 ms] 343.61/291.47 (10) CdtProblem 343.61/291.47 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 127 ms] 343.61/291.47 (12) CdtProblem 343.61/291.47 (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 343.61/291.47 (14) BOUNDS(1, 1) 343.61/291.47 (15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 343.61/291.47 (16) TRS for Loop Detection 343.61/291.47 (17) DecreasingLoopProof [LOWER BOUND(ID), 48 ms] 343.61/291.47 (18) BEST 343.61/291.47 (19) proven lower bound 343.61/291.47 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 343.61/291.47 (21) BOUNDS(n^1, INF) 343.61/291.47 (22) TRS for Loop Detection 343.61/291.47 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (0) 343.61/291.47 Obligation: 343.61/291.47 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 343.61/291.47 343.61/291.47 343.61/291.47 The TRS R consists of the following rules: 343.61/291.47 343.61/291.47 loop(Cons(x, xs), Nil, pp, ss) -> False 343.61/291.47 loop(Cons(x', xs'), Cons(x, xs), pp, ss) -> loop[Ite](!EQ(x', x), Cons(x', xs'), Cons(x, xs), pp, ss) 343.61/291.47 loop(Nil, s, pp, ss) -> True 343.61/291.47 match1(p, s) -> loop(p, s, p, s) 343.61/291.47 343.61/291.47 The (relative) TRS S consists of the following rules: 343.61/291.47 343.61/291.47 !EQ(S(x), S(y)) -> !EQ(x, y) 343.61/291.47 !EQ(0, S(y)) -> False 343.61/291.47 !EQ(S(x), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 loop[Ite](False, p, s, pp, Cons(x, xs)) -> loop(pp, xs, pp, xs) 343.61/291.47 loop[Ite](True, Cons(x', xs'), Cons(x, xs), pp, ss) -> loop(xs', xs, pp, ss) 343.61/291.47 343.61/291.47 Rewrite Strategy: INNERMOST 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 343.61/291.47 proved termination of relative rules 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (2) 343.61/291.47 Obligation: 343.61/291.47 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 343.61/291.47 343.61/291.47 343.61/291.47 The TRS R consists of the following rules: 343.61/291.47 343.61/291.47 loop(Cons(x, xs), Nil, pp, ss) -> False 343.61/291.47 loop(Cons(x', xs'), Cons(x, xs), pp, ss) -> loop[Ite](!EQ(x', x), Cons(x', xs'), Cons(x, xs), pp, ss) 343.61/291.47 loop(Nil, s, pp, ss) -> True 343.61/291.47 match1(p, s) -> loop(p, s, p, s) 343.61/291.47 343.61/291.47 The (relative) TRS S consists of the following rules: 343.61/291.47 343.61/291.47 !EQ(S(x), S(y)) -> !EQ(x, y) 343.61/291.47 !EQ(0, S(y)) -> False 343.61/291.47 !EQ(S(x), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 loop[Ite](False, p, s, pp, Cons(x, xs)) -> loop(pp, xs, pp, xs) 343.61/291.47 loop[Ite](True, Cons(x', xs'), Cons(x, xs), pp, ss) -> loop(xs', xs, pp, ss) 343.61/291.47 343.61/291.47 Rewrite Strategy: INNERMOST 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 343.61/291.47 Converted Cpx (relative) TRS to CDT 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (4) 343.61/291.47 Obligation: 343.61/291.47 Complexity Dependency Tuples Problem 343.61/291.47 343.61/291.47 Rules: 343.61/291.47 !EQ(S(z0), S(z1)) -> !EQ(z0, z1) 343.61/291.47 !EQ(0, S(z0)) -> False 343.61/291.47 !EQ(S(z0), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 loop[Ite](False, z0, z1, z2, Cons(z3, z4)) -> loop(z2, z4, z2, z4) 343.61/291.47 loop[Ite](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> loop(z1, z3, z4, z5) 343.61/291.47 loop(Cons(z0, z1), Nil, z2, z3) -> False 343.61/291.47 loop(Cons(z0, z1), Cons(z2, z3), z4, z5) -> loop[Ite](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5) 343.61/291.47 loop(Nil, z0, z1, z2) -> True 343.61/291.47 match1(z0, z1) -> loop(z0, z1, z0, z1) 343.61/291.47 Tuples: 343.61/291.47 !EQ'(S(z0), S(z1)) -> c(!EQ'(z0, z1)) 343.61/291.47 !EQ'(0, S(z0)) -> c1 343.61/291.47 !EQ'(S(z0), 0) -> c2 343.61/291.47 !EQ'(0, 0) -> c3 343.61/291.47 LOOP[ITE](False, z0, z1, z2, Cons(z3, z4)) -> c4(LOOP(z2, z4, z2, z4)) 343.61/291.47 LOOP[ITE](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> c5(LOOP(z1, z3, z4, z5)) 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 MATCH1(z0, z1) -> c9(LOOP(z0, z1, z0, z1)) 343.61/291.47 S tuples: 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 MATCH1(z0, z1) -> c9(LOOP(z0, z1, z0, z1)) 343.61/291.47 K tuples:none 343.61/291.47 Defined Rule Symbols: loop_4, match1_2, !EQ_2, loop[Ite]_5 343.61/291.47 343.61/291.47 Defined Pair Symbols: !EQ'_2, LOOP[ITE]_5, LOOP_4, MATCH1_2 343.61/291.47 343.61/291.47 Compound Symbols: c_1, c1, c2, c3, c4_1, c5_1, c6, c7_2, c8, c9_1 343.61/291.47 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (5) CdtLeafRemovalProof (ComplexityIfPolyImplication) 343.61/291.47 Removed 1 leading nodes: 343.61/291.47 MATCH1(z0, z1) -> c9(LOOP(z0, z1, z0, z1)) 343.61/291.47 Removed 3 trailing nodes: 343.61/291.47 !EQ'(0, 0) -> c3 343.61/291.47 !EQ'(S(z0), 0) -> c2 343.61/291.47 !EQ'(0, S(z0)) -> c1 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (6) 343.61/291.47 Obligation: 343.61/291.47 Complexity Dependency Tuples Problem 343.61/291.47 343.61/291.47 Rules: 343.61/291.47 !EQ(S(z0), S(z1)) -> !EQ(z0, z1) 343.61/291.47 !EQ(0, S(z0)) -> False 343.61/291.47 !EQ(S(z0), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 loop[Ite](False, z0, z1, z2, Cons(z3, z4)) -> loop(z2, z4, z2, z4) 343.61/291.47 loop[Ite](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> loop(z1, z3, z4, z5) 343.61/291.47 loop(Cons(z0, z1), Nil, z2, z3) -> False 343.61/291.47 loop(Cons(z0, z1), Cons(z2, z3), z4, z5) -> loop[Ite](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5) 343.61/291.47 loop(Nil, z0, z1, z2) -> True 343.61/291.47 match1(z0, z1) -> loop(z0, z1, z0, z1) 343.61/291.47 Tuples: 343.61/291.47 !EQ'(S(z0), S(z1)) -> c(!EQ'(z0, z1)) 343.61/291.47 LOOP[ITE](False, z0, z1, z2, Cons(z3, z4)) -> c4(LOOP(z2, z4, z2, z4)) 343.61/291.47 LOOP[ITE](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> c5(LOOP(z1, z3, z4, z5)) 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 S tuples: 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 K tuples:none 343.61/291.47 Defined Rule Symbols: loop_4, match1_2, !EQ_2, loop[Ite]_5 343.61/291.47 343.61/291.47 Defined Pair Symbols: !EQ'_2, LOOP[ITE]_5, LOOP_4 343.61/291.47 343.61/291.47 Compound Symbols: c_1, c4_1, c5_1, c6, c7_2, c8 343.61/291.47 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 343.61/291.47 The following rules are not usable and were removed: 343.61/291.47 loop[Ite](False, z0, z1, z2, Cons(z3, z4)) -> loop(z2, z4, z2, z4) 343.61/291.47 loop[Ite](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> loop(z1, z3, z4, z5) 343.61/291.47 loop(Cons(z0, z1), Nil, z2, z3) -> False 343.61/291.47 loop(Cons(z0, z1), Cons(z2, z3), z4, z5) -> loop[Ite](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5) 343.61/291.47 loop(Nil, z0, z1, z2) -> True 343.61/291.47 match1(z0, z1) -> loop(z0, z1, z0, z1) 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (8) 343.61/291.47 Obligation: 343.61/291.47 Complexity Dependency Tuples Problem 343.61/291.47 343.61/291.47 Rules: 343.61/291.47 !EQ(S(z0), S(z1)) -> !EQ(z0, z1) 343.61/291.47 !EQ(0, S(z0)) -> False 343.61/291.47 !EQ(S(z0), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 Tuples: 343.61/291.47 !EQ'(S(z0), S(z1)) -> c(!EQ'(z0, z1)) 343.61/291.47 LOOP[ITE](False, z0, z1, z2, Cons(z3, z4)) -> c4(LOOP(z2, z4, z2, z4)) 343.61/291.47 LOOP[ITE](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> c5(LOOP(z1, z3, z4, z5)) 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 S tuples: 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 K tuples:none 343.61/291.47 Defined Rule Symbols: !EQ_2 343.61/291.47 343.61/291.47 Defined Pair Symbols: !EQ'_2, LOOP[ITE]_5, LOOP_4 343.61/291.47 343.61/291.47 Compound Symbols: c_1, c4_1, c5_1, c6, c7_2, c8 343.61/291.47 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 343.61/291.47 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 We considered the (Usable) Rules:none 343.61/291.47 And the Tuples: 343.61/291.47 !EQ'(S(z0), S(z1)) -> c(!EQ'(z0, z1)) 343.61/291.47 LOOP[ITE](False, z0, z1, z2, Cons(z3, z4)) -> c4(LOOP(z2, z4, z2, z4)) 343.61/291.47 LOOP[ITE](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> c5(LOOP(z1, z3, z4, z5)) 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 The order we found is given by the following interpretation: 343.61/291.47 343.61/291.47 Polynomial interpretation : 343.61/291.47 343.61/291.47 POL(!EQ(x_1, x_2)) = [3] 343.61/291.47 POL(!EQ'(x_1, x_2)) = 0 343.61/291.47 POL(0) = [3] 343.61/291.47 POL(Cons(x_1, x_2)) = [1] + x_2 343.61/291.47 POL(False) = [3] 343.61/291.47 POL(LOOP(x_1, x_2, x_3, x_4)) = [2] + [2]x_4 343.61/291.47 POL(LOOP[ITE](x_1, x_2, x_3, x_4, x_5)) = [2] + [2]x_5 343.61/291.47 POL(Nil) = [3] 343.61/291.47 POL(S(x_1)) = [3] + x_1 343.61/291.47 POL(True) = [3] 343.61/291.47 POL(c(x_1)) = x_1 343.61/291.47 POL(c4(x_1)) = x_1 343.61/291.47 POL(c5(x_1)) = x_1 343.61/291.47 POL(c6) = 0 343.61/291.47 POL(c7(x_1, x_2)) = x_1 + x_2 343.61/291.47 POL(c8) = 0 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (10) 343.61/291.47 Obligation: 343.61/291.47 Complexity Dependency Tuples Problem 343.61/291.47 343.61/291.47 Rules: 343.61/291.47 !EQ(S(z0), S(z1)) -> !EQ(z0, z1) 343.61/291.47 !EQ(0, S(z0)) -> False 343.61/291.47 !EQ(S(z0), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 Tuples: 343.61/291.47 !EQ'(S(z0), S(z1)) -> c(!EQ'(z0, z1)) 343.61/291.47 LOOP[ITE](False, z0, z1, z2, Cons(z3, z4)) -> c4(LOOP(z2, z4, z2, z4)) 343.61/291.47 LOOP[ITE](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> c5(LOOP(z1, z3, z4, z5)) 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 S tuples: 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 K tuples: 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 Defined Rule Symbols: !EQ_2 343.61/291.47 343.61/291.47 Defined Pair Symbols: !EQ'_2, LOOP[ITE]_5, LOOP_4 343.61/291.47 343.61/291.47 Compound Symbols: c_1, c4_1, c5_1, c6, c7_2, c8 343.61/291.47 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 343.61/291.47 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 We considered the (Usable) Rules:none 343.61/291.47 And the Tuples: 343.61/291.47 !EQ'(S(z0), S(z1)) -> c(!EQ'(z0, z1)) 343.61/291.47 LOOP[ITE](False, z0, z1, z2, Cons(z3, z4)) -> c4(LOOP(z2, z4, z2, z4)) 343.61/291.47 LOOP[ITE](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> c5(LOOP(z1, z3, z4, z5)) 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 The order we found is given by the following interpretation: 343.61/291.47 343.61/291.47 Polynomial interpretation : 343.61/291.47 343.61/291.47 POL(!EQ(x_1, x_2)) = 0 343.61/291.47 POL(!EQ'(x_1, x_2)) = 0 343.61/291.47 POL(0) = 0 343.61/291.47 POL(Cons(x_1, x_2)) = [2] + x_2 343.61/291.47 POL(False) = 0 343.61/291.47 POL(LOOP(x_1, x_2, x_3, x_4)) = [2] + x_1 + [2]x_3 + x_4 + x_3*x_4 343.61/291.47 POL(LOOP[ITE](x_1, x_2, x_3, x_4, x_5)) = x_2 + [2]x_4 + x_5 + x_4*x_5 343.61/291.47 POL(Nil) = 0 343.61/291.47 POL(S(x_1)) = 0 343.61/291.47 POL(True) = 0 343.61/291.47 POL(c(x_1)) = x_1 343.61/291.47 POL(c4(x_1)) = x_1 343.61/291.47 POL(c5(x_1)) = x_1 343.61/291.47 POL(c6) = 0 343.61/291.47 POL(c7(x_1, x_2)) = x_1 + x_2 343.61/291.47 POL(c8) = 0 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (12) 343.61/291.47 Obligation: 343.61/291.47 Complexity Dependency Tuples Problem 343.61/291.47 343.61/291.47 Rules: 343.61/291.47 !EQ(S(z0), S(z1)) -> !EQ(z0, z1) 343.61/291.47 !EQ(0, S(z0)) -> False 343.61/291.47 !EQ(S(z0), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 Tuples: 343.61/291.47 !EQ'(S(z0), S(z1)) -> c(!EQ'(z0, z1)) 343.61/291.47 LOOP[ITE](False, z0, z1, z2, Cons(z3, z4)) -> c4(LOOP(z2, z4, z2, z4)) 343.61/291.47 LOOP[ITE](True, Cons(z0, z1), Cons(z2, z3), z4, z5) -> c5(LOOP(z1, z3, z4, z5)) 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 S tuples:none 343.61/291.47 K tuples: 343.61/291.47 LOOP(Cons(z0, z1), Nil, z2, z3) -> c6 343.61/291.47 LOOP(Nil, z0, z1, z2) -> c8 343.61/291.47 LOOP(Cons(z0, z1), Cons(z2, z3), z4, z5) -> c7(LOOP[ITE](!EQ(z0, z2), Cons(z0, z1), Cons(z2, z3), z4, z5), !EQ'(z0, z2)) 343.61/291.47 Defined Rule Symbols: !EQ_2 343.61/291.47 343.61/291.47 Defined Pair Symbols: !EQ'_2, LOOP[ITE]_5, LOOP_4 343.61/291.47 343.61/291.47 Compound Symbols: c_1, c4_1, c5_1, c6, c7_2, c8 343.61/291.47 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (13) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 343.61/291.47 The set S is empty 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (14) 343.61/291.47 BOUNDS(1, 1) 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 343.61/291.47 Transformed a relative TRS into a decreasing-loop problem. 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (16) 343.61/291.47 Obligation: 343.61/291.47 Analyzing the following TRS for decreasing loops: 343.61/291.47 343.61/291.47 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 343.61/291.47 343.61/291.47 343.61/291.47 The TRS R consists of the following rules: 343.61/291.47 343.61/291.47 loop(Cons(x, xs), Nil, pp, ss) -> False 343.61/291.47 loop(Cons(x', xs'), Cons(x, xs), pp, ss) -> loop[Ite](!EQ(x', x), Cons(x', xs'), Cons(x, xs), pp, ss) 343.61/291.47 loop(Nil, s, pp, ss) -> True 343.61/291.47 match1(p, s) -> loop(p, s, p, s) 343.61/291.47 343.61/291.47 The (relative) TRS S consists of the following rules: 343.61/291.47 343.61/291.47 !EQ(S(x), S(y)) -> !EQ(x, y) 343.61/291.47 !EQ(0, S(y)) -> False 343.61/291.47 !EQ(S(x), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 loop[Ite](False, p, s, pp, Cons(x, xs)) -> loop(pp, xs, pp, xs) 343.61/291.47 loop[Ite](True, Cons(x', xs'), Cons(x, xs), pp, ss) -> loop(xs', xs, pp, ss) 343.61/291.47 343.61/291.47 Rewrite Strategy: INNERMOST 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (17) DecreasingLoopProof (LOWER BOUND(ID)) 343.61/291.47 The following loop(s) give(s) rise to the lower bound Omega(n^1): 343.61/291.47 343.61/291.47 The rewrite sequence 343.61/291.47 343.61/291.47 loop(Cons(0, xs'), Cons(0, xs), pp, ss) ->^+ loop(xs', xs, pp, ss) 343.61/291.47 343.61/291.47 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 343.61/291.47 343.61/291.47 The pumping substitution is [xs' / Cons(0, xs'), xs / Cons(0, xs)]. 343.61/291.47 343.61/291.47 The result substitution is [ ]. 343.61/291.47 343.61/291.47 343.61/291.47 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (18) 343.61/291.47 Complex Obligation (BEST) 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (19) 343.61/291.47 Obligation: 343.61/291.47 Proved the lower bound n^1 for the following obligation: 343.61/291.47 343.61/291.47 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 343.61/291.47 343.61/291.47 343.61/291.47 The TRS R consists of the following rules: 343.61/291.47 343.61/291.47 loop(Cons(x, xs), Nil, pp, ss) -> False 343.61/291.47 loop(Cons(x', xs'), Cons(x, xs), pp, ss) -> loop[Ite](!EQ(x', x), Cons(x', xs'), Cons(x, xs), pp, ss) 343.61/291.47 loop(Nil, s, pp, ss) -> True 343.61/291.47 match1(p, s) -> loop(p, s, p, s) 343.61/291.47 343.61/291.47 The (relative) TRS S consists of the following rules: 343.61/291.47 343.61/291.47 !EQ(S(x), S(y)) -> !EQ(x, y) 343.61/291.47 !EQ(0, S(y)) -> False 343.61/291.47 !EQ(S(x), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 loop[Ite](False, p, s, pp, Cons(x, xs)) -> loop(pp, xs, pp, xs) 343.61/291.47 loop[Ite](True, Cons(x', xs'), Cons(x, xs), pp, ss) -> loop(xs', xs, pp, ss) 343.61/291.47 343.61/291.47 Rewrite Strategy: INNERMOST 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (20) LowerBoundPropagationProof (FINISHED) 343.61/291.47 Propagated lower bound. 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (21) 343.61/291.47 BOUNDS(n^1, INF) 343.61/291.47 343.61/291.47 ---------------------------------------- 343.61/291.47 343.61/291.47 (22) 343.61/291.47 Obligation: 343.61/291.47 Analyzing the following TRS for decreasing loops: 343.61/291.47 343.61/291.47 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). 343.61/291.47 343.61/291.47 343.61/291.47 The TRS R consists of the following rules: 343.61/291.47 343.61/291.47 loop(Cons(x, xs), Nil, pp, ss) -> False 343.61/291.47 loop(Cons(x', xs'), Cons(x, xs), pp, ss) -> loop[Ite](!EQ(x', x), Cons(x', xs'), Cons(x, xs), pp, ss) 343.61/291.47 loop(Nil, s, pp, ss) -> True 343.61/291.47 match1(p, s) -> loop(p, s, p, s) 343.61/291.47 343.61/291.47 The (relative) TRS S consists of the following rules: 343.61/291.47 343.61/291.47 !EQ(S(x), S(y)) -> !EQ(x, y) 343.61/291.47 !EQ(0, S(y)) -> False 343.61/291.47 !EQ(S(x), 0) -> False 343.61/291.47 !EQ(0, 0) -> True 343.61/291.47 loop[Ite](False, p, s, pp, Cons(x, xs)) -> loop(pp, xs, pp, xs) 343.61/291.47 loop[Ite](True, Cons(x', xs'), Cons(x, xs), pp, ss) -> loop(xs', xs, pp, ss) 343.61/291.47 343.61/291.47 Rewrite Strategy: INNERMOST 343.72/291.51 EOF