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