Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381716610
details
property
value
status
complete
benchmark
Ex8_BLR02_Z.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n049.star.cs.uiowa.edu
space
Transformed_CSR_04
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.112251996994 seconds
cpu usage
0.108705201
max memory
4669440.0
stage attributes
key
value
output-size
7934
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 activate : [o] --> o add : [o * o] --> o cons : [o * o] --> o fib : [o] --> o fib1 : [o * o] --> o n!6220!6220fib1 : [o * o] --> o s : [o] --> o sel : [o * o] --> o fib(X) => sel(X, fib1(s(0), s(0))) fib1(X, Y) => cons(X, n!6220!6220fib1(Y, add(X, Y))) add(0, X) => X add(s(X), Y) => s(add(X, Y)) sel(0, cons(X, Y)) => X sel(s(X), cons(Y, Z)) => sel(X, activate(Z)) fib1(X, Y) => n!6220!6220fib1(X, Y) activate(n!6220!6220fib1(X, Y)) => fib1(X, Y) activate(X) => X We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): fib(X) >? sel(X, fib1(s(0), s(0))) fib1(X, Y) >? cons(X, n!6220!6220fib1(Y, add(X, Y))) add(0, X) >? X add(s(X), Y) >? s(add(X, Y)) sel(0, cons(X, Y)) >? X sel(s(X), cons(Y, Z)) >? sel(X, activate(Z)) fib1(X, Y) >? n!6220!6220fib1(X, Y) activate(n!6220!6220fib1(X, Y)) >? fib1(X, Y) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ We choose Lex = {sel} and Mul = {activate, add, cons, fib, fib1, n!6220!6220fib1, s}, and the following precedence: fib > sel > activate > fib1 > add > cons > n!6220!6220fib1 > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: fib(X) >= sel(X, fib1(s(_|_), s(_|_))) fib1(X, Y) >= cons(X, n!6220!6220fib1(Y, add(X, Y))) add(_|_, X) > X add(s(X), Y) >= s(add(X, Y)) sel(_|_, cons(X, Y)) >= X sel(s(X), cons(Y, Z)) > sel(X, activate(Z)) fib1(X, Y) >= n!6220!6220fib1(X, Y) activate(n!6220!6220fib1(X, Y)) > fib1(X, Y) activate(X) >= X With these choices, we have: 1] fib(X) >= sel(X, fib1(s(_|_), s(_|_))) because [2], by (Star) 2] fib*(X) >= sel(X, fib1(s(_|_), s(_|_))) because fib > sel, [3] and [5], by (Copy) 3] fib*(X) >= X because [4], by (Select) 4] X >= X by (Meta) 5] fib*(X) >= fib1(s(_|_), s(_|_)) because fib > fib1, [6] and [6], by (Copy) 6] fib*(X) >= s(_|_) because fib > s and [7], by (Copy) 7] fib*(X) >= _|_ by (Bot) 8] fib1(X, Y) >= cons(X, n!6220!6220fib1(Y, add(X, Y))) because [9], by (Star) 9] fib1*(X, Y) >= cons(X, n!6220!6220fib1(Y, add(X, Y))) because fib1 > cons, [10] and [12], by (Copy) 10] fib1*(X, Y) >= X because [11], by (Select) 11] X >= X by (Meta) 12] fib1*(X, Y) >= n!6220!6220fib1(Y, add(X, Y)) because fib1 > n!6220!6220fib1, [13] and [15], by (Copy) 13] fib1*(X, Y) >= Y because [14], by (Select) 14] Y >= Y by (Meta) 15] fib1*(X, Y) >= add(X, Y) because fib1 > add, [10] and [13], by (Copy) 16] add(_|_, X) > X because [17], by definition 17] add*(_|_, X) >= X because [11], by (Select) 18] add(s(X), Y) >= s(add(X, Y)) because [19], by (Star) 19] add*(s(X), Y) >= s(add(X, Y)) because add > s and [20], by (Copy) 20] add*(s(X), Y) >= add(X, Y) because add in Mul, [21] and [23], by (Stat) 21] s(X) > X because [22], by definition 22] s*(X) >= X because [11], by (Select) 23] Y >= Y by (Meta) 24] sel(_|_, cons(X, Y)) >= X because [25], by (Star) 25] sel*(_|_, cons(X, Y)) >= X because [26], by (Select) 26] cons(X, Y) >= X because [27], by (Star) 27] cons*(X, Y) >= X because [11], by (Select)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472