Počet záznamů: 1  

A Turing Machine Distance Hierarchy

  1. 1.
    0383266 - ÚI 2014 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
    Žák, Stanislav - Šíma, Jiří
    A Turing Machine Distance Hierarchy.
    Language and Automata Theory and Applications. Berlin: Springer, 2013 - (Dediu, A.; Martín-Vide, C.; Truthe, B.), s. 570-578. Lecture Notes in Computer Science, 7810. ISBN 978-3-642-37063-2. ISSN 0302-9743.
    [LATA 2013. International Conference on Language and Automata Theory and Applications /7./. Bilbao (ES), 02.04.2013-05.04.2013]
    Grant CEP: GA ČR GAP202/10/1333; GA ČR GBP202/12/G061
    Institucionální podpora: RVO:67985807
    Klíčová slova: Turing machine * hierarchy * distance complexity * diagonalization
    Kód oboru RIV: IN - Informatika

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

     
    Název souboruStaženoVelikostKomentářVerzePřístup
    a0383266.pdf11177 KBVydavatelský postprintvyžádat
    0383266.pdf2794.7 KBAutorský preprintpovolen
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.