34.56/9.93 WORST_CASE(Omega(n^1), O(n^1)) 34.56/9.94 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 34.56/9.94 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 34.56/9.94 34.56/9.94 34.56/9.94 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 34.56/9.94 34.56/9.94 (0) CpxTRS 34.56/9.94 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 34.56/9.94 (2) CdtProblem 34.56/9.94 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 34.56/9.94 (4) CdtProblem 34.56/9.94 (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 34.56/9.94 (6) CdtProblem 34.56/9.94 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 101 ms] 34.56/9.94 (8) CdtProblem 34.56/9.94 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 25 ms] 34.56/9.94 (10) CdtProblem 34.56/9.94 (11) CdtKnowledgeProof [FINISHED, 0 ms] 34.56/9.94 (12) BOUNDS(1, 1) 34.56/9.94 (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 34.56/9.94 (14) TRS for Loop Detection 34.56/9.94 (15) DecreasingLoopProof [LOWER BOUND(ID), 34 ms] 34.56/9.94 (16) BEST 34.56/9.94 (17) proven lower bound 34.56/9.94 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 34.56/9.94 (19) BOUNDS(n^1, INF) 34.56/9.94 (20) TRS for Loop Detection 34.56/9.94 34.56/9.94 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (0) 34.56/9.94 Obligation: 34.56/9.94 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 34.56/9.94 34.56/9.94 34.56/9.94 The TRS R consists of the following rules: 34.56/9.94 34.56/9.94 f4(S(x''), S(x'), x3, x4, S(x)) -> f2(S(x''), x', x3, x4, x) 34.56/9.94 f4(S(x'), 0, x3, x4, S(x)) -> f3(x', 0, x3, x4, x) 34.56/9.94 f2(x1, x2, S(x''), S(x'), S(x)) -> f5(x1, x2, S(x''), x', x) 34.56/9.94 f2(x1, x2, S(x'), 0, S(x)) -> f3(x1, x2, x', 0, x) 34.56/9.94 f4(S(x'), S(x), x3, x4, 0) -> 0 34.56/9.94 f4(S(x), 0, x3, x4, 0) -> 0 34.56/9.94 f2(x1, x2, S(x'), S(x), 0) -> 0 34.56/9.94 f2(x1, x2, S(x), 0, 0) -> 0 34.56/9.94 f0(x1, S(x'), x3, S(x), x5) -> f1(x', S(x'), x, S(x), S(x)) 34.56/9.94 f0(x1, S(x), x3, 0, x5) -> 0 34.56/9.94 f6(x1, x2, x3, x4, S(x)) -> f0(x1, x2, x4, x3, x) 34.56/9.94 f5(x1, x2, x3, x4, S(x)) -> f6(x2, x1, x3, x4, x) 34.56/9.94 f3(x1, x2, x3, x4, S(x)) -> f4(x1, x2, x4, x3, x) 34.56/9.94 f1(x1, x2, x3, x4, S(x)) -> f2(x2, x1, x3, x4, x) 34.56/9.94 f6(x1, x2, x3, x4, 0) -> 0 34.56/9.94 f5(x1, x2, x3, x4, 0) -> 0 34.56/9.94 f4(0, x2, x3, x4, x5) -> 0 34.56/9.94 f3(x1, x2, x3, x4, 0) -> 0 34.56/9.94 f2(x1, x2, 0, x4, x5) -> 0 34.56/9.94 f1(x1, x2, x3, x4, 0) -> 0 34.56/9.94 f0(x1, 0, x3, x4, x5) -> 0 34.56/9.94 34.56/9.94 S is empty. 34.56/9.94 Rewrite Strategy: INNERMOST 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 34.56/9.94 Converted Cpx (relative) TRS to CDT 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (2) 34.56/9.94 Obligation: 34.56/9.94 Complexity Dependency Tuples Problem 34.56/9.94 34.56/9.94 Rules: 34.56/9.94 f4(S(z0), S(z1), z2, z3, S(z4)) -> f2(S(z0), z1, z2, z3, z4) 34.56/9.94 f4(S(z0), 0, z1, z2, S(z3)) -> f3(z0, 0, z1, z2, z3) 34.56/9.94 f4(S(z0), S(z1), z2, z3, 0) -> 0 34.56/9.94 f4(S(z0), 0, z1, z2, 0) -> 0 34.56/9.94 f4(0, z0, z1, z2, z3) -> 0 34.56/9.94 f2(z0, z1, S(z2), S(z3), S(z4)) -> f5(z0, z1, S(z2), z3, z4) 34.56/9.94 f2(z0, z1, S(z2), 0, S(z3)) -> f3(z0, z1, z2, 0, z3) 34.56/9.94 f2(z0, z1, S(z2), S(z3), 0) -> 0 34.56/9.94 f2(z0, z1, S(z2), 0, 0) -> 0 34.56/9.94 f2(z0, z1, 0, z2, z3) -> 0 34.56/9.94 f0(z0, S(z1), z2, S(z3), z4) -> f1(z1, S(z1), z3, S(z3), S(z3)) 34.56/9.94 f0(z0, S(z1), z2, 0, z3) -> 0 34.56/9.94 f0(z0, 0, z1, z2, z3) -> 0 34.56/9.94 f6(z0, z1, z2, z3, S(z4)) -> f0(z0, z1, z3, z2, z4) 34.56/9.94 f6(z0, z1, z2, z3, 0) -> 0 34.56/9.94 f5(z0, z1, z2, z3, S(z4)) -> f6(z1, z0, z2, z3, z4) 34.56/9.94 f5(z0, z1, z2, z3, 0) -> 0 34.56/9.94 f3(z0, z1, z2, z3, S(z4)) -> f4(z0, z1, z3, z2, z4) 34.56/9.94 f3(z0, z1, z2, z3, 0) -> 0 34.56/9.94 f1(z0, z1, z2, z3, S(z4)) -> f2(z1, z0, z2, z3, z4) 34.56/9.94 f1(z0, z1, z2, z3, 0) -> 0 34.56/9.94 Tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 F4(S(z0), S(z1), z2, z3, 0) -> c2 34.56/9.94 F4(S(z0), 0, z1, z2, 0) -> c3 34.56/9.94 F4(0, z0, z1, z2, z3) -> c4 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), 0) -> c7 34.56/9.94 F2(z0, z1, S(z2), 0, 0) -> c8 34.56/9.94 F2(z0, z1, 0, z2, z3) -> c9 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F0(z0, S(z1), z2, 0, z3) -> c11 34.56/9.94 F0(z0, 0, z1, z2, z3) -> c12 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F6(z0, z1, z2, z3, 0) -> c14 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F5(z0, z1, z2, z3, 0) -> c16 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F3(z0, z1, z2, z3, 0) -> c18 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 F1(z0, z1, z2, z3, 0) -> c20 34.56/9.94 S tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 F4(S(z0), S(z1), z2, z3, 0) -> c2 34.56/9.94 F4(S(z0), 0, z1, z2, 0) -> c3 34.56/9.94 F4(0, z0, z1, z2, z3) -> c4 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), 0) -> c7 34.56/9.94 F2(z0, z1, S(z2), 0, 0) -> c8 34.56/9.94 F2(z0, z1, 0, z2, z3) -> c9 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F0(z0, S(z1), z2, 0, z3) -> c11 34.56/9.94 F0(z0, 0, z1, z2, z3) -> c12 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F6(z0, z1, z2, z3, 0) -> c14 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F5(z0, z1, z2, z3, 0) -> c16 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F3(z0, z1, z2, z3, 0) -> c18 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 F1(z0, z1, z2, z3, 0) -> c20 34.56/9.94 K tuples:none 34.56/9.94 Defined Rule Symbols: f4_5, f2_5, f0_5, f6_5, f5_5, f3_5, f1_5 34.56/9.94 34.56/9.94 Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 34.56/9.94 34.56/9.94 Compound Symbols: c_1, c1_1, c2, c3, c4, c5_1, c6_1, c7, c8, c9, c10_1, c11, c12, c13_1, c14, c15_1, c16, c17_1, c18, c19_1, c20 34.56/9.94 34.56/9.94 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 34.56/9.94 Removed 12 trailing nodes: 34.56/9.94 F4(S(z0), 0, z1, z2, 0) -> c3 34.56/9.94 F0(z0, S(z1), z2, 0, z3) -> c11 34.56/9.94 F2(z0, z1, S(z2), 0, 0) -> c8 34.56/9.94 F0(z0, 0, z1, z2, z3) -> c12 34.56/9.94 F6(z0, z1, z2, z3, 0) -> c14 34.56/9.94 F2(z0, z1, S(z2), S(z3), 0) -> c7 34.56/9.94 F4(0, z0, z1, z2, z3) -> c4 34.56/9.94 F1(z0, z1, z2, z3, 0) -> c20 34.56/9.94 F2(z0, z1, 0, z2, z3) -> c9 34.56/9.94 F4(S(z0), S(z1), z2, z3, 0) -> c2 34.56/9.94 F5(z0, z1, z2, z3, 0) -> c16 34.56/9.94 F3(z0, z1, z2, z3, 0) -> c18 34.56/9.94 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (4) 34.56/9.94 Obligation: 34.56/9.94 Complexity Dependency Tuples Problem 34.56/9.94 34.56/9.94 Rules: 34.56/9.94 f4(S(z0), S(z1), z2, z3, S(z4)) -> f2(S(z0), z1, z2, z3, z4) 34.56/9.94 f4(S(z0), 0, z1, z2, S(z3)) -> f3(z0, 0, z1, z2, z3) 34.56/9.94 f4(S(z0), S(z1), z2, z3, 0) -> 0 34.56/9.94 f4(S(z0), 0, z1, z2, 0) -> 0 34.56/9.94 f4(0, z0, z1, z2, z3) -> 0 34.56/9.94 f2(z0, z1, S(z2), S(z3), S(z4)) -> f5(z0, z1, S(z2), z3, z4) 34.56/9.94 f2(z0, z1, S(z2), 0, S(z3)) -> f3(z0, z1, z2, 0, z3) 34.56/9.94 f2(z0, z1, S(z2), S(z3), 0) -> 0 34.56/9.94 f2(z0, z1, S(z2), 0, 0) -> 0 34.56/9.94 f2(z0, z1, 0, z2, z3) -> 0 34.56/9.94 f0(z0, S(z1), z2, S(z3), z4) -> f1(z1, S(z1), z3, S(z3), S(z3)) 34.56/9.94 f0(z0, S(z1), z2, 0, z3) -> 0 34.56/9.94 f0(z0, 0, z1, z2, z3) -> 0 34.56/9.94 f6(z0, z1, z2, z3, S(z4)) -> f0(z0, z1, z3, z2, z4) 34.56/9.94 f6(z0, z1, z2, z3, 0) -> 0 34.56/9.94 f5(z0, z1, z2, z3, S(z4)) -> f6(z1, z0, z2, z3, z4) 34.56/9.94 f5(z0, z1, z2, z3, 0) -> 0 34.56/9.94 f3(z0, z1, z2, z3, S(z4)) -> f4(z0, z1, z3, z2, z4) 34.56/9.94 f3(z0, z1, z2, z3, 0) -> 0 34.56/9.94 f1(z0, z1, z2, z3, S(z4)) -> f2(z1, z0, z2, z3, z4) 34.56/9.94 f1(z0, z1, z2, z3, 0) -> 0 34.56/9.94 Tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 S tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 K tuples:none 34.56/9.94 Defined Rule Symbols: f4_5, f2_5, f0_5, f6_5, f5_5, f3_5, f1_5 34.56/9.94 34.56/9.94 Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 34.56/9.94 34.56/9.94 Compound Symbols: c_1, c1_1, c5_1, c6_1, c10_1, c13_1, c15_1, c17_1, c19_1 34.56/9.94 34.56/9.94 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 34.56/9.94 The following rules are not usable and were removed: 34.56/9.94 f4(S(z0), S(z1), z2, z3, S(z4)) -> f2(S(z0), z1, z2, z3, z4) 34.56/9.94 f4(S(z0), 0, z1, z2, S(z3)) -> f3(z0, 0, z1, z2, z3) 34.56/9.94 f4(S(z0), S(z1), z2, z3, 0) -> 0 34.56/9.94 f4(S(z0), 0, z1, z2, 0) -> 0 34.56/9.94 f4(0, z0, z1, z2, z3) -> 0 34.56/9.94 f2(z0, z1, S(z2), S(z3), S(z4)) -> f5(z0, z1, S(z2), z3, z4) 34.56/9.94 f2(z0, z1, S(z2), 0, S(z3)) -> f3(z0, z1, z2, 0, z3) 34.56/9.94 f2(z0, z1, S(z2), S(z3), 0) -> 0 34.56/9.94 f2(z0, z1, S(z2), 0, 0) -> 0 34.56/9.94 f2(z0, z1, 0, z2, z3) -> 0 34.56/9.94 f0(z0, S(z1), z2, S(z3), z4) -> f1(z1, S(z1), z3, S(z3), S(z3)) 34.56/9.94 f0(z0, S(z1), z2, 0, z3) -> 0 34.56/9.94 f0(z0, 0, z1, z2, z3) -> 0 34.56/9.94 f6(z0, z1, z2, z3, S(z4)) -> f0(z0, z1, z3, z2, z4) 34.56/9.94 f6(z0, z1, z2, z3, 0) -> 0 34.56/9.94 f5(z0, z1, z2, z3, S(z4)) -> f6(z1, z0, z2, z3, z4) 34.56/9.94 f5(z0, z1, z2, z3, 0) -> 0 34.56/9.94 f3(z0, z1, z2, z3, S(z4)) -> f4(z0, z1, z3, z2, z4) 34.56/9.94 f3(z0, z1, z2, z3, 0) -> 0 34.56/9.94 f1(z0, z1, z2, z3, S(z4)) -> f2(z1, z0, z2, z3, z4) 34.56/9.94 f1(z0, z1, z2, z3, 0) -> 0 34.56/9.94 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (6) 34.56/9.94 Obligation: 34.56/9.94 Complexity Dependency Tuples Problem 34.56/9.94 34.56/9.94 Rules:none 34.56/9.94 Tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 S tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 K tuples:none 34.56/9.94 Defined Rule Symbols:none 34.56/9.94 34.56/9.94 Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 34.56/9.94 34.56/9.94 Compound Symbols: c_1, c1_1, c5_1, c6_1, c10_1, c13_1, c15_1, c17_1, c19_1 34.56/9.94 34.56/9.94 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 34.56/9.94 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 We considered the (Usable) Rules:none 34.56/9.94 And the Tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 The order we found is given by the following interpretation: 34.56/9.94 34.56/9.94 Polynomial interpretation : 34.56/9.94 34.56/9.94 POL(0) = [1] 34.56/9.94 POL(F0(x_1, x_2, x_3, x_4, x_5)) = x_2 34.56/9.94 POL(F1(x_1, x_2, x_3, x_4, x_5)) = x_2 34.56/9.94 POL(F2(x_1, x_2, x_3, x_4, x_5)) = x_1 34.56/9.94 POL(F3(x_1, x_2, x_3, x_4, x_5)) = x_1 34.56/9.94 POL(F4(x_1, x_2, x_3, x_4, x_5)) = x_1 34.56/9.94 POL(F5(x_1, x_2, x_3, x_4, x_5)) = x_1 34.56/9.94 POL(F6(x_1, x_2, x_3, x_4, x_5)) = x_2 34.56/9.94 POL(S(x_1)) = [1] + x_1 34.56/9.94 POL(c(x_1)) = x_1 34.56/9.94 POL(c1(x_1)) = x_1 34.56/9.94 POL(c10(x_1)) = x_1 34.56/9.94 POL(c13(x_1)) = x_1 34.56/9.94 POL(c15(x_1)) = x_1 34.56/9.94 POL(c17(x_1)) = x_1 34.56/9.94 POL(c19(x_1)) = x_1 34.56/9.94 POL(c5(x_1)) = x_1 34.56/9.94 POL(c6(x_1)) = x_1 34.56/9.94 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (8) 34.56/9.94 Obligation: 34.56/9.94 Complexity Dependency Tuples Problem 34.56/9.94 34.56/9.94 Rules:none 34.56/9.94 Tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 S tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 K tuples: 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 Defined Rule Symbols:none 34.56/9.94 34.56/9.94 Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 34.56/9.94 34.56/9.94 Compound Symbols: c_1, c1_1, c5_1, c6_1, c10_1, c13_1, c15_1, c17_1, c19_1 34.56/9.94 34.56/9.94 34.56/9.94 ---------------------------------------- 34.56/9.94 34.56/9.94 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 34.56/9.94 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 We considered the (Usable) Rules:none 34.56/9.94 And the Tuples: 34.56/9.94 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.94 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.94 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.94 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.94 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.94 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.94 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.94 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.94 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.94 The order we found is given by the following interpretation: 34.56/9.94 34.56/9.94 Polynomial interpretation : 34.56/9.94 34.56/9.94 POL(0) = 0 34.56/9.94 POL(F0(x_1, x_2, x_3, x_4, x_5)) = x_4 34.56/9.94 POL(F1(x_1, x_2, x_3, x_4, x_5)) = x_3 34.56/9.94 POL(F2(x_1, x_2, x_3, x_4, x_5)) = x_3 34.56/9.94 POL(F3(x_1, x_2, x_3, x_4, x_5)) = x_3 + x_4 34.56/9.94 POL(F4(x_1, x_2, x_3, x_4, x_5)) = x_3 + x_4 34.56/9.94 POL(F5(x_1, x_2, x_3, x_4, x_5)) = x_3 34.56/9.94 POL(F6(x_1, x_2, x_3, x_4, x_5)) = x_3 34.56/9.94 POL(S(x_1)) = [1] + x_1 34.56/9.94 POL(c(x_1)) = x_1 34.56/9.94 POL(c1(x_1)) = x_1 34.56/9.94 POL(c10(x_1)) = x_1 34.56/9.94 POL(c13(x_1)) = x_1 34.56/9.94 POL(c15(x_1)) = x_1 34.56/9.94 POL(c17(x_1)) = x_1 34.56/9.94 POL(c19(x_1)) = x_1 34.56/9.95 POL(c5(x_1)) = x_1 34.56/9.95 POL(c6(x_1)) = x_1 34.56/9.95 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (10) 34.56/9.95 Obligation: 34.56/9.95 Complexity Dependency Tuples Problem 34.56/9.95 34.56/9.95 Rules:none 34.56/9.95 Tuples: 34.56/9.95 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.95 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.95 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.95 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.95 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.95 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.95 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.95 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.95 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.95 S tuples: 34.56/9.95 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.95 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.95 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.95 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.95 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.95 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.95 K tuples: 34.56/9.95 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.95 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.95 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.95 Defined Rule Symbols:none 34.56/9.95 34.56/9.95 Defined Pair Symbols: F4_5, F2_5, F0_5, F6_5, F5_5, F3_5, F1_5 34.56/9.95 34.56/9.95 Compound Symbols: c_1, c1_1, c5_1, c6_1, c10_1, c13_1, c15_1, c17_1, c19_1 34.56/9.95 34.56/9.95 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (11) CdtKnowledgeProof (FINISHED) 34.56/9.95 The following tuples could be moved from S to K by knowledge propagation: 34.56/9.95 F3(z0, z1, z2, z3, S(z4)) -> c17(F4(z0, z1, z3, z2, z4)) 34.56/9.95 F1(z0, z1, z2, z3, S(z4)) -> c19(F2(z1, z0, z2, z3, z4)) 34.56/9.95 F4(S(z0), S(z1), z2, z3, S(z4)) -> c(F2(S(z0), z1, z2, z3, z4)) 34.56/9.95 F4(S(z0), 0, z1, z2, S(z3)) -> c1(F3(z0, 0, z1, z2, z3)) 34.56/9.95 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.95 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.95 F2(z0, z1, S(z2), S(z3), S(z4)) -> c5(F5(z0, z1, S(z2), z3, z4)) 34.56/9.95 F2(z0, z1, S(z2), 0, S(z3)) -> c6(F3(z0, z1, z2, 0, z3)) 34.56/9.95 F5(z0, z1, z2, z3, S(z4)) -> c15(F6(z1, z0, z2, z3, z4)) 34.56/9.95 F6(z0, z1, z2, z3, S(z4)) -> c13(F0(z0, z1, z3, z2, z4)) 34.56/9.95 F0(z0, S(z1), z2, S(z3), z4) -> c10(F1(z1, S(z1), z3, S(z3), S(z3))) 34.56/9.95 Now S is empty 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (12) 34.56/9.95 BOUNDS(1, 1) 34.56/9.95 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 34.56/9.95 Transformed a relative TRS into a decreasing-loop problem. 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (14) 34.56/9.95 Obligation: 34.56/9.95 Analyzing the following TRS for decreasing loops: 34.56/9.95 34.56/9.95 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 34.56/9.95 34.56/9.95 34.56/9.95 The TRS R consists of the following rules: 34.56/9.95 34.56/9.95 f4(S(x''), S(x'), x3, x4, S(x)) -> f2(S(x''), x', x3, x4, x) 34.56/9.95 f4(S(x'), 0, x3, x4, S(x)) -> f3(x', 0, x3, x4, x) 34.56/9.95 f2(x1, x2, S(x''), S(x'), S(x)) -> f5(x1, x2, S(x''), x', x) 34.56/9.95 f2(x1, x2, S(x'), 0, S(x)) -> f3(x1, x2, x', 0, x) 34.56/9.95 f4(S(x'), S(x), x3, x4, 0) -> 0 34.56/9.95 f4(S(x), 0, x3, x4, 0) -> 0 34.56/9.95 f2(x1, x2, S(x'), S(x), 0) -> 0 34.56/9.95 f2(x1, x2, S(x), 0, 0) -> 0 34.56/9.95 f0(x1, S(x'), x3, S(x), x5) -> f1(x', S(x'), x, S(x), S(x)) 34.56/9.95 f0(x1, S(x), x3, 0, x5) -> 0 34.56/9.95 f6(x1, x2, x3, x4, S(x)) -> f0(x1, x2, x4, x3, x) 34.56/9.95 f5(x1, x2, x3, x4, S(x)) -> f6(x2, x1, x3, x4, x) 34.56/9.95 f3(x1, x2, x3, x4, S(x)) -> f4(x1, x2, x4, x3, x) 34.56/9.95 f1(x1, x2, x3, x4, S(x)) -> f2(x2, x1, x3, x4, x) 34.56/9.95 f6(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f5(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f4(0, x2, x3, x4, x5) -> 0 34.56/9.95 f3(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f2(x1, x2, 0, x4, x5) -> 0 34.56/9.95 f1(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f0(x1, 0, x3, x4, x5) -> 0 34.56/9.95 34.56/9.95 S is empty. 34.56/9.95 Rewrite Strategy: INNERMOST 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (15) DecreasingLoopProof (LOWER BOUND(ID)) 34.56/9.95 The following loop(s) give(s) rise to the lower bound Omega(n^1): 34.56/9.95 34.56/9.95 The rewrite sequence 34.56/9.95 34.56/9.95 f4(S(x'), 0, x3, x4, S(S(x5_0))) ->^+ f4(x', 0, x4, x3, x5_0) 34.56/9.95 34.56/9.95 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 34.56/9.95 34.56/9.95 The pumping substitution is [x' / S(x'), x5_0 / S(S(x5_0))]. 34.56/9.95 34.56/9.95 The result substitution is [x3 / x4, x4 / x3]. 34.56/9.95 34.56/9.95 34.56/9.95 34.56/9.95 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (16) 34.56/9.95 Complex Obligation (BEST) 34.56/9.95 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (17) 34.56/9.95 Obligation: 34.56/9.95 Proved the lower bound n^1 for the following obligation: 34.56/9.95 34.56/9.95 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 34.56/9.95 34.56/9.95 34.56/9.95 The TRS R consists of the following rules: 34.56/9.95 34.56/9.95 f4(S(x''), S(x'), x3, x4, S(x)) -> f2(S(x''), x', x3, x4, x) 34.56/9.95 f4(S(x'), 0, x3, x4, S(x)) -> f3(x', 0, x3, x4, x) 34.56/9.95 f2(x1, x2, S(x''), S(x'), S(x)) -> f5(x1, x2, S(x''), x', x) 34.56/9.95 f2(x1, x2, S(x'), 0, S(x)) -> f3(x1, x2, x', 0, x) 34.56/9.95 f4(S(x'), S(x), x3, x4, 0) -> 0 34.56/9.95 f4(S(x), 0, x3, x4, 0) -> 0 34.56/9.95 f2(x1, x2, S(x'), S(x), 0) -> 0 34.56/9.95 f2(x1, x2, S(x), 0, 0) -> 0 34.56/9.95 f0(x1, S(x'), x3, S(x), x5) -> f1(x', S(x'), x, S(x), S(x)) 34.56/9.95 f0(x1, S(x), x3, 0, x5) -> 0 34.56/9.95 f6(x1, x2, x3, x4, S(x)) -> f0(x1, x2, x4, x3, x) 34.56/9.95 f5(x1, x2, x3, x4, S(x)) -> f6(x2, x1, x3, x4, x) 34.56/9.95 f3(x1, x2, x3, x4, S(x)) -> f4(x1, x2, x4, x3, x) 34.56/9.95 f1(x1, x2, x3, x4, S(x)) -> f2(x2, x1, x3, x4, x) 34.56/9.95 f6(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f5(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f4(0, x2, x3, x4, x5) -> 0 34.56/9.95 f3(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f2(x1, x2, 0, x4, x5) -> 0 34.56/9.95 f1(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f0(x1, 0, x3, x4, x5) -> 0 34.56/9.95 34.56/9.95 S is empty. 34.56/9.95 Rewrite Strategy: INNERMOST 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (18) LowerBoundPropagationProof (FINISHED) 34.56/9.95 Propagated lower bound. 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (19) 34.56/9.95 BOUNDS(n^1, INF) 34.56/9.95 34.56/9.95 ---------------------------------------- 34.56/9.95 34.56/9.95 (20) 34.56/9.95 Obligation: 34.56/9.95 Analyzing the following TRS for decreasing loops: 34.56/9.95 34.56/9.95 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 34.56/9.95 34.56/9.95 34.56/9.95 The TRS R consists of the following rules: 34.56/9.95 34.56/9.95 f4(S(x''), S(x'), x3, x4, S(x)) -> f2(S(x''), x', x3, x4, x) 34.56/9.95 f4(S(x'), 0, x3, x4, S(x)) -> f3(x', 0, x3, x4, x) 34.56/9.95 f2(x1, x2, S(x''), S(x'), S(x)) -> f5(x1, x2, S(x''), x', x) 34.56/9.95 f2(x1, x2, S(x'), 0, S(x)) -> f3(x1, x2, x', 0, x) 34.56/9.95 f4(S(x'), S(x), x3, x4, 0) -> 0 34.56/9.95 f4(S(x), 0, x3, x4, 0) -> 0 34.56/9.95 f2(x1, x2, S(x'), S(x), 0) -> 0 34.56/9.95 f2(x1, x2, S(x), 0, 0) -> 0 34.56/9.95 f0(x1, S(x'), x3, S(x), x5) -> f1(x', S(x'), x, S(x), S(x)) 34.56/9.95 f0(x1, S(x), x3, 0, x5) -> 0 34.56/9.95 f6(x1, x2, x3, x4, S(x)) -> f0(x1, x2, x4, x3, x) 34.56/9.95 f5(x1, x2, x3, x4, S(x)) -> f6(x2, x1, x3, x4, x) 34.56/9.95 f3(x1, x2, x3, x4, S(x)) -> f4(x1, x2, x4, x3, x) 34.56/9.95 f1(x1, x2, x3, x4, S(x)) -> f2(x2, x1, x3, x4, x) 34.56/9.95 f6(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f5(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f4(0, x2, x3, x4, x5) -> 0 34.56/9.95 f3(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f2(x1, x2, 0, x4, x5) -> 0 34.56/9.95 f1(x1, x2, x3, x4, 0) -> 0 34.56/9.95 f0(x1, 0, x3, x4, x5) -> 0 34.56/9.95 34.56/9.95 S is empty. 34.56/9.95 Rewrite Strategy: INNERMOST 34.80/9.98 EOF