Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381716020
details
property
value
status
complete
benchmark
MYNAT_nosorts_GM.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n006.star.cs.uiowa.edu
space
Transformed_CSR_04
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.220923900604 seconds
cpu usage
0.217514858
max memory
6791168.0
stage attributes
key
value
output-size
13227
starexec-result
YES
output
/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o a!6220!6220and : [o * o] --> o a!6220!6220plus : [o * o] --> o a!6220!6220x : [o * o] --> o and : [o * o] --> o mark : [o] --> o plus : [o * o] --> o s : [o] --> o tt : [] --> o x : [o * o] --> o a!6220!6220and(tt, X) => mark(X) a!6220!6220plus(X, 0) => mark(X) a!6220!6220plus(X, s(Y)) => s(a!6220!6220plus(mark(X), mark(Y))) a!6220!6220x(X, 0) => 0 a!6220!6220x(X, s(Y)) => a!6220!6220plus(a!6220!6220x(mark(X), mark(Y)), mark(X)) mark(and(X, Y)) => a!6220!6220and(mark(X), Y) mark(plus(X, Y)) => a!6220!6220plus(mark(X), mark(Y)) mark(x(X, Y)) => a!6220!6220x(mark(X), mark(Y)) mark(tt) => tt mark(0) => 0 mark(s(X)) => s(mark(X)) a!6220!6220and(X, Y) => and(X, Y) a!6220!6220plus(X, Y) => plus(X, Y) a!6220!6220x(X, Y) => x(X, Y) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): a!6220!6220and(tt, X) >? mark(X) a!6220!6220plus(X, 0) >? mark(X) a!6220!6220plus(X, s(Y)) >? s(a!6220!6220plus(mark(X), mark(Y))) a!6220!6220x(X, 0) >? 0 a!6220!6220x(X, s(Y)) >? a!6220!6220plus(a!6220!6220x(mark(X), mark(Y)), mark(X)) mark(and(X, Y)) >? a!6220!6220and(mark(X), Y) mark(plus(X, Y)) >? a!6220!6220plus(mark(X), mark(Y)) mark(x(X, Y)) >? a!6220!6220x(mark(X), mark(Y)) mark(tt) >? tt mark(0) >? 0 mark(s(X)) >? s(mark(X)) a!6220!6220and(X, Y) >? and(X, Y) a!6220!6220plus(X, Y) >? plus(X, Y) a!6220!6220x(X, Y) >? x(X, Y) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[a!6220!6220plus(x_1, x_2)]] = a!6220!6220plus(x_2, x_1) [[mark(x_1)]] = x_1 [[plus(x_1, x_2)]] = plus(x_2, x_1) [[tt]] = _|_ We choose Lex = {a!6220!6220plus, plus} and Mul = {a!6220!6220and, a!6220!6220x, and, s, x}, and the following precedence: a!6220!6220and = and > a!6220!6220x = x > a!6220!6220plus = plus > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: a!6220!6220and(_|_, X) >= X a!6220!6220plus(X, _|_) > X a!6220!6220plus(X, s(Y)) >= s(a!6220!6220plus(X, Y)) a!6220!6220x(X, _|_) >= _|_ a!6220!6220x(X, s(Y)) > a!6220!6220plus(a!6220!6220x(X, Y), X) and(X, Y) >= a!6220!6220and(X, Y) plus(X, Y) >= a!6220!6220plus(X, Y) x(X, Y) >= a!6220!6220x(X, Y) _|_ >= _|_ _|_ >= _|_ s(X) >= s(X) a!6220!6220and(X, Y) >= and(X, Y) a!6220!6220plus(X, Y) >= plus(X, Y) a!6220!6220x(X, Y) >= x(X, Y) With these choices, we have: 1] a!6220!6220and(_|_, X) >= X because [2], by (Star) 2] a!6220!6220and*(_|_, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] a!6220!6220plus(X, _|_) > X because [5], by definition 5] a!6220!6220plus*(X, _|_) >= X because [6], by (Select) 6] X >= X by (Meta) 7] a!6220!6220plus(X, s(Y)) >= s(a!6220!6220plus(X, Y)) because [8], by (Star) 8] a!6220!6220plus*(X, s(Y)) >= s(a!6220!6220plus(X, Y)) because a!6220!6220plus > s and [9], by (Copy) 9] a!6220!6220plus*(X, s(Y)) >= a!6220!6220plus(X, Y) because [10], [13] and [14], by (Stat)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472