Number of the records: 1  

On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity

  1. 1.
    0393220 - ÚI 2018 RIV NL eng J - Journal Article
    Šíma, Jiří - Žák, Stanislav
    On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity.
    Fundamenta Informaticae. Roč. 152, č. 4 (2017), s. 397-409. ISSN 0169-2968. E-ISSN 1875-8681
    R&D Projects: GA ČR GBP202/12/G061; GA ČR GAP202/10/1333
    Institutional support: RVO:67985807
    Keywords : Turing machine * hierarchy * buffer complexity * diagonalization
    OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
    Impact factor: 0.725, year: 2017

    We formulate a very general tight diagonalization method for the Blum complexity measures satisfying two additional axioms related to our diagonalizer machine. We apply this method to two new, mutually related, distance and buffer complexities of Turing machine computations which are important nontrivial examples of natural Blum complexity measures different from time and space. In particular, these measures capture how many times the worktape head needs to move a certain distance during the computation which corresponds to the number of necessary block uploads into a buffer cache memory. We start this study by proving a tight separation which shows that a very small increase in the distance or buffer complexity bound (roughly from f(n) to f(n + 1)) brings provably more computational power to both deterministic and nondeterministic Turing machines even for unary languages. We also obtain hierarchies of the distance and buffer complexity classes.
    Permanent Link: http://hdl.handle.net/11104/0221961

     
     
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.