Operations on weakly recognizing morphisms
From MaRDI portal
Publication:2829976
DOI10.1007/978-3-319-41114-9_10zbMATH Open1476.68159arXiv1603.05376OpenAlexW2297709294MaRDI QIDQ2829976FDOQ2829976
Authors: Lukas Fleischer, Manfred Kufleitner 
Publication date: 9 November 2016
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1603.05376
Recommendations
Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Weak Second‐Order Arithmetic and Finite Automata
- Title not available (Why is that?)
- A syntactic congruence for rational \(\omega\)-languages
- Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
- Finite automata and unary languages
- Two-generator semigroups of binary relations
- Title not available (Why is that?)
- Nondeterminism and the size of two way finite automata
- On deterministic finite automata and syntactic monoid size
- A proof of Devadze's theorem on generators of the semigroup of Boolean matrices.
Cited In (1)
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)
