Transition function complexity of finite automata

DOI10.1007/978-3-642-22600-7_24MaRDI QIDQ5200100zbMATH OpenOpenAlexFDO

Authors Māris Valdats

Publication date 29 July 2011

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

Full work available at URL https://doi.org/10.1007/978-3-642-22600-7_24

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Boolean circuit complexity of regular languages
• State complexity of regular languages
• Descriptional and computational complexity of the circuit representation of finite automata
• Automaticity. I: Properties of a measure of descriptional complexity
• Descriptional and Computational Complexity of Finite Automata

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1033441 (Why is no real title available?)
• scientific article; zbMATH DE number 194333 (Why is no real title available?)
• STACS 2005
• The average-case parallel complexity of sorting

Cited in

(3)

• scientific article; zbMATH DE number 2125663 (Why is no real title available?)
• Complexity Analysis: Transformation Monoids of Finite Automata
• Boolean circuit complexity of regular languages

This page was built for publication: Transition function complexity of finite automata

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