details

property	value
status	complete
benchmark	MYNAT_nosorts_FR.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n026.star.cs.uiowa.edu
space	Transformed_CSR_04

run statistics

property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	0.0690951347351 seconds
cpu usage	0.064611921
max memory	2568192.0

stage attributes

key	value
output-size	5121
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. 0 : [] --> o activate : [o] --> o and : [o * o] --> o plus : [o * o] --> o s : [o] --> o tt : [] --> o x : [o * o] --> o and(tt, X) => activate(X) plus(X, 0) => X plus(X, s(Y)) => s(plus(X, Y)) x(X, 0) => 0 x(X, s(Y)) => plus(x(X, 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 : [] --> xa activate : [k] --> k and : [i * k] --> k plus : [xa * xa] --> xa s : [xa] --> xa tt : [] --> i x : [xa * xa] --> xa We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): and(tt, X) >? activate(X) plus(X, 0) >? X plus(X, s(Y)) >? s(plus(X, Y)) x(X, 0) >? 0 x(X, s(Y)) >? plus(x(X, 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 We choose Lex = {plus} and Mul = {and, s, tt, x}, and the following precedence: and > tt > x > plus > s Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: and(tt, X) >= X plus(X, _|_) >= X plus(X, s(Y)) > s(plus(X, Y)) x(X, _|_) >= _|_ x(X, s(Y)) > plus(x(X, Y), X) X >= X With these choices, we have: 1] and(tt, X) >= X because [2], by (Star) 2] and*(tt, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] plus(X, _|_) >= X because [5], by (Star) 5] plus*(X, _|_) >= X because [6], by (Select) 6] X >= X by (Meta) 7] plus(X, s(Y)) > s(plus(X, Y)) because [8], by definition 8] plus*(X, s(Y)) >= s(plus(X, Y)) because plus > s and [9], by (Copy) 9] plus*(X, s(Y)) >= plus(X, Y) because [10], [11], [14] and [15], by (Stat) 10] X >= X by (Meta) 11] s(Y) > Y because [12], by definition 12] s*(Y) >= Y because [13], by (Select) 13] Y >= Y by (Meta) 14] plus*(X, s(Y)) >= X because [10], by (Select) 15] plus*(X, s(Y)) >= Y because [16], by (Select) 16] s(Y) >= Y because [12], by (Star) 17] x(X, _|_) >= _|_ by (Bot) 18] x(X, s(Y)) > plus(x(X, Y), X) because [19], by definition 19] x*(X, s(Y)) >= plus(x(X, Y), X) because x > plus, [20] and [21], by (Copy) 20] x*(X, s(Y)) >= x(X, Y) because x in Mul, [10] and [11], by (Stat) 21] x*(X, s(Y)) >= X because [10], by (Select) 22] X >= X by (Meta) We can thus remove the following rules: plus(X, s(Y)) => s(plus(X, Y)) popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to TRS Stand 20472