Separating the Classes of Recursively Enumerable Languages Based on Machine Size

Počet záznamů: 1

1.

SYSNO ASEP	0449858
Druh ASEP	J - Článek v odborném periodiku
Zařazení RIV	J - Článek v odborném periodiku
Poddruh J	Článek ve WOS
Název	Separating the Classes of Recursively Enumerable Languages Based on Machine Size
Tvůrce(i)	van Leeuwen, J. (NL) Wiedermann, Jiří (UIVT-O)_{RID, SAI, ORCID}
Zdroj.dok.	International Journal of Foundations of Computer Science - ISSN 0129-0541 Roč. 26, č. 6 (2015), s. 677-695
Poč.str.	19 s.
Jazyk dok.	eng - angličtina
Země vyd.	SG - Singapur
Klíč. slova	recursively enumerable languages ; RE hierarchy ; finite languages ; machine size ; descriptional complexity ; Turing machines with advice
Vědní obor RIV	IN - Informatika
CEP	GAP202/10/1333 GA ČR - Grantová agentura ČR
Institucionální podpora	UIVT-O - RVO:67985807
UT WOS	000364655800002
EID SCOPUS	84947257202
DOI	10.1142/S0129054115500380
Anotace	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 results improving the previously known results. Some proofs make use of several auxiliary results for Turing machines with advice.
Pracoviště	Ústav informatiky
Kontakt	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Rok sběru	2016

Počet záznamů: 1