Počet záznamů: 1
A Turing Machine Distance Hierarchy
- 1.
SYSNO ASEP 0383266 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název A Turing Machine Distance Hierarchy Tvůrce(i) Žák, Stanislav (UIVT-O) SAI, RID
Šíma, Jiří (UIVT-O) RID, SAI, ORCIDZdroj.dok. Language and Automata Theory and Applications. - Berlin : Springer, 2013 / Dediu A.H. ; Martín-Vide C. ; Truthe B. - ISSN 0302-9743 - ISBN 978-3-642-37063-2 Rozsah stran s. 570-578 Poč.str. 9 s. Forma vydání Tištěná - P Akce LATA 2013. International Conference on Language and Automata Theory and Applications /7./ Datum konání 02.04.2013-05.04.2013 Místo konání Bilbao Země ES - Španělsko Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova Turing machine ; hierarchy ; distance complexity ; diagonalization Vědní obor RIV IN - Informatika CEP GAP202/10/1333 GA ČR - Grantová agentura ČR GBP202/12/G061 GA ČR - Grantová agentura ČR Institucionální podpora UIVT-O - RVO:67985807 EID SCOPUS 84875651467 DOI https://doi.org/10.1007/978-3-642-37064-9_50 Anotace We introduce a new so-called distance complexity measure for Turing machine computations which is sensitive to long-distance transfers of information on the worktape. An important special case of this measure can be interpreted as a kind of buffering complexity which counts the number of necessary block uploads into a virtual buffer on top of worktape. Thus, the distance measure can be used for investigating the buffering aspects of Turing computations. In this paper, we start this study by proving a tight separation and hierarchy result. In particular, we show that a very small increase in the distance complexity bound (roughly from c(n) to c(n + 1) + constant) brings provably more computational power to deterministic or nondeterministic Turing machines. For this purpose, we formulate a very general diagonalization method for Blum-like complexity measures. We also obtain a hierarchy of the distance complexity classes. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2014
Počet záznamů: 1