/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given RelTRS could be proven: (0) RelTRS (1) RelTRSRRRProof [EQUIVALENT, 59 ms] (2) RelTRS (3) RelTRSRRRProof [EQUIVALENT, 51 ms] (4) RelTRS (5) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 152 ms] (6) RelTRS (7) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 79 ms] (8) RelTRS (9) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 80 ms] (10) RelTRS (11) RIsEmptyProof [EQUIVALENT, 0 ms] (12) YES ---------------------------------------- (0) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: top(ok(queue(old(x), bot))) -> top(check(queue(x, bot))) top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) top(ok(queue(bot, old(x)))) -> top(check(queue(bot, x))) top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) top(ok(queue(old(x), old(y)))) -> top(check(queue(x, y))) top(ok(queue(old(x), new(y)))) -> top(check(queue(x, y))) top(ok(queue(new(x), old(y)))) -> top(check(queue(x, y))) top(ok(queue(new(x), new(y)))) -> top(check(queue(x, y))) The relative TRS consists of the following S rules: top(ok(queue(old(x), y))) -> top(check(queue(x, y))) top(ok(queue(new(x), y))) -> top(check(queue(x, y))) bot -> new(bot) check(old(x)) -> ok(old(x)) check(new(x)) -> new(check(x)) check(queue(x, y)) -> queue(check(x), y) check(queue(x, y)) -> queue(x, check(y)) old(ok(x)) -> ok(old(x)) new(ok(x)) -> ok(new(x)) queue(ok(x), y) -> ok(queue(x, y)) queue(x, ok(y)) -> ok(queue(x, y)) ---------------------------------------- (1) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(bot) = 0 POL(check(x_1)) = x_1 POL(new(x_1)) = x_1 POL(ok(x_1)) = x_1 POL(old(x_1)) = 1 + x_1 POL(queue(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(queue(old(x), bot))) -> top(check(queue(x, bot))) top(ok(queue(bot, old(x)))) -> top(check(queue(bot, x))) top(ok(queue(old(x), old(y)))) -> top(check(queue(x, y))) top(ok(queue(old(x), new(y)))) -> top(check(queue(x, y))) top(ok(queue(new(x), old(y)))) -> top(check(queue(x, y))) Rules from S: top(ok(queue(old(x), y))) -> top(check(queue(x, y))) ---------------------------------------- (2) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) top(ok(queue(new(x), new(y)))) -> top(check(queue(x, y))) The relative TRS consists of the following S rules: top(ok(queue(new(x), y))) -> top(check(queue(x, y))) bot -> new(bot) check(old(x)) -> ok(old(x)) check(new(x)) -> new(check(x)) check(queue(x, y)) -> queue(check(x), y) check(queue(x, y)) -> queue(x, check(y)) old(ok(x)) -> ok(old(x)) new(ok(x)) -> ok(new(x)) queue(ok(x), y) -> ok(queue(x, y)) queue(x, ok(y)) -> ok(queue(x, y)) ---------------------------------------- (3) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(top(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(ok(x_1)) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 >>> <<< POL(queue(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 >>> <<< POL(new(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 >>> <<< POL(bot) = [[0], [0]] >>> <<< POL(check(x_1)) = [[0], [0]] + [[1, 0], [1, 1]] * x_1 >>> <<< POL(old(x_1)) = [[1], [1]] + [[1, 1], [0, 1]] * x_1 >>> With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: old(ok(x)) -> ok(old(x)) ---------------------------------------- (4) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) top(ok(queue(new(x), new(y)))) -> top(check(queue(x, y))) The relative TRS consists of the following S rules: top(ok(queue(new(x), y))) -> top(check(queue(x, y))) bot -> new(bot) check(old(x)) -> ok(old(x)) check(new(x)) -> new(check(x)) check(queue(x, y)) -> queue(check(x), y) check(queue(x, y)) -> queue(x, check(y)) new(ok(x)) -> ok(new(x)) queue(ok(x), y) -> ok(queue(x, y)) queue(x, ok(y)) -> ok(queue(x, y)) ---------------------------------------- (5) 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[] queue_2: component 1: OR[x_1^1, x_2^1] new_1: component 1: OR[x_1^1] check_1: component 1: OR[x_1^1] bot_0: component 1: OR[] old_1: component 1: AND[] Our labelling function was: top_1:component 1: XOR[x_1^1] ok_1:component 1: OR[] queue_2:component 1: XOR[] new_1:component 1: XOR[-x_1^1] check_1:component 1: OR[x_1^1] bot_0:component 1: AND[] old_1:component 1: XOR[] Our labelled system was: ^[f]top^[t](^[t]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]y))) -> ^[f]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y))) ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[f]new^[t](^[f]x), ^[t]y))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[f]x, ^[t]y))) ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[f]y))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]y))) ^[f]bot^[t] -> ^[f]new^[t](^[f]bot^[t]) ^[t]check^[t](^[t]old^[f](^[f]x)) -> ^[t]ok^[f](^[t]old^[f](^[f]x)) ^[f]check^[f](^[f]new^[t](^[f]x)) -> ^[f]new^[t](^[f]check^[f](^[f]x)) ^[t]check^[t](^[t]new^[f](^[t]x)) -> ^[t]new^[f](^[t]check^[t](^[t]x)) ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]check^[f](^[f]x), ^[f]y) ^[t]check^[t](^[t]queue^[f](^[f]x, ^[t]y)) -> ^[t]queue^[f](^[f]check^[f](^[f]x), ^[t]y) ^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]y)) -> ^[t]queue^[f](^[t]check^[t](^[t]x), ^[f]y) ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]x, ^[f]check^[f](^[f]y)) ^[t]check^[t](^[t]queue^[f](^[f]x, ^[t]y)) -> ^[t]queue^[f](^[f]x, ^[t]check^[t](^[t]y)) ^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]y)) -> ^[t]queue^[f](^[t]x, ^[f]check^[f](^[f]y)) ^[t]new^[f](^[t]ok^[f](^[f]x)) -> ^[t]ok^[f](^[f]new^[t](^[f]x)) ^[t]new^[f](^[t]ok^[f](^[t]x)) -> ^[t]ok^[f](^[t]new^[f](^[t]x)) ^[t]queue^[f](^[t]ok^[f](^[f]x), ^[f]y) -> ^[t]ok^[f](^[f]queue^[f](^[f]x, ^[f]y)) ^[t]queue^[f](^[t]ok^[f](^[f]x), ^[t]y) -> ^[t]ok^[f](^[t]queue^[f](^[f]x, ^[t]y)) ^[t]queue^[f](^[f]x, ^[t]ok^[f](^[f]y)) -> ^[t]ok^[f](^[f]queue^[f](^[f]x, ^[f]y)) ^[t]queue^[f](^[f]x, ^[t]ok^[f](^[t]y)) -> ^[t]ok^[f](^[t]queue^[f](^[f]x, ^[t]y)) ^[f]top^[t](^[t]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]bot^[t]))) -> ^[f]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]bot^[t]))) ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[f]bot^[t]))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]bot^[t]))) ^[f]top^[t](^[t]ok^[f](^[f]queue^[f](^[f]bot^[t], ^[f]new^[t](^[f]x)))) -> ^[f]top^[f](^[f]check^[f](^[f]queue^[f](^[f]bot^[t], ^[f]x))) ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[f]bot^[t], ^[t]new^[f](^[t]x)))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[f]bot^[t], ^[t]x))) ^[f]top^[t](^[t]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]new^[t](^[f]y)))) -> ^[f]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y))) ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[f]new^[t](^[f]x), ^[t]new^[f](^[t]y)))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[f]x, ^[t]y))) ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[f]new^[t](^[f]y)))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]y))) ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[t]new^[f](^[t]y)))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[t]x, ^[t]y))) 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(queue^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(queue^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(new^[false])(x_1) = 1 + 1*x_1 P(new^[true])(x_1) = 0 + 1*x_1 P(check^[false])(x_1) = 0 + 1*x_1 P(check^[true])(x_1) = 0 + 1*x_1 P(bot^[false])() = 0 P(bot^[true])() = 1 P(old^[false])(x_1) = 0 + 1*x_1 P(old^[true])(x_1) = 0 + 1*x_1 The following rules were deleted from R: top(ok(queue(new(x), new(y)))) -> top(check(queue(x, y))) The following rules were deleted from S: none ---------------------------------------- (6) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) The relative TRS consists of the following S rules: top(ok(queue(new(x), y))) -> top(check(queue(x, y))) bot -> new(bot) check(old(x)) -> ok(old(x)) check(new(x)) -> new(check(x)) check(queue(x, y)) -> queue(check(x), y) check(queue(x, y)) -> queue(x, check(y)) new(ok(x)) -> ok(new(x)) queue(ok(x), y) -> ok(queue(x, y)) queue(x, ok(y)) -> ok(queue(x, y)) ---------------------------------------- (7) 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[] queue_2: component 1: AND[x_1^1, x_2^1] new_1: component 1: OR[x_1^1] check_1: component 1: OR[x_1^1] bot_0: component 1: AND[] old_1: component 1: OR[] Our labelling function was: top_1:component 1: XOR[-x_1^1] ok_1:component 1: OR[x_1^1] queue_2:component 1: AND[x_1^1, x_2^1] new_1:component 1: OR[-x_1^1] check_1:component 1: OR[x_1^1] bot_0:component 1: OR[] old_1:component 1: OR[] Our labelled system was: ^[t]top^[t](^[f]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]y))) -> ^[t]top^[t](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y))) ^[t]top^[t](^[f]ok^[f](^[f]queue^[f](^[t]new^[f](^[t]x), ^[f]y))) -> ^[t]top^[t](^[f]check^[f](^[f]queue^[f](^[t]x, ^[f]y))) ^[t]top^[t](^[f]ok^[t](^[t]queue^[t](^[t]new^[f](^[t]x), ^[t]y))) -> ^[t]top^[f](^[t]check^[t](^[t]queue^[t](^[t]x, ^[t]y))) ^[t]bot^[f] -> ^[t]new^[f](^[t]bot^[f]) ^[f]check^[f](^[f]old^[f](^[f]x)) -> ^[f]ok^[f](^[f]old^[f](^[f]x)) ^[f]check^[f](^[f]new^[t](^[f]x)) -> ^[f]new^[t](^[f]check^[f](^[f]x)) ^[t]check^[t](^[t]new^[f](^[t]x)) -> ^[t]new^[f](^[t]check^[t](^[t]x)) ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]check^[f](^[f]x), ^[f]y) ^[f]check^[f](^[f]queue^[f](^[t]x, ^[f]y)) -> ^[f]queue^[f](^[t]check^[t](^[t]x), ^[f]y) ^[t]check^[t](^[t]queue^[t](^[t]x, ^[t]y)) -> ^[t]queue^[t](^[t]check^[t](^[t]x), ^[t]y) ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]x, ^[f]check^[f](^[f]y)) ^[f]check^[f](^[f]queue^[f](^[f]x, ^[t]y)) -> ^[f]queue^[f](^[f]x, ^[t]check^[t](^[t]y)) ^[t]check^[t](^[t]queue^[t](^[t]x, ^[t]y)) -> ^[t]queue^[t](^[t]x, ^[t]check^[t](^[t]y)) ^[f]new^[t](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]new^[t](^[f]x)) ^[f]new^[t](^[f]ok^[t](^[t]x)) -> ^[f]ok^[t](^[t]new^[f](^[t]x)) ^[f]queue^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[f]ok^[f](^[f]queue^[f](^[f]x, ^[f]y)) ^[f]queue^[f](^[f]ok^[t](^[t]x), ^[f]y) -> ^[f]ok^[f](^[f]queue^[f](^[t]x, ^[f]y)) ^[f]queue^[f](^[f]ok^[t](^[t]x), ^[t]y) -> ^[f]ok^[t](^[t]queue^[t](^[t]x, ^[t]y)) ^[f]queue^[f](^[f]x, ^[f]ok^[f](^[f]y)) -> ^[f]ok^[f](^[f]queue^[f](^[f]x, ^[f]y)) ^[f]queue^[f](^[f]x, ^[f]ok^[t](^[t]y)) -> ^[f]ok^[f](^[f]queue^[f](^[f]x, ^[t]y)) ^[f]queue^[f](^[t]x, ^[f]ok^[t](^[t]y)) -> ^[f]ok^[t](^[t]queue^[t](^[t]x, ^[t]y)) ^[t]top^[t](^[f]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[t]bot^[f]))) -> ^[t]top^[t](^[f]check^[f](^[f]queue^[f](^[f]x, ^[t]bot^[f]))) ^[t]top^[t](^[f]ok^[t](^[t]queue^[t](^[t]new^[f](^[t]x), ^[t]bot^[f]))) -> ^[t]top^[f](^[t]check^[t](^[t]queue^[t](^[t]x, ^[t]bot^[f]))) ^[t]top^[t](^[f]ok^[f](^[f]queue^[f](^[t]bot^[f], ^[f]new^[t](^[f]x)))) -> ^[t]top^[t](^[f]check^[f](^[f]queue^[f](^[t]bot^[f], ^[f]x))) ^[t]top^[t](^[f]ok^[t](^[t]queue^[t](^[t]bot^[f], ^[t]new^[f](^[t]x)))) -> ^[t]top^[f](^[t]check^[t](^[t]queue^[t](^[t]bot^[f], ^[t]x))) 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(queue^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(queue^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(new^[false])(x_1) = 0 + 1*x_1 P(new^[true])(x_1) = 1 + 1*x_1 P(check^[false])(x_1) = 0 + 1*x_1 P(check^[true])(x_1) = 0 + 1*x_1 P(bot^[false])() = 0 P(bot^[true])() = 0 P(old^[false])(x_1) = 0 + 1*x_1 P(old^[true])(x_1) = 0 + 1*x_1 The following rules were deleted from R: top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) The following rules were deleted from S: none ---------------------------------------- (8) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) The relative TRS consists of the following S rules: top(ok(queue(new(x), y))) -> top(check(queue(x, y))) bot -> new(bot) check(old(x)) -> ok(old(x)) check(new(x)) -> new(check(x)) check(queue(x, y)) -> queue(check(x), y) check(queue(x, y)) -> queue(x, check(y)) new(ok(x)) -> ok(new(x)) queue(ok(x), y) -> ok(queue(x, y)) queue(x, ok(y)) -> ok(queue(x, y)) ---------------------------------------- (9) 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[] queue_2: component 1: AND[x_1^1, x_2^1] new_1: component 1: OR[x_1^1] check_1: component 1: OR[x_1^1] bot_0: component 1: AND[] old_1: component 1: OR[] Our labelling function was: top_1:component 1: XOR[x_1^1] ok_1:component 1: OR[-x_1^1] queue_2:component 1: OR[] new_1:component 1: OR[-x_1^1] check_1:component 1: OR[] bot_0:component 1: AND[] old_1:component 1: OR[x_1^1] Our labelled system was: ^[t]top^[f](^[f]ok^[t](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]y))) -> ^[t]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y))) ^[t]top^[f](^[f]ok^[t](^[f]queue^[f](^[t]new^[f](^[t]x), ^[f]y))) -> ^[t]top^[f](^[f]check^[f](^[f]queue^[f](^[t]x, ^[f]y))) ^[t]top^[f](^[f]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[t]y))) -> ^[t]top^[t](^[t]check^[f](^[t]queue^[f](^[t]x, ^[t]y))) ^[t]bot^[t] -> ^[t]new^[f](^[t]bot^[t]) ^[f]check^[f](^[f]old^[f](^[f]x)) -> ^[f]ok^[t](^[f]old^[f](^[f]x)) ^[f]check^[f](^[f]old^[t](^[t]x)) -> ^[f]ok^[t](^[f]old^[t](^[t]x)) ^[f]check^[f](^[f]new^[t](^[f]x)) -> ^[f]new^[t](^[f]check^[f](^[f]x)) ^[t]check^[f](^[t]new^[f](^[t]x)) -> ^[t]new^[f](^[t]check^[f](^[t]x)) ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]check^[f](^[f]x), ^[f]y) ^[f]check^[f](^[f]queue^[f](^[t]x, ^[f]y)) -> ^[f]queue^[f](^[t]check^[f](^[t]x), ^[f]y) ^[t]check^[f](^[t]queue^[f](^[t]x, ^[t]y)) -> ^[t]queue^[f](^[t]check^[f](^[t]x), ^[t]y) ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]x, ^[f]check^[f](^[f]y)) ^[f]check^[f](^[f]queue^[f](^[f]x, ^[t]y)) -> ^[f]queue^[f](^[f]x, ^[t]check^[f](^[t]y)) ^[t]check^[f](^[t]queue^[f](^[t]x, ^[t]y)) -> ^[t]queue^[f](^[t]x, ^[t]check^[f](^[t]y)) ^[f]new^[t](^[f]ok^[t](^[f]x)) -> ^[f]ok^[t](^[f]new^[t](^[f]x)) ^[f]new^[t](^[f]ok^[f](^[t]x)) -> ^[f]ok^[f](^[t]new^[f](^[t]x)) ^[f]queue^[f](^[f]ok^[t](^[f]x), ^[f]y) -> ^[f]ok^[t](^[f]queue^[f](^[f]x, ^[f]y)) ^[f]queue^[f](^[f]ok^[f](^[t]x), ^[f]y) -> ^[f]ok^[t](^[f]queue^[f](^[t]x, ^[f]y)) ^[f]queue^[f](^[f]ok^[f](^[t]x), ^[t]y) -> ^[f]ok^[f](^[t]queue^[f](^[t]x, ^[t]y)) ^[f]queue^[f](^[f]x, ^[f]ok^[t](^[f]y)) -> ^[f]ok^[t](^[f]queue^[f](^[f]x, ^[f]y)) ^[f]queue^[f](^[f]x, ^[f]ok^[f](^[t]y)) -> ^[f]ok^[t](^[f]queue^[f](^[f]x, ^[t]y)) ^[f]queue^[f](^[t]x, ^[f]ok^[f](^[t]y)) -> ^[f]ok^[f](^[t]queue^[f](^[t]x, ^[t]y)) ^[t]top^[f](^[f]ok^[t](^[f]queue^[f](^[f]new^[t](^[f]x), ^[t]bot^[t]))) -> ^[t]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[t]bot^[t]))) ^[t]top^[f](^[f]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[t]bot^[t]))) -> ^[t]top^[t](^[t]check^[f](^[t]queue^[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) = 1 + 1*x_1 P(ok^[true])(x_1) = 0 + 1*x_1 P(queue^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(queue^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 P(new^[false])(x_1) = 0 + 1*x_1 P(new^[true])(x_1) = 1 + 1*x_1 P(check^[false])(x_1) = 0 + 1*x_1 P(check^[true])(x_1) = 0 + 1*x_1 P(bot^[false])() = 0 P(bot^[true])() = 0 P(old^[false])(x_1) = 1 + 1*x_1 P(old^[true])(x_1) = 1 + 1*x_1 The following rules were deleted from R: top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) The following rules were deleted from S: none ---------------------------------------- (10) Obligation: Relative term rewrite system: R is empty. The relative TRS consists of the following S rules: top(ok(queue(new(x), y))) -> top(check(queue(x, y))) bot -> new(bot) check(old(x)) -> ok(old(x)) check(new(x)) -> new(check(x)) check(queue(x, y)) -> queue(check(x), y) check(queue(x, y)) -> queue(x, check(y)) new(ok(x)) -> ok(new(x)) queue(ok(x), y) -> ok(queue(x, y)) queue(x, ok(y)) -> ok(queue(x, y)) ---------------------------------------- (11) RIsEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (12) YES