Restricted Global Grammar Constraints

Details Restricted Global Grammar Constraints Restricted Global Grammar Constraints

2009-06-29

arxiv.org/abs/0906.5233v1

Computer Science

Artificial Intelligence

Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming, Lisbon, Portugal. Septe

Scientific paper

We investigate the global GRAMMAR constraint over restricted classes of context free grammars like deterministic and unambiguous context-free grammars. We show that detecting disentailment for the GRAMMAR constraint in these cases is as hard as parsing an unrestricted context free grammar.We also consider the class of linear grammars and give a propagator that runs in quadratic time. Finally, to demonstrate the use of linear grammars, we show that a weighted linear GRAMMAR constraint can efficiently encode the EDITDISTANCE constraint, and a conjunction of the EDITDISTANCE constraint and the REGULAR constraint

Affiliated with

Also associated with

No associations

Rating

Restricted Global Grammar Constraints 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 Restricted Global Grammar Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Restricted Global Grammar Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-247449