buechihom.FSTTCS15.final.pdf (431.27 kB)
Download file

Efficient algorithms for morphisms over omega-regular languages

Download (431.27 kB)
conference contribution
posted on 23.02.2018, 14:23 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, LIPIcs

Volume

45

Pages

112 - 124

Citation

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 Informatics

Version

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

2015

Notes

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

9783939897972

ISSN

1868-8969

Book series

Leibniz International Proceedings in Informatics, LIPIcs;45

Language

en