The Monadic Second-Order Dominance Logic and Parallelism Constraints

Author: Joachim Niehren and Mateu Villaret

Editor:

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.