|
Some Problems in Dynamic Descriptive Complexity Theory
Sam McGuire
UMass
We consider such a dynamic context from a descriptive point of view. Towards this end, we define the notion of dynamic queries and discuss a framework for studying them. We’ll show upper bounds and lower bounds for the dynamic maintenance of regular languages and, time permitting, discuss the problem of dynamically counting satisfying assignments to first-order sentences.