非表示:
キーワード:
-
要旨:
The formalism of monadic second-order (MS) logic has been very successful in
unifying a large number of algorithms for graphs of bounded treewidth. We
extend the elegant framework of MS logic from static problems to dynamic
problems, in which queries about MS properties of a graph of bounded treewidth
are interspersed with updates of vertex and edge labels. This allows us to
unify and occasionally strengthen a number of scattered previous results
obtained in an ad hoc manner and to enable solutions to a wide range of
additional problems to be
derived automatically.
As an auxiliary result of independent interest, we dynamize a data structure
of Chazelle for answering queries about products of labels along paths in a
tree with edges labeled by elements of a semigroup.
