Operations on weakly recognizing morphisms

DOI10.1007/978-3-319-41114-9_10MaRDI QIDQ2829976zbMATH OpenOpenAlexFDO

Authors Lukas Fleischer, Manfred Kufleitner

Publication date 9 November 2016

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.05376, https://dspace.lboro.ac.uk/2134/31973

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: Weakly recognizing morphisms from free semigroups onto finite semigroups are a classical way for defining the class of omega-regular languages, i.e., a set of infinite words is weakly recognizable by such a morphism if and only if it is accepted by some B"uchi automaton. We consider the descriptional complexity of various constructions for weakly recognizing morphisms. This includes the conversion from and to B"uchi automata, the conversion into strongly recognizing morphisms, and complementation. For some problems, we are able to give more precise bounds in the case of binary alphabets or simple semigroups.

Recommendations

• The complexity of weakly recognizing morphisms
• Efficient algorithms for morphisms over omega-regular languages
• scientific article; zbMATH DE number 988807
• scientific article; zbMATH DE number 512865
• Factorizations and universal automaton of omega languages

Cites work

• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 3353590 (Why is no real title available?)
• A proof of Devadze's theorem on generators of the semigroup of Boolean matrices.
• A syntactic congruence for rational \(\omega\)-languages
• Efficient algorithms for morphisms over omega-regular languages
• Finite automata and unary languages
• Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
• Nondeterminism and the size of two way finite automata
• On deterministic finite automata and syntactic monoid size
• Two-generator semigroups of binary relations
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(3)

• The complexity of weakly recognizing morphisms
• Efficient algorithms for morphisms over omega-regular languages
• McCammond’s normal forms for free aperiodic semigroups revisited

This page was built for publication: Operations on weakly recognizing morphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829976)