Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
HRS union beta 16688 pair #381734217
details
property
value
status
complete
benchmark
prefixshuffle.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n108.star.cs.uiowa.edu
space
Mixed_HO_12
run statistics
property
value
solver
Wanda
configuration
HigherOrder
runtime (wallclock)
1.28988695145 seconds
cpu usage
2.849570321
max memory
1.6011264E8
stage attributes
key
value
output-size
15373
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 : [natlist * natlist] --> natlist apply2 : [pair -> nat -> pair * pair * nat] --> pair cons : [nat * natlist] --> natlist fst : [pair] --> natlist nil : [] --> natlist p : [natlist * natlist] --> pair pcons : [pair * plist] --> plist pnil : [] --> plist pps : [natlist] --> plist prefixshuffle : [pair * natlist] --> plist pshuffle : [natlist] --> pair reverse : [natlist] --> natlist s : [nat] --> nat shuffle : [natlist] --> natlist Rules: app(nil, x) => x app(cons(x, y), z) => cons(x, app(y, z)) reverse(nil) => nil reverse(cons(x, y)) => app(reverse(y), cons(x, nil)) shuffle(nil) => nil shuffle(cons(x, y)) => cons(x, shuffle(reverse(y))) fst(p(x, y)) => x pshuffle(x) => p(x, shuffle(x)) prefixshuffle(x, nil) => pcons(x, pnil) prefixshuffle(x, cons(y, z)) => pcons(x, prefixshuffle(apply2(/\u./\v.pshuffle(app(fst(u), cons(v, nil))), x, y), reverse(z))) apply2(f, x, 0) => x apply2(f, x, s(y)) => f x s(y) pps(x) => prefixshuffle(p(nil, nil), x) 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: app(nil, X) => X app(cons(X, Y), Z) => cons(X, app(Y, Z)) reverse(nil) => nil reverse(cons(X, Y)) => app(reverse(Y), cons(X, nil)) shuffle(nil) => nil shuffle(cons(X, Y)) => cons(X, shuffle(reverse(Y))) fst(p(X, Y)) => X pshuffle(X) => p(X, shuffle(X)) 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) QTRSRRRProof [EQUIVALENT] || (6) QTRS || (7) QTRSRRRProof [EQUIVALENT] || (8) QTRS || (9) QTRSRRRProof [EQUIVALENT] || (10) QTRS || (11) QTRSRRRProof [EQUIVALENT] || (12) QTRS || (13) QTRSRRRProof [EQUIVALENT] || (14) QTRS || (15) RisEmptyProof [EQUIVALENT] || (16) YES || || || ---------------------------------------- || || (0) || Obligation: || Q restricted rewrite system: || The TRS R consists of the following rules: || || app(nil, %X) -> %X || app(cons(%X, %Y), %Z) -> cons(%X, app(%Y, %Z)) || reverse(nil) -> nil || reverse(cons(%X, %Y)) -> app(reverse(%Y), cons(%X, nil)) || shuffle(nil) -> nil || shuffle(cons(%X, %Y)) -> cons(%X, shuffle(reverse(%Y))) || fst(p(%X, %Y)) -> %X || pshuffle(%X) -> p(%X, shuffle(%X))
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to HRS union beta 16688