Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381716140
details
property
value
status
complete
benchmark
Ex8_BLR02_FR.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n108.star.cs.uiowa.edu
space
Transformed_CSR_04
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.156491994858 seconds
cpu usage
0.135032449
max memory
6066176.0
stage attributes
key
value
output-size
10182
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!6220add : [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, n!6220!6220add(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) add(X, Y) => n!6220!6220add(X, Y) activate(n!6220!6220fib1(X, Y)) => fib1(activate(X), activate(Y)) activate(n!6220!6220add(X, Y)) => add(activate(X), activate(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, n!6220!6220add(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) add(X, Y) >? n!6220!6220add(X, Y) activate(n!6220!6220fib1(X, Y)) >? fib1(activate(X), activate(Y)) activate(n!6220!6220add(X, Y)) >? add(activate(X), activate(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!6220add, n!6220!6220fib1, s}, and the following precedence: fib > sel > activate > add > fib1 > cons > n!6220!6220add > 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, n!6220!6220add(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) add(X, Y) > n!6220!6220add(X, Y) activate(n!6220!6220fib1(X, Y)) > fib1(activate(X), activate(Y)) activate(n!6220!6220add(X, Y)) >= add(activate(X), activate(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, n!6220!6220add(X, Y))) because [9], by (Star) 9] fib1*(X, Y) >= cons(X, n!6220!6220fib1(Y, n!6220!6220add(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, n!6220!6220add(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) >= n!6220!6220add(X, Y) because fib1 > n!6220!6220add, [10] and [13], by (Copy) 16] add(_|_, X) >= X because [17], by (Star) 17] add*(_|_, X) >= X because [11], by (Select) 18] add(s(X), Y) > s(add(X, Y)) because [19], by definition 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
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472