2015/09/21 by Lukas Fleischer, Fleischer, Lukas, Manfred Kufleitner +1
Computer Science · #Logic, programming, and type systems #Natural Language Processing Techniques #cs.DS #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1509.06215
Full version of a paper accepted to FSTTCS 2015
arxiv created 2015/11/09 · arxiv updated 2015/11/10
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.