Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
HRS union beta 16688 pair #381734482
details
property
value
status
complete
benchmark
iterative.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n054.star.cs.uiowa.edu
space
Mixed_HO_10
run statistics
property
value
solver
Wanda
configuration
HigherOrder
runtime (wallclock)
0.539262056351 seconds
cpu usage
0.53561385
max memory
2.8450816E7
stage attributes
key
value
output-size
4718
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: a : [] --> o b : [] --> o f : [o * o -> o] --> o g : [o * o * o -> o] --> o Rules: g(x, y, h) => f(f(x, h), h) f(x, h) => b b => a f(b, /\x.g(x, x, h)) => g(f(a, /\y.g(y, y, h)), f(b, /\z.b), h) 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]): g(X, Y, F) >? f(f(X, F), F) f(X, F) >? b b >? a f(b, /\x.g(x, x, F)) >? g(f(a, /\y.g(y, y, F)), f(b, /\z.b), F) about to try horpo We use a recursive path ordering as defined in [Kop12, Chapter 5]. Argument functions: [[a]] = _|_ We choose Lex = {} and Mul = {b, f, g}, and the following precedence: g > f > b Taking the argument function into account, and fixing the greater / greater equal choices, the constraints can be denoted as follows: g(X, Y, F) >= f(f(X, F), F) f(X, F) >= b b > _|_ f(b, /\x.g(x, x, F)) > g(f(_|_, /\x.g(x, x, F)), f(b, /\y.b), F) With these choices, we have: 1] g(X, Y, F) >= f(f(X, F), F) because [2], by (Star) 2] g*(X, Y, F) >= f(f(X, F), F) because g > f, [3] and [6], by (Copy) 3] g*(X, Y, F) >= f(X, F) because g > f, [4] and [6], by (Copy) 4] g*(X, Y, F) >= X because [5], by (Select) 5] X >= X by (Meta) 6] g*(X, Y, F) >= F because [7], by (Select) 7] F >= F by (Meta) 8] f(X, F) >= b because [9], by (Star) 9] f*(X, F) >= b because f > b, by (Copy) 10] b > _|_ because [11], by definition 11] b* >= _|_ by (Bot) 12] f(b, /\x.g(x, x, F)) > g(f(_|_, /\x.g(x, x, F)), f(b, /\y.b), F) because [13], by definition 13] f*(b, /\x.g(x, x, F)) >= g(f(_|_, /\x.g(x, x, F)), f(b, /\y.b), F) because [14], by (Select) 14] g(f*(b, /\x.g(x, x, F)), f*(b, /\y.g(y, y, F)), F) >= g(f(_|_, /\x.g(x, x, F)), f(b, /\y.b), F) because g in Mul, [15], [20] and [19], by (Fun) 15] f*(b, /\x.g(x, x, F)) >= f(_|_, /\x.g(x, x, F)) because f in Mul, [10] and [16], by (Stat) 16] /\y.g(y, y, F) >= /\y.g(y, y, F) because [17], by (Abs) 17] g(x, x, F) >= g(x, x, F) because g in Mul, [18], [18] and [19], by (Fun) 18] x >= x by (Var) 19] F >= F by (Meta) 20] f*(b, /\y.g(y, y, F)) >= f(b, /\y.b) because [21], by (Select) 21] g(f*(b, /\y.g(y, y, F)), f*(b, /\z.g(z, z, F)), F) >= f(b, /\y.b) because [22], by (Star) 22] g*(f*(b, /\y.g(y, y, F)), f*(b, /\z.g(z, z, F)), F) >= f(b, /\y.b) because g > f, [23] and [24], by (Copy) 23] g*(f*(b, /\y.g(y, y, F)), f*(b, /\z.g(z, z, F)), F) >= b because g > b, by (Copy) 24] g*(f*(b, /\y.g(y, y, F)), f*(b, /\z.g(z, z, F)), F) >= /\y.b because [25], by (F-Abs) 25] g*(f*(b, /\y.g(y, y, F)), f*(b, /\z.g(z, z, F)), F, u) >= b because g > b, by (Copy) We can thus remove the following rules: b => a f(b, /\x.g(x, x, F)) => g(f(a, /\y.g(y, y, F)), f(b, /\z.b), F) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): g(X, Y, F) >? f(f(X, F), F) f(X, F) >? b We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: b = 0 f = \y0G1.y0 + G1(0)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to HRS union beta 16688