Paper: Omega-Regular Expressions with Bounds (at LICS 2006)

Authors: Mikołaj Bojańczyk Thomas Colcombet

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.

BibTeX

  @InProceedings{BojaczykColcombet-OmegaRegularExpress,
    author = 	 {Mikołaj Bojańczyk and Thomas Colcombet},
    title = 	 {Omega-Regular Expressions with Bounds},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {285--294},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }