/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 (innermost) 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), 203 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsTAProof [FINISHED, 181 ms] (8) BOUNDS(1, n^1) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: fst(0, Z) -> nil fst(s, cons(Y)) -> cons(Y) from(X) -> cons(X) add(0, X) -> X add(s, Y) -> s len(nil) -> 0 len(cons(X)) -> s S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (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(0) -> 0 encArg(nil) -> nil encArg(s) -> s encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(cons_fst(x_1, x_2)) -> fst(encArg(x_1), encArg(x_2)) encArg(cons_from(x_1)) -> from(encArg(x_1)) encArg(cons_add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(cons_len(x_1)) -> len(encArg(x_1)) encode_fst(x_1, x_2) -> fst(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_nil -> nil encode_s -> s encode_cons(x_1) -> cons(encArg(x_1)) encode_from(x_1) -> from(encArg(x_1)) encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_len(x_1) -> len(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: fst(0, Z) -> nil fst(s, cons(Y)) -> cons(Y) from(X) -> cons(X) add(0, X) -> X add(s, Y) -> s len(nil) -> 0 len(cons(X)) -> s The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(nil) -> nil encArg(s) -> s encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(cons_fst(x_1, x_2)) -> fst(encArg(x_1), encArg(x_2)) encArg(cons_from(x_1)) -> from(encArg(x_1)) encArg(cons_add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(cons_len(x_1)) -> len(encArg(x_1)) encode_fst(x_1, x_2) -> fst(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_nil -> nil encode_s -> s encode_cons(x_1) -> cons(encArg(x_1)) encode_from(x_1) -> from(encArg(x_1)) encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_len(x_1) -> len(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: fst(0, Z) -> nil fst(s, cons(Y)) -> cons(Y) from(X) -> cons(X) add(0, X) -> X add(s, Y) -> s len(nil) -> 0 len(cons(X)) -> s The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(nil) -> nil encArg(s) -> s encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(cons_fst(x_1, x_2)) -> fst(encArg(x_1), encArg(x_2)) encArg(cons_from(x_1)) -> from(encArg(x_1)) encArg(cons_add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(cons_len(x_1)) -> len(encArg(x_1)) encode_fst(x_1, x_2) -> fst(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_nil -> nil encode_s -> s encode_cons(x_1) -> cons(encArg(x_1)) encode_from(x_1) -> from(encArg(x_1)) encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_len(x_1) -> len(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) RelTrsToTrsProof (UPPER BOUND(ID)) transformed relative TRS to TRS ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: fst(0, Z) -> nil fst(s, cons(Y)) -> cons(Y) from(X) -> cons(X) add(0, X) -> X add(s, Y) -> s len(nil) -> 0 len(cons(X)) -> s encArg(0) -> 0 encArg(nil) -> nil encArg(s) -> s encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(cons_fst(x_1, x_2)) -> fst(encArg(x_1), encArg(x_2)) encArg(cons_from(x_1)) -> from(encArg(x_1)) encArg(cons_add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(cons_len(x_1)) -> len(encArg(x_1)) encode_fst(x_1, x_2) -> fst(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_nil -> nil encode_s -> s encode_cons(x_1) -> cons(encArg(x_1)) encode_from(x_1) -> from(encArg(x_1)) encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_len(x_1) -> len(encArg(x_1)) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (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 2. 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, 12, 13] transitions: 00() -> 0 nil0() -> 0 s0() -> 0 cons0(0) -> 0 cons_fst0(0, 0) -> 0 cons_from0(0) -> 0 cons_add0(0, 0) -> 0 cons_len0(0) -> 0 fst0(0, 0) -> 1 from0(0) -> 2 add0(0, 0) -> 3 len0(0) -> 4 encArg0(0) -> 5 encode_fst0(0, 0) -> 6 encode_00() -> 7 encode_nil0() -> 8 encode_s0() -> 9 encode_cons0(0) -> 10 encode_from0(0) -> 11 encode_add0(0, 0) -> 12 encode_len0(0) -> 13 nil1() -> 1 cons1(0) -> 1 cons1(0) -> 2 s1() -> 3 01() -> 4 s1() -> 4 01() -> 5 nil1() -> 5 s1() -> 5 encArg1(0) -> 14 cons1(14) -> 5 encArg1(0) -> 15 encArg1(0) -> 16 fst1(15, 16) -> 5 encArg1(0) -> 17 from1(17) -> 5 encArg1(0) -> 18 encArg1(0) -> 19 add1(18, 19) -> 5 encArg1(0) -> 20 len1(20) -> 5 fst1(15, 16) -> 6 01() -> 7 nil1() -> 8 s1() -> 9 cons1(14) -> 10 from1(17) -> 11 add1(18, 19) -> 12 len1(20) -> 13 cons2(17) -> 5 cons2(17) -> 11 01() -> 14 01() -> 15 01() -> 16 01() -> 17 01() -> 18 01() -> 19 01() -> 20 nil1() -> 14 nil1() -> 15 nil1() -> 16 nil1() -> 17 nil1() -> 18 nil1() -> 19 nil1() -> 20 s1() -> 14 s1() -> 15 s1() -> 16 s1() -> 17 s1() -> 18 s1() -> 19 s1() -> 20 cons1(14) -> 14 cons1(14) -> 15 cons1(14) -> 16 cons1(14) -> 17 cons1(14) -> 18 cons1(14) -> 19 cons1(14) -> 20 fst1(15, 16) -> 14 fst1(15, 16) -> 15 fst1(15, 16) -> 16 fst1(15, 16) -> 17 fst1(15, 16) -> 18 fst1(15, 16) -> 19 fst1(15, 16) -> 20 from1(17) -> 14 from1(17) -> 15 from1(17) -> 16 from1(17) -> 17 from1(17) -> 18 from1(17) -> 19 from1(17) -> 20 add1(18, 19) -> 14 add1(18, 19) -> 15 add1(18, 19) -> 16 add1(18, 19) -> 17 add1(18, 19) -> 18 add1(18, 19) -> 19 add1(18, 19) -> 20 len1(20) -> 14 len1(20) -> 15 len1(20) -> 16 len1(20) -> 17 len1(20) -> 18 len1(20) -> 19 len1(20) -> 20 nil2() -> 5 nil2() -> 6 nil2() -> 14 nil2() -> 15 nil2() -> 16 nil2() -> 17 nil2() -> 18 nil2() -> 19 nil2() -> 20 cons2(14) -> 5 cons2(14) -> 6 cons2(14) -> 14 cons2(14) -> 15 cons2(14) -> 16 cons2(14) -> 17 cons2(14) -> 18 cons2(14) -> 19 cons2(14) -> 20 cons2(17) -> 14 cons2(17) -> 15 cons2(17) -> 16 cons2(17) -> 17 cons2(17) -> 18 cons2(17) -> 19 cons2(17) -> 20 s2() -> 5 s2() -> 12 s2() -> 14 s2() -> 15 s2() -> 16 s2() -> 17 s2() -> 18 s2() -> 19 02() -> 5 02() -> 13 02() -> 14 02() -> 15 02() -> 16 02() -> 17 02() -> 18 02() -> 19 s2() -> 13 cons2(17) -> 6 0 -> 3 19 -> 5 19 -> 12 19 -> 14 19 -> 15 19 -> 16 19 -> 17 19 -> 18 19 -> 20 ---------------------------------------- (8) BOUNDS(1, n^1)