Work-sensitive Dynamic Complexity of Formal Languages

DynFO is the dynamic complexity class of all queries that can be main- tained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of tuples. If one tries to make the “DynFO approach” to maintaining queries relevant for practical considerations, the work that is needed to carry out the specified updates, hence the work of an algorithm (i. e. the sum of the number of operations of all processors) implementing them, is a crucial factor. In this talk, I will introduce a work-aware version of DynFO and present first results for the question which queries can be maintained in DynFO with little work – in this first investigation restricted to dynamic language membership queries.

Authors

• Jonas Schmidt

Keywords

No keywords are indexed for this paper.