Separating the classes of recursively enumerable languages based on machine size

DOI10.1142/S0129054115500380MaRDI QIDQ3455749zbMATH OpenOpenAlexFDO

Authors J. Van Leeuwen, Jiří 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

descriptional complexityfinite languagesmachine sizeRE hierarchyrecursively enumerable languagesTuring machines with advice

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Turing machines with one-sided advice and acceptance of the co-RE languages
• Homomorphic characterizations of recursively enumerable languages with very small language classes
• scientific article; zbMATH DE number 4019040
• scientific article; zbMATH DE number 3857079
• A hierarchy of fast reversible Turing machines

Cites work

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

This page was built for publication: Separating the classes of recursively enumerable languages based on machine size

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