Separating the Classes of Recursively Enumerable Languages Based on Machine Size

DOI10.1142/S0129054115500380zbMath1333.68176OpenAlexW2198076835MaRDI QIDQ3455749

Jan van Leeuwen, Juraj Wiedermann

Publication date: 11 December 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054115500380

zbMATH Keywords

finite languagesrecursively enumerable languagesdescriptional complexitymachine sizeRE hierarchyTuring machines with advice

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• A maxmin problem on finite automata
• Algorithmic complexity of recursive and inductive algorithms
• On the average state and transition complexity of finite languages
• A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity
• On the size of machines
• The state complexity of Turing machines
• An Overview of the Theory of Computational Complexity
• NON-UNIQUENESS AND RADIUS OF CYCLIC UNARY NFAs

This page was built for publication: Separating the Classes of Recursively Enumerable Languages Based on Machine Size