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