Paper: Representing Constraints With Automata

ACL ID P97-1060
Title Representing Constraints With Automata
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1997

In this paper we describe an approach to constraint based syntactic theories in terms of finite tree automata. The solutions to constraints expressed in weak monadic sec- ond order (MSO) logic are represented by tree automata recognizing the assignments which make the formulas true. We show that this allows an efficient representation of knowledge about the content of con- straints which can be used as a practical tool for grammatical theory verification. We achieve this by using the intertrans- latability of formulae of MSO logic and tree automata and the embedding of MSO logic into a constraint logic programming scheme. The usefulness of the approach is discussed with examples from the realm of Principles-and-Parameters based parsing.