details

property	value
status	complete
benchmark	Applicative_first_order_05__#3.13.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)	2.01850104332 seconds
cpu usage	3.316271991
max memory	1.56852224E8

stage attributes

key	value
output-size	36154
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 cons : [d * e] --> e edge : [a * a * b] --> b empty : [] --> b eq : [a * a] --> c false : [] --> c filter : [d -> c * e] --> e filter2 : [c * d -> c * d * e] --> e if!fac6220reach!fac62201 : [c * a * a * b * b] --> c if!fac6220reach!fac62202 : [c * a * a * b * b] --> c map : [d -> d * e] --> e nil : [] --> e or : [c * c] --> c reach : [a * a * b * b] --> c s : [a] --> a true : [] --> c union : [b * b] --> b Rules: eq(0, 0) => true eq(0, s(x)) => false eq(s(x), 0) => false eq(s(x), s(y)) => eq(x, y) or(true, x) => true or(false, x) => x union(empty, x) => x union(edge(x, y, z), u) => edge(x, y, union(z, u)) reach(x, y, empty, z) => false reach(x, y, edge(z, u, v), w) => if!fac6220reach!fac62201(eq(x, z), x, y, edge(z, u, v), w) if!fac6220reach!fac62201(true, x, y, edge(z, u, v), w) => if!fac6220reach!fac62202(eq(y, u), x, y, edge(z, u, v), w) if!fac6220reach!fac62201(false, x, y, edge(z, u, v), w) => reach(x, y, v, edge(z, u, w)) if!fac6220reach!fac62202(true, x, y, edge(z, u, v), w) => true if!fac6220reach!fac62202(false, x, y, edge(z, u, v), w) => or(reach(x, y, v, w), reach(u, y, union(v, w), empty)) map(f, nil) => nil map(f, cons(x, y)) => cons(f x, map(f, y)) filter(f, nil) => nil filter(f, cons(x, y)) => filter2(f x, f, x, y) filter2(true, f, x, y) => cons(x, filter(f, y)) filter2(false, f, x, y) => filter(f, y) This AFS is converted to an AFSM simply by replacing all free variables by meta-variables (with arity 0). We observe that the rules contain a first-order subset: eq(0, 0) => true eq(0, s(X)) => false eq(s(X), 0) => false eq(s(X), s(Y)) => eq(X, Y) or(true, X) => true or(false, X) => X union(empty, X) => X union(edge(X, Y, Z), U) => edge(X, Y, union(Z, U)) reach(X, Y, empty, Z) => false reach(X, Y, edge(Z, U, V), W) => if!fac6220reach!fac62201(eq(X, Z), X, Y, edge(Z, U, V), W) if!fac6220reach!fac62201(true, X, Y, edge(Z, U, V), W) => if!fac6220reach!fac62202(eq(Y, U), X, Y, edge(Z, U, V), W) if!fac6220reach!fac62201(false, X, Y, edge(Z, U, V), W) => reach(X, Y, V, edge(Z, U, W)) if!fac6220reach!fac62202(true, X, Y, edge(Z, U, V), W) => true if!fac6220reach!fac62202(false, X, Y, edge(Z, U, V), W) => or(reach(X, Y, V, W), reach(U, Y, union(V, W), empty)) Moreover, the system is orthogonal. Thus, by [Kop12, Thm. 7.55], we may omit all first-order dependency pairs from the dependency pair problem (DP(R), R) if this first-order part is terminating when seen as a many-sorted first-order TRS. According to the external first-order termination prover, this system is indeed terminating: || proof of resources/system.trs || # AProVE Commit ID: d84c10301d352dfd14de2104819581f4682260f5 fuhs 20130616 || || || Termination w.r.t. Q of the given QTRS could be proven: || || (0) QTRS || (1) Overlay + Local Confluence [EQUIVALENT] || (2) QTRS || (3) DependencyPairsProof [EQUIVALENT] || (4) QDP || (5) DependencyGraphProof [EQUIVALENT] || (6) AND || (7) QDP || (8) UsableRulesProof [EQUIVALENT] || (9) QDP || (10) QReductionProof [EQUIVALENT] || (11) QDP || (12) QDPSizeChangeProof [EQUIVALENT] || (13) YES || (14) QDP || (15) UsableRulesProof [EQUIVALENT] || (16) QDP || (17) QReductionProof [EQUIVALENT] || (18) QDP popout

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

job log

popout

actions

all output return to HRS union beta 16688