{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:32Z","timestamp":1750307012994,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T00:00:00Z","timestamp":1343779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>\n            The article investigates the power of the dynamic complexity classes D\n            <jats:sc>yn<\/jats:sc>\n            FO, D\n            <jats:sc>yn<\/jats:sc>\n            QF, and D\n            <jats:sc>yn<\/jats:sc>\n            PROP 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 D\n            <jats:sc>yn<\/jats:sc>\n            PROP are exactly the regular languages, even when allowing arbitrary precomputation. This enables lower bounds for D\n            <jats:sc>yn<\/jats:sc>\n            PROP and separates D\n            <jats:sc>yn<\/jats:sc>\n            PROP from D\n            <jats:sc>yn<\/jats:sc>\n            QF and D\n            <jats:sc>yn<\/jats:sc>\n            FO. Further, it is shown that any context-free language can be maintained in D\n            <jats:sc>yn<\/jats:sc>\n            FO and a number of specific context-free languages, for example all Dyck-languages, are maintainable in D\n            <jats:sc>yn<\/jats:sc>\n            QF. 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 D\n            <jats:sc>yn<\/jats:sc>\n            PROP. On the other hand, any existential first-order property can be maintained in D\n            <jats:sc>yn<\/jats:sc>\n            QF when allowing precomputation.\n          <\/jats:p>","DOI":"10.1145\/2287718.2287719","type":"journal-article","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T13:09:44Z","timestamp":1346159384000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["The dynamic complexity of formal languages"],"prefix":"10.1145","volume":"13","author":[{"given":"Wouter","family":"Gelade","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcel","family":"Marquardt","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Dortmund"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Dortmund"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,8,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1042046.1042050"},{"volume-title":"Proceedings of the IEEE International Conference on Data Engineering. 671--682","author":"Barbosa D.","key":"e_1_2_1_2_1","unstructured":"Barbosa , D. , Mendelzon , A. O. , Libkin , L. , Mignet , L. , and Arenas , M . 2004. Efficient incremental validation of XML documents . In Proceedings of the IEEE International Conference on Data Engineering. 671--682 . Barbosa, D., Mendelzon, A. O., Libkin, L., Mignet, L., and Arenas, M. 2004. Efficient incremental validation of XML documents. In Proceedings of the IEEE International Conference on Data Engineering. 671--682."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514915"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00017-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018951521198"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1565"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530820"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275514"},{"volume-title":"Proceedings of the Workshop on Algorithms and Data Structures. 98--108","author":"Frandsen G. S.","key":"e_1_2_1_9_1","unstructured":"Frandsen , G. S. , Husfeldt , T. , Miltersen , P. B. , Rauhe , T. , and Skyum , S . 1995. Dynamic algorithms for the Dyck languages . In Proceedings of the Workshop on Algorithms and Data Structures. 98--108 . Frandsen, G. S., Husfeldt, T., Miltersen, P. B., Rauhe, T., and Skyum, S. 1995. Dynamic algorithms for the Dyck languages. In Proceedings of the Workshop on Algorithms and Data Structures. 98--108."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/256303.256309"},{"key":"e_1_2_1_11_1","unstructured":"Graham R. L. and Rothschild B. L. 1990. Ramsey Theory 2nd Ed. Wiley-Interscience New York NY.   Graham R. L. and Rothschild B. L. 1990. Ramsey Theory 2nd Ed. Wiley-Interscience New York NY."},{"key":"e_1_2_1_12_1","unstructured":"Hesse W. 2003a. Conditional and unconditional separations of dynamic complexity classes. Unpublished manuscript http:\/\/people.clarkson.edu\/whesse\/.  Hesse W. 2003a. Conditional and unconditional separations of dynamic complexity classes. Unpublished manuscript http:\/\/people.clarkson.edu\/whesse\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00740-5"},{"volume-title":"Proceedings of the Annual IEEE Symposium on Logic in Computer Science. 313--324","author":"Hesse W.","key":"e_1_2_1_15_1","unstructured":"Hesse , W. and Immerman , N . 2002. Complete problems for dynamic complexity classes . In Proceedings of the Annual IEEE Symposium on Logic in Computer Science. 313--324 . Hesse, W. and Immerman, N. 2002. Complete problems for dynamic complexity classes. In Proceedings of the Annual IEEE Symposium on Logic in Computer Science. 313--324."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of Advances in Data Structures. Satellite Workshop of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS).","author":"Miltersen P. B.","year":"1999","unstructured":"Miltersen , P. B. 1999 . Cell probe complexity - a survey . In Proceedings of Advances in Data Structures. Satellite Workshop of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Miltersen, P. B. 1999. Cell probe complexity - a survey. In Proceedings of Advances in Data Structures. Satellite Workshop of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90159-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1520"},{"volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"Vollmer H.","key":"e_1_2_1_19_1","unstructured":"Vollmer , H. 1999. Introduction to Circuit Complexity: A Uniform Approach . Springer . Vollmer, H. 1999. Introduction to Circuit Complexity: A Uniform Approach. Springer."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1312-0"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2287718.2287719","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2287718.2287719","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:04Z","timestamp":1750236544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2287718.2287719"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1145\/2287718.2287719"],"URL":"https:\/\/doi.org\/10.1145\/2287718.2287719","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2012,8]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-08-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}