License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.10
URN: urn:nbn:de:0030-drops-99095
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9909/
Go to the corresponding LIPIcs Volume Portal

Abu Zaid, Faried

Uniformly Automatic Classes of Finite Structures

pdf-format:
LIPIcs-FSTTCS-2018-10.pdf (0.6 MB)

Abstract

We investigate the recently introduced concept of uniformly tree-automatic classes in the realm of parameterized complexity theory. Roughly speaking, a class of finite structures is uniformly tree-automatic if it can be presented by a set of finite trees and a tuple of automata. A tree t encodes a structure and an element of this structure is encoded by a labeling of t. The automata are used to present the relations of the structure. We use this formalism to obtain algorithmic meta-theorems for first-order logic and in some cases also monadic second-order logic on classes of finite Boolean algebras, finite groups, and graphs of bounded tree-depth. Our main concern is the efficiency of this approach with respect to the hidden parameter dependence (size of the formula). We develop a method to analyze the complexity of uniformly tree-automatic presentations, which allows us to give upper bounds for the runtime of the automata-based model checking algorithm on the presented class. It turns out that the parameter dependence is elementary for all the above mentioned classes. Additionally we show that one can lift the FPT results, which are obtained by our method, from a class C to the closure of C under direct products with only a singly exponential blow-up in the parameter dependence.

BibTeX - Entry

@InProceedings{abuzaid:LIPIcs:2018:9909,
  author =	{Faried Abu Zaid},
  title =	{{Uniformly Automatic Classes of Finite Structures}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9909},
  URN =		{urn:nbn:de:0030-drops-99095},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.10},
  annote =	{Keywords: Automatic Structures, Model Checking, Fixed-Parameter Tractability, Algorithmic Meta Theorems}
}

Keywords: Automatic Structures, Model Checking, Fixed-Parameter Tractability, Algorithmic Meta Theorems
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI