Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381712931
details
property
value
status
complete
benchmark
rta3.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n081.star.cs.uiowa.edu
space
AProVE_04
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.126909017563 seconds
cpu usage
0.097069287
max memory
4354048.0
stage attributes
key
value
output-size
5178
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 ack : [o * o] --> o f : [o * o] --> o s : [o] --> o ack(0, X) => s(X) ack(s(X), 0) => ack(X, s(0)) ack(s(X), s(Y)) => ack(X, ack(s(X), Y)) f(s(X), Y) => f(X, s(X)) f(X, s(Y)) => f(Y, X) f(X, Y) => ack(X, Y) ack(s(X), Y) => f(X, X) 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] ack#(s(X), 0) =#> ack#(X, s(0)) 1] ack#(s(X), s(Y)) =#> ack#(X, ack(s(X), Y)) 2] ack#(s(X), s(Y)) =#> ack#(s(X), Y) 3] f#(s(X), Y) =#> f#(X, s(X)) 4] f#(X, s(Y)) =#> f#(Y, X) 5] f#(X, Y) =#> ack#(X, Y) 6] ack#(s(X), Y) =#> f#(X, X) Rules R_0: ack(0, X) => s(X) ack(s(X), 0) => ack(X, s(0)) ack(s(X), s(Y)) => ack(X, ack(s(X), Y)) f(s(X), Y) => f(X, s(X)) f(X, s(Y)) => f(Y, X) f(X, Y) => ack(X, Y) ack(s(X), Y) => f(X, X) 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: ack#(s(X), 0) >? ack#(X, s(0)) ack#(s(X), s(Y)) >? ack#(X, ack(s(X), Y)) ack#(s(X), s(Y)) >? ack#(s(X), Y) f#(s(X), Y) >? f#(X, s(X)) f#(X, s(Y)) >? f#(Y, X) f#(X, Y) >? ack#(X, Y) ack#(s(X), Y) >? f#(X, X) ack(0, X) >= s(X) ack(s(X), 0) >= ack(X, s(0)) ack(s(X), s(Y)) >= ack(X, ack(s(X), Y)) f(s(X), Y) >= f(X, s(X)) f(X, s(Y)) >= f(Y, X) f(X, Y) >= ack(X, Y) ack(s(X), Y) >= f(X, X) We orient these requirements with a polynomial interpretation in the natural numbers. We consider usable_rules with respect to the following argument filtering: ack#(x_1,x_2) = ack#(x_1) This leaves the following ordering requirements: ack#(s(X), 0) > ack#(X, s(0)) ack#(s(X), s(Y)) >= ack#(X, ack(s(X), Y)) ack#(s(X), s(Y)) >= ack#(s(X), Y) f#(s(X), Y) >= f#(X, s(X)) f#(X, s(Y)) >= f#(Y, X) f#(X, Y) >= ack#(X, Y) ack#(s(X), Y) >= f#(X, X) The following interpretation satisfies the requirements: 0 = 0 ack = \y0y1.0 ack# = \y0y1.y0 f = \y0y1.0 f# = \y0y1.y1 + 2y0 s = \y0.1 + 3y0 Using this interpretation, the requirements translate to: [[ack#(s(_x0), 0)]] = 1 + 3x0 > x0 = [[ack#(_x0, s(0))]] [[ack#(s(_x0), s(_x1))]] = 1 + 3x0 > x0 = [[ack#(_x0, ack(s(_x0), _x1))]] [[ack#(s(_x0), s(_x1))]] = 1 + 3x0 >= 1 + 3x0 = [[ack#(s(_x0), _x1)]] [[f#(s(_x0), _x1)]] = 2 + x1 + 6x0 > 1 + 5x0 = [[f#(_x0, s(_x0))]]
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472