Number of the records: 1

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

SYSNO ASEP	0393220
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity
Author(s)	Šíma, Jiří (UIVT-O)_{RID, SAI, ORCID} Žák, Stanislav (UIVT-O)_{SAI, RID}
Source Title	Fundamenta Informaticae. - : IOS Press - ISSN 0169-2968 Roč. 152, č. 4 (2017), s. 397-409
Number of pages	13 s.
Language	eng - English
Country	NL - Netherlands
Keywords	Turing machine ; hierarchy ; buffer complexity ; diagonalization
Subject RIV	IN - Informatics, Computer Science
OECD category	Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
R&D Projects	GBP202/12/G061 GA ČR - Czech Science Foundation (CSF)
	GAP202/10/1333 GA ČR - Czech Science Foundation (CSF)
Institutional support	UIVT-O - RVO:67985807
UT WOS	000401338000004
EID SCOPUS	85019447188
DOI	10.3233/FI-2017-1526
Annotation	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.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2018

Number of the records: 1