details

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

run statistics

property	value
solver	Wanda
configuration	HigherOrder
runtime (wallclock)	1.33223986626 seconds
cpu usage	1.32941369
max memory	6.1554688E7

stage attributes

key	value
output-size	26910
starexec-result	YES

output

/export/starexec/sandbox/solver/bin/starexec_run_HigherOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. Alphabet: 0 : [] --> nat ascending!6220sort : [list] --> list cons : [nat * list] --> list descending!6220sort : [list] --> list insert : [nat * list * nat -> nat -> nat * nat -> nat -> nat] --> list max : [nat * nat] --> nat min : [nat * nat] --> nat nil : [] --> list s : [nat] --> nat sort : [list * nat -> nat -> nat * nat -> nat -> nat] --> list Rules: max(0, x) => x max(x, 0) => x max(s(x), s(y)) => s(max(x, y)) min(0, x) => 0 min(x, 0) => 0 min(s(x), s(y)) => s(min(x, y)) insert(x, nil, f, g) => cons(x, nil) insert(x, cons(y, z), f, g) => cons(f x y, insert(g x y, z, f, g)) sort(nil, f, g) => nil sort(cons(x, y), f, g) => insert(x, sort(y, f, g), f, g) ascending!6220sort(x) => sort(x, /\y./\z.min(y, z), /\u./\v.max(u, v)) descending!6220sort(x) => sort(x, /\y./\z.max(y, z), /\u./\v.min(u, v)) This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): max(0, X) >? X max(X, 0) >? X max(s(X), s(Y)) >? s(max(X, Y)) min(0, X) >? 0 min(X, 0) >? 0 min(s(X), s(Y)) >? s(min(X, Y)) insert(X, nil, F, G) >? cons(X, nil) insert(X, cons(Y, Z), F, G) >? cons(F X Y, insert(G X Y, Z, F, G)) sort(nil, F, G) >? nil sort(cons(X, Y), F, G) >? insert(X, sort(Y, F, G), F, G) ascending!6220sort(X) >? sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) descending!6220sort(X) >? sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[insert(x_1, x_2, x_3, x_4)]] = insert(x_2, x_4, x_1, x_3) [[nil]] = _|_ We choose Lex = {insert} and Mul = {@_{o -> o -> o}, @_{o -> o}, ascending!6220sort, cons, descending!6220sort, max, min, s, sort}, and the following precedence: ascending!6220sort > descending!6220sort > max > min > s > sort > insert > @_{o -> o -> o} > @_{o -> o} > cons Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: max(_|_, X) > X max(X, _|_) >= X max(s(X), s(Y)) >= s(max(X, Y)) min(_|_, X) >= _|_ min(X, _|_) >= _|_ min(s(X), s(Y)) >= s(min(X, Y)) insert(X, _|_, F, G) >= cons(X, _|_) insert(X, cons(Y, Z), F, G) >= cons(@_{o -> o}(@_{o -> o -> o}(F, X), Y), insert(@_{o -> o}(@_{o -> o -> o}(G, X), Y), Z, F, G)) sort(_|_, F, G) >= _|_ sort(cons(X, Y), F, G) >= insert(X, sort(Y, F, G), F, G) ascending!6220sort(X) >= sort(X, /\x./\y.min(x, y), /\z./\u.max(z, u)) descending!6220sort(X) >= sort(X, /\x./\y.max(x, y), /\z./\u.min(z, u)) With these choices, we have: 1] max(_|_, X) > X because [2], by definition 2] max*(_|_, X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] max(X, _|_) >= X because [5], by (Star) 5] max*(X, _|_) >= X because [6], by (Select) 6] X >= X by (Meta) 7] max(s(X), s(Y)) >= s(max(X, Y)) because [8], by (Star) 8] max*(s(X), s(Y)) >= s(max(X, Y)) because max > s and [9], by (Copy) 9] max*(s(X), s(Y)) >= max(X, Y) because max in Mul, [10] and [13], by (Stat) 10] s(X) >= X because [11], by (Star) 11] s*(X) >= X because [12], by (Select) 12] X >= X by (Meta) 13] s(Y) > Y because [14], by definition popout

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

job log

popout

actions

all output return to HRS union beta 16688