Transformation Between Regular Expressions and omega-Automata

Authors Christof Löding, Andreas Tollkötter



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.88.pdf
  • Filesize: 499 kB
  • 13 pages

Document Identifiers

Author Details

Christof Löding
Andreas Tollkötter

Cite AsGet BibTex

Christof Löding and Andreas Tollkötter. Transformation Between Regular Expressions and omega-Automata. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 88:1-88:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.88

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.
Keywords
  • infinity regular expressions
  • parity automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Anne Brüggemann-Klein. Regular expressions into finite automata. Theor. Comput. Sci., 120(2):197-213, 1993. URL: http://dx.doi.org/10.1016/0304-3975(93)90287-4.
  2. Anne Brüggemann-Klein and Derick Wood. One-unambiguous regular languages. Inf. Comput., 140(2):229-253, 1998. URL: http://dx.doi.org/10.1006/inco.1997.2688.
  3. Janusz A Brzozowski and Edward J McCluskey. Signal flow graph techniques for sequential circuit state diagrams. IEEE Transactions on Electronic Computers, 12(2):67-76, 1963. Google Scholar
  4. Olivier Carton and Ramón Maceiras. Computing the Rabin index of a parity automaton. RAIRO Theoretical Informatics and Applications, 33(6):495-506, 1999. Google Scholar
  5. Michael J. Fischer and Richard E. Ladner. Propositional dynamic logic of regular programs. J. Comput. Syst. Sci., 18(2):194-211, 1979. URL: http://dx.doi.org/10.1016/0022-0000(79)90046-1.
  6. Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. Automata, Logics, and Infinite Games, volume 2500 of Lecture Notes in Computer Science. Springer, 2002. Google Scholar
  7. John E. Hopcroft and Jeffrey D. Ullman. Formal Languages and their Relation to Automata. Addison-Wesley, 1969. Google Scholar
  8. Bakhadyr Khoussainov and Anil Nerode. Automata theory and its applications, volume 21 of Progress in Computer Science and Applied Logic. Birkhäuser, 2001. Google Scholar
  9. Orna Kupferman and Moshe Y. Vardi. Safraless decision procedures. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pages 531-542. IEEE Computer Society, 2005. URL: http://dx.doi.org/10.1109/SFCS.2005.66.
  10. Martin Leucker and César Sánchez. Regular linear temporal logic. In Theoretical Aspects of Computing - ICTAC 2007, 4th International Colloquium, Macau, China, September 26-28, 2007, Proceedings, volume 4711 of Lecture Notes in Computer Science, pages 291-305. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-75292-9_20.
  11. Dominique Perrin and Jean-Éric Pin. Semigroups and automata on infinite words. In NATO Advanced Study Institute Semigroups, Formal Languages and Groups. Kluwer academic publishers, 1995. Google Scholar
  12. Dominique Perrin and Jean-Éric Pin. Infinite words : automata, semigroups, logic and games. Pure and applied mathematics. Academic, London, San Diego (Calif.), 2004. URL: http://opac.inria.fr/record=b1100620.
  13. IEEE Standard for Property Specification Language (PSL) IEEE Std 1850-2005 (2005). Google Scholar
  14. Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997. Google Scholar
  15. Wolfgang Thomas. Automata on infinite objects. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pages 133-192. Elsevier Science Publishers, 1990. Google Scholar
  16. Wolfgang Thomas. Languages, automata, and logic. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, Vol. 3, pages 389-455. Springer-Verlag New York, Inc., New York, NY, USA, 1997. URL: http://dl.acm.org/citation.cfm?id=267871.267878.
  17. Andreas Tollkötter. Transformations between regular expressions and ω-automata. Bachelor Thesis, RWTH Aachen, Germany, 2015. Available on URL: https://www.lii.rwth-aachen.de/images/Mitarbeiter/pub/loeding/tollkoetter15-bsc.pdf.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail