Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381714507
details
property
value
status
complete
benchmark
Ex9_BLR02_GM.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n030.star.cs.uiowa.edu
space
Transformed_CSR_04
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.592785835266 seconds
cpu usage
0.590346603
max memory
1.6482304E7
stage attributes
key
value
output-size
24262
starexec-result
YES
output
/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o a!6220!6220filter : [o * o * o] --> o a!6220!6220nats : [o] --> o a!6220!6220sieve : [o] --> o a!6220!6220zprimes : [] --> o cons : [o * o] --> o filter : [o * o * o] --> o mark : [o] --> o nats : [o] --> o s : [o] --> o sieve : [o] --> o zprimes : [] --> o a!6220!6220filter(cons(X, Y), 0, Z) => cons(0, filter(Y, Z, Z)) a!6220!6220filter(cons(X, Y), s(Z), U) => cons(mark(X), filter(Y, Z, U)) a!6220!6220sieve(cons(0, X)) => cons(0, sieve(X)) a!6220!6220sieve(cons(s(X), Y)) => cons(s(mark(X)), sieve(filter(Y, X, X))) a!6220!6220nats(X) => cons(mark(X), nats(s(X))) a!6220!6220zprimes => a!6220!6220sieve(a!6220!6220nats(s(s(0)))) mark(filter(X, Y, Z)) => a!6220!6220filter(mark(X), mark(Y), mark(Z)) mark(sieve(X)) => a!6220!6220sieve(mark(X)) mark(nats(X)) => a!6220!6220nats(mark(X)) mark(zprimes) => a!6220!6220zprimes mark(cons(X, Y)) => cons(mark(X), Y) mark(0) => 0 mark(s(X)) => s(mark(X)) a!6220!6220filter(X, Y, Z) => filter(X, Y, Z) a!6220!6220sieve(X) => sieve(X) a!6220!6220nats(X) => nats(X) a!6220!6220zprimes => zprimes We use the dependency pair framework as described in [Kop12, Ch. 6/7], with static dependency pairs (see [KusIsoSakBla09] and the adaptation for AFSMs in [Kop12, Ch. 7.8]). We thus obtain the following dependency pair problem (P_0, R_0, minimal, formative): Dependency Pairs P_0: 0] a!6220!6220filter#(cons(X, Y), s(Z), U) =#> mark#(X) 1] a!6220!6220sieve#(cons(s(X), Y)) =#> mark#(X) 2] a!6220!6220nats#(X) =#> mark#(X) 3] a!6220!6220zprimes# =#> a!6220!6220sieve#(a!6220!6220nats(s(s(0)))) 4] a!6220!6220zprimes# =#> a!6220!6220nats#(s(s(0))) 5] mark#(filter(X, Y, Z)) =#> a!6220!6220filter#(mark(X), mark(Y), mark(Z)) 6] mark#(filter(X, Y, Z)) =#> mark#(X) 7] mark#(filter(X, Y, Z)) =#> mark#(Y) 8] mark#(filter(X, Y, Z)) =#> mark#(Z) 9] mark#(sieve(X)) =#> a!6220!6220sieve#(mark(X)) 10] mark#(sieve(X)) =#> mark#(X) 11] mark#(nats(X)) =#> a!6220!6220nats#(mark(X)) 12] mark#(nats(X)) =#> mark#(X) 13] mark#(zprimes) =#> a!6220!6220zprimes# 14] mark#(cons(X, Y)) =#> mark#(X) 15] mark#(s(X)) =#> mark#(X) Rules R_0: a!6220!6220filter(cons(X, Y), 0, Z) => cons(0, filter(Y, Z, Z)) a!6220!6220filter(cons(X, Y), s(Z), U) => cons(mark(X), filter(Y, Z, U)) a!6220!6220sieve(cons(0, X)) => cons(0, sieve(X)) a!6220!6220sieve(cons(s(X), Y)) => cons(s(mark(X)), sieve(filter(Y, X, X))) a!6220!6220nats(X) => cons(mark(X), nats(s(X))) a!6220!6220zprimes => a!6220!6220sieve(a!6220!6220nats(s(s(0)))) mark(filter(X, Y, Z)) => a!6220!6220filter(mark(X), mark(Y), mark(Z)) mark(sieve(X)) => a!6220!6220sieve(mark(X)) mark(nats(X)) => a!6220!6220nats(mark(X)) mark(zprimes) => a!6220!6220zprimes mark(cons(X, Y)) => cons(mark(X), Y) mark(0) => 0 mark(s(X)) => s(mark(X)) a!6220!6220filter(X, Y, Z) => filter(X, Y, Z) a!6220!6220sieve(X) => sieve(X) a!6220!6220nats(X) => nats(X) a!6220!6220zprimes => zprimes 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 will use the reduction pair processor [Kop12, Thm. 7.16]. It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: a!6220!6220filter#(cons(X, Y), s(Z), U) >? mark#(X) a!6220!6220sieve#(cons(s(X), Y)) >? mark#(X) a!6220!6220nats#(X) >? mark#(X) a!6220!6220zprimes# >? a!6220!6220sieve#(a!6220!6220nats(s(s(0)))) a!6220!6220zprimes# >? a!6220!6220nats#(s(s(0))) mark#(filter(X, Y, Z)) >? a!6220!6220filter#(mark(X), mark(Y), mark(Z)) mark#(filter(X, Y, Z)) >? mark#(X) mark#(filter(X, Y, Z)) >? mark#(Y) mark#(filter(X, Y, Z)) >? mark#(Z)
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472