Bounds in w-Regularity

Abstract

We consider an extension of w-regular expressions where two new variants of the Kleene star L* are added: LB and L^S. These exponents act as the standard star, but restrict the number of iterations to be bounded (for LB) or to tend toward infinity (for L^S). These expressions can define languages that are not w-regular. We develop a theory for these languages. We study the decidability and closure questions. We also define an equivalent automaton model, extending Buchi automata. This culminates with a -- partial -- complementation result.