Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
HRS union beta 16688 pair #381734628
details
property
value
status
complete
benchmark
Applicative_05__Ex5Sorting.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n084.star.cs.uiowa.edu
space
Uncurried_Applicative_11
run statistics
property
value
solver
Wanda
configuration
HigherOrder
runtime (wallclock)
0.656430959702 seconds
cpu usage
0.650985342
max memory
3.328E7
stage attributes
key
value
output-size
11668
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 : [] --> a ascending!fac6220sort : [b] --> b cons : [a * b] --> b descending!fac6220sort : [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: 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 insert(f, g, nil, x) => cons(x, nil) insert(f, g, cons(x, y), z) => cons(f z x, insert(f, g, y, g z x)) sort(f, g, nil) => nil sort(f, g, cons(x, y)) => insert(f, g, sort(f, g, y), x) ascending!fac6220sort(x) => sort(min, max, x) descending!fac6220sort(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]): 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 insert(F, G, nil, X) >? cons(X, nil) insert(F, G, cons(X, Y), Z) >? cons(F Z X, insert(F, G, Y, G Z X)) sort(F, G, nil) >? nil sort(F, G, cons(X, Y)) >? insert(F, G, sort(F, G, Y), X) ascending!fac6220sort(X) >? sort(min, max, X) descending!fac6220sort(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_2, x_3, x_4, x_1) [[nil]] = _|_ We choose Lex = {insert} and Mul = {@_{o -> o -> o}, @_{o -> o}, ascending!fac6220sort, cons, descending!fac6220sort, max, min, s, sort}, and the following precedence: ascending!fac6220sort > descending!fac6220sort = min > max > s > sort > insert > cons > @_{o -> o -> 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}(@_{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}(min, _|_), X) >= _|_ @_{o -> o}(@_{o -> o -> o}(min, X), _|_) >= _|_ @_{o -> o}(@_{o -> o -> o}(min, s(X)), s(Y)) >= @_{o -> o}(@_{o -> o -> o}(min, X), Y) insert(F, G, _|_, X) >= cons(X, _|_) insert(F, G, cons(X, Y), Z) > cons(@_{o -> o}(@_{o -> o -> o}(F, Z), X), insert(F, G, Y, @_{o -> o}(@_{o -> o -> o}(G, Z), X))) sort(F, G, _|_) >= _|_ sort(F, G, cons(X, Y)) > insert(F, G, sort(F, G, Y), X) ascending!fac6220sort(X) >= sort(min, max, X) descending!fac6220sort(X) >= sort(max, min, X) With these choices, we have: 1] @_{o -> o}(@_{o -> o -> o}(max, _|_), X) >= X because [2], by (Star) 2] @_{o -> o}*(@_{o -> o -> o}(max, _|_), X) >= X because [3], by (Select) 3] X >= X by (Meta) 4] @_{o -> o}(@_{o -> o -> o}(max, X), _|_) >= X because [5], by (Star) 5] @_{o -> o}*(@_{o -> o -> o}(max, X), _|_) >= X because [6], by (Select) 6] @_{o -> o -> o}(max, X) @_{o -> o}*(@_{o -> o -> o}(max, X), _|_) >= X because [7] 7] @_{o -> o -> o}*(max, X, @_{o -> o}*(@_{o -> o -> o}(max, X), _|_)) >= X because [8], by (Select) 8] X >= X by (Meta) 9] @_{o -> o}(@_{o -> o -> o}(max, s(X)), s(Y)) >= @_{o -> o}(@_{o -> o -> o}(max, X), Y) because @_{o -> o} in Mul, [10] and [16], by (Fun) 10] @_{o -> o -> o}(max, s(X)) >= @_{o -> o -> o}(max, X) because [11], by (Star) 11] @_{o -> o -> o}*(max, s(X)) >= @_{o -> o -> o}(max, X) because @_{o -> o -> o} in Mul, [12] and [13], by (Stat) 12] max >= max by (Fun) 13] s(X) > X 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