The Dynamic Complexity of Formal Languages
The Dynamic Complexity of Formal Languages
复制标题
DOI：
10.1145/2287718.2287719
复制
发表时间：
2012-08-01
影响因子：
0.5
通讯作者：
Schwentick, Thomas
中科院分区：
文献类型：
--
作者：
Gelade, Wouter;Marquardt, Marcel;Schwentick, Thomas
本文研究了动态复杂性类别DYNFO，DYNQF和DYNPROP对字符串语言的功能。后两个类包含可以使用无量词的一阶更新来维持的问题，分别具有和没有辅助功能。据表明，即使允许任意预先计算，在DynProp中可维护的语言正是普通语言。这使DynProp的下限为下限，并将DynProp与Dynqf和Dynfo分开。此外，结果表明，任何无上下文的语言都可以在Dynfo中维护，并且许多特定的无上下文语言，例如所有dyck语言，在Dynqf中均可维持。此外，还研究了常规树语言的动态复杂性，并获得了有关任意结构的一些结果：存在DynProp中无法维护的一阶定义属性。另一方面，在允许预录时，任何存在的一阶属性都可以在DYNQF中保持。
The 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.