Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
HRS union beta 16688 pair #381734608
details
property
value
status
complete
benchmark
qsort.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n027.star.cs.uiowa.edu
space
Mixed_HO_10
run statistics
property
value
solver
Wanda
configuration
HigherOrder
runtime (wallclock)
1.32481193542 seconds
cpu usage
2.190944768
max memory
1.09887488E8
stage attributes
key
value
output-size
21271
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 app : [list * list] --> list cons : [nat * list] --> list false : [] --> bool filter : [nat -> bool * list] --> list gr : [nat * nat] --> bool if : [bool * list * list] --> list le : [nat * nat] --> bool nil : [] --> list qsort : [list] --> list s : [nat] --> nat true : [] --> bool Rules: if(true, x, y) => x if(false, x, y) => y app(nil, x) => x app(cons(x, y), z) => cons(x, app(y, z)) le(0, x) => true le(s(x), 0) => false le(s(x), s(y)) => le(x, y) gr(0, x) => false gr(s(x), 0) => true gr(s(x), s(y)) => gr(x, y) filter(f, nil) => nil filter(f, cons(x, y)) => if(f x, cons(x, filter(f, y)), filter(f, y)) qsort(nil) => nil qsort(cons(x, y)) => app(qsort(filter(/\z.le(z, x), y)), app(cons(x, nil), qsort(filter(/\u.gr(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: if(true, X, Y) => X if(false, X, Y) => Y app(nil, X) => X app(cons(X, Y), Z) => cons(X, app(Y, Z)) le(0, X) => true le(s(X), 0) => false le(s(X), s(Y)) => le(X, Y) gr(0, X) => false gr(s(X), 0) => true gr(s(X), s(Y)) => gr(X, Y) 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) QTRSRRRProof [EQUIVALENT] || (2) QTRS || (3) QTRSRRRProof [EQUIVALENT] || (4) QTRS || (5) RisEmptyProof [EQUIVALENT] || (6) YES || || || ---------------------------------------- || || (0) || Obligation: || Q restricted rewrite system: || The TRS R consists of the following rules: || || if(true, %X, %Y) -> %X || if(false, %X, %Y) -> %Y || app(nil, %X) -> %X || app(cons(%X, %Y), %Z) -> cons(%X, app(%Y, %Z)) || le(0, %X) -> true || le(s(%X), 0) -> false || le(s(%X), s(%Y)) -> le(%X, %Y) || gr(0, %X) -> false || gr(s(%X), 0) -> true || gr(s(%X), s(%Y)) -> gr(%X, %Y) || || Q is empty. || || ---------------------------------------- || || (1) QTRSRRRProof (EQUIVALENT) || Used ordering: || Polynomial interpretation [POLO]:
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to HRS union beta 16688