buechihom.FSTTCS15.final.pdf (431.27 kB)
Efficient algorithms for morphisms over omega-regular languages
conference contributionposted on 2018-02-23, 14:23 authored by Lukas Fleischer, Manfred Kufleitner
© Lukas Fleischer and Manfred Kufleitner;. Morphisms to finite semigroups can be used for recognizing omega-regular languages. The socalled 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.
This work was supported by the DFG grants DI 435/5-2 and KU 2716/1-1.
- Computer Science
Published inLeibniz International Proceedings in Informatics, LIPIcs
Pages112 - 124
CitationFLEISCHER, L. and KUFLEITNER, M., 2015. Efficient algorithms for morphisms over omega-regular languages. Presented at the 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015), Bangalore. December 16–18th, pp. 112-124.
PublisherSchloss Dagstuhl – Leibniz Center for Informatics
- AM (Accepted Manuscript)
Publisher statementThis work is made available according to the conditions of the Creative Commons Attribution 4.0 International (CC BY 4.0) licence. Full details of this licence are available at: http://creativecommons.org/licenses/ by/4.0/
NotesThis is an Open Access Article. It is published by Schloss Dagstuhl – Leibniz Center for Informatics under the Creative Commons Attribution 4.0 Unported Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/4.0/
Book seriesLeibniz International Proceedings in Informatics, LIPIcs;45