Separating the Classes of Recursively Enumerable Languages Based on Machine Size

0449858 - ÚI 2016 RIV SG eng J - Článek v odborném periodiku
van Leeuwen, J. - Wiedermann, Jiří
Separating the Classes of Recursively Enumerable Languages Based on Machine Size.
International Journal of Foundations of Computer Science. Roč. 26, č. 6 (2015), s. 677-695. ISSN 0129-0541. E-ISSN 1793-6373
Grant CEP: GA ČR GAP202/10/1333
Grant ostatní: GA ČR(CZ) GA15-04960S
Institucionální podpora: RVO:67985807
Klíčová slova: recursively enumerable languages * RE hierarchy * finite languages * machine size * descriptional complexity * Turing machines with advice
Kód oboru RIV: IN - Informatika
Impakt faktor: 0.467, rok: 2015

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.
Trvalý link: http://hdl.handle.net/11104/0251272