Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
HRS union beta 16688 pair #381734672
details
property
value
status
complete
benchmark
Applicative_05__Ex7Sorting.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n014.star.cs.uiowa.edu
space
Uncurried_Applicative_11
run statistics
property
value
solver
Wanda
configuration
HigherOrder
runtime (wallclock)
0.849603176117 seconds
cpu usage
0.846315111
max memory
3.9571456E7
stage attributes
key
value
output-size
11726
starexec-result
YES
output
/export/starexec/sandbox2/solver/bin/starexec_run_HigherOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. Alphabet: 0 : [] --> a asort : [b] --> b cons : [a * b] --> b dsort : [b] --> b insert : [a -> a -> a * a -> a -> a * b * a] --> b max : [] --> a -> a -> a min : [] --> a -> a -> a nil : [] --> b s : [a] --> a sort : [a -> a -> a * a -> a -> a * b] --> b Rules: sort(f, g, nil) => nil sort(f, g, cons(x, y)) => insert(f, g, sort(f, g, y), x) insert(f, g, nil, x) => cons(x, nil) insert(f, g, cons(x, y), z) => cons(f x z, insert(f, g, y, g x z)) max 0 x => x max x 0 => x max s(x) s(y) => max x y min 0 x => 0 min x 0 => 0 min s(x) s(y) => min x y asort(x) => sort(min, max, x) dsort(x) => sort(max, min, 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]): sort(F, G, nil) >? nil sort(F, G, cons(X, Y)) >? insert(F, G, sort(F, G, Y), X) insert(F, G, nil, X) >? cons(X, nil) insert(F, G, cons(X, Y), Z) >? cons(F X Z, insert(F, G, Y, G X Z)) max 0 X >? X max X 0 >? X max s(X) s(Y) >? max X Y min 0 X >? 0 min X 0 >? 0 min s(X) s(Y) >? min X Y asort(X) >? sort(min, max, X) dsort(X) >? sort(max, min, X) 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_3, x_1, x_4, x_2) [[min]] = _|_ [[nil]] = _|_ We choose Lex = {insert} and Mul = {@_{o -> o -> o}, @_{o -> o}, asort, cons, dsort, max, s, sort}, and the following precedence: asort > dsort > max > 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: sort(F, G, _|_) >= _|_ sort(F, G, cons(X, Y)) >= insert(F, G, sort(F, G, Y), X) insert(F, G, _|_, X) > cons(X, _|_) insert(F, G, cons(X, Y), Z) > cons(@_{o -> o}(@_{o -> o -> o}(F, X), Z), insert(F, G, Y, @_{o -> o}(@_{o -> o -> o}(G, X), Z))) @_{o -> o}(@_{o -> o -> o}(max, _|_), X) >= X @_{o -> o}(@_{o -> o -> o}(max, X), _|_) >= X @_{o -> o}(@_{o -> o -> o}(max, s(X)), s(Y)) > @_{o -> o}(@_{o -> o -> o}(max, X), Y) @_{o -> o}(@_{o -> o -> o}(_|_, _|_), X) >= _|_ @_{o -> o}(@_{o -> o -> o}(_|_, X), _|_) >= _|_ @_{o -> o}(@_{o -> o -> o}(_|_, s(X)), s(Y)) >= @_{o -> o}(@_{o -> o -> o}(_|_, X), Y) asort(X) >= sort(_|_, max, X) dsort(X) >= sort(max, _|_, X) With these choices, we have: 1] sort(F, G, _|_) >= _|_ by (Bot) 2] sort(F, G, cons(X, Y)) >= insert(F, G, sort(F, G, Y), X) because [3], by (Star) 3] sort*(F, G, cons(X, Y)) >= insert(F, G, sort(F, G, Y), X) because sort > insert, [4], [6], [8] and [14], by (Copy) 4] sort*(F, G, cons(X, Y)) >= F because [5], by (Select) 5] F >= F by (Meta) 6] sort*(F, G, cons(X, Y)) >= G because [7], by (Select) 7] G >= G by (Meta) 8] sort*(F, G, cons(X, Y)) >= sort(F, G, Y) because sort in Mul, [9], [10] and [11], by (Stat) 9] F >= F by (Meta) 10] G >= G by (Meta) 11] cons(X, Y) > Y because [12], by definition 12] cons*(X, Y) >= Y because [13], by (Select) 13] Y >= Y by (Meta)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to HRS union beta 16688