/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), 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(n^1, n^1). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 68 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsProof [FINISHED, 0 ms] (8) BOUNDS(1, n^1) (9) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (10) TRS for Loop Detection (11) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (12) BEST (13) proven lower bound (14) LowerBoundPropagationProof [FINISHED, 0 ms] (15) BOUNDS(n^1, INF) (16) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(x1)))))))))) 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(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(1(x_1)) -> 1(encArg(x_1)) encArg(2(x_1)) -> 2(encArg(x_1)) encArg(cons_0(x_1)) -> 0(encArg(x_1)) encode_0(x_1) -> 0(encArg(x_1)) encode_1(x_1) -> 1(encArg(x_1)) encode_2(x_1) -> 2(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(x1)))))))))) 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(x1))))))))))))) The (relative) TRS S consists of the following rules: encArg(1(x_1)) -> 1(encArg(x_1)) encArg(2(x_1)) -> 2(encArg(x_1)) encArg(cons_0(x_1)) -> 0(encArg(x_1)) encode_0(x_1) -> 0(encArg(x_1)) encode_1(x_1) -> 1(encArg(x_1)) encode_2(x_1) -> 2(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(n^1, n^1). The TRS R consists of the following rules: 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(x1)))))))))) 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(x1))))))))))))) The (relative) TRS S consists of the following rules: encArg(1(x_1)) -> 1(encArg(x_1)) encArg(2(x_1)) -> 2(encArg(x_1)) encArg(cons_0(x_1)) -> 0(encArg(x_1)) encode_0(x_1) -> 0(encArg(x_1)) encode_1(x_1) -> 1(encArg(x_1)) encode_2(x_1) -> 2(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: 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(x1)))))))))) 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(x1))))))))))))) encArg(1(x_1)) -> 1(encArg(x_1)) encArg(2(x_1)) -> 2(encArg(x_1)) encArg(cons_0(x_1)) -> 0(encArg(x_1)) encode_0(x_1) -> 0(encArg(x_1)) encode_1(x_1) -> 1(encArg(x_1)) encode_2(x_1) -> 2(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 4. The certificate found is represented by the following graph. "[9, 10, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 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, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189] {(9,10,[0_1|0, encArg_1|0, encode_0_1|0, encode_1_1|0, encode_2_1|0]), (9,16,[1_1|1]), (9,25,[1_1|1]), (9,37,[1_1|1, 2_1|1, 0_1|1]), (9,38,[1_1|2]), (9,47,[1_1|2]), (10,10,[1_1|0, 2_1|0, cons_0_1|0]), (16,17,[2_1|1]), (17,18,[1_1|1]), (18,19,[1_1|1]), (19,20,[0_1|1]), (19,59,[1_1|2]), (19,68,[1_1|2]), (20,21,[1_1|1]), (21,22,[2_1|1]), (22,23,[0_1|1]), (22,16,[1_1|1]), (22,25,[1_1|1]), (23,24,[1_1|1]), (24,10,[2_1|1]), (25,26,[2_1|1]), (26,27,[1_1|1]), (27,28,[1_1|1]), (28,29,[0_1|1]), (28,80,[1_1|2]), (28,89,[1_1|2]), (29,30,[1_1|1]), (30,31,[2_1|1]), (31,32,[0_1|1]), (31,59,[1_1|2]), (31,68,[1_1|2]), (32,33,[1_1|1]), (33,34,[2_1|1]), (34,35,[0_1|1]), (34,16,[1_1|1]), (34,25,[1_1|1]), (35,36,[1_1|1]), (36,10,[2_1|1]), (37,10,[encArg_1|1]), (37,37,[1_1|1, 2_1|1, 0_1|1]), (37,38,[1_1|2]), (37,47,[1_1|2]), (38,39,[2_1|2]), (39,40,[1_1|2]), (40,41,[1_1|2]), (41,42,[0_1|2]), (41,101,[1_1|3]), (41,110,[1_1|3]), (42,43,[1_1|2]), (43,44,[2_1|2]), (44,45,[0_1|2]), (44,38,[1_1|2]), (44,47,[1_1|2]), (44,101,[1_1|3]), (44,110,[1_1|3]), (45,46,[1_1|2]), (46,37,[2_1|2]), (46,38,[2_1|2]), (46,47,[2_1|2]), (46,40,[2_1|2]), (46,49,[2_1|2]), (47,48,[2_1|2]), (48,49,[1_1|2]), (49,50,[1_1|2]), (50,51,[0_1|2]), (50,101,[1_1|3]), (50,110,[1_1|3]), (51,52,[1_1|2]), (52,53,[2_1|2]), (53,54,[0_1|2]), (53,101,[1_1|3]), (53,110,[1_1|3]), (54,55,[1_1|2]), (55,56,[2_1|2]), (56,57,[0_1|2]), (56,38,[1_1|2]), (56,47,[1_1|2]), (56,101,[1_1|3]), (56,110,[1_1|3]), (57,58,[1_1|2]), (58,37,[2_1|2]), (58,38,[2_1|2]), (58,47,[2_1|2]), (58,40,[2_1|2]), (58,49,[2_1|2]), (59,60,[2_1|2]), (60,61,[1_1|2]), (61,62,[1_1|2]), (62,63,[0_1|2]), (63,64,[1_1|2]), (64,65,[2_1|2]), (65,66,[0_1|2]), (66,67,[1_1|2]), (67,16,[2_1|2]), (67,25,[2_1|2]), (68,69,[2_1|2]), (69,70,[1_1|2]), (70,71,[1_1|2]), (71,72,[0_1|2]), (72,73,[1_1|2]), (73,74,[2_1|2]), (74,75,[0_1|2]), (75,76,[1_1|2]), (76,77,[2_1|2]), (77,78,[0_1|2]), (78,79,[1_1|2]), (79,16,[2_1|2]), (79,25,[2_1|2]), (80,81,[2_1|2]), (81,82,[1_1|2]), (82,83,[1_1|2]), (83,84,[0_1|2]), (84,85,[1_1|2]), (85,86,[2_1|2]), (86,87,[0_1|2]), (87,88,[1_1|2]), (88,59,[2_1|2]), (88,68,[2_1|2]), (89,90,[2_1|2]), (90,91,[1_1|2]), (91,92,[1_1|2]), (92,93,[0_1|2]), (93,94,[1_1|2]), (94,95,[2_1|2]), (95,96,[0_1|2]), (96,97,[1_1|2]), (97,98,[2_1|2]), (98,99,[0_1|2]), (99,100,[1_1|2]), (100,59,[2_1|2]), (100,68,[2_1|2]), (101,102,[2_1|3]), (102,103,[1_1|3]), (103,104,[1_1|3]), (104,105,[0_1|3]), (104,148,[1_1|4]), (104,157,[1_1|4]), (105,106,[1_1|3]), (106,107,[2_1|3]), (107,108,[0_1|3]), (107,127,[1_1|4]), (107,136,[1_1|4]), (108,109,[1_1|3]), (109,38,[2_1|3]), (109,47,[2_1|3]), (109,101,[2_1|3]), (109,110,[2_1|3]), (109,41,[2_1|3]), (109,50,[2_1|3]), (110,111,[2_1|3]), (111,112,[1_1|3]), (112,113,[1_1|3]), (113,114,[0_1|3]), (113,169,[1_1|4]), (113,178,[1_1|4]), (114,115,[1_1|3]), (115,116,[2_1|3]), (116,117,[0_1|3]), (116,148,[1_1|4]), (116,157,[1_1|4]), (117,118,[1_1|3]), (118,119,[2_1|3]), (119,120,[0_1|3]), (119,127,[1_1|4]), (119,136,[1_1|4]), (120,121,[1_1|3]), (121,38,[2_1|3]), (121,47,[2_1|3]), (121,101,[2_1|3]), (121,110,[2_1|3]), (121,41,[2_1|3]), (121,50,[2_1|3]), (127,128,[2_1|4]), (128,129,[1_1|4]), (129,130,[1_1|4]), (130,131,[0_1|4]), (131,132,[1_1|4]), (132,133,[2_1|4]), (133,134,[0_1|4]), (134,135,[1_1|4]), (135,101,[2_1|4]), (135,110,[2_1|4]), (136,137,[2_1|4]), (137,138,[1_1|4]), (138,139,[1_1|4]), (139,140,[0_1|4]), (140,141,[1_1|4]), (141,142,[2_1|4]), (142,143,[0_1|4]), (143,144,[1_1|4]), (144,145,[2_1|4]), (145,146,[0_1|4]), (146,147,[1_1|4]), (147,101,[2_1|4]), (147,110,[2_1|4]), (148,149,[2_1|4]), (149,150,[1_1|4]), (150,151,[1_1|4]), (151,152,[0_1|4]), (152,153,[1_1|4]), (153,154,[2_1|4]), (154,155,[0_1|4]), (155,156,[1_1|4]), (156,127,[2_1|4]), (156,136,[2_1|4]), (157,158,[2_1|4]), (158,159,[1_1|4]), (159,160,[1_1|4]), (160,161,[0_1|4]), (161,162,[1_1|4]), (162,163,[2_1|4]), (163,164,[0_1|4]), (164,165,[1_1|4]), (165,166,[2_1|4]), (166,167,[0_1|4]), (167,168,[1_1|4]), (168,127,[2_1|4]), (168,136,[2_1|4]), (169,170,[2_1|4]), (170,171,[1_1|4]), (171,172,[1_1|4]), (172,173,[0_1|4]), (173,174,[1_1|4]), (174,175,[2_1|4]), (175,176,[0_1|4]), (176,177,[1_1|4]), (177,148,[2_1|4]), (177,157,[2_1|4]), (178,179,[2_1|4]), (179,180,[1_1|4]), (180,181,[1_1|4]), (181,182,[0_1|4]), (182,183,[1_1|4]), (183,184,[2_1|4]), (184,185,[0_1|4]), (185,186,[1_1|4]), (186,187,[2_1|4]), (187,188,[0_1|4]), (188,189,[1_1|4]), (189,148,[2_1|4]), (189,157,[2_1|4])}" ---------------------------------------- (8) BOUNDS(1, n^1) ---------------------------------------- (9) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (10) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(x1)))))))))) 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(x1))))))))))))) The (relative) TRS S consists of the following rules: encArg(1(x_1)) -> 1(encArg(x_1)) encArg(2(x_1)) -> 2(encArg(x_1)) encArg(cons_0(x_1)) -> 0(encArg(x_1)) encode_0(x_1) -> 0(encArg(x_1)) encode_1(x_1) -> 1(encArg(x_1)) encode_2(x_1) -> 2(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (11) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence 0(1(2(1(x1)))) ->^+ 1(2(1(1(0(1(2(0(1(2(x1)))))))))) gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0,0,0,0,0,0]. The pumping substitution is [x1 / 1(x1)]. The result substitution is [ ]. ---------------------------------------- (12) Complex Obligation (BEST) ---------------------------------------- (13) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(x1)))))))))) 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(x1))))))))))))) The (relative) TRS S consists of the following rules: encArg(1(x_1)) -> 1(encArg(x_1)) encArg(2(x_1)) -> 2(encArg(x_1)) encArg(cons_0(x_1)) -> 0(encArg(x_1)) encode_0(x_1) -> 0(encArg(x_1)) encode_1(x_1) -> 1(encArg(x_1)) encode_2(x_1) -> 2(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (14) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (15) BOUNDS(n^1, INF) ---------------------------------------- (16) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(x1)))))))))) 0(1(2(1(x1)))) -> 1(2(1(1(0(1(2(0(1(2(0(1(2(x1))))))))))))) The (relative) TRS S consists of the following rules: encArg(1(x_1)) -> 1(encArg(x_1)) encArg(2(x_1)) -> 2(encArg(x_1)) encArg(cons_0(x_1)) -> 0(encArg(x_1)) encode_0(x_1) -> 0(encArg(x_1)) encode_1(x_1) -> 1(encArg(x_1)) encode_2(x_1) -> 2(encArg(x_1)) Rewrite Strategy: FULL