Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381715810
details
property
value
status
complete
benchmark
MYNAT_nosorts-noand_FR.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n085.star.cs.uiowa.edu
space
Transformed_CSR_04
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.363396883011 seconds
cpu usage
0.359333093
max memory
1.3975552E7
stage attributes
key
value
output-size
15425
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 U11 : [o * o * o] --> o U12 : [o * o * o] --> o U21 : [o * o * o] --> o U22 : [o * o * o] --> o activate : [o] --> o plus : [o * o] --> o s : [o] --> o tt : [] --> o x : [o * o] --> o U11(tt, X, Y) => U12(tt, activate(X), activate(Y)) U12(tt, X, Y) => s(plus(activate(Y), activate(X))) U21(tt, X, Y) => U22(tt, activate(X), activate(Y)) U22(tt, X, Y) => plus(x(activate(Y), activate(X)), activate(Y)) plus(X, 0) => X plus(X, s(Y)) => U11(tt, Y, X) x(X, 0) => 0 x(X, s(Y)) => U21(tt, Y, X) activate(X) => X As the system is orthogonal, it is terminating if it is innermost terminating by [Gra95]. Then, by [FuhGieParSchSwi11], it suffices to prove (innermost) termination of the typed system, with sort annotations chosen to respect the rules, as follows: 0 : [] --> tc U11 : [l * tc * tc] --> tc U12 : [l * tc * tc] --> tc U21 : [l * tc * tc] --> tc U22 : [l * tc * tc] --> tc activate : [tc] --> tc plus : [tc * tc] --> tc s : [tc] --> tc tt : [] --> l x : [tc * tc] --> tc We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): U11(tt, X, Y) >? U12(tt, activate(X), activate(Y)) U12(tt, X, Y) >? s(plus(activate(Y), activate(X))) U21(tt, X, Y) >? U22(tt, activate(X), activate(Y)) U22(tt, X, Y) >? plus(x(activate(Y), activate(X)), activate(Y)) plus(X, 0) >? X plus(X, s(Y)) >? U11(tt, Y, X) x(X, 0) >? 0 x(X, s(Y)) >? U21(tt, Y, X) activate(X) >? X about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[activate(x_1)]] = x_1 [[tt]] = _|_ We choose Lex = {} and Mul = {U11, U12, U21, U22, plus, s, x}, and the following precedence: U21 = U22 = x > U11 = U12 = plus > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: U11(_|_, X, Y) >= U12(_|_, X, Y) U12(_|_, X, Y) >= s(plus(Y, X)) U21(_|_, X, Y) >= U22(_|_, X, Y) U22(_|_, X, Y) >= plus(x(Y, X), Y) plus(X, _|_) > X plus(X, s(Y)) >= U11(_|_, Y, X) x(X, _|_) >= _|_ x(X, s(Y)) >= U21(_|_, Y, X) X >= X With these choices, we have: 1] U11(_|_, X, Y) >= U12(_|_, X, Y) because U11 = U12, U11 in Mul, [2], [3] and [4], by (Fun) 2] _|_ >= _|_ by (Bot) 3] X >= X by (Meta) 4] Y >= Y by (Meta) 5] U12(_|_, X, Y) >= s(plus(Y, X)) because [6], by (Star) 6] U12*(_|_, X, Y) >= s(plus(Y, X)) because U12 > s and [7], by (Copy) 7] U12*(_|_, X, Y) >= plus(Y, X) because U12 = plus, U12 in Mul, [3] and [4], by (Stat) 8] U21(_|_, X, Y) >= U22(_|_, X, Y) because U21 = U22, U21 in Mul, [2], [3] and [4], by (Fun) 9] U22(_|_, X, Y) >= plus(x(Y, X), Y) because [10], by (Star) 10] U22*(_|_, X, Y) >= plus(x(Y, X), Y) because U22 > plus, [11] and [12], by (Copy) 11] U22*(_|_, X, Y) >= x(Y, X) because U22 = x, U22 in Mul, [3] and [4], by (Stat) 12] U22*(_|_, X, Y) >= Y because [4], by (Select)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472