Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381711562
details
property
value
status
complete
benchmark
#4.33.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n095.star.cs.uiowa.edu
space
Strategy_removed_AG01
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.14820098877 seconds
cpu usage
0.14084132
max memory
6275072.0
stage attributes
key
value
output-size
6356
starexec-result
YES
output
/export/starexec/sandbox/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o cons : [o * o] --> o nil : [] --> o s : [o] --> o sum : [o * o] --> o weight : [o] --> o sum(cons(s(X), Y), cons(Z, U)) => sum(cons(X, Y), cons(s(Z), U)) sum(cons(0, X), Y) => sum(X, Y) sum(nil, X) => X weight(cons(X, cons(Y, Z))) => weight(sum(cons(X, cons(Y, Z)), cons(0, Z))) weight(cons(X, nil)) => X As the system is orthogonal, it is terminating if it is innermost terminating by [Gra95]. Then, by [FuhGieParSchSwi11], it suffices to prove (innermost) termination of the typed system, with sort annotations chosen to respect the rules, as follows: 0 : [] --> ea cons : [ea * nb] --> nb nil : [] --> nb s : [ea] --> ea sum : [nb * nb] --> nb weight : [nb] --> ea 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] sum#(cons(s(X), Y), cons(Z, U)) =#> sum#(cons(X, Y), cons(s(Z), U)) 1] sum#(cons(0, X), Y) =#> sum#(X, Y) 2] weight#(cons(X, cons(Y, Z))) =#> weight#(sum(cons(X, cons(Y, Z)), cons(0, Z))) 3] weight#(cons(X, cons(Y, Z))) =#> sum#(cons(X, cons(Y, Z)), cons(0, Z)) Rules R_0: sum(cons(s(X), Y), cons(Z, U)) => sum(cons(X, Y), cons(s(Z), U)) sum(cons(0, X), Y) => sum(X, Y) sum(nil, X) => X weight(cons(X, cons(Y, Z))) => weight(sum(cons(X, cons(Y, Z)), cons(0, Z))) weight(cons(X, nil)) => 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 place the elements of P in a dependency graph approximation G (see e.g. [Kop12, Thm. 7.27, 7.29], as follows: * 0 : 0, 1 * 1 : 0, 1 * 2 : 2, 3 * 3 : 0, 1 This graph has the following strongly connected components: P_1: sum#(cons(s(X), Y), cons(Z, U)) =#> sum#(cons(X, Y), cons(s(Z), U)) sum#(cons(0, X), Y) =#> sum#(X, Y) P_2: weight#(cons(X, cons(Y, Z))) =#> weight#(sum(cons(X, cons(Y, Z)), cons(0, Z))) By [Kop12, Thm. 7.31], we may replace any dependency pair problem (P_0, R_0, m, f) by (P_1, R_0, m, f) and (P_2, R_0, m, f). Thus, the original system is terminating if each of (P_1, R_0, minimal, formative) and (P_2, R_0, minimal, formative) is finite. We consider the dependency pair problem (P_2, R_0, minimal, formative). We will use the reduction pair processor with usable rules [Kop12, Thm. 7.44]. The usable rules of (P_2, R_0) are: sum(cons(s(X), Y), cons(Z, U)) => sum(cons(X, Y), cons(s(Z), U)) sum(cons(0, X), Y) => sum(X, Y) sum(nil, X) => X It suffices to find a standard reduction pair [Kop12, Def. 6.69]. Thus, we must orient: weight#(cons(X, cons(Y, Z))) >? weight#(sum(cons(X, cons(Y, Z)), cons(0, Z))) sum(cons(s(X), Y), cons(Z, U)) >= sum(cons(X, Y), cons(s(Z), U)) sum(cons(0, X), Y) >= sum(X, Y) sum(nil, X) >= X We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: 0 = 0 cons = \y0y1.3 + y1 nil = 0
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472