|
Frank Morawietz and Tom Cornell"Representing Constraints with Automata"8pp., DVI (56kb); Postscript (195kb)1-up; Postscript gzip-komprimiert (79kb) 1-up , 2-up. AbstractIn 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 second 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 constraints which can be used as a practical tool for grammatical theory verification. We achieve this by using the intertranslatability of formulas 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.
Appears in the Proceedings of the ACL/EACL Conference '97, Madrid, Spain. Replaced with revised version 20.06.97. Also available from The Computation and Language E-Print Archive as cmp-lg/9704006. 1997. |
|
In case of problems or for comments, please contact: frank@sfs.uni-tuebingen.de Last updated: 13-Mar-2000 |