Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/14309
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGELADE, Wouter-
dc.contributor.authorMarquardt, Marcel-
dc.contributor.authorSchwentick, Thomas-
dc.date.accessioned2012-11-09T12:47:13Z-
dc.date.available2012-11-09T12:47:13Z-
dc.date.issued2012-
dc.identifier.citationACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 13 (3)-
dc.identifier.issn1529-3785-
dc.identifier.urihttp://hdl.handle.net/1942/14309-
dc.description.abstractThe article 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 are exactly 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.isoen-
dc.publisherASSOC COMPUTING MACHINERY-
dc.subject.otherLanguages; Theory-
dc.subject.otherComputer Science, Theory & Methods; Logic; languages; theory-
dc.titleThe Dynamic Complexity of Formal Languages-
dc.typeJournal Contribution-
dc.identifier.issue3-
dc.identifier.volume13-
local.format.pages36-
local.bibliographicCitation.jcatA1-
dc.description.notes[Gelade, Wouter] Hasselt Univ, Diepenbeek, Belgium. [Gelade, Wouter] Transnatl Univ Limburg, Limburg, Belgium. [Marquardt, Marcel; Schwentick, Thomas] Tech Univ Dortmund, Dortmund, Germany. thomas.schwentick@udo.edu-
local.publisher.placeNEW YORK-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.doi10.1145/2287718.2287719-
dc.identifier.isi000308370100001-
item.accessRightsRestricted Access-
item.contributorGELADE, Wouter-
item.contributorMarquardt, Marcel-
item.contributorSchwentick, Thomas-
item.validationecoom 2013-
item.fullcitationGELADE, Wouter; Marquardt, Marcel & Schwentick, Thomas (2012) The Dynamic Complexity of Formal Languages. In: ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 13 (3).-
item.fulltextWith Fulltext-
crisitem.journal.issn1529-3785-
crisitem.journal.eissn1557-945X-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
a19-gelade.pdf
  Restricted Access		Published version392.1 kBAdobe PDFView/Open    Request a copy
Show simple item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.