details

property	value
status	complete
benchmark	thiemann30.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n056.star.cs.uiowa.edu
space	AProVE_07

run statistics

property	value
solver	Wanda
configuration	FirstOrder
runtime (wallclock)	0.881341934204 seconds
cpu usage	0.878435695
max memory	4.7202304E7

stage attributes

key	value
output-size	3057
starexec-result	MAYBE

output

/export/starexec/sandbox2/solver/bin/starexec_run_FirstOrder /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE We consider the system theBenchmark. We are asked to determine termination of the following first-order TRS. 0 : [] --> o add : [o * o] --> o app : [o * o] --> o eq : [o * o] --> o false : [] --> o head : [o] --> o if!6220min : [o * o * o * o] --> o if!6220minsort : [o * o * o] --> o if!6220rm : [o * o * o] --> o le : [o * o] --> o min : [o] --> o minIter : [o * o * o] --> o minsort : [o * o] --> o nil : [] --> o null : [o] --> o rm : [o * o] --> o s : [o] --> o tail : [o] --> o true : [] --> o eq(0, 0) => true eq(0, s(X)) => false eq(s(X), 0) => false eq(s(X), s(Y)) => eq(X, Y) le(0, X) => true le(s(X), 0) => false le(s(X), s(Y)) => le(X, Y) app(nil, X) => X app(add(X, Y), Z) => add(X, app(Y, Z)) min(nil) => 0 min(add(X, Y)) => minIter(add(X, Y), add(X, Y), 0) minIter(nil, add(X, Y), Z) => minIter(add(X, Y), add(X, Y), s(Z)) minIter(add(X, Y), Z, U) => if!6220min(le(X, U), Y, Z, U) if!6220min(true, X, Y, Z) => Z if!6220min(false, X, Y, Z) => minIter(X, Y, Z) head(add(X, Y)) => X tail(add(X, Y)) => Y tail(nil) => nil null(nil) => true null(add(X, Y)) => false rm(X, nil) => nil rm(X, add(Y, Z)) => if!6220rm(eq(X, Y), X, add(Y, Z)) if!6220rm(true, X, add(Y, Z)) => rm(X, Z) if!6220rm(false, X, add(Y, Z)) => add(Y, rm(X, Z)) minsort(nil, nil) => nil minsort(add(X, Y), Z) => if!6220minsort(eq(X, min(add(X, Y))), add(X, Y), Z) if!6220minsort(true, add(X, Y), Z) => add(X, minsort(app(rm(X, Y), Z), nil)) if!6220minsort(false, add(X, Y), Z) => minsort(Y, add(X, Z)) 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 : [] --> gk add : [gk * gk] --> gk app : [gk * gk] --> gk eq : [gk * gk] --> zi false : [] --> zi head : [gk] --> gk if!6220min : [zi * gk * gk * gk] --> gk if!6220minsort : [zi * gk * gk] --> gk if!6220rm : [zi * gk * gk] --> gk le : [gk * gk] --> zi min : [gk] --> gk minIter : [gk * gk * gk] --> gk minsort : [gk * gk] --> gk nil : [] --> gk null : [gk] --> zi rm : [gk * gk] --> gk s : [gk] --> gk tail : [gk] --> gk true : [] --> zi +++ Citations +++ [FuhGieParSchSwi11] C. Fuhs, J. Giesl, M. Parting, P. Schneider-Kamp, and S. Swiderski. Proving Termination by Dependency Pairs and Inductive Theorem Proving. In volume 47(2) of Journal of Automated Reasoning. 133--160, 2011. [Gra95] B. Gramlich. Abstract Relations Between Restricted Termination and Confluence Properties of Rewrite Systems. In volume 24(1-2) of Fundamentae Informaticae. 3--23, 1995. popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to TRS Stand 20472