13.19/4.49 WORST_CASE(Omega(n^1), O(n^1)) 13.19/4.50 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 13.19/4.50 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.19/4.50 13.19/4.50 13.19/4.50 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 13.19/4.50 13.19/4.50 (0) CpxRelTRS 13.19/4.50 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 154 ms] 13.19/4.50 (2) CpxRelTRS 13.19/4.50 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 13.19/4.50 (4) CdtProblem 13.19/4.50 (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 13.19/4.50 (6) CdtProblem 13.19/4.50 (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 13.19/4.50 (8) CdtProblem 13.19/4.50 (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 13.19/4.50 (10) CdtProblem 13.19/4.50 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 45 ms] 13.19/4.50 (12) CdtProblem 13.19/4.50 (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 8 ms] 13.19/4.50 (14) CdtProblem 13.19/4.50 (15) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 13.19/4.50 (16) BOUNDS(1, 1) 13.19/4.50 (17) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 13.19/4.50 (18) TRS for Loop Detection 13.19/4.50 (19) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 13.19/4.50 (20) BEST 13.19/4.50 (21) proven lower bound 13.19/4.50 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 13.19/4.50 (23) BOUNDS(n^1, INF) 13.19/4.50 (24) TRS for Loop Detection 13.19/4.50 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (0) 13.19/4.50 Obligation: 13.19/4.50 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 13.19/4.50 13.19/4.50 13.19/4.50 The TRS R consists of the following rules: 13.19/4.50 13.19/4.50 a(C(x1, x2), y) -> C(a(x1, y), a(x2, C(x1, x2))) 13.19/4.50 a(Z, y) -> Z 13.19/4.50 eqZList(C(x1, x2), C(y1, y2)) -> and(eqZList(x1, y1), eqZList(x2, y2)) 13.19/4.50 eqZList(C(x1, x2), Z) -> False 13.19/4.50 eqZList(Z, C(y1, y2)) -> False 13.19/4.50 eqZList(Z, Z) -> True 13.19/4.50 second(C(x1, x2)) -> x2 13.19/4.50 first(C(x1, x2)) -> x1 13.19/4.50 13.19/4.50 The (relative) TRS S consists of the following rules: 13.19/4.50 13.19/4.50 and(False, False) -> False 13.19/4.50 and(True, False) -> False 13.19/4.50 and(False, True) -> False 13.19/4.50 and(True, True) -> True 13.19/4.50 13.19/4.50 Rewrite Strategy: INNERMOST 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 13.19/4.50 proved termination of relative rules 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (2) 13.19/4.50 Obligation: 13.19/4.50 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 13.19/4.50 13.19/4.50 13.19/4.50 The TRS R consists of the following rules: 13.19/4.50 13.19/4.50 a(C(x1, x2), y) -> C(a(x1, y), a(x2, C(x1, x2))) 13.19/4.50 a(Z, y) -> Z 13.19/4.50 eqZList(C(x1, x2), C(y1, y2)) -> and(eqZList(x1, y1), eqZList(x2, y2)) 13.19/4.50 eqZList(C(x1, x2), Z) -> False 13.19/4.50 eqZList(Z, C(y1, y2)) -> False 13.19/4.50 eqZList(Z, Z) -> True 13.19/4.50 second(C(x1, x2)) -> x2 13.19/4.50 first(C(x1, x2)) -> x1 13.19/4.50 13.19/4.50 The (relative) TRS S consists of the following rules: 13.19/4.50 13.19/4.50 and(False, False) -> False 13.19/4.50 and(True, False) -> False 13.19/4.50 and(False, True) -> False 13.19/4.50 and(True, True) -> True 13.19/4.50 13.19/4.50 Rewrite Strategy: INNERMOST 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 13.19/4.50 Converted Cpx (relative) TRS to CDT 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (4) 13.19/4.50 Obligation: 13.19/4.50 Complexity Dependency Tuples Problem 13.19/4.50 13.19/4.50 Rules: 13.19/4.50 and(False, False) -> False 13.19/4.50 and(True, False) -> False 13.19/4.50 and(False, True) -> False 13.19/4.50 and(True, True) -> True 13.19/4.50 a(C(z0, z1), z2) -> C(a(z0, z2), a(z1, C(z0, z1))) 13.19/4.50 a(Z, z0) -> Z 13.19/4.50 eqZList(C(z0, z1), C(z2, z3)) -> and(eqZList(z0, z2), eqZList(z1, z3)) 13.19/4.50 eqZList(C(z0, z1), Z) -> False 13.19/4.50 eqZList(Z, C(z0, z1)) -> False 13.19/4.50 eqZList(Z, Z) -> True 13.19/4.50 second(C(z0, z1)) -> z1 13.19/4.50 first(C(z0, z1)) -> z0 13.19/4.50 Tuples: 13.19/4.50 AND(False, False) -> c 13.19/4.50 AND(True, False) -> c1 13.19/4.50 AND(False, True) -> c2 13.19/4.50 AND(True, True) -> c3 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 A(Z, z0) -> c5 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(AND(eqZList(z0, z2), eqZList(z1, z3)), EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 EQZLIST(C(z0, z1), Z) -> c7 13.19/4.50 EQZLIST(Z, C(z0, z1)) -> c8 13.19/4.50 EQZLIST(Z, Z) -> c9 13.19/4.50 SECOND(C(z0, z1)) -> c10 13.19/4.50 FIRST(C(z0, z1)) -> c11 13.19/4.50 S tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 A(Z, z0) -> c5 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(AND(eqZList(z0, z2), eqZList(z1, z3)), EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 EQZLIST(C(z0, z1), Z) -> c7 13.19/4.50 EQZLIST(Z, C(z0, z1)) -> c8 13.19/4.50 EQZLIST(Z, Z) -> c9 13.19/4.50 SECOND(C(z0, z1)) -> c10 13.19/4.50 FIRST(C(z0, z1)) -> c11 13.19/4.50 K tuples:none 13.19/4.50 Defined Rule Symbols: a_2, eqZList_2, second_1, first_1, and_2 13.19/4.50 13.19/4.50 Defined Pair Symbols: AND_2, A_2, EQZLIST_2, SECOND_1, FIRST_1 13.19/4.50 13.19/4.50 Compound Symbols: c, c1, c2, c3, c4_2, c5, c6_3, c7, c8, c9, c10, c11 13.19/4.50 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 13.19/4.50 Removed 10 trailing nodes: 13.19/4.50 EQZLIST(Z, Z) -> c9 13.19/4.50 SECOND(C(z0, z1)) -> c10 13.19/4.50 AND(False, False) -> c 13.19/4.50 AND(False, True) -> c2 13.19/4.50 A(Z, z0) -> c5 13.19/4.50 FIRST(C(z0, z1)) -> c11 13.19/4.50 AND(True, False) -> c1 13.19/4.50 EQZLIST(C(z0, z1), Z) -> c7 13.19/4.50 AND(True, True) -> c3 13.19/4.50 EQZLIST(Z, C(z0, z1)) -> c8 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (6) 13.19/4.50 Obligation: 13.19/4.50 Complexity Dependency Tuples Problem 13.19/4.50 13.19/4.50 Rules: 13.19/4.50 and(False, False) -> False 13.19/4.50 and(True, False) -> False 13.19/4.50 and(False, True) -> False 13.19/4.50 and(True, True) -> True 13.19/4.50 a(C(z0, z1), z2) -> C(a(z0, z2), a(z1, C(z0, z1))) 13.19/4.50 a(Z, z0) -> Z 13.19/4.50 eqZList(C(z0, z1), C(z2, z3)) -> and(eqZList(z0, z2), eqZList(z1, z3)) 13.19/4.50 eqZList(C(z0, z1), Z) -> False 13.19/4.50 eqZList(Z, C(z0, z1)) -> False 13.19/4.50 eqZList(Z, Z) -> True 13.19/4.50 second(C(z0, z1)) -> z1 13.19/4.50 first(C(z0, z1)) -> z0 13.19/4.50 Tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(AND(eqZList(z0, z2), eqZList(z1, z3)), EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 S tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(AND(eqZList(z0, z2), eqZList(z1, z3)), EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 K tuples:none 13.19/4.50 Defined Rule Symbols: a_2, eqZList_2, second_1, first_1, and_2 13.19/4.50 13.19/4.50 Defined Pair Symbols: A_2, EQZLIST_2 13.19/4.50 13.19/4.50 Compound Symbols: c4_2, c6_3 13.19/4.50 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 13.19/4.50 Removed 1 trailing tuple parts 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (8) 13.19/4.50 Obligation: 13.19/4.50 Complexity Dependency Tuples Problem 13.19/4.50 13.19/4.50 Rules: 13.19/4.50 and(False, False) -> False 13.19/4.50 and(True, False) -> False 13.19/4.50 and(False, True) -> False 13.19/4.50 and(True, True) -> True 13.19/4.50 a(C(z0, z1), z2) -> C(a(z0, z2), a(z1, C(z0, z1))) 13.19/4.50 a(Z, z0) -> Z 13.19/4.50 eqZList(C(z0, z1), C(z2, z3)) -> and(eqZList(z0, z2), eqZList(z1, z3)) 13.19/4.50 eqZList(C(z0, z1), Z) -> False 13.19/4.50 eqZList(Z, C(z0, z1)) -> False 13.19/4.50 eqZList(Z, Z) -> True 13.19/4.50 second(C(z0, z1)) -> z1 13.19/4.50 first(C(z0, z1)) -> z0 13.19/4.50 Tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 S tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 K tuples:none 13.19/4.50 Defined Rule Symbols: a_2, eqZList_2, second_1, first_1, and_2 13.19/4.50 13.19/4.50 Defined Pair Symbols: A_2, EQZLIST_2 13.19/4.50 13.19/4.50 Compound Symbols: c4_2, c6_2 13.19/4.50 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 13.19/4.50 The following rules are not usable and were removed: 13.19/4.50 and(False, False) -> False 13.19/4.50 and(True, False) -> False 13.19/4.50 and(False, True) -> False 13.19/4.50 and(True, True) -> True 13.19/4.50 a(C(z0, z1), z2) -> C(a(z0, z2), a(z1, C(z0, z1))) 13.19/4.50 a(Z, z0) -> Z 13.19/4.50 eqZList(C(z0, z1), C(z2, z3)) -> and(eqZList(z0, z2), eqZList(z1, z3)) 13.19/4.50 eqZList(C(z0, z1), Z) -> False 13.19/4.50 eqZList(Z, C(z0, z1)) -> False 13.19/4.50 eqZList(Z, Z) -> True 13.19/4.50 second(C(z0, z1)) -> z1 13.19/4.50 first(C(z0, z1)) -> z0 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (10) 13.19/4.50 Obligation: 13.19/4.50 Complexity Dependency Tuples Problem 13.19/4.50 13.19/4.50 Rules:none 13.19/4.50 Tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 S tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 K tuples:none 13.19/4.50 Defined Rule Symbols:none 13.19/4.50 13.19/4.50 Defined Pair Symbols: A_2, EQZLIST_2 13.19/4.50 13.19/4.50 Compound Symbols: c4_2, c6_2 13.19/4.50 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 13.19/4.50 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 We considered the (Usable) Rules:none 13.19/4.50 And the Tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 The order we found is given by the following interpretation: 13.19/4.50 13.19/4.50 Polynomial interpretation : 13.19/4.50 13.19/4.50 POL(A(x_1, x_2)) = [1] + x_1 13.19/4.50 POL(C(x_1, x_2)) = [1] + x_1 + x_2 13.19/4.50 POL(EQZLIST(x_1, x_2)) = [1] + x_1 + x_2 13.19/4.50 POL(c4(x_1, x_2)) = x_1 + x_2 13.19/4.50 POL(c6(x_1, x_2)) = x_1 + x_2 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (12) 13.19/4.50 Obligation: 13.19/4.50 Complexity Dependency Tuples Problem 13.19/4.50 13.19/4.50 Rules:none 13.19/4.50 Tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 S tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 K tuples: 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 Defined Rule Symbols:none 13.19/4.50 13.19/4.50 Defined Pair Symbols: A_2, EQZLIST_2 13.19/4.50 13.19/4.50 Compound Symbols: c4_2, c6_2 13.19/4.50 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 13.19/4.50 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 We considered the (Usable) Rules:none 13.19/4.50 And the Tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 The order we found is given by the following interpretation: 13.19/4.50 13.19/4.50 Polynomial interpretation : 13.19/4.50 13.19/4.50 POL(A(x_1, x_2)) = [1] + [3]x_1 13.19/4.50 POL(C(x_1, x_2)) = [3] + x_1 + x_2 13.19/4.50 POL(EQZLIST(x_1, x_2)) = [2] + [3]x_1 + [3]x_2 13.19/4.50 POL(c4(x_1, x_2)) = x_1 + x_2 13.19/4.50 POL(c6(x_1, x_2)) = x_1 + x_2 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (14) 13.19/4.50 Obligation: 13.19/4.50 Complexity Dependency Tuples Problem 13.19/4.50 13.19/4.50 Rules:none 13.19/4.50 Tuples: 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 S tuples:none 13.19/4.50 K tuples: 13.19/4.50 EQZLIST(C(z0, z1), C(z2, z3)) -> c6(EQZLIST(z0, z2), EQZLIST(z1, z3)) 13.19/4.50 A(C(z0, z1), z2) -> c4(A(z0, z2), A(z1, C(z0, z1))) 13.19/4.50 Defined Rule Symbols:none 13.19/4.50 13.19/4.50 Defined Pair Symbols: A_2, EQZLIST_2 13.19/4.50 13.19/4.50 Compound Symbols: c4_2, c6_2 13.19/4.50 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (15) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 13.19/4.50 The set S is empty 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (16) 13.19/4.50 BOUNDS(1, 1) 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (17) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 13.19/4.50 Transformed a relative TRS into a decreasing-loop problem. 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (18) 13.19/4.50 Obligation: 13.19/4.50 Analyzing the following TRS for decreasing loops: 13.19/4.50 13.19/4.50 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 13.19/4.50 13.19/4.50 13.19/4.50 The TRS R consists of the following rules: 13.19/4.50 13.19/4.50 a(C(x1, x2), y) -> C(a(x1, y), a(x2, C(x1, x2))) 13.19/4.50 a(Z, y) -> Z 13.19/4.50 eqZList(C(x1, x2), C(y1, y2)) -> and(eqZList(x1, y1), eqZList(x2, y2)) 13.19/4.50 eqZList(C(x1, x2), Z) -> False 13.19/4.50 eqZList(Z, C(y1, y2)) -> False 13.19/4.50 eqZList(Z, Z) -> True 13.19/4.50 second(C(x1, x2)) -> x2 13.19/4.50 first(C(x1, x2)) -> x1 13.19/4.50 13.19/4.50 The (relative) TRS S consists of the following rules: 13.19/4.50 13.19/4.50 and(False, False) -> False 13.19/4.50 and(True, False) -> False 13.19/4.50 and(False, True) -> False 13.19/4.50 and(True, True) -> True 13.19/4.50 13.19/4.50 Rewrite Strategy: INNERMOST 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (19) DecreasingLoopProof (LOWER BOUND(ID)) 13.19/4.50 The following loop(s) give(s) rise to the lower bound Omega(n^1): 13.19/4.50 13.19/4.50 The rewrite sequence 13.19/4.50 13.19/4.50 eqZList(C(x1, x2), C(y1, y2)) ->^+ and(eqZList(x1, y1), eqZList(x2, y2)) 13.19/4.50 13.19/4.50 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 13.19/4.50 13.19/4.50 The pumping substitution is [x1 / C(x1, x2), y1 / C(y1, y2)]. 13.19/4.50 13.19/4.50 The result substitution is [ ]. 13.19/4.50 13.19/4.50 13.19/4.50 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (20) 13.19/4.50 Complex Obligation (BEST) 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (21) 13.19/4.50 Obligation: 13.19/4.50 Proved the lower bound n^1 for the following obligation: 13.19/4.50 13.19/4.50 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 13.19/4.50 13.19/4.50 13.19/4.50 The TRS R consists of the following rules: 13.19/4.50 13.19/4.50 a(C(x1, x2), y) -> C(a(x1, y), a(x2, C(x1, x2))) 13.19/4.50 a(Z, y) -> Z 13.19/4.50 eqZList(C(x1, x2), C(y1, y2)) -> and(eqZList(x1, y1), eqZList(x2, y2)) 13.19/4.50 eqZList(C(x1, x2), Z) -> False 13.19/4.50 eqZList(Z, C(y1, y2)) -> False 13.19/4.50 eqZList(Z, Z) -> True 13.19/4.50 second(C(x1, x2)) -> x2 13.19/4.50 first(C(x1, x2)) -> x1 13.19/4.50 13.19/4.50 The (relative) TRS S consists of the following rules: 13.19/4.50 13.19/4.50 and(False, False) -> False 13.19/4.50 and(True, False) -> False 13.19/4.50 and(False, True) -> False 13.19/4.50 and(True, True) -> True 13.19/4.50 13.19/4.50 Rewrite Strategy: INNERMOST 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (22) LowerBoundPropagationProof (FINISHED) 13.19/4.50 Propagated lower bound. 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (23) 13.19/4.50 BOUNDS(n^1, INF) 13.19/4.50 13.19/4.50 ---------------------------------------- 13.19/4.50 13.19/4.50 (24) 13.19/4.50 Obligation: 13.19/4.50 Analyzing the following TRS for decreasing loops: 13.19/4.50 13.19/4.50 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 13.19/4.50 13.19/4.50 13.19/4.50 The TRS R consists of the following rules: 13.19/4.50 13.19/4.50 a(C(x1, x2), y) -> C(a(x1, y), a(x2, C(x1, x2))) 13.19/4.50 a(Z, y) -> Z 13.19/4.50 eqZList(C(x1, x2), C(y1, y2)) -> and(eqZList(x1, y1), eqZList(x2, y2)) 13.19/4.50 eqZList(C(x1, x2), Z) -> False 13.19/4.50 eqZList(Z, C(y1, y2)) -> False 13.19/4.50 eqZList(Z, Z) -> True 13.19/4.50 second(C(x1, x2)) -> x2 13.19/4.50 first(C(x1, x2)) -> x1 13.19/4.50 13.19/4.50 The (relative) TRS S consists of the following rules: 13.19/4.50 13.19/4.50 and(False, False) -> False 13.19/4.50 and(True, False) -> False 13.19/4.50 and(False, True) -> False 13.19/4.50 and(True, True) -> True 13.19/4.50 13.19/4.50 Rewrite Strategy: INNERMOST 13.19/4.53 EOF