details

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

run statistics

property	value
solver	Wanda
configuration	HigherOrder
runtime (wallclock)	0.0813419818878 seconds
cpu usage	0.077913347
max memory	4579328.0

stage attributes

key	value
output-size	4226
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 cons : [nat * list] --> list foldr : [nat -> nat -> nat * nat * list] --> nat length : [list] --> nat nil : [] --> list s : [nat] --> nat Rules: foldr(f, x, nil) => x foldr(f, x, cons(y, z)) => f y foldr(f, x, z) length(x) => foldr(/\y./\z.s(z), 0, x) 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]): foldr(F, X, nil) >? X foldr(F, X, cons(Y, Z)) >? F Y foldr(F, X, Z) length(X) >? foldr(/\x./\y.s(y), 0, X) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[0]] = _|_ [[s(x_1)]] = x_1 We choose Lex = {} and Mul = {@_{o -> o -> o}, @_{o -> o}, cons, foldr, length, nil}, and the following precedence: length > foldr > @_{o -> o} > @_{o -> o -> o} > cons > nil Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: foldr(F, X, nil) >= X foldr(F, X, cons(Y, Z)) > @_{o -> o}(@_{o -> o -> o}(F, Y), foldr(F, X, Z)) length(X) >= foldr(/\x./\y.y, _|_, X) With these choices, we have: 1] foldr(F, X, nil) >= X because [2], by (Star) 2] foldr*(F, X, nil) >= X because [3], by (Select) 3] X >= X by (Meta) 4] foldr(F, X, cons(Y, Z)) > @_{o -> o}(@_{o -> o -> o}(F, Y), foldr(F, X, Z)) because [5], by definition 5] foldr*(F, X, cons(Y, Z)) >= @_{o -> o}(@_{o -> o -> o}(F, Y), foldr(F, X, Z)) because foldr > @_{o -> o}, [6] and [13], by (Copy) 6] foldr*(F, X, cons(Y, Z)) >= @_{o -> o -> o}(F, Y) because foldr > @_{o -> o -> o}, [7] and [9], by (Copy) 7] foldr*(F, X, cons(Y, Z)) >= F because [8], by (Select) 8] F >= F by (Meta) 9] foldr*(F, X, cons(Y, Z)) >= Y because [10], by (Select) 10] cons(Y, Z) >= Y because [11], by (Star) 11] cons*(Y, Z) >= Y because [12], by (Select) 12] Y >= Y by (Meta) 13] foldr*(F, X, cons(Y, Z)) >= foldr(F, X, Z) because foldr in Mul, [14], [15] and [16], by (Stat) 14] F >= F by (Meta) 15] X >= X by (Meta) 16] cons(Y, Z) > Z because [17], by definition 17] cons*(Y, Z) >= Z because [18], by (Select) 18] Z >= Z by (Meta) 19] length(X) >= foldr(/\x./\y.y, _|_, X) because [20], by (Star) 20] length*(X) >= foldr(/\x./\y.y, _|_, X) because length > foldr, [21], [25] and [26], by (Copy) 21] length*(X) >= /\y./\z.z because [22], by (F-Abs) 22] length*(X, x) >= /\z.z because [23], by (F-Abs) 23] length*(X, x, y) >= y because [24], by (Select) 24] y >= y by (Var) 25] length*(X) >= _|_ by (Bot) 26] length*(X) >= X because [27], by (Select) 27] X >= X by (Meta) We can thus remove the following rules: foldr(F, X, cons(Y, Z)) => F Y foldr(F, X, Z) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): foldr(F, X, nil) >? X length(X) >? foldr(/\x./\y.s(y), 0, X) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 foldr = \G0y1y2.y1 + y2 + G0(0,0) popout

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

job log

popout

actions

all output return to HRS union beta 16688