Complexity Analysis: Transformation Monoids of Finite Automata

DOI10.1007/978-3-319-21500-6_11zbMath1434.68308OpenAlexW1188686926MaRDI QIDQ3451097

Christian Brandl, Hans Ulrich Simon

Publication date: 10 November 2015

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-21500-6_11

zbMATH Keywords

Green's relationsregular languagescommunication complexityfinite monoidsPSPACE-completeness

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Green's relations in finite transformation semigroups ⋮ The complexity of properties of transformation semigroups ⋮ Green's relations in deterministic finite automata ⋮ Completely Reachable Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-automaton aperiodicity is PSPACE-complete
• Complete classifications for the communication complexity of regular languages
• Green’s Relations and Their Use in Automata Theory
• Complexity of some problems from the theory of automata
• Communication Complexity
• On finite monoids having only trivial subgroups

This page was built for publication: Complexity Analysis: Transformation Monoids of Finite Automata