Separating the Classes of Recursively Enumerable Languages Based on Machine Size

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F15%3A00449858" target="_blank" >RIV/67985807:_____/15:00449858 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1142/S0129054115500380" target="_blank" >http://dx.doi.org/10.1142/S0129054115500380</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1142/S0129054115500380" target="_blank" >10.1142/S0129054115500380</a>

Result language
angličtina
Original language name
Separating the Classes of Recursively Enumerable Languages Based on Machine Size
Original language description
In the late nineteen sixties it was observed that the r.e. languages form an infinite proper hierarchy based on the size of the Turing machines that accept them. We examine the fundamental position of the finite languages and their complements in the hierarchy and bring new resutls improving the previously known results. Some proofs make use of several auxiliary results for Turing machines with advice.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
<a href="/en/project/GAP202%2F10%2F1333" target="_blank" >GAP202/10/1333: NoSCoM: Non-Standard Computational Models and Their Applications in Complexity, Linguistics, and Learning</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)