TRS Relative pair #487520742

details

property	value
status	complete
benchmark	rtL-cbn1.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n022.star.cs.uiowa.edu
space	Relative_05

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	5.07451510429 seconds
cpu usage	16.211891489
max memory	2.413273088E9

stage attributes

key	value
output-size	29495
starexec-result	YES

output

/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination of the given RelTRS could be proven:

(0) RelTRS
(1) RelTRSRRRProof [EQUIVALENT, 96 ms]
(2) RelTRS
(3) RelTRSRRRProof [EQUIVALENT, 52 ms]
(4) RelTRS
(5) RelTRSRRRProof [EQUIVALENT, 30 ms]
(6) RelTRS
(7) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 251 ms]
(8) RelTRS
(9) RelTRSRRRProof [EQUIVALENT, 0 ms]
(10) RelTRS
(11) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 131 ms]
(12) RelTRS
(13) RelTRSRRRProof [EQUIVALENT, 13 ms]
(14) RelTRS
(15) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 67 ms]
(16) RelTRS
(17) RelTRSRRRProof [EQUIVALENT, 0 ms]
(18) RelTRS
(19) RIsEmptyProof [EQUIVALENT, 0 ms]
(20) YES


----------------------------------------

(0)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tl(O(x), y) -> Wr(check(x), y)
   Tl(O(x), y) -> Wr(x, check(y))
   Tl(N(x), y) -> Wr(check(x), y)
   Tl(N(x), y) -> Wr(x, check(y))
   Tr(x, O(y)) -> Wl(check(x), y)
   Tr(x, O(y)) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wl(check(x), y)
   Tr(x, N(y)) -> Wl(x, check(y))
   Tl(B, y) -> Wr(check(B), y)
   Tl(B, y) -> Wr(B, check(y))
   Tr(x, B) -> Wl(check(x), B)
   Tr(x, B) -> Wl(x, check(B))

The relative TRS consists of the following S rules:

   Tl(O(x), y) -> Wl(check(x), y)
   Tl(O(x), y) -> Wl(x, check(y))
   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, O(y)) -> Wr(check(x), y)
   Tr(x, O(y)) -> Wr(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   Tr(x, N(y)) -> Wr(x, check(y))
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   Wr(x, ok(y)) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(1) RelTRSRRRProof (EQUIVALENT)
We used the following monotonic ordering for rule removal:
Polynomial interpretation [POLO]:

   POL(B) = 0
   POL(N(x_1)) = x_1
   POL(O(x_1)) = 1 + x_1
   POL(Tl(x_1, x_2)) = x_1 + x_2
   POL(Tr(x_1, x_2)) = x_1 + x_2
   POL(Wl(x_1, x_2)) = x_1 + x_2
   POL(Wr(x_1, x_2)) = x_1 + x_2
   POL(check(x_1)) = x_1
   POL(ok(x_1)) = x_1
With this ordering the following rules can be removed [MATRO] because they are oriented strictly:
Rules from R:

   Tl(O(x), y) -> Wr(check(x), y)
   Tl(O(x), y) -> Wr(x, check(y))
   Tr(x, O(y)) -> Wl(check(x), y)
   Tr(x, O(y)) -> Wl(x, check(y))

popout

output may be truncated. 'popout' for the full output.

job log

popout

actions all output return to TRS Relative