Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/9918
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GELADE, Wouter | - |
dc.contributor.author | Marquardt, Marcel | - |
dc.contributor.author | Schwentick, Thomas | - |
dc.date.accessioned | 2009-10-27T13:23:51Z | - |
dc.date.available | 2009-10-27T13:23:51Z | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | Albers, Susanne & Marion, Jean-Yves (Ed.) Proceedings of the International Symposium on Theoretical Aspects of Computer Science. p. 481-492. | - |
dc.identifier.isbn | 978-3-939897-09-5 | - |
dc.identifier.uri | http://hdl.handle.net/1942/9918 | - |
dc.description.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. | - |
dc.language.iso | en | - |
dc.publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany | - |
dc.relation.ispartofseries | Dagstuhl Seminar Proceedings | - |
dc.subject.other | Dynamic complexity theory, dynFO, dynPROP, quantifier-free first-order updates | - |
dc.title | The Dynamic Complexity of Formal Languages | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.authors | Albers, Susanne | - |
local.bibliographicCitation.authors | Marion, Jean-Yves | - |
local.bibliographicCitation.conferencename | International Symposium on Theoretical Aspects of Computer Science | - |
dc.bibliographicCitation.conferencenr | 26 | - |
local.bibliographicCitation.conferenceplace | Freiburg, Germany, February 26-28, 2009 | - |
dc.identifier.epage | 492 | - |
dc.identifier.spage | 481 | - |
local.bibliographicCitation.jcat | C1 | - |
local.type.specified | Proceedings Paper | - |
local.relation.ispartofseriesnr | 09001 | - |
dc.bibliographicCitation.oldjcat | - | |
dc.identifier.url | http://drops.dagstuhl.de/opus/volltexte/2009/1829 | - |
local.bibliographicCitation.btitle | Proceedings of the International Symposium on Theoretical Aspects of Computer Science | - |
item.accessRights | Open Access | - |
item.contributor | GELADE, Wouter | - |
item.contributor | Marquardt, Marcel | - |
item.contributor | Schwentick, Thomas | - |
item.fulltext | With Fulltext | - |
item.fullcitation | GELADE, Wouter; Marquardt, Marcel & Schwentick, Thomas (2009) The Dynamic Complexity of Formal Languages. In: Albers, Susanne & Marion, Jean-Yves (Ed.) Proceedings of the International Symposium on Theoretical Aspects of Computer Science. p. 481-492.. | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
09001.GeladeWouter.1829.pdf | Published version | 175.91 kB | Adobe PDF | View/Open |
Page view(s)
52
checked on Sep 7, 2022
Download(s)
98
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.