License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.88
URN: urn:nbn:de:0030-drops-64962
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6496/
Go to the corresponding LIPIcs Volume Portal

Löding, Christof ; Tollkötter, Andreas

Transformation Between Regular Expressions and omega-Automata

pdf-format:
LIPIcs-MFCS-2016-88.pdf (0.5 MB)

Abstract

We propose a new definition of regular expressions for describing languages of omega-words, called infinity-regular expressions. These expressions are obtained by adding to the standard regular expression on finite words an operator infinity that acts similar to the Kleene-star but can be iterated finitely or infinitely often (as opposed to the omega-operator from standard omega-regular expressions, which has to be iterated infinitely often). We show that standard constructions between automata and regular expressions for finite words can smoothly be adapted to infinite words in this setting: We extend the Glushkov construction yielding a simple translation of infinity-regular expressions into parity automata, and we show how to translate parity automata into infinity-regular expressions by the classical state elimination technique, where in both cases the nesting of the * and the infinity operators corresponds to the priority range used in the parity automaton. We also briefly discuss the concept of deterministic expressions that directly transfers from standard regular expressions to infinity-regular expressions.

BibTeX - Entry

@InProceedings{lding_et_al:LIPIcs:2016:6496,
  author =	{Christof L{\"o}ding and Andreas Tollk{\"o}tter},
  title =	{{Transformation Between Regular Expressions and omega-Automata}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{88:1--88:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6496},
  URN =		{urn:nbn:de:0030-drops-64962},
  doi =		{10.4230/LIPIcs.MFCS.2016.88},
  annote =	{Keywords: infinity regular expressions, parity automata}
}

Keywords: infinity regular expressions, parity automata
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI