Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381709902
details
property
value
status
complete
benchmark
secret3.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n003.star.cs.uiowa.edu
space
Secret_07_TRS
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.350670099258 seconds
cpu usage
0.347894757
max memory
1.5527936E7
stage attributes
key
value
output-size
17731
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. a : [o * o * o] --> o app : [o * o] --> o cons : [o * o] --> o h : [] --> o nil : [] --> o s : [o] --> o sum : [o] --> o app(nil, X) => X app(X, nil) => X app(cons(X, Y), Z) => cons(X, app(Y, Z)) sum(cons(X, nil)) => cons(X, nil) sum(cons(X, cons(Y, Z))) => sum(cons(a(X, Y, h), Z)) a(h, h, X) => s(X) a(X, s(Y), h) => a(X, Y, s(h)) a(X, s(Y), s(Z)) => a(X, Y, a(X, s(Y), Z)) a(s(X), h, Y) => a(X, Y, 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]): app(nil, X) >? X app(X, nil) >? X app(cons(X, Y), Z) >? cons(X, app(Y, Z)) sum(cons(X, nil)) >? cons(X, nil) sum(cons(X, cons(Y, Z))) >? sum(cons(a(X, Y, h), Z)) a(h, h, X) >? s(X) a(X, s(Y), h) >? a(X, Y, s(h)) a(X, s(Y), s(Z)) >? a(X, Y, a(X, s(Y), Z)) a(s(X), h, Y) >? a(X, Y, Y) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[cons(x_1, x_2)]] = cons(x_2, x_1) [[h]] = _|_ We choose Lex = {a, cons} and Mul = {app, nil, s, sum}, and the following precedence: nil > sum > app > cons > a > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: app(nil, X) >= X app(X, nil) > X app(cons(X, Y), Z) > cons(X, app(Y, Z)) sum(cons(X, nil)) >= cons(X, nil) sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_), Z)) a(_|_, _|_, X) >= s(X) a(X, s(Y), _|_) > a(X, Y, s(_|_)) a(X, s(Y), s(Z)) >= a(X, Y, a(X, s(Y), Z)) a(s(X), _|_, Y) >= a(X, Y, Y) With these choices, we have: 1] app(nil, X) >= X because [2], by (Star) 2] app*(nil, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] app(X, nil) > X because [5], by definition 5] app*(X, nil) >= X because [6], by (Select) 6] X >= X by (Meta) 7] app(cons(X, Y), Z) > cons(X, app(Y, Z)) because [8], by definition 8] app*(cons(X, Y), Z) >= cons(X, app(Y, Z)) because app > cons, [9] and [13], by (Copy) 9] app*(cons(X, Y), Z) >= X because [10], by (Select) 10] cons(X, Y) >= X because [11], by (Star) 11] cons*(X, Y) >= X because [12], by (Select) 12] X >= X by (Meta) 13] app*(cons(X, Y), Z) >= app(Y, Z) because app in Mul, [14] and [16], by (Stat) 14] cons(X, Y) > Y because [15], by definition 15] cons*(X, Y) >= Y because [6], by (Select) 16] Z >= Z by (Meta) 17] sum(cons(X, nil)) >= cons(X, nil) because [18], by (Star) 18] sum*(cons(X, nil)) >= cons(X, nil) because [19], by (Select) 19] cons(X, nil) >= cons(X, nil) because [20] and [21], by (Fun) 20] X >= X by (Meta) 21] nil >= nil by (Fun) 22] sum(cons(X, cons(Y, Z))) >= sum(cons(a(X, Y, _|_), Z)) because sum in Mul and [23], by (Fun) 23] cons(X, cons(Y, Z)) >= cons(a(X, Y, _|_), Z) because [24], by (Star) 24] cons*(X, cons(Y, Z)) >= cons(a(X, Y, _|_), Z) because [25], [27] and [34], by (Stat) 25] cons(Y, Z) > Z because [26], by definition 26] cons*(Y, Z) >= Z because [6], by (Select) 27] cons*(X, cons(Y, Z)) >= a(X, Y, _|_) because cons > a, [28], [29] and [33], by (Copy) 28] cons*(X, cons(Y, Z)) >= X because [20], by (Select)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472