Nicolas Markey

Résumé

Dynamic complexity is concerned with updating the output of a problem when the input is slightly changed. We study the dynamic complexity of model checking a fixed monadic second-order formula over evolving subgraphs of a fixed maximal graph having bounded tree-width; here the subgraph evolves by losing or gaining edges (from the maximal graph). We show that this problem is in DynFO (with LOGSPACE precomputation), via a reduction to a Dyck reachability problem on an acyclic automaton.

@techreport{arxiv1702.05183-BJM,
  author =              {Bouyer, Patricia and Jug{\'e}, Vincent and Markey,
                         Nicolas},
  title =               {{C}ourcelle's Theorem Made Dynamic},
  number =              {1702.05183},
  year =                {2017},
  month =               feb,
  institution =         {arXiv},
  abstract =            {Dynamic complexity is concerned with updating the
                         output of a problem when the input is slightly
                         changed. We study the dynamic complexity of model
                         checking a fixed monadic second-order formula over
                         evolving subgraphs of a fixed maximal graph having
                         bounded tree-width; here the subgraph evolves by
                         losing or gaining edges (from the maximal graph).
                         We~show that this problem is in DynFO (with LOGSPACE
                         precomputation), via a reduction to a Dyck
                         reachability problem on an acyclic automaton.},
}