Separating the Classes of Recursively Enumerable Languages Based on Machine Size
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Separating the Classes of Recursively Enumerable Languages Based on Machine Size
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Separating the Classes of Recursively Enumerable Languages Based on Machine Size
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GAP202%2F10%2F1333" target="_blank" >GAP202/10/1333: NoSCoM: Nestandardní výpočetní modely a jejich aplikace ve složitosti, lingvistice a učení</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2015
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
International Journal of Foundations of Computer Science
ISSN
0129-0541
e-ISSN
—
Svazek periodika
26
Číslo periodika v rámci svazku
6
Stát vydavatele periodika
SG - Singapurská republika
Počet stran výsledku
19
Strana od-do
677-695
Kód UT WoS článku
000364655800002
EID výsledku v databázi Scopus
2-s2.0-84947257202