1 Search Results for "Marquardt, Marcel"

Document
DOI: 10.4230/LIPIcs.STACS.2009.1829
The Dynamic Complexity of Formal Languages

Authors: Wouter Gelade, Marcel Marquardt, and Thomas Schwentick

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
The paper investigates the power of the dynamic complexity classes DynFO, DynQF and DynPROP over string languages. The latter two classes contain problems that can be maintained using quantifier-free first-order updates, with and without auxiliary functions, respectively. It is shown that the languages maintainable in DynPROP exactly are the regular languages, even when allowing arbitrary precomputation. This enables lower bounds for DynPROP and separates DynPROP from DynQF and DynFO. Further, it is shown that any context-free language can be maintained in DynFO and a number of specific context-free languages, for example all Dyck-languages, are maintainable in DynQF. Furthermore, the dynamic complexity of regular tree languages is investigated and some results concerning arbitrary structures are obtained: there exist first-order definable properties which are not maintainable in DynPROP. On the other hand any existential first-order property can be maintained in DynQF when allowing precomputation.
Cite as

Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The Dynamic Complexity of Formal Languages. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 481-492, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{gelade_et_al:LIPIcs.STACS.2009.1829,
  author =	{Gelade, Wouter and Marquardt, Marcel and Schwentick, Thomas},
  title =	{{The Dynamic Complexity of Formal Languages}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{481--492},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1829},
  URN =		{urn:nbn:de:0030-drops-18297},
  doi =		{10.4230/LIPIcs.STACS.2009.1829},
  annote =	{Keywords: Dynamic complexity, Regular languages, Context-free languages, DynFO}
}
  • Refine by Author
  • 1 Gelade, Wouter
  • 1 Marquardt, Marcel
  • 1 Schwentick, Thomas

  • Refine by Classification

  • Refine by Keyword
  • 1 Context-free languages
  • 1 DynFO
  • 1 Dynamic complexity
  • 1 Regular languages

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2009

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact