Complexity Analysis: Transformation Monoids of Finite Automata

DOI10.1007/978-3-319-21500-6_11MaRDI QIDQ3451097zbMATH OpenOpenAlexFDO

Authors 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

communication complexityfinite monoidsGreen's relationsPSPACE-completenessregular languages

Mathematics Subject Classification ID

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

Recommendations

• Implementation and Application of Automata
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• Transition function complexity of finite automata
• scientific article; zbMATH DE number 4041268
• Automaton transformations and monadic theories of infinite sequences
• scientific article; zbMATH DE number 2125663
• scientific article; zbMATH DE number 475412
• scientific article; zbMATH DE number 6719345
• scientific article; zbMATH DE number 4104394
• scientific article; zbMATH DE number 3846880

Cites work

• Communication Complexity
• Complete classifications for the communication complexity of regular languages
• Complexity of some problems from the theory of automata
• Finite-automaton aperiodicity is PSPACE-complete
• Green's relations and their use in automata theory
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• On finite monoids having only trivial subgroups

Cited in

(13)

• Characterization of idempotent transformation monoids
• Green's relations in deterministic finite automata
• Green's relations in finite transformation semigroups
• Completely reachable automata
• The complexity of intersecting finite automata having few final states
• Checking whether an automaton is monotonic is NP-complete
• Green's relations and their use in automata theory
• The intersection problem for finite monoids
• The complexity of intersecting finite automata having few final states
• The membership problem in aperiodic transformation monoids
• The complexity of properties of transformation semigroups
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• Over Which Monoids is the Transducer Determinization Procedure Applicable?

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

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