Representing Constraints with Automata

Details Representing Constraints with Automata Representing Constraints with Automata

1997-04-21

arxiv.org/abs/cmp-lg/9704006v2

Computer Science

Computation and Language

8 pages; uses aclap.sty, harvard.sty and dcu.bst. Corrections to three examples

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

Representing Constraints with Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Representing Constraints with Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Representing Constraints with Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147485