details

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

run statistics

property	value
solver	Wanda
configuration	HigherOrder
runtime (wallclock)	1.09790897369 seconds
cpu usage	2.391281741
max memory	1.44543744E8

stage attributes

key	value
output-size	14277
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 cons : [nat * list] --> list false : [] --> bool gcd : [nat * nat] --> nat gcdlists : [list * list] --> list if : [bool * nat * nat] --> nat le : [nat * nat] --> bool minus : [nat * nat] --> nat nil : [] --> list s : [nat] --> nat true : [] --> bool zipWith : [nat -> nat -> nat * list * list] --> list Rules: le(0, x) => true le(s(x), 0) => false le(s(x), s(y)) => le(x, y) minus(x, 0) => x minus(s(x), s(y)) => minus(x, y) gcd(0, x) => 0 gcd(s(x), 0) => 0 gcd(s(x), s(y)) => if(le(y, x), s(x), s(y)) if(true, s(x), s(y)) => gcd(minus(x, y), s(y)) if(false, s(x), s(y)) => gcd(minus(y, x), s(x)) zipWith(f, x, nil) => nil zipWith(f, nil, x) => nil zipWith(f, cons(x, y), cons(z, u)) => cons(f x z, zipWith(f, y, u)) gcdlists(x, y) => zipWith(/\z./\u.gcd(z, u), x, 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: le(0, X) => true le(s(X), 0) => false le(s(X), s(Y)) => le(X, Y) minus(X, 0) => X minus(s(X), s(Y)) => minus(X, Y) gcd(0, X) => 0 gcd(s(X), 0) => 0 gcd(s(X), s(Y)) => if(le(Y, X), s(X), s(Y)) if(true, s(X), s(Y)) => gcd(minus(X, Y), s(Y)) if(false, s(X), s(Y)) => gcd(minus(Y, X), s(X)) Moreover, the system is finitely branching. 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 Ce-terminating when seen as a many-sorted first-order TRS. According to the external first-order termination prover, this system is indeed Ce-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) DependencyPairsProof [EQUIVALENT] || (2) QDP || (3) DependencyGraphProof [EQUIVALENT] || (4) AND || (5) QDP || (6) UsableRulesProof [EQUIVALENT] || (7) QDP || (8) QDPSizeChangeProof [EQUIVALENT] || (9) YES || (10) QDP || (11) UsableRulesProof [EQUIVALENT] || (12) QDP || (13) QDPSizeChangeProof [EQUIVALENT] || (14) YES || (15) QDP || (16) QDPOrderProof [EQUIVALENT] || (17) QDP || (18) DependencyGraphProof [EQUIVALENT] || (19) TRUE || || || ---------------------------------------- || || (0) || Obligation: || Q restricted rewrite system: || The TRS R consists of the following rules: || || le(0, %X) -> true || le(s(%X), 0) -> false || le(s(%X), s(%Y)) -> le(%X, %Y) || minus(%X, 0) -> %X || minus(s(%X), s(%Y)) -> minus(%X, %Y) popout

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

job log

popout

actions

all output return to HRS union beta 16688