/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.

  B : [] --> o 
  BF : [] --> o 
  F : [] --> o 
  FS : [] --> o 
  S : [] --> o 
  busy : [o * o * o * o * o * o * o] --> o 
  closed : [] --> o 
  correct : [] --> o 
  down : [] --> o 
  empty : [] --> o 
  false : [] --> o 
  idle : [o * o * o * o * o * o * o] --> o 
  incorrect : [] --> o 
  newbuttons : [o * o * o * o] --> o 
  open : [] --> o 
  or : [o * o] --> o 
  start : [o] --> o 
  stop : [] --> o 
  true : [] --> o 
  up : [] --> o 

  start(X) => busy(F, closed, stop, false, false, false, X) 
  busy(BF, X, stop, Y, Z, U, V) => incorrect 
  busy(FS, X, stop, Y, Z, U, V) => incorrect 
  busy(X, open, up, Y, Z, U, V) => incorrect 
  busy(X, open, down, Y, Z, U, V) => incorrect 
  busy(B, closed, stop, false, false, false, empty) => correct 
  busy(F, closed, stop, false, false, false, empty) => correct 
  busy(S, closed, stop, false, false, false, empty) => correct 
  busy(B, closed, stop, false, false, false, newbuttons(X, Y, Z, U)) => idle(B, closed, stop, false, false, false, newbuttons(X, Y, Z, U)) 
  busy(F, closed, stop, false, false, false, newbuttons(X, Y, Z, U)) => idle(F, closed, stop, false, false, false, newbuttons(X, Y, Z, U)) 
  busy(S, closed, stop, false, false, false, newbuttons(X, Y, Z, U)) => idle(S, closed, stop, false, false, false, newbuttons(X, Y, Z, U)) 
  busy(B, open, stop, false, X, Y, Z) => idle(B, closed, stop, false, X, Y, Z) 
  busy(F, open, stop, X, false, Y, Z) => idle(F, closed, stop, X, false, Y, Z) 
  busy(S, open, stop, X, Y, false, Z) => idle(S, closed, stop, X, Y, false, Z) 
  busy(B, X, stop, true, Y, Z, U) => idle(B, open, stop, false, Y, Z, U) 
  busy(F, X, stop, Y, true, Z, U) => idle(F, open, stop, Y, false, Z, U) 
  busy(S, X, stop, Y, Z, true, U) => idle(S, open, stop, Y, Z, false, U) 
  busy(B, closed, down, X, Y, Z, U) => idle(B, closed, stop, X, Y, Z, U) 
  busy(S, closed, up, X, Y, Z, U) => idle(S, closed, stop, X, Y, Z, U) 
  busy(B, closed, up, true, X, Y, Z) => idle(B, closed, stop, true, X, Y, Z) 
  busy(F, closed, up, X, true, Y, Z) => idle(F, closed, stop, X, true, Y, Z) 
  busy(F, closed, down, X, true, Y, Z) => idle(F, closed, stop, X, true, Y, Z) 
  busy(S, closed, down, X, Y, true, Z) => idle(S, closed, stop, X, Y, true, Z) 
  busy(B, closed, up, false, X, Y, Z) => idle(BF, closed, up, false, X, Y, Z) 
  busy(F, closed, up, X, false, Y, Z) => idle(FS, closed, up, X, false, Y, Z) 
  busy(F, closed, down, X, false, Y, Z) => idle(BF, closed, down, X, false, Y, Z) 
  busy(S, closed, down, X, Y, false, Z) => idle(FS, closed, down, X, Y, false, Z) 
  busy(BF, closed, up, X, Y, Z, U) => idle(F, closed, up, X, Y, Z, U) 
  busy(BF, closed, down, X, Y, Z, U) => idle(B, closed, down, X, Y, Z, U) 
  busy(FS, closed, up, X, Y, Z, U) => idle(S, closed, up, X, Y, Z, U) 
  busy(FS, closed, down, X, Y, Z, U) => idle(F, closed, down, X, Y, Z, U) 
  busy(B, closed, stop, false, true, X, Y) => idle(B, closed, up, false, true, X, Y) 
  busy(B, closed, stop, false, false, true, X) => idle(B, closed, up, false, false, true, X) 
  busy(F, closed, stop, true, false, X, Y) => idle(F, closed, down, true, false, X, Y) 
  busy(F, closed, stop, false, false, true, X) => idle(F, closed, up, false, false, true, X) 
  busy(S, closed, stop, X, true, false, Y) => idle(S, closed, down, X, true, false, Y) 
  busy(S, closed, stop, true, false, false, X) => idle(S, closed, down, true, false, false, X) 
  idle(X, Y, Z, U, V, W, empty) => busy(X, Y, Z, U, V, W, empty) 
  idle(X, Y, Z, U, V, W, newbuttons(Q, R, T, X')) => busy(X, Y, Z, or(U, Q), or(V, R), or(W, T), X') 
  or(true, X) => true 
  or(false, X) => 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:

  B : [] --> ee 
  BF : [] --> ee 
  F : [] --> ee 
  FS : [] --> ee 
  S : [] --> ee 
  busy : [ee * lc * uy * naa * naa * naa * tz] --> jaa 
  closed : [] --> lc 
  correct : [] --> jaa 
  down : [] --> uy 
  empty : [] --> tz 
  false : [] --> naa 
  idle : [ee * lc * uy * naa * naa * naa * tz] --> jaa 
  incorrect : [] --> jaa 
  newbuttons : [naa * naa * naa * tz] --> tz 
  open : [] --> lc 
  or : [naa * naa] --> naa 
  start : [tz] --> jaa 
  stop : [] --> uy 
  true : [] --> naa 
  up : [] --> uy 


+++ 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.