License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2336
URN: urn:nbn:de:0030-drops-23365
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2336/
Go to the corresponding LIPIcs Volume Portal

Dawar, Anuj

Structure and Specification as Sources of Complexity

pdf-format:
09005.DawarAnuj.2336.pdf (0.2 MB)

Abstract

If computational complexity is the study of what makes certain computational
problems inherently difficult to solve, an important contribution of
descriptive complexity in this regard is the separation it provides between
the specification of a decision problem and the structure against which this
specification is checked. The formalisation of these two aspects leads to
tools for studying them as sources of complexity, and on the one hand leads to
results in the characterisation of complexity classes and on the other elates
to parameterized complexity. In these notes accompanying the invited talk,
some definitions and results are presented leading to recent work on the
characterisation of polynomial time and on the parameterized complexity of
first-order logic on restricted graph classes.

BibTeX - Entry

@InProceedings{dawar:LIPIcs:2009:2336,
  author =	{Anuj Dawar},
  title =	{{Structure and Specification as Sources of Complexity}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{407--416},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Ravi Kannan and K. Narayan Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2336},
  URN =		{urn:nbn:de:0030-drops-23365},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2336},
  annote =	{Keywords: Computational Complexity, Descriptive Complexity, Logical Complexity, Parametrized Complexity, Locality, Automata }
}

Keywords: Computational Complexity, Descriptive Complexity, Logical Complexity, Parametrized Complexity, Locality, Automata
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2009
Date of publication: 14.12.2009

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