2017/02/16 by Patricia Bouyer-Decitre, Bouyer-Decitre, Patricia, Vincent Jugé +3
Computer Science · #Advanced Graph Theory Research #semigroups and automata theory #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.1702.05183
Dynamic complexity is concerned with updating the output of a problem when\nthe input is slightly changed. We study the dynamic complexity of model\nchecking a fixed monadic second-order formula over evolving subgraphs of a\nfixed maximal graph having bounded tree-width; here the subgraph evolves by\nlosing or gaining edges (from the maximal graph). We show that this problem is\nin DynFO (with LOGSPACE precomputation), via a reduction to a Dyck reachability\nproblem on an acyclic automaton.\n