details

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

run statistics

property	value
solver	Wanda
configuration	HigherOrder
runtime (wallclock)	0.108747959137 seconds
cpu usage	0.105027877
max memory	3723264.0

stage attributes

key	value
output-size	10197
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 : [] --> nat I : [nat] --> nat s : [nat] --> nat twice : [nat -> nat] --> nat -> nat Rules: I(0) => 0 I(s(x)) => s(twice(/\y.I(y)) x) twice(f) => /\x.f (f x) This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). We use the dependency pair framework as described in [Kop12, Ch. 6/7], with dynamic dependency pairs. To start, the system is beta-saturated by adding the following rules: twice(F) X => F (F X) 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, formative): Dependency Pairs P_0: 0] I#(s(X)) =#> twice(/\x.I(x)) X 1] I#(s(X)) =#> twice#(/\x.I(x)) 2] I#(s(X)) =#> I#(x) 3] twice#(F) =#> F(F x) 4] twice#(F) =#> F(x) 5] twice(F) X =#> F(F X) 6] twice(F) X =#> F(X) Rules R_0: I(0) => 0 I(s(X)) => s(twice(/\x.I(x)) X) twice(F) => /\x.F (F x) twice(F) X => F (F X) Thus, the original system is terminating if (P_0, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_0, R_0, minimal, formative). 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 : 3, 4 * 2 : * 3 : 0, 1, 2, 3, 4, 5, 6 * 4 : 0, 1, 2, 3, 4, 5, 6 * 5 : 0, 1, 2, 3, 4, 5, 6 * 6 : 0, 1, 2, 3, 4, 5, 6 This graph has the following strongly connected components: P_1: I#(s(X)) =#> twice(/\x.I(x)) X I#(s(X)) =#> twice#(/\x.I(x)) twice#(F) =#> F(F x) twice#(F) =#> F(x) twice(F) X =#> F(F X) twice(F) X =#> F(X) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f). Thus, the original system is terminating if (P_1, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_0, minimal, formative). The formative rules of (P_1, R_0) are R_1 ::= I(s(X)) => s(twice(/\x.I(x)) X) twice(F) X => F (F X) By [Kop12, Thm. 7.17], we may replace the dependency pair problem (P_1, R_0, minimal, formative) by (P_1, R_1, minimal, formative). Thus, the original system is terminating if (P_1, R_1, minimal, formative) is finite. We consider the dependency pair problem (P_1, R_1, minimal, formative). We will use the reduction pair processor [Kop12, Thm. 7.16]. As the system is abstraction-simple and the formative flag is set, it suffices to find a tagged reduction pair [Kop12, Def. 6.70]. Thus, we must orient: I#(s(X)) >? twice(/\x.I-(x), X) I#(s(X)) >? twice#(/\x.I-(x)) ~c0 twice#(F) X >? F(F ~c1) twice#(F) X >? F(~c2) twice(F, X) >? F(F X) twice(F, X) >? F(X) I(s(X)) >= s(twice(/\x.I-(x), X)) popout

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

job log

popout

actions

all output return to HRS union beta 16688