The Monadic Second-Order Dominance Logic and Parallelism Constraints
Autor: Joachim Niehren and Mateu Villaret
Herausgeber:
Parallelism constraints are known to have the same
expressiveness as context unification. We propose
a new extension of parallelism constraints by formulas
of the monadic second-order dominance logic (\SFSDom) that we introduce. We establish the classical relations between
logic and tree automata for \SFSDom. Based on this
result, we prove that the extension of parallelism
constraints with \SFSDom formulas
is equal in expressive power to context unification plus
tree regular constraints.
|