Počet záznamů: 1
On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity
- 1.
SYSNO ASEP 0393220 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 On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity Tvůrce(i) Šíma, Jiří (UIVT-O) RID, SAI, ORCID
Žák, Stanislav (UIVT-O) SAI, RIDZdroj.dok. Fundamenta Informaticae. - : IOS Press - ISSN 0169-2968
Roč. 152, č. 4 (2017), s. 397-409Poč.str. 13 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova Turing machine ; hierarchy ; buffer complexity ; diagonalization Vědní obor RIV IN - Informatika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) CEP GBP202/12/G061 GA ČR - Grantová agentura ČR GAP202/10/1333 GA ČR - Grantová agentura ČR Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000401338000004 EID SCOPUS 85019447188 DOI 10.3233/FI-2017-1526 Anotace 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2018
Počet záznamů: 1