/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 192 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsTAProof [FINISHED, 1018 ms] (8) BOUNDS(1, n^1) ---------------------------------------- (0) Obligation: The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(X) -> if(X, c, n__f(true)) if(true, X, Y) -> X if(false, X, Y) -> activate(Y) f(X) -> n__f(X) activate(n__f(X)) -> f(X) activate(X) -> X S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(c) -> c encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(true) -> true encArg(false) -> false encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_c -> c encode_n__f(x_1) -> n__f(encArg(x_1)) encode_true -> true encode_false -> false encode_activate(x_1) -> activate(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(X) -> if(X, c, n__f(true)) if(true, X, Y) -> X if(false, X, Y) -> activate(Y) f(X) -> n__f(X) activate(n__f(X)) -> f(X) activate(X) -> X The (relative) TRS S consists of the following rules: encArg(c) -> c encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(true) -> true encArg(false) -> false encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_c -> c encode_n__f(x_1) -> n__f(encArg(x_1)) encode_true -> true encode_false -> false encode_activate(x_1) -> activate(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(X) -> if(X, c, n__f(true)) if(true, X, Y) -> X if(false, X, Y) -> activate(Y) f(X) -> n__f(X) activate(n__f(X)) -> f(X) activate(X) -> X The (relative) TRS S consists of the following rules: encArg(c) -> c encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(true) -> true encArg(false) -> false encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_c -> c encode_n__f(x_1) -> n__f(encArg(x_1)) encode_true -> true encode_false -> false encode_activate(x_1) -> activate(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (5) RelTrsToTrsProof (UPPER BOUND(ID)) transformed relative TRS to TRS ---------------------------------------- (6) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(X) -> if(X, c, n__f(true)) if(true, X, Y) -> X if(false, X, Y) -> activate(Y) f(X) -> n__f(X) activate(n__f(X)) -> f(X) activate(X) -> X encArg(c) -> c encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(true) -> true encArg(false) -> false encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_c -> c encode_n__f(x_1) -> n__f(encArg(x_1)) encode_true -> true encode_false -> false encode_activate(x_1) -> activate(encArg(x_1)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (7) CpxTrsMatchBoundsTAProof (FINISHED) A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 4. The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] transitions: c0() -> 0 n__f0(0) -> 0 true0() -> 0 false0() -> 0 cons_f0(0) -> 0 cons_if0(0, 0, 0) -> 0 cons_activate0(0) -> 0 f0(0) -> 1 if0(0, 0, 0) -> 2 activate0(0) -> 3 encArg0(0) -> 4 encode_f0(0) -> 5 encode_if0(0, 0, 0) -> 6 encode_c0() -> 7 encode_n__f0(0) -> 8 encode_true0() -> 9 encode_false0() -> 10 encode_activate0(0) -> 11 c1() -> 12 true1() -> 14 n__f1(14) -> 13 if1(0, 12, 13) -> 1 activate1(0) -> 2 n__f1(0) -> 1 f1(0) -> 3 c1() -> 4 encArg1(0) -> 15 n__f1(15) -> 4 true1() -> 4 false1() -> 4 encArg1(0) -> 16 f1(16) -> 4 encArg1(0) -> 17 encArg1(0) -> 18 encArg1(0) -> 19 if1(17, 18, 19) -> 4 encArg1(0) -> 20 activate1(20) -> 4 f1(16) -> 5 if1(17, 18, 19) -> 6 c1() -> 7 n__f1(15) -> 8 true1() -> 9 false1() -> 10 activate1(20) -> 11 c2() -> 21 true2() -> 23 n__f2(23) -> 22 if2(0, 21, 22) -> 3 if2(16, 21, 22) -> 4 if2(16, 21, 22) -> 5 activate1(13) -> 1 n__f2(0) -> 3 n__f2(16) -> 4 n__f2(16) -> 5 f1(0) -> 2 c1() -> 15 c1() -> 16 c1() -> 17 c1() -> 18 c1() -> 19 c1() -> 20 n__f1(15) -> 15 n__f1(15) -> 16 n__f1(15) -> 17 n__f1(15) -> 18 n__f1(15) -> 19 n__f1(15) -> 20 true1() -> 15 true1() -> 16 true1() -> 17 true1() -> 18 true1() -> 19 true1() -> 20 false1() -> 15 false1() -> 16 false1() -> 17 false1() -> 18 false1() -> 19 false1() -> 20 f1(16) -> 15 f1(16) -> 16 f1(16) -> 17 f1(16) -> 18 f1(16) -> 19 f1(16) -> 20 if1(17, 18, 19) -> 15 if1(17, 18, 19) -> 16 if1(17, 18, 19) -> 17 if1(17, 18, 19) -> 18 if1(17, 18, 19) -> 19 if1(17, 18, 19) -> 20 activate1(20) -> 15 activate1(20) -> 16 activate1(20) -> 17 activate1(20) -> 18 activate1(20) -> 19 activate1(20) -> 20 if2(0, 21, 22) -> 2 if2(16, 21, 22) -> 11 if2(16, 21, 22) -> 15 if2(16, 21, 22) -> 16 if2(16, 21, 22) -> 17 if2(16, 21, 22) -> 18 if2(16, 21, 22) -> 19 if2(16, 21, 22) -> 20 activate2(19) -> 4 activate2(19) -> 6 activate2(19) -> 11 activate2(19) -> 15 activate2(19) -> 16 activate2(19) -> 17 activate2(19) -> 18 n__f2(0) -> 2 n__f2(16) -> 11 n__f2(16) -> 15 n__f2(16) -> 16 n__f2(16) -> 17 n__f2(16) -> 18 f2(14) -> 1 f2(15) -> 4 f2(15) -> 11 f2(15) -> 15 f2(15) -> 16 f2(15) -> 17 f2(15) -> 18 activate1(22) -> 3 activate2(22) -> 4 activate2(22) -> 5 activate1(22) -> 2 activate2(22) -> 6 activate2(22) -> 11 activate2(22) -> 15 activate2(22) -> 16 activate2(22) -> 17 activate2(22) -> 18 f2(23) -> 3 f2(16) -> 4 f2(16) -> 6 f2(16) -> 11 f2(16) -> 15 f2(16) -> 16 f2(16) -> 17 f2(16) -> 18 c3() -> 24 true3() -> 26 n__f3(26) -> 25 if3(14, 24, 25) -> 1 if3(15, 24, 25) -> 4 if3(15, 24, 25) -> 6 if3(15, 24, 25) -> 11 if3(15, 24, 25) -> 15 if3(15, 24, 25) -> 16 if3(15, 24, 25) -> 17 if3(15, 24, 25) -> 18 n__f3(14) -> 1 n__f3(15) -> 4 n__f3(15) -> 6 n__f3(15) -> 11 n__f3(15) -> 15 n__f3(15) -> 16 n__f3(15) -> 17 n__f3(15) -> 18 f3(16) -> 4 f3(23) -> 4 f3(23) -> 5 f3(16) -> 6 f3(16) -> 11 f3(16) -> 15 f3(16) -> 16 f3(16) -> 17 f3(16) -> 18 f2(23) -> 2 if3(23, 24, 25) -> 3 if3(16, 24, 25) -> 4 if3(16, 24, 25) -> 6 if3(16, 24, 25) -> 11 if3(16, 24, 25) -> 15 if3(16, 24, 25) -> 16 if3(16, 24, 25) -> 17 if3(16, 24, 25) -> 18 n__f3(23) -> 3 n__f3(16) -> 4 n__f3(16) -> 6 n__f3(16) -> 11 n__f3(16) -> 15 n__f3(16) -> 16 n__f3(16) -> 17 n__f3(16) -> 18 f3(23) -> 6 f3(23) -> 11 f3(23) -> 15 f3(23) -> 16 f3(23) -> 17 f3(23) -> 18 c4() -> 27 true4() -> 29 n__f4(29) -> 28 if4(16, 27, 28) -> 4 if4(23, 27, 28) -> 4 if4(23, 27, 28) -> 5 if4(16, 27, 28) -> 6 if4(16, 27, 28) -> 11 if4(16, 27, 28) -> 15 if4(16, 27, 28) -> 16 if4(16, 27, 28) -> 17 if4(16, 27, 28) -> 18 activate2(25) -> 4 activate2(25) -> 6 activate2(25) -> 11 activate2(25) -> 15 activate2(25) -> 16 activate2(25) -> 17 activate2(25) -> 18 n__f4(16) -> 4 n__f4(23) -> 4 n__f4(23) -> 5 n__f4(16) -> 6 n__f4(16) -> 11 n__f4(16) -> 15 n__f4(16) -> 16 n__f4(16) -> 17 n__f4(16) -> 18 f3(15) -> 4 f3(15) -> 6 f3(15) -> 11 f3(15) -> 15 f3(15) -> 16 f3(15) -> 17 f3(15) -> 18 f2(23) -> 4 f2(23) -> 6 f2(23) -> 11 f2(23) -> 15 f2(23) -> 16 f2(23) -> 17 f2(23) -> 18 if3(23, 24, 25) -> 2 n__f3(23) -> 2 if4(15, 27, 28) -> 4 if4(23, 27, 28) -> 6 if4(15, 27, 28) -> 6 if4(23, 27, 28) -> 11 if4(15, 27, 28) -> 11 if4(23, 27, 28) -> 15 if4(15, 27, 28) -> 15 if4(23, 27, 28) -> 16 if4(15, 27, 28) -> 16 if4(23, 27, 28) -> 17 if4(15, 27, 28) -> 17 if4(23, 27, 28) -> 18 if4(15, 27, 28) -> 18 n__f4(15) -> 4 n__f4(23) -> 6 n__f4(15) -> 6 n__f4(23) -> 11 n__f4(15) -> 11 n__f4(23) -> 15 n__f4(15) -> 15 n__f4(23) -> 16 n__f4(15) -> 16 n__f4(23) -> 17 n__f4(15) -> 17 n__f4(23) -> 18 n__f4(15) -> 18 f3(26) -> 4 f3(26) -> 6 f3(26) -> 11 f3(26) -> 15 f3(26) -> 16 f3(26) -> 17 f3(26) -> 18 activate2(28) -> 4 activate2(28) -> 6 activate2(28) -> 11 activate2(28) -> 15 activate2(28) -> 16 activate2(28) -> 17 activate2(28) -> 18 if3(23, 24, 25) -> 4 if3(23, 24, 25) -> 6 if3(23, 24, 25) -> 11 if3(23, 24, 25) -> 15 if3(23, 24, 25) -> 16 if3(23, 24, 25) -> 17 if3(23, 24, 25) -> 18 n__f3(23) -> 4 n__f3(23) -> 6 n__f3(23) -> 11 n__f3(23) -> 15 n__f3(23) -> 16 n__f3(23) -> 17 n__f3(23) -> 18 if4(26, 27, 28) -> 4 if4(26, 27, 28) -> 6 if4(26, 27, 28) -> 11 if4(26, 27, 28) -> 15 if4(26, 27, 28) -> 16 if4(26, 27, 28) -> 17 if4(26, 27, 28) -> 18 n__f4(26) -> 4 n__f4(26) -> 6 n__f4(26) -> 11 n__f4(26) -> 15 n__f4(26) -> 16 n__f4(26) -> 17 n__f4(26) -> 18 f2(26) -> 4 f2(26) -> 6 f2(26) -> 11 f2(26) -> 15 f2(26) -> 16 f2(26) -> 17 f2(26) -> 18 f3(29) -> 4 f3(29) -> 6 f3(29) -> 11 f3(29) -> 15 f3(29) -> 16 f3(29) -> 17 f3(29) -> 18 if3(26, 24, 25) -> 4 if3(26, 24, 25) -> 6 if3(26, 24, 25) -> 11 if3(26, 24, 25) -> 15 if3(26, 24, 25) -> 16 if3(26, 24, 25) -> 17 if3(26, 24, 25) -> 18 if4(29, 27, 28) -> 4 if4(29, 27, 28) -> 6 if4(29, 27, 28) -> 11 if4(29, 27, 28) -> 15 if4(29, 27, 28) -> 16 if4(29, 27, 28) -> 17 if4(29, 27, 28) -> 18 f2(29) -> 4 f2(29) -> 6 f2(29) -> 11 f2(29) -> 15 f2(29) -> 16 f2(29) -> 17 f2(29) -> 18 if3(29, 24, 25) -> 4 if3(29, 24, 25) -> 6 if3(29, 24, 25) -> 11 if3(29, 24, 25) -> 15 if3(29, 24, 25) -> 16 if3(29, 24, 25) -> 17 if3(29, 24, 25) -> 18 n__f3(29) -> 4 n__f3(29) -> 6 n__f3(29) -> 11 n__f3(29) -> 15 n__f3(29) -> 16 n__f3(29) -> 17 n__f3(29) -> 18 0 -> 2 0 -> 3 12 -> 1 20 -> 4 20 -> 11 20 -> 15 20 -> 16 20 -> 17 20 -> 18 18 -> 4 18 -> 6 18 -> 11 18 -> 15 18 -> 16 18 -> 17 18 -> 19 18 -> 20 13 -> 1 21 -> 3 21 -> 4 21 -> 5 21 -> 2 21 -> 6 21 -> 11 21 -> 15 21 -> 16 21 -> 17 21 -> 18 22 -> 3 22 -> 4 22 -> 5 22 -> 2 22 -> 6 22 -> 11 22 -> 15 22 -> 16 22 -> 17 22 -> 18 19 -> 4 19 -> 6 19 -> 11 19 -> 15 19 -> 16 19 -> 17 19 -> 18 24 -> 1 24 -> 4 24 -> 6 24 -> 11 24 -> 15 24 -> 16 24 -> 17 24 -> 18 24 -> 3 24 -> 2 25 -> 4 25 -> 6 25 -> 11 25 -> 15 25 -> 16 25 -> 17 25 -> 18 27 -> 4 27 -> 6 27 -> 11 27 -> 15 27 -> 16 27 -> 17 27 -> 18 27 -> 5 28 -> 4 28 -> 6 28 -> 11 28 -> 15 28 -> 16 28 -> 17 28 -> 18 ---------------------------------------- (8) BOUNDS(1, n^1)