The complexity of weakly recognizing morphisms

DOI10.1051/ITA/2018006MaRDI QIDQ5223827zbMATH OpenOpenAlexFDO

Authors Lukas Fleischer, Manfred Kufleitner

Publication date 18 July 2019

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ita/2018006

zbMATH Keywords

automatacomputational complexitydecision problemdescriptional complexityregular languagesemigroup

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Operations on weakly recognizing morphisms
• Efficient algorithms for morphisms over omega-regular languages
• scientific article; zbMATH DE number 512865
• Deciding the weak definability of Büchi definable tree languages
• scientific article; zbMATH DE number 1303030

Cites work

• A proof of Devadze's theorem on generators of the semigroup of Boolean matrices.
• A syntactic congruence for rational -languages
• Finite automata and unary languages
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3959795 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (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?)
• Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique
• New problems complete for nondeterministic log space
• Nondeterminism and the size of two way finite automata
• Nondeterministic Space is Closed under Complementation
• On deterministic finite automata and syntactic monoid size
• On uniformity within \(NC^ 1\)
• Space-bounded reducibility among combinatorial problems
• The method of forced enumeration for nondeterministic automata
• The parallel complexity of finite-state automata problems
• Two-generator semigroups of binary relations
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(5)

• On the complexity of specification morphisms
• Operations on weakly recognizing morphisms
• Weakly Unambiguous Morphisms with Respect to Sets of Patterns with Constants
• Recognizability for sequences of morphisms
• Efficient algorithms for morphisms over omega-regular languages

This page was built for publication: The complexity of weakly recognizing morphisms

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