Comparing verboseness for finite automata and Turing machines

DOI10.1007/S00224-003-1108-4MaRDI QIDQ705065zbMATH OpenOpenAlexFDO

Authors Till Tantau

Publication date 25 January 2005

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-003-1108-4

zbMATH Keywords

complexity classesfinite automataregular languagesTuring machinesverboseness

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 2086408
• scientific article; zbMATH DE number 1361501
• scientific article; zbMATH DE number 4094826
• On polynomially \(\mathcal{D}\)-verbose sets
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation

Cited in

(2)

• Weak cardinality theorems
• scientific article; zbMATH DE number 2086408 (Why is no real title available?)

This page was built for publication: Comparing verboseness for finite automata and Turing machines

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