details

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

run statistics

property	value
solver	Wanda
configuration	HigherOrder
runtime (wallclock)	2.4027030468 seconds
cpu usage	2.399427717
max memory	1.17776384E8

stage attributes

key	value
output-size	15994
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: !plus : [proc * proc] --> proc !times : [proc * proc] --> proc delta : [] --> proc sigma : [data -> proc] --> proc Rules: !plus(x, x) => x !times(!plus(x, y), z) => !plus(!times(x, z), !times(y, z)) !times(!times(x, y), z) => !times(x, !times(y, z)) !plus(x, delta) => x !times(delta, x) => delta sigma(/\x.y) => y !plus(sigma(/\x.f x), f y) => sigma(/\z.f z) sigma(/\x.!plus(f x, g x)) => !plus(sigma(/\y.f y), sigma(/\z.g z)) !times(sigma(/\x.f x), y) => sigma(/\z.!times(f z, y)) Using the transformations described in [Kop11], this system can be brought in a form without leading free variables in the left-hand side, and where the left-hand side of a variable is always a functional term or application headed by a functional term. We now transform the resulting AFS into an AFSM by replacing all free variables by meta-variables (with arity 0). This leads to the following AFSM: Alphabet: !plus : [proc * proc] --> proc !times : [proc * proc] --> proc delta : [] --> proc sigma : [data -> proc] --> proc ~AP1 : [data -> proc * data] --> proc Rules: !plus(X, X) => X !times(!plus(X, Y), Z) => !plus(!times(X, Z), !times(Y, Z)) !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) !plus(X, delta) => X !times(delta, X) => delta sigma(/\x.X) => X !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) => sigma(/\y.~AP1(F, y)) sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) => !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) !times(sigma(/\x.~AP1(F, x)), X) => sigma(/\y.!times(~AP1(F, y), X)) ~AP1(F, X) => F X We use the dependency pair framework as described in [Kop12, Ch. 6/7], with dynamic dependency pairs. After applying [Kop12, Thm. 7.22] to denote collapsing dependency pairs in an extended form, we thus obtain the following dependency pair problem (P_0, R_0, minimal, all): Dependency Pairs P_0: 0] !times#(!plus(X, Y), Z) =#> !plus#(!times(X, Z), !times(Y, Z)) 1] !times#(!plus(X, Y), Z) =#> !times#(X, Z) 2] !times#(!plus(X, Y), Z) =#> !times#(Y, Z) 3] !times#(!times(X, Y), Z) =#> !times#(X, !times(Y, Z)) 4] !times#(!times(X, Y), Z) =#> !times#(Y, Z) 5] !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) =#> sigma#(/\y.~AP1(F, y)) 6] !plus#(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) =#> ~AP1#(F, y) 7] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> !plus#(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) 8] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(F, y)) 9] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> ~AP1#(F, y) 10] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> sigma#(/\y.~AP1(G, y)) 11] sigma#(/\x.!plus(~AP1(F, x), ~AP1(G, x))) =#> ~AP1#(G, y) 12] !times#(sigma(/\x.~AP1(F, x)), X) =#> sigma#(/\y.!times(~AP1(F, y), X)) 13] !times#(sigma(/\x.~AP1(F, x)), X) =#> !times#(~AP1(F, y), X) 14] !times#(sigma(/\x.~AP1(F, x)), X) =#> ~AP1#(F, y) 15] ~AP1#(F, X) =#> F(X) Rules R_0: !plus(X, X) => X !times(!plus(X, Y), Z) => !plus(!times(X, Z), !times(Y, Z)) !times(!times(X, Y), Z) => !times(X, !times(Y, Z)) !plus(X, delta) => X !times(delta, X) => delta sigma(/\x.X) => X !plus(sigma(/\x.~AP1(F, x)), ~AP1(F, X)) => sigma(/\y.~AP1(F, y)) sigma(/\x.!plus(~AP1(F, x), ~AP1(G, x))) => !plus(sigma(/\y.~AP1(F, y)), sigma(/\z.~AP1(G, z))) !times(sigma(/\x.~AP1(F, x)), X) => sigma(/\y.!times(~AP1(F, y), X)) ~AP1(F, X) => F X Thus, the original system is terminating if (P_0, R_0, minimal, all) is finite. We consider the dependency pair problem (P_0, R_0, minimal, all). We place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 5, 6 * 1 : 0, 1, 2, 3, 4, 12, 13, 14 * 2 : 0, 1, 2, 3, 4, 12, 13, 14 * 3 : 0, 1, 2, 3, 4, 12, 13, 14 * 4 : 0, 1, 2, 3, 4, 12, 13, 14 popout

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

job log

popout

actions

all output return to HRS union beta 16688