Comparing verboseness for finite automata and Turing machines

DOI10.1007/S00224-003-1108-4zbMATH Open1069.68070OpenAlexW2071094043MaRDI QIDQ705065FDOQ705065

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

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

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)

Cited In (2)

• Weak cardinality theorems
• Title not available (Why is that?)

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)