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.FSTTCS.2015.112
URN: urn:nbn:de:0030-drops-56200
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5620/
Go to the corresponding LIPIcs Volume Portal

Fleischer, Lukas ; Kufleitner, Manfred

Efficient Algorithms for Morphisms over Omega-Regular Languages

pdf-format:
4.pdf (0.4 MB)

Abstract

Morphisms to finite semigroups can be used for recognizing omega-regular languages. The so-called strongly recognizing morphisms can be seen as a deterministic computation model which provides minimal objects (known as the syntactic morphism) and a trivial complementation procedure. We give a quadratic-time algorithm for computing the syntactic morphism from any given strongly recognizing morphism, thereby showing that minimization is easy as well. In addition, we give algorithms for efficiently solving various decision problems for weakly recognizing morphisms. Weakly recognizing morphism are often smaller than their strongly recognizing counterparts. Finally, we describe the language operations needed for converting formulas in monadic second-order logic (MSO) into strongly recognizing morphisms, and we give some experimental results.

BibTeX - Entry

@InProceedings{fleischer_et_al:LIPIcs:2015:5620,
  author =	{Lukas Fleischer and Manfred Kufleitner},
  title =	{{Efficient Algorithms for Morphisms over Omega-Regular Languages}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{112--124},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Prahladh Harsha and G. Ramalingam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5620},
  URN =		{urn:nbn:de:0030-drops-56200},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.112},
  annote =	{Keywords: B{\"u}chi automata, omega-regular language, syntactic semigroup, recognizing morphism, MSO}
}

Keywords: Büchi automata, omega-regular language, syntactic semigroup, recognizing morphism, MSO
Collection: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Issue Date: 2015
Date of publication: 14.12.2015

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