buechihom.FSTTCS15.final.pdf (431.27 kB)
Download fileEfficient algorithms for morphisms over omega-regular languages
conference contribution
posted 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.
Funding
This work was supported by the DFG grants DI 435/5-2 and KU 2716/1-1.
History
School
- Science
Department
- Computer Science
Published in
Leibniz International Proceedings in Informatics, LIPIcsVolume
45Pages
112 - 124Citation
FLEISCHER, 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.Publisher
Schloss Dagstuhl – Leibniz Center for InformaticsVersion
- AM (Accepted Manuscript)
Publisher statement
This 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/Publication date
2015Notes
This 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/ISBN
9783939897972ISSN
1868-8969Publisher version
Book series
Leibniz International Proceedings in Informatics, LIPIcs;45Language
- en