Comparing verboseness for finite automata and Turing machines

DOI10.1007/S00224-003-1108-4zbMath1069.68070OpenAlexW2071094043MaRDI QIDQ705065

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

Turing machinesfinite automataregular languagescomplexity classesverboseness

Mathematics Subject Classification ID

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

Related Items (1)

Weak cardinality theorems

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