/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), 40 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsProof [FINISHED, 28 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: a(a(a(b(x1)))) -> b(a(b(a(x1)))) b(b(a(x1))) -> a(a(a(b(x1)))) 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(cons_a(x_1)) -> a(encArg(x_1)) encArg(cons_b(x_1)) -> b(encArg(x_1)) encode_a(x_1) -> a(encArg(x_1)) encode_b(x_1) -> b(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: a(a(a(b(x1)))) -> b(a(b(a(x1)))) b(b(a(x1))) -> a(a(a(b(x1)))) The (relative) TRS S consists of the following rules: encArg(cons_a(x_1)) -> a(encArg(x_1)) encArg(cons_b(x_1)) -> b(encArg(x_1)) encode_a(x_1) -> a(encArg(x_1)) encode_b(x_1) -> b(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: a(a(a(b(x1)))) -> b(a(b(a(x1)))) b(b(a(x1))) -> a(a(a(b(x1)))) The (relative) TRS S consists of the following rules: encArg(cons_a(x_1)) -> a(encArg(x_1)) encArg(cons_b(x_1)) -> b(encArg(x_1)) encode_a(x_1) -> a(encArg(x_1)) encode_b(x_1) -> b(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: a(a(a(b(x1)))) -> b(a(b(a(x1)))) b(b(a(x1))) -> a(a(a(b(x1)))) encArg(cons_a(x_1)) -> a(encArg(x_1)) encArg(cons_b(x_1)) -> b(encArg(x_1)) encode_a(x_1) -> a(encArg(x_1)) encode_b(x_1) -> b(encArg(x_1)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (7) CpxTrsMatchBoundsProof (FINISHED) A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 7. The certificate found is represented by the following graph. "[30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65] {(30,31,[a_1|0, b_1|0, encArg_1|0, encode_a_1|0, encode_b_1|0]), (30,32,[a_1|1, b_1|1]), (30,33,[b_1|2]), (30,36,[a_1|2]), (30,39,[b_1|3]), (31,31,[cons_a_1|0, cons_b_1|0]), (32,31,[encArg_1|1]), (32,32,[a_1|1, b_1|1]), (32,33,[b_1|2]), (32,36,[a_1|2]), (32,39,[b_1|3]), (33,34,[a_1|2]), (34,35,[b_1|2]), (34,42,[a_1|3]), (34,45,[b_1|4]), (35,32,[a_1|2]), (35,33,[a_1|2, b_1|2]), (35,39,[a_1|2]), (36,37,[a_1|2]), (37,38,[a_1|2]), (38,32,[b_1|2]), (38,36,[b_1|2, a_1|2]), (38,34,[b_1|2]), (38,42,[a_1|3]), (38,40,[b_1|2]), (38,39,[b_1|3]), (38,45,[b_1|4]), (39,40,[a_1|3]), (40,41,[b_1|3]), (40,42,[a_1|3]), (40,48,[a_1|4]), (40,45,[b_1|4]), (40,51,[b_1|5]), (41,32,[a_1|3]), (41,36,[a_1|3]), (41,34,[a_1|3]), (41,33,[b_1|2]), (41,40,[a_1|3]), (41,39,[a_1|3, b_1|3]), (41,45,[a_1|3]), (42,43,[a_1|3]), (43,44,[a_1|3]), (44,34,[b_1|3]), (44,40,[b_1|3]), (44,32,[b_1|3]), (44,33,[b_1|3]), (44,42,[a_1|3]), (44,39,[b_1|3]), (44,36,[b_1|3, a_1|2]), (44,48,[a_1|4]), (44,45,[b_1|4, b_1|3]), (44,46,[b_1|3]), (44,51,[b_1|5]), (44,52,[b_1|3]), (45,46,[a_1|4]), (46,47,[b_1|4]), (46,42,[a_1|3]), (46,48,[a_1|4]), (46,45,[b_1|4]), (46,51,[b_1|5]), (47,34,[a_1|4]), (47,40,[a_1|4]), (47,32,[a_1|4]), (47,33,[a_1|4, b_1|2]), (47,39,[a_1|4, b_1|3]), (47,36,[a_1|4]), (47,45,[a_1|4]), (47,46,[a_1|4]), (47,51,[a_1|4]), (47,52,[a_1|4]), (48,49,[a_1|4]), (49,50,[a_1|4]), (50,32,[b_1|4]), (50,36,[b_1|4, a_1|2]), (50,34,[b_1|4]), (50,40,[b_1|4]), (50,46,[b_1|4]), (50,39,[b_1|4, b_1|3]), (50,45,[b_1|4]), (50,42,[a_1|3]), (50,48,[a_1|4]), (50,54,[a_1|5]), (50,33,[b_1|4]), (50,51,[b_1|5, b_1|4]), (50,57,[b_1|6, b_1|4]), (50,52,[b_1|4]), (51,52,[a_1|5]), (52,53,[b_1|5]), (52,48,[a_1|4]), (52,42,[a_1|3]), (52,51,[b_1|5]), (52,45,[b_1|4]), (53,32,[a_1|5]), (53,36,[a_1|5]), (53,34,[a_1|5]), (53,40,[a_1|5]), (53,46,[a_1|5]), (53,39,[a_1|5, b_1|3]), (53,45,[a_1|5]), (53,33,[b_1|2, a_1|5]), (53,51,[a_1|5]), (53,57,[a_1|5]), (53,52,[a_1|5]), (54,55,[a_1|5]), (55,56,[a_1|5]), (56,46,[b_1|5]), (56,34,[b_1|5]), (56,40,[b_1|5]), (56,32,[b_1|5]), (56,33,[b_1|5]), (56,39,[b_1|5, b_1|3]), (56,36,[b_1|5, a_1|2]), (56,45,[b_1|5, b_1|4]), (56,54,[a_1|5]), (56,52,[b_1|5]), (56,51,[b_1|5]), (56,42,[a_1|3]), (56,48,[a_1|4]), (56,60,[a_1|6]), (56,57,[b_1|6, b_1|5]), (56,63,[b_1|7]), (57,58,[a_1|6]), (58,59,[b_1|6]), (58,42,[a_1|3]), (58,48,[a_1|4]), (58,45,[b_1|4]), (58,51,[b_1|5]), (59,46,[a_1|6]), (59,34,[a_1|6]), (59,40,[a_1|6]), (59,32,[a_1|6]), (59,33,[a_1|6, b_1|2]), (59,39,[a_1|6, b_1|3]), (59,36,[a_1|6]), (59,45,[a_1|6]), (59,52,[a_1|6]), (59,51,[a_1|6]), (59,57,[a_1|6]), (59,63,[a_1|6]), (60,61,[a_1|6]), (61,62,[a_1|6]), (62,52,[b_1|6]), (62,32,[b_1|6]), (62,36,[b_1|6, a_1|2]), (62,34,[b_1|6]), (62,40,[b_1|6]), (62,46,[b_1|6]), (62,39,[b_1|6, b_1|3]), (62,45,[b_1|6, b_1|4]), (62,33,[b_1|6]), (62,51,[b_1|6, b_1|5]), (62,57,[b_1|6]), (62,60,[a_1|6]), (62,54,[a_1|5]), (62,42,[a_1|3]), (62,48,[a_1|4]), (62,63,[b_1|7]), (63,64,[a_1|7]), (64,65,[b_1|7]), (64,48,[a_1|4]), (64,42,[a_1|3]), (64,51,[b_1|5]), (64,45,[b_1|4]), (65,52,[a_1|7]), (65,32,[a_1|7]), (65,36,[a_1|7]), (65,34,[a_1|7]), (65,40,[a_1|7]), (65,46,[a_1|7]), (65,39,[a_1|7, b_1|3]), (65,45,[a_1|7]), (65,33,[a_1|7, b_1|2]), (65,51,[a_1|7]), (65,57,[a_1|7]), (65,63,[a_1|7])}" ---------------------------------------- (8) BOUNDS(1, n^1)