Título:
|
The parameterized space complexity of model-checking bounded variable first-order logic
|
Autor/a:
|
Chen, Yijia; Elberfeld, Michael; Muller, Moritz Martin
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
The parameterized model-checking problem for a class of first-order sentences (queries) asks to decide whether a given sentence from the class holds true in a given relational structure (database); the parameter is the length of the sentence. We study the parameterized space complexity of the model-checking problem for queries with a bounded number of variables. For each bound on the quantifier alternation rank the problem becomes complete for the corresponding level of what we call the tree hierarchy, a hierarchy of parameterized complexity classes defined via space bounded alternating machines between parameterized logarithmic space and fixed-parameter tractable time. We observe that a parameterized logarithmic space model-checker for existential bounded variable queries would allow to improve Savitch's classical simulation of nondeterministic logarithmic space in deterministic space O(log2n). Further, we define a highly space efficient model-checker for queries with a bounded number of variables and bounded quantifier alternation rank. We study its optimality under the assumption that Savitch's Theorem is optimal. |
Abstract:
|
Peer Reviewed |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat -Computational complexity -First-order logic -Query languages (Computer science) -Model-checking -Bounded variable first-order logic -Parameterized logarithmic space -Complexitat computacional -Lògica de primer ordre -Llenguatges d'interrogació (Informàtica) |
Derechos:
|
Attribution 3.0 Spain
http://creativecommons.org/licenses/by/3.0/es/ |
Tipo de documento:
|
Artículo - Versión publicada Artículo |
Compartir:
|
|