Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381710248
details
property
value
status
complete
benchmark
cime1.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n016.star.cs.uiowa.edu
space
Secret_05_TRS
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
22.8112671375 seconds
cpu usage
22.775441275
max memory
3.27012352E8
stage attributes
key
value
output-size
27007
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. circ : [o * o] --> o cons : [o * o] --> o id : [] --> o lift : [] --> o msubst : [o * o] --> o sop : [o] --> o sortSu : [o] --> o subst : [o * o] --> o te : [o] --> o sortSu(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) => sortSu(cons(te(msubst(te(X), sortSu(Z))), sortSu(circ(sortSu(Y), sortSu(Z))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) => sortSu(cons(te(Y), sortSu(circ(sortSu(X), sortSu(Z))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) => sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))) sortSu(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) => sortSu(circ(sortSu(X), sortSu(circ(sortSu(Y), sortSu(Z))))) sortSu(circ(sortSu(X), sortSu(id))) => sortSu(X) sortSu(circ(sortSu(id), sortSu(X))) => sortSu(X) sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) => sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))), sortSu(Z))) te(subst(te(X), sortSu(id))) => te(X) te(msubst(te(X), sortSu(id))) => te(X) te(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) => te(msubst(te(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 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] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(cons(te(msubst(te(X), sortSu(Z))), sortSu(circ(sortSu(Y), sortSu(Z))))) 1] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> te#(msubst(te(X), sortSu(Z))) 2] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> te#(X) 3] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z) 4] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(Y), sortSu(Z))) 5] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Y) 6] sortSu#(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z) 7] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(cons(te(Y), sortSu(circ(sortSu(X), sortSu(Z))))) 8] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> te#(Y) 9] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(circ(sortSu(X), sortSu(Z))) 10] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(X) 11] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) =#> sortSu#(Z) 12] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))) 13] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(circ(sortSu(X), sortSu(Y))) 14] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(X) 15] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) =#> sortSu#(Y) 16] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 17] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(X) 18] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(Y), sortSu(Z))) 19] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Y) 20] sortSu#(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z) 21] sortSu#(circ(sortSu(X), sortSu(id))) =#> sortSu#(X) 22] sortSu#(circ(sortSu(id), sortSu(X))) =#> sortSu#(X) 23] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))), sortSu(Z))) 24] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))) 25] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(circ(sortSu(X), sortSu(Y))) 26] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(X) 27] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(Y) 28] sortSu#(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) =#> sortSu#(Z) 29] te#(subst(te(X), sortSu(id))) =#> te#(X) 30] te#(msubst(te(X), sortSu(id))) =#> te#(X) 31] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> te#(msubst(te(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 32] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> te#(X) 33] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(circ(sortSu(Y), sortSu(Z))) 34] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Y) 35] te#(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) =#> sortSu#(Z) Rules R_0: sortSu(circ(sortSu(cons(te(X), sortSu(Y))), sortSu(Z))) => sortSu(cons(te(msubst(te(X), sortSu(Z))), sortSu(circ(sortSu(Y), sortSu(Z))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(te(Y), sortSu(Z))))) => sortSu(cons(te(Y), sortSu(circ(sortSu(X), sortSu(Z))))) sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(cons(sop(lift), sortSu(Y))))) => sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))) sortSu(circ(sortSu(circ(sortSu(X), sortSu(Y))), sortSu(Z))) => sortSu(circ(sortSu(X), sortSu(circ(sortSu(Y), sortSu(Z))))) sortSu(circ(sortSu(X), sortSu(id))) => sortSu(X) sortSu(circ(sortSu(id), sortSu(X))) => sortSu(X) sortSu(circ(sortSu(cons(sop(lift), sortSu(X))), sortSu(circ(sortSu(cons(sop(lift), sortSu(Y))), sortSu(Z))))) => sortSu(circ(sortSu(cons(sop(lift), sortSu(circ(sortSu(X), sortSu(Y))))), sortSu(Z))) te(subst(te(X), sortSu(id))) => te(X) te(msubst(te(X), sortSu(id))) => te(X) te(msubst(te(msubst(te(X), sortSu(Y))), sortSu(Z))) => te(msubst(te(X), sortSu(circ(sortSu(Y), sortSu(Z))))) 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 : * 1 : 30, 31, 32, 33, 34, 35 * 2 : 29, 30, 31, 32, 33, 34, 35 * 3 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 * 4 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 * 5 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472