/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given RelTRS could be proven: (0) RelTRS (1) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 568 ms] (2) RelTRS (3) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 273 ms] (4) RelTRS (5) RelTRSRRRProof [EQUIVALENT, 0 ms] (6) RelTRS (7) RIsEmptyProof [EQUIVALENT, 0 ms] (8) YES ---------------------------------------- (0) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: top(ok(left(car(x, y), z))) -> top(check(right(y, z))) top(ok(right(x, car(y, z)))) -> top(check(left(x, z))) top(ok(left(bot, x))) -> top(check(right(bot, x))) top(ok(right(x, bot))) -> top(check(left(x, bot))) The relative TRS consists of the following S rules: top(ok(left(car(x, y), z))) -> top(check(left(y, z))) top(ok(right(x, car(y, z)))) -> top(check(right(x, z))) bot -> car(new, bot) check(old) -> ok(old) check(car(x, y)) -> car(check(x), y) check(car(x, y)) -> car(x, check(y)) check(left(x, y)) -> left(check(x), y) check(left(x, y)) -> left(x, check(y)) check(right(x, y)) -> right(check(x), y) check(right(x, y)) -> right(x, check(y)) car(ok(x), y) -> ok(car(x, y)) car(x, ok(y)) -> ok(car(x, y)) left(ok(x), y) -> ok(left(x, y)) left(x, ok(y)) -> ok(left(x, y)) right(ok(x), y) -> ok(right(x, y)) right(x, ok(y)) -> ok(right(x, y)) ---------------------------------------- (1) RelTRSSemanticLabellingPOLOProof (EQUIVALENT) We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB] We use semantic labelling over boolean tuples of size 1. We used the following model: top_1: component 1: OR[] ok_1: component 1: AND[] left_2: component 1: OR[x_1^1, x_2^1] car_2: component 1: OR[x_1^1, x_2^1] check_1: component 1: OR[x_1^1] right_2: component 1: OR[x_1^1, x_2^1] bot_0: component 1: OR[] new_0: component 1: OR[] old_0: component 1: AND[] Our labelling function was: top_1:component 1: XOR[x_1^1] ok_1:component 1: OR[] left_2:component 1: XOR[x_2^1] car_2:component 1: OR[x_2^1] check_1:component 1: XOR[] right_2:component 1: AND[x_1^1] bot_0:component 1: AND[] new_0:component 1: OR[] old_0:component 1: OR[] Our labelled system was: ^[f]top^[t](^[t]ok^[f](^[f]left^[f](^[f]car^[f](^[f]x, ^[f]y), ^[f]z))) -> ^[f]top^[f](^[f]check^[f](^[f]left^[f](^[f]y, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[t](^[f]car^[f](^[f]x, ^[f]y), ^[t]z))) -> ^[f]top^[t](^[t]check^[f](^[t]left^[t](^[f]y, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[f](^[t]car^[t](^[f]x, ^[t]y), ^[f]z))) -> ^[f]top^[t](^[t]check^[f](^[t]left^[f](^[t]y, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[t](^[t]car^[t](^[f]x, ^[t]y), ^[t]z))) -> ^[f]top^[t](^[t]check^[f](^[t]left^[t](^[t]y, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[f](^[t]car^[f](^[t]x, ^[f]y), ^[f]z))) -> ^[f]top^[f](^[f]check^[f](^[f]left^[f](^[f]y, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[t](^[t]car^[f](^[t]x, ^[f]y), ^[t]z))) -> ^[f]top^[t](^[t]check^[f](^[t]left^[t](^[f]y, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[f]right^[f](^[f]x, ^[f]car^[f](^[f]y, ^[f]z)))) -> ^[f]top^[f](^[f]check^[f](^[f]right^[f](^[f]x, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[f](^[f]x, ^[t]car^[t](^[f]y, ^[t]z)))) -> ^[f]top^[t](^[t]check^[f](^[t]right^[f](^[f]x, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[f](^[f]x, ^[t]car^[f](^[t]y, ^[f]z)))) -> ^[f]top^[f](^[f]check^[f](^[f]right^[f](^[f]x, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[t](^[t]x, ^[f]car^[f](^[f]y, ^[f]z)))) -> ^[f]top^[t](^[t]check^[f](^[t]right^[t](^[t]x, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[t](^[t]x, ^[t]car^[t](^[f]y, ^[t]z)))) -> ^[f]top^[t](^[t]check^[f](^[t]right^[t](^[t]x, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[t](^[t]x, ^[t]car^[f](^[t]y, ^[f]z)))) -> ^[f]top^[t](^[t]check^[f](^[t]right^[t](^[t]x, ^[f]z))) ^[f]bot^[t] -> ^[f]car^[f](^[f]new^[f], ^[f]bot^[t]) ^[t]check^[f](^[t]old^[f]) -> ^[t]ok^[f](^[t]old^[f]) ^[f]check^[f](^[f]car^[f](^[f]x, ^[f]y)) -> ^[f]car^[f](^[f]check^[f](^[f]x), ^[f]y) ^[t]check^[f](^[t]car^[t](^[f]x, ^[t]y)) -> ^[t]car^[t](^[f]check^[f](^[f]x), ^[t]y) ^[t]check^[f](^[t]car^[f](^[t]x, ^[f]y)) -> ^[t]car^[f](^[t]check^[f](^[t]x), ^[f]y) ^[t]check^[f](^[t]car^[t](^[t]x, ^[t]y)) -> ^[t]car^[t](^[t]check^[f](^[t]x), ^[t]y) ^[f]check^[f](^[f]car^[f](^[f]x, ^[f]y)) -> ^[f]car^[f](^[f]x, ^[f]check^[f](^[f]y)) ^[t]check^[f](^[t]car^[t](^[f]x, ^[t]y)) -> ^[t]car^[t](^[f]x, ^[t]check^[f](^[t]y)) ^[t]check^[f](^[t]car^[f](^[t]x, ^[f]y)) -> ^[t]car^[f](^[t]x, ^[f]check^[f](^[f]y)) ^[f]check^[f](^[f]left^[f](^[f]x, ^[f]y)) -> ^[f]left^[f](^[f]check^[f](^[f]x), ^[f]y) ^[t]check^[f](^[t]left^[t](^[f]x, ^[t]y)) -> ^[t]left^[t](^[f]check^[f](^[f]x), ^[t]y) ^[t]check^[f](^[t]left^[f](^[t]x, ^[f]y)) -> ^[t]left^[f](^[t]check^[f](^[t]x), ^[f]y) ^[t]check^[f](^[t]left^[t](^[t]x, ^[t]y)) -> ^[t]left^[t](^[t]check^[f](^[t]x), ^[t]y) ^[f]check^[f](^[f]left^[f](^[f]x, ^[f]y)) -> ^[f]left^[f](^[f]x, ^[f]check^[f](^[f]y)) ^[t]check^[f](^[t]left^[t](^[f]x, ^[t]y)) -> ^[t]left^[t](^[f]x, ^[t]check^[f](^[t]y)) ^[t]check^[f](^[t]left^[f](^[t]x, ^[f]y)) -> ^[t]left^[f](^[t]x, ^[f]check^[f](^[f]y)) ^[f]check^[f](^[f]right^[f](^[f]x, ^[f]y)) -> ^[f]right^[f](^[f]check^[f](^[f]x), ^[f]y) ^[t]check^[f](^[t]right^[f](^[f]x, ^[t]y)) -> ^[t]right^[f](^[f]check^[f](^[f]x), ^[t]y) ^[t]check^[f](^[t]right^[t](^[t]x, ^[f]y)) -> ^[t]right^[t](^[t]check^[f](^[t]x), ^[f]y) ^[f]check^[f](^[f]right^[f](^[f]x, ^[f]y)) -> ^[f]right^[f](^[f]x, ^[f]check^[f](^[f]y)) ^[t]check^[f](^[t]right^[f](^[f]x, ^[t]y)) -> ^[t]right^[f](^[f]x, ^[t]check^[f](^[t]y)) ^[t]check^[f](^[t]right^[t](^[t]x, ^[f]y)) -> ^[t]right^[t](^[t]x, ^[f]check^[f](^[f]y)) ^[t]check^[f](^[t]right^[t](^[t]x, ^[t]y)) -> ^[t]right^[t](^[t]x, ^[t]check^[f](^[t]y)) ^[t]car^[f](^[t]ok^[f](^[f]x), ^[f]y) -> ^[t]ok^[f](^[f]car^[f](^[f]x, ^[f]y)) ^[t]car^[t](^[t]ok^[f](^[f]x), ^[t]y) -> ^[t]ok^[f](^[t]car^[t](^[f]x, ^[t]y)) ^[t]car^[f](^[t]ok^[f](^[t]x), ^[f]y) -> ^[t]ok^[f](^[t]car^[f](^[t]x, ^[f]y)) ^[t]car^[t](^[f]x, ^[t]ok^[f](^[f]y)) -> ^[t]ok^[f](^[f]car^[f](^[f]x, ^[f]y)) ^[t]car^[t](^[f]x, ^[t]ok^[f](^[t]y)) -> ^[t]ok^[f](^[t]car^[t](^[f]x, ^[t]y)) ^[t]car^[t](^[t]x, ^[t]ok^[f](^[f]y)) -> ^[t]ok^[f](^[t]car^[f](^[t]x, ^[f]y)) ^[t]left^[f](^[t]ok^[f](^[f]x), ^[f]y) -> ^[t]ok^[f](^[f]left^[f](^[f]x, ^[f]y)) ^[t]left^[t](^[t]ok^[f](^[f]x), ^[t]y) -> ^[t]ok^[f](^[t]left^[t](^[f]x, ^[t]y)) ^[t]left^[f](^[t]ok^[f](^[t]x), ^[f]y) -> ^[t]ok^[f](^[t]left^[f](^[t]x, ^[f]y)) ^[t]left^[t](^[f]x, ^[t]ok^[f](^[f]y)) -> ^[t]ok^[f](^[f]left^[f](^[f]x, ^[f]y)) ^[t]left^[t](^[f]x, ^[t]ok^[f](^[t]y)) -> ^[t]ok^[f](^[t]left^[t](^[f]x, ^[t]y)) ^[t]left^[t](^[t]x, ^[t]ok^[f](^[f]y)) -> ^[t]ok^[f](^[t]left^[f](^[t]x, ^[f]y)) ^[t]right^[t](^[t]ok^[f](^[f]x), ^[f]y) -> ^[t]ok^[f](^[f]right^[f](^[f]x, ^[f]y)) ^[t]right^[t](^[t]ok^[f](^[f]x), ^[t]y) -> ^[t]ok^[f](^[t]right^[f](^[f]x, ^[t]y)) ^[t]right^[t](^[t]ok^[f](^[t]x), ^[f]y) -> ^[t]ok^[f](^[t]right^[t](^[t]x, ^[f]y)) ^[t]right^[f](^[f]x, ^[t]ok^[f](^[f]y)) -> ^[t]ok^[f](^[f]right^[f](^[f]x, ^[f]y)) ^[t]right^[f](^[f]x, ^[t]ok^[f](^[t]y)) -> ^[t]ok^[f](^[t]right^[f](^[f]x, ^[t]y)) ^[t]right^[t](^[t]x, ^[t]ok^[f](^[f]y)) -> ^[t]ok^[f](^[t]right^[t](^[t]x, ^[f]y)) ^[f]top^[t](^[t]ok^[f](^[f]left^[f](^[f]car^[f](^[f]x, ^[f]y), ^[f]z))) -> ^[f]top^[f](^[f]check^[f](^[f]right^[f](^[f]y, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[t](^[f]car^[f](^[f]x, ^[f]y), ^[t]z))) -> ^[f]top^[t](^[t]check^[f](^[t]right^[f](^[f]y, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[f](^[t]car^[t](^[f]x, ^[t]y), ^[f]z))) -> ^[f]top^[t](^[t]check^[f](^[t]right^[t](^[t]y, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[t](^[t]car^[t](^[f]x, ^[t]y), ^[t]z))) -> ^[f]top^[t](^[t]check^[f](^[t]right^[t](^[t]y, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[f](^[t]car^[f](^[t]x, ^[f]y), ^[f]z))) -> ^[f]top^[f](^[f]check^[f](^[f]right^[f](^[f]y, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]left^[t](^[t]car^[f](^[t]x, ^[f]y), ^[t]z))) -> ^[f]top^[t](^[t]check^[f](^[t]right^[f](^[f]y, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[f]right^[f](^[f]x, ^[f]car^[f](^[f]y, ^[f]z)))) -> ^[f]top^[f](^[f]check^[f](^[f]left^[f](^[f]x, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[f](^[f]x, ^[t]car^[t](^[f]y, ^[t]z)))) -> ^[f]top^[t](^[t]check^[f](^[t]left^[t](^[f]x, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[f](^[f]x, ^[t]car^[f](^[t]y, ^[f]z)))) -> ^[f]top^[f](^[f]check^[f](^[f]left^[f](^[f]x, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[t](^[t]x, ^[f]car^[f](^[f]y, ^[f]z)))) -> ^[f]top^[t](^[t]check^[f](^[t]left^[f](^[t]x, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[t](^[t]x, ^[t]car^[t](^[f]y, ^[t]z)))) -> ^[f]top^[t](^[t]check^[f](^[t]left^[t](^[t]x, ^[t]z))) ^[f]top^[t](^[t]ok^[f](^[t]right^[t](^[t]x, ^[t]car^[f](^[t]y, ^[f]z)))) -> ^[f]top^[t](^[t]check^[f](^[t]left^[f](^[t]x, ^[f]z))) ^[f]top^[t](^[t]ok^[f](^[f]left^[f](^[f]bot^[t], ^[f]x))) -> ^[f]top^[f](^[f]check^[f](^[f]right^[f](^[f]bot^[t], ^[f]x))) ^[f]top^[t](^[t]ok^[f](^[t]left^[t](^[f]bot^[t], ^[t]x))) -> ^[f]top^[t](^[t]check^[f](^[t]right^[f](^[f]bot^[t], ^[t]x))) ^[f]top^[t](^[t]ok^[f](^[f]right^[f](^[f]x, ^[f]bot^[t]))) -> ^[f]top^[f](^[f]check^[f](^[f]left^[f](^[f]x, ^[f]bot^[t]))) ^[f]top^[t](^[t]ok^[f](^[t]right^[t](^[t]x, ^[f]bot^[t]))) -> ^[f]top^[t](^[t]check^[f](^[t]left^[f](^[t]x, ^[f]bot^[t]))) Our polynomial interpretation was: P(top^[false])(x_1) = 0 + 1*x_1 P(top^[true])(x_1) = 1 + 1*x_1 P(ok^[false])(x_1) = 0 + 1*x_1 P(ok^[true])(x_1) = 0 + 1*x_1 P(left^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(left^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(car^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(car^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 P(check^[false])(x_1) = 0 + 1*x_1 P(check^[true])(x_1) = 0 + 1*x_1 P(right^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(right^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 P(bot^[false])() = 0 P(bot^[true])() = 0 P(new^[false])() = 0 P(new^[true])() = 0 P(old^[false])() = 0 P(old^[true])() = 1 The following rules were deleted from R: top(ok(right(x, car(y, z)))) -> top(check(left(x, z))) The following rules were deleted from S: none ---------------------------------------- (2) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: top(ok(left(car(x, y), z))) -> top(check(right(y, z))) top(ok(left(bot, x))) -> top(check(right(bot, x))) top(ok(right(x, bot))) -> top(check(left(x, bot))) The relative TRS consists of the following S rules: top(ok(left(car(x, y), z))) -> top(check(left(y, z))) top(ok(right(x, car(y, z)))) -> top(check(right(x, z))) bot -> car(new, bot) check(old) -> ok(old) check(car(x, y)) -> car(check(x), y) check(car(x, y)) -> car(x, check(y)) check(left(x, y)) -> left(check(x), y) check(left(x, y)) -> left(x, check(y)) check(right(x, y)) -> right(check(x), y) check(right(x, y)) -> right(x, check(y)) car(ok(x), y) -> ok(car(x, y)) car(x, ok(y)) -> ok(car(x, y)) left(ok(x), y) -> ok(left(x, y)) left(x, ok(y)) -> ok(left(x, y)) right(ok(x), y) -> ok(right(x, y)) right(x, ok(y)) -> ok(right(x, y)) ---------------------------------------- (3) RelTRSSemanticLabellingPOLOProof (EQUIVALENT) We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB] We use semantic labelling over boolean tuples of size 1. We used the following model: top_1: component 1: AND[] ok_1: component 1: OR[x_1^1] left_2: component 1: OR[] car_2: component 1: AND[x_1^1, x_2^1] check_1: component 1: OR[x_1^1] right_2: component 1: AND[x_1^1, x_2^1] bot_0: component 1: AND[] new_0: component 1: AND[] old_0: component 1: OR[] Our labelling function was: top_1:component 1: OR[] ok_1:component 1: OR[x_1^1] left_2:component 1: AND[-x_2^1] car_2:component 1: AND[x_1^1, x_2^1] check_1:component 1: OR[] right_2:component 1: AND[-x_1^1, x_2^1] bot_0:component 1: AND[] new_0:component 1: OR[] old_0:component 1: AND[] Our labelled system was: ^[t]top^[f](^[f]ok^[f](^[f]left^[t](^[f]car^[f](^[f]x, ^[f]y), ^[f]z))) -> ^[t]top^[f](^[f]check^[f](^[f]left^[t](^[f]y, ^[f]z))) ^[t]top^[f](^[f]ok^[f](^[f]left^[f](^[f]car^[f](^[f]x, ^[f]y), ^[t]z))) -> ^[t]top^[f](^[f]check^[f](^[f]left^[f](^[f]y, ^[t]z))) ^[t]top^[f](^[f]ok^[f](^[f]left^[t](^[t]car^[t](^[t]x, ^[t]y), ^[f]z))) -> ^[t]top^[f](^[f]check^[f](^[f]left^[t](^[t]y, ^[f]z))) ^[t]top^[f](^[f]ok^[f](^[f]left^[f](^[t]car^[t](^[t]x, ^[t]y), ^[t]z))) -> ^[t]top^[f](^[f]check^[f](^[f]left^[f](^[t]y, ^[t]z))) ^[t]top^[f](^[f]ok^[f](^[f]right^[f](^[f]x, ^[f]car^[f](^[f]y, ^[f]z)))) -> ^[t]top^[f](^[f]check^[f](^[f]right^[f](^[f]x, ^[f]z))) ^[t]top^[f](^[f]ok^[f](^[f]right^[f](^[f]x, ^[f]car^[f](^[f]y, ^[t]z)))) -> ^[t]top^[f](^[f]check^[f](^[f]right^[t](^[f]x, ^[t]z))) ^[t]top^[f](^[f]ok^[f](^[f]right^[t](^[f]x, ^[t]car^[t](^[t]y, ^[t]z)))) -> ^[t]top^[f](^[f]check^[f](^[f]right^[t](^[f]x, ^[t]z))) ^[t]top^[f](^[f]ok^[f](^[f]right^[f](^[t]x, ^[f]car^[f](^[f]y, ^[t]z)))) -> ^[t]top^[f](^[t]check^[f](^[t]right^[f](^[t]x, ^[t]z))) ^[t]top^[f](^[t]ok^[t](^[t]right^[f](^[t]x, ^[t]car^[t](^[t]y, ^[t]z)))) -> ^[t]top^[f](^[t]check^[f](^[t]right^[f](^[t]x, ^[t]z))) ^[t]bot^[t] -> ^[t]car^[t](^[t]new^[f], ^[t]bot^[t]) ^[f]check^[f](^[f]old^[t]) -> ^[f]ok^[f](^[f]old^[t]) ^[f]check^[f](^[f]car^[f](^[f]x, ^[f]y)) -> ^[f]car^[f](^[f]check^[f](^[f]x), ^[f]y) ^[f]check^[f](^[f]car^[f](^[t]x, ^[f]y)) -> ^[f]car^[f](^[t]check^[f](^[t]x), ^[f]y) ^[t]check^[f](^[t]car^[t](^[t]x, ^[t]y)) -> ^[t]car^[t](^[t]check^[f](^[t]x), ^[t]y) ^[f]check^[f](^[f]car^[f](^[f]x, ^[f]y)) -> ^[f]car^[f](^[f]x, ^[f]check^[f](^[f]y)) ^[f]check^[f](^[f]car^[f](^[f]x, ^[t]y)) -> ^[f]car^[f](^[f]x, ^[t]check^[f](^[t]y)) ^[t]check^[f](^[t]car^[t](^[t]x, ^[t]y)) -> ^[t]car^[t](^[t]x, ^[t]check^[f](^[t]y)) ^[f]check^[f](^[f]left^[t](^[f]x, ^[f]y)) -> ^[f]left^[t](^[f]check^[f](^[f]x), ^[f]y) ^[f]check^[f](^[f]left^[f](^[f]x, ^[t]y)) -> ^[f]left^[f](^[f]check^[f](^[f]x), ^[t]y) ^[f]check^[f](^[f]left^[t](^[t]x, ^[f]y)) -> ^[f]left^[t](^[t]check^[f](^[t]x), ^[f]y) ^[f]check^[f](^[f]left^[f](^[t]x, ^[t]y)) -> ^[f]left^[f](^[t]check^[f](^[t]x), ^[t]y) ^[f]check^[f](^[f]left^[t](^[f]x, ^[f]y)) -> ^[f]left^[t](^[f]x, ^[f]check^[f](^[f]y)) ^[f]check^[f](^[f]left^[f](^[f]x, ^[t]y)) -> ^[f]left^[f](^[f]x, ^[t]check^[f](^[t]y)) ^[f]check^[f](^[f]right^[f](^[f]x, ^[f]y)) -> ^[f]right^[f](^[f]check^[f](^[f]x), ^[f]y) ^[f]check^[f](^[f]right^[t](^[f]x, ^[t]y)) -> ^[f]right^[t](^[f]check^[f](^[f]x), ^[t]y) ^[f]check^[f](^[f]right^[f](^[t]x, ^[f]y)) -> ^[f]right^[f](^[t]check^[f](^[t]x), ^[f]y) ^[t]check^[f](^[t]right^[f](^[t]x, ^[t]y)) -> ^[t]right^[f](^[t]check^[f](^[t]x), ^[t]y) ^[f]check^[f](^[f]right^[f](^[f]x, ^[f]y)) -> ^[f]right^[f](^[f]x, ^[f]check^[f](^[f]y)) ^[f]check^[f](^[f]right^[t](^[f]x, ^[t]y)) -> ^[f]right^[t](^[f]x, ^[t]check^[f](^[t]y)) ^[t]check^[f](^[t]right^[f](^[t]x, ^[t]y)) -> ^[t]right^[f](^[t]x, ^[t]check^[f](^[t]y)) ^[f]car^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[f]ok^[f](^[f]car^[f](^[f]x, ^[f]y)) ^[f]car^[f](^[t]ok^[t](^[t]x), ^[f]y) -> ^[f]ok^[f](^[f]car^[f](^[t]x, ^[f]y)) ^[t]car^[t](^[t]ok^[t](^[t]x), ^[t]y) -> ^[t]ok^[t](^[t]car^[t](^[t]x, ^[t]y)) ^[f]car^[f](^[f]x, ^[f]ok^[f](^[f]y)) -> ^[f]ok^[f](^[f]car^[f](^[f]x, ^[f]y)) ^[f]car^[f](^[f]x, ^[t]ok^[t](^[t]y)) -> ^[f]ok^[f](^[f]car^[f](^[f]x, ^[t]y)) ^[t]car^[t](^[t]x, ^[t]ok^[t](^[t]y)) -> ^[t]ok^[t](^[t]car^[t](^[t]x, ^[t]y)) ^[f]left^[t](^[f]ok^[f](^[f]x), ^[f]y) -> ^[f]ok^[f](^[f]left^[t](^[f]x, ^[f]y)) ^[f]left^[f](^[f]ok^[f](^[f]x), ^[t]y) -> ^[f]ok^[f](^[f]left^[f](^[f]x, ^[t]y)) ^[f]left^[t](^[t]ok^[t](^[t]x), ^[f]y) -> ^[f]ok^[f](^[f]left^[t](^[t]x, ^[f]y)) ^[f]left^[f](^[t]ok^[t](^[t]x), ^[t]y) -> ^[f]ok^[f](^[f]left^[f](^[t]x, ^[t]y)) ^[f]left^[t](^[f]x, ^[f]ok^[f](^[f]y)) -> ^[f]ok^[f](^[f]left^[t](^[f]x, ^[f]y)) ^[f]left^[f](^[f]x, ^[t]ok^[t](^[t]y)) -> ^[f]ok^[f](^[f]left^[f](^[f]x, ^[t]y)) ^[f]right^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[f]ok^[f](^[f]right^[f](^[f]x, ^[f]y)) ^[f]right^[t](^[f]ok^[f](^[f]x), ^[t]y) -> ^[f]ok^[f](^[f]right^[t](^[f]x, ^[t]y)) ^[f]right^[f](^[t]ok^[t](^[t]x), ^[f]y) -> ^[f]ok^[f](^[f]right^[f](^[t]x, ^[f]y)) ^[t]right^[f](^[t]ok^[t](^[t]x), ^[t]y) -> ^[t]ok^[t](^[t]right^[f](^[t]x, ^[t]y)) ^[f]right^[f](^[f]x, ^[f]ok^[f](^[f]y)) -> ^[f]ok^[f](^[f]right^[f](^[f]x, ^[f]y)) ^[f]right^[t](^[f]x, ^[t]ok^[t](^[t]y)) -> ^[f]ok^[f](^[f]right^[t](^[f]x, ^[t]y)) ^[t]right^[f](^[t]x, ^[t]ok^[t](^[t]y)) -> ^[t]ok^[t](^[t]right^[f](^[t]x, ^[t]y)) ^[t]top^[f](^[f]ok^[f](^[f]left^[t](^[f]car^[f](^[f]x, ^[f]y), ^[f]z))) -> ^[t]top^[f](^[f]check^[f](^[f]right^[f](^[f]y, ^[f]z))) ^[t]top^[f](^[f]ok^[f](^[f]left^[f](^[f]car^[f](^[f]x, ^[f]y), ^[t]z))) -> ^[t]top^[f](^[f]check^[f](^[f]right^[t](^[f]y, ^[t]z))) ^[t]top^[f](^[f]ok^[f](^[f]left^[f](^[f]car^[f](^[f]x, ^[t]y), ^[t]z))) -> ^[t]top^[f](^[t]check^[f](^[t]right^[f](^[t]y, ^[t]z))) ^[t]top^[f](^[f]ok^[f](^[f]left^[t](^[t]car^[t](^[t]x, ^[t]y), ^[f]z))) -> ^[t]top^[f](^[f]check^[f](^[f]right^[f](^[t]y, ^[f]z))) ^[t]top^[f](^[f]ok^[f](^[f]left^[f](^[t]car^[t](^[t]x, ^[t]y), ^[t]z))) -> ^[t]top^[f](^[t]check^[f](^[t]right^[f](^[t]y, ^[t]z))) ^[t]top^[f](^[f]ok^[f](^[f]left^[t](^[t]bot^[t], ^[f]x))) -> ^[t]top^[f](^[f]check^[f](^[f]right^[f](^[t]bot^[t], ^[f]x))) ^[t]top^[f](^[f]ok^[f](^[f]left^[f](^[t]bot^[t], ^[t]x))) -> ^[t]top^[f](^[t]check^[f](^[t]right^[f](^[t]bot^[t], ^[t]x))) ^[t]top^[f](^[f]ok^[f](^[f]right^[t](^[f]x, ^[t]bot^[t]))) -> ^[t]top^[f](^[f]check^[f](^[f]left^[f](^[f]x, ^[t]bot^[t]))) ^[t]top^[f](^[t]ok^[t](^[t]right^[f](^[t]x, ^[t]bot^[t]))) -> ^[t]top^[f](^[f]check^[f](^[f]left^[f](^[t]x, ^[t]bot^[t]))) Our polynomial interpretation was: P(top^[false])(x_1) = 0 + 1*x_1 P(top^[true])(x_1) = 0 + 1*x_1 P(ok^[false])(x_1) = 0 + 1*x_1 P(ok^[true])(x_1) = 1 + 1*x_1 P(left^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(left^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(car^[false])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 P(car^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(check^[false])(x_1) = 0 + 1*x_1 P(check^[true])(x_1) = 0 + 1*x_1 P(right^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(right^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2 P(bot^[false])() = 0 P(bot^[true])() = 0 P(new^[false])() = 0 P(new^[true])() = 0 P(old^[false])() = 1 P(old^[true])() = 1 The following rules were deleted from R: top(ok(right(x, bot))) -> top(check(left(x, bot))) The following rules were deleted from S: none ---------------------------------------- (4) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: top(ok(left(car(x, y), z))) -> top(check(right(y, z))) top(ok(left(bot, x))) -> top(check(right(bot, x))) The relative TRS consists of the following S rules: top(ok(left(car(x, y), z))) -> top(check(left(y, z))) top(ok(right(x, car(y, z)))) -> top(check(right(x, z))) bot -> car(new, bot) check(old) -> ok(old) check(car(x, y)) -> car(check(x), y) check(car(x, y)) -> car(x, check(y)) check(left(x, y)) -> left(check(x), y) check(left(x, y)) -> left(x, check(y)) check(right(x, y)) -> right(check(x), y) check(right(x, y)) -> right(x, check(y)) car(ok(x), y) -> ok(car(x, y)) car(x, ok(y)) -> ok(car(x, y)) left(ok(x), y) -> ok(left(x, y)) left(x, ok(y)) -> ok(left(x, y)) right(ok(x), y) -> ok(right(x, y)) right(x, ok(y)) -> ok(right(x, y)) ---------------------------------------- (5) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(bot) = 0 POL(car(x_1, x_2)) = x_1 + x_2 POL(check(x_1)) = x_1 POL(left(x_1, x_2)) = 1 + x_1 + x_2 POL(new) = 0 POL(ok(x_1)) = x_1 POL(old) = 0 POL(right(x_1, x_2)) = x_1 + x_2 POL(top(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: top(ok(left(car(x, y), z))) -> top(check(right(y, z))) top(ok(left(bot, x))) -> top(check(right(bot, x))) Rules from S: none ---------------------------------------- (6) Obligation: Relative term rewrite system: R is empty. The relative TRS consists of the following S rules: top(ok(left(car(x, y), z))) -> top(check(left(y, z))) top(ok(right(x, car(y, z)))) -> top(check(right(x, z))) bot -> car(new, bot) check(old) -> ok(old) check(car(x, y)) -> car(check(x), y) check(car(x, y)) -> car(x, check(y)) check(left(x, y)) -> left(check(x), y) check(left(x, y)) -> left(x, check(y)) check(right(x, y)) -> right(check(x), y) check(right(x, y)) -> right(x, check(y)) car(ok(x), y) -> ok(car(x, y)) car(x, ok(y)) -> ok(car(x, y)) left(ok(x), y) -> ok(left(x, y)) left(x, ok(y)) -> ok(left(x, y)) right(ok(x), y) -> ok(right(x, y)) right(x, ok(y)) -> ok(right(x, y)) ---------------------------------------- (7) RIsEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (8) YES