Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381712839
details
property
value
status
complete
benchmark
list-sum-prod-assoc.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n073.star.cs.uiowa.edu
space
CiME_04
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.201261997223 seconds
cpu usage
0.198588769
max memory
8495104.0
stage attributes
key
value
output-size
11740
starexec-result
YES
output
/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. !plus : [o * o] --> o !times : [o * o] --> o 0 : [] --> o cons : [o * o] --> o nil : [] --> o prod : [o] --> o s : [o] --> o sum : [o] --> o !plus(X, 0) => X !plus(0, X) => X !plus(s(X), s(Y)) => s(s(!plus(X, Y))) !plus(!plus(X, Y), Z) => !plus(X, !plus(Y, Z)) !times(X, 0) => 0 !times(0, X) => 0 !times(s(X), s(Y)) => s(!plus(!times(X, Y), !plus(X, Y))) !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) sum(nil) => 0 sum(cons(X, Y)) => !plus(X, sum(Y)) prod(nil) => s(0) prod(cons(X, Y)) => !times(X, prod(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]): !plus(X, 0) >? X !plus(0, X) >? X !plus(s(X), s(Y)) >? s(s(!plus(X, Y))) !plus(!plus(X, Y), Z) >? !plus(X, !plus(Y, Z)) !times(X, 0) >? 0 !times(0, X) >? 0 !times(s(X), s(Y)) >? s(!plus(!times(X, Y), !plus(X, Y))) !times(!times(X, Y), Z) >? !times(X, !times(Y, Z)) sum(nil) >? 0 sum(cons(X, Y)) >? !plus(X, sum(Y)) prod(nil) >? s(0) prod(cons(X, Y)) >? !times(X, prod(Y)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ We choose Lex = {!plus, !times} and Mul = {cons, nil, prod, s, sum}, and the following precedence: cons > nil > prod > !times > !plus > s > sum Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: !plus(X, _|_) >= X !plus(_|_, X) > X !plus(s(X), s(Y)) > s(s(!plus(X, Y))) !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) !times(X, _|_) >= _|_ !times(_|_, X) >= _|_ !times(s(X), s(Y)) >= s(!plus(!times(X, Y), !plus(X, Y))) !times(!times(X, Y), Z) > !times(X, !times(Y, Z)) sum(nil) >= _|_ sum(cons(X, Y)) > !plus(X, sum(Y)) prod(nil) > s(_|_) prod(cons(X, Y)) >= !times(X, prod(Y)) With these choices, we have: 1] !plus(X, _|_) >= X because [2], by (Star) 2] !plus*(X, _|_) >= X because [3], by (Select) 3] X >= X by (Meta) 4] !plus(_|_, X) > X because [5], by definition 5] !plus*(_|_, X) >= X because [3], by (Select) 6] !plus(s(X), s(Y)) > s(s(!plus(X, Y))) because [7], by definition 7] !plus*(s(X), s(Y)) >= s(s(!plus(X, Y))) because !plus > s and [8], by (Copy) 8] !plus*(s(X), s(Y)) >= s(!plus(X, Y)) because !plus > s and [9], by (Copy) 9] !plus*(s(X), s(Y)) >= !plus(X, Y) because [10], [12] and [14], by (Stat) 10] s(X) > X because [11], by definition 11] s*(X) >= X because [3], by (Select) 12] !plus*(s(X), s(Y)) >= X because [13], by (Select) 13] s(X) >= X because [11], by (Star) 14] !plus*(s(X), s(Y)) >= Y because [15], by (Select) 15] s(Y) >= Y because [16], by (Star) 16] s*(Y) >= Y because [17], by (Select) 17] Y >= Y by (Meta) 18] !plus(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [19], by (Star) 19] !plus*(!plus(X, Y), Z) >= !plus(X, !plus(Y, Z)) because [20], [22] and [24], by (Stat) 20] !plus(X, Y) > X because [21], by definition
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472