Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
HRS union beta 16688 pair #381734619
details
property
value
status
complete
benchmark
Applicative_05__Ex5Folding.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n053.star.cs.uiowa.edu
space
Uncurried_Applicative_11
run statistics
property
value
solver
Wanda
configuration
HigherOrder
runtime (wallclock)
0.233154058456 seconds
cpu usage
0.229493391
max memory
1.1522048E7
stage attributes
key
value
output-size
8988
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 : [] --> c add : [] --> a -> c -> c cons : [a * b] --> b fold : [a -> c -> c * c] --> b -> c mul : [] --> a -> c -> c nil : [] --> b plus : [c * c] --> c prod : [] --> b -> c s : [c] --> c sum : [] --> b -> c times : [c * c] --> c Rules: fold(f, x) nil => x fold(f, x) cons(y, z) => f y (fold(f, x) z) plus(0, x) => x plus(s(x), y) => s(plus(x, y)) times(0, x) => 0 times(s(x), y) => plus(times(x, y), y) sum => fold(add, 0) prod => fold(mul, s(0)) 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]): fold(F, X) nil >? X fold(F, X) cons(Y, Z) >? F Y (fold(F, X) Z) plus(0, X) >? X plus(s(X), Y) >? s(plus(X, Y)) times(0, X) >? 0 times(s(X), Y) >? plus(times(X, Y), Y) sum >? fold(add, 0) prod >? fold(mul, s(0)) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[add]] = _|_ [[mul]] = _|_ We choose Lex = {} and Mul = {0, @_{o -> o -> o}, @_{o -> o}, cons, fold, nil, plus, prod, s, sum, times}, and the following precedence: sum > prod > times > plus > s > 0 > fold > nil > @_{o -> o} > cons > @_{o -> o -> o} Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: @_{o -> o}(fold(F, X), nil) >= X @_{o -> o}(fold(F, X), cons(Y, Z)) > @_{o -> o}(@_{o -> o -> o}(F, Y), @_{o -> o}(fold(F, X), Z)) plus(0, X) >= X plus(s(X), Y) > s(plus(X, Y)) times(0, X) >= 0 times(s(X), Y) >= plus(times(X, Y), Y) sum >= fold(_|_, 0) prod > fold(_|_, s(0)) With these choices, we have: 1] @_{o -> o}(fold(F, X), nil) >= X because [2], by (Star) 2] @_{o -> o}*(fold(F, X), nil) >= X because [3], by (Select) 3] fold(F, X) @_{o -> o}*(fold(F, X), nil) >= X because [4] 4] fold*(F, X, @_{o -> o}*(fold(F, X), nil)) >= X because [5], by (Select) 5] X >= X by (Meta) 6] @_{o -> o}(fold(F, X), cons(Y, Z)) > @_{o -> o}(@_{o -> o -> o}(F, Y), @_{o -> o}(fold(F, X), Z)) because [7], by definition 7] @_{o -> o}*(fold(F, X), cons(Y, Z)) >= @_{o -> o}(@_{o -> o -> o}(F, Y), @_{o -> o}(fold(F, X), Z)) because [8], by (Select) 8] fold(F, X) @_{o -> o}*(fold(F, X), cons(Y, Z)) >= @_{o -> o}(@_{o -> o -> o}(F, Y), @_{o -> o}(fold(F, X), Z)) because [9] 9] fold*(F, X, @_{o -> o}*(fold(F, X), cons(Y, Z))) >= @_{o -> o}(@_{o -> o -> o}(F, Y), @_{o -> o}(fold(F, X), Z)) because fold > @_{o -> o}, [10] and [18], by (Copy) 10] fold*(F, X, @_{o -> o}*(fold(F, X), cons(Y, Z))) >= @_{o -> o -> o}(F, Y) because fold > @_{o -> o -> o}, [11] and [13], by (Copy) 11] fold*(F, X, @_{o -> o}*(fold(F, X), cons(Y, Z))) >= F because [12], by (Select) 12] F >= F by (Meta) 13] fold*(F, X, @_{o -> o}*(fold(F, X), cons(Y, Z))) >= Y because [14], by (Select) 14] @_{o -> o}*(fold(F, X), cons(Y, Z)) >= Y because [15], by (Select) 15] cons(Y, Z) >= Y because [16], by (Star) 16] cons*(Y, Z) >= Y because [17], by (Select) 17] Y >= Y by (Meta) 18] fold*(F, X, @_{o -> o}*(fold(F, X), cons(Y, Z))) >= @_{o -> o}(fold(F, X), Z) because [19], by (Select) 19] @_{o -> o}*(fold(F, X), cons(Y, Z)) >= @_{o -> o}(fold(F, X), Z) because @_{o -> o} in Mul, [20] and [23], by (Stat) 20] fold(F, X) >= fold(F, X) because fold in Mul, [21] and [22], by (Fun) 21] F >= F by (Meta) 22] X >= X by (Meta) 23] cons(Y, Z) > Z because [24], by definition 24] cons*(Y, Z) >= Z because [25], by (Select) 25] Z >= Z by (Meta)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to HRS union beta 16688