Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
TRS Stand 20472 pair #381714684
details
property
value
status
complete
benchmark
PALINDROME_nosorts_noand_C.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n013.star.cs.uiowa.edu
space
Transformed_CSR_04
run statistics
property
value
solver
Wanda
configuration
FirstOrder
runtime (wallclock)
0.313899040222 seconds
cpu usage
0.309688926
max memory
7069696.0
stage attributes
key
value
output-size
18959
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. !6220!6220 : [o * o] --> o U11 : [o] --> o U12 : [o] --> o active : [o] --> o isNePal : [o] --> o mark : [o] --> o nil : [] --> o ok : [o] --> o proper : [o] --> o top : [o] --> o tt : [] --> o active(!6220!6220(!6220!6220(X, Y), Z)) => mark(!6220!6220(X, !6220!6220(Y, Z))) active(!6220!6220(X, nil)) => mark(X) active(!6220!6220(nil, X)) => mark(X) active(U11(tt)) => mark(U12(tt)) active(U12(tt)) => mark(tt) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) => mark(U11(tt)) active(!6220!6220(X, Y)) => !6220!6220(active(X), Y) active(!6220!6220(X, Y)) => !6220!6220(X, active(Y)) active(U11(X)) => U11(active(X)) active(U12(X)) => U12(active(X)) active(isNePal(X)) => isNePal(active(X)) !6220!6220(mark(X), Y) => mark(!6220!6220(X, Y)) !6220!6220(X, mark(Y)) => mark(!6220!6220(X, Y)) U11(mark(X)) => mark(U11(X)) U12(mark(X)) => mark(U12(X)) isNePal(mark(X)) => mark(isNePal(X)) proper(!6220!6220(X, Y)) => !6220!6220(proper(X), proper(Y)) proper(nil) => ok(nil) proper(U11(X)) => U11(proper(X)) proper(tt) => ok(tt) proper(U12(X)) => U12(proper(X)) proper(isNePal(X)) => isNePal(proper(X)) !6220!6220(ok(X), ok(Y)) => ok(!6220!6220(X, Y)) U11(ok(X)) => ok(U11(X)) U12(ok(X)) => ok(U12(X)) isNePal(ok(X)) => ok(isNePal(X)) top(mark(X)) => top(proper(X)) top(ok(X)) => top(active(X)) We use rule removal, following [Kop12, Theorem 2.23]. This gives the following requirements (possibly using Theorems 2.25 and 2.26 in [Kop12]): active(!6220!6220(!6220!6220(X, Y), Z)) >? mark(!6220!6220(X, !6220!6220(Y, Z))) active(!6220!6220(X, nil)) >? mark(X) active(!6220!6220(nil, X)) >? mark(X) active(U11(tt)) >? mark(U12(tt)) active(U12(tt)) >? mark(tt) active(isNePal(!6220!6220(X, !6220!6220(Y, X)))) >? mark(U11(tt)) active(!6220!6220(X, Y)) >? !6220!6220(active(X), Y) active(!6220!6220(X, Y)) >? !6220!6220(X, active(Y)) active(U11(X)) >? U11(active(X)) active(U12(X)) >? U12(active(X)) active(isNePal(X)) >? isNePal(active(X)) !6220!6220(mark(X), Y) >? mark(!6220!6220(X, Y)) !6220!6220(X, mark(Y)) >? mark(!6220!6220(X, Y)) U11(mark(X)) >? mark(U11(X)) U12(mark(X)) >? mark(U12(X)) isNePal(mark(X)) >? mark(isNePal(X)) proper(!6220!6220(X, Y)) >? !6220!6220(proper(X), proper(Y)) proper(nil) >? ok(nil) proper(U11(X)) >? U11(proper(X)) proper(tt) >? ok(tt) proper(U12(X)) >? U12(proper(X)) proper(isNePal(X)) >? isNePal(proper(X)) !6220!6220(ok(X), ok(Y)) >? ok(!6220!6220(X, Y)) U11(ok(X)) >? ok(U11(X)) U12(ok(X)) >? ok(U12(X)) isNePal(ok(X)) >? ok(isNePal(X)) top(mark(X)) >? top(proper(X)) top(ok(X)) >? top(active(X)) We orient these requirements with a polynomial interpretation in the natural numbers. The following interpretation satisfies the requirements: !6220!6220 = \y0y1.y1 + 2y0 U11 = \y0.y0 U12 = \y0.2y0 active = \y0.y0 isNePal = \y0.y0 mark = \y0.y0 nil = 1 ok = \y0.y0 proper = \y0.y0 top = \y0.y0 tt = 0
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to TRS Stand 20472