Grammar constraints

作者：Kadioglu Serdar; Sellmann Meinolf^*

来源：Constraints, 2010, 15(1): 117-144.

DOI：10.1007/s10601-009-9073-4

• Constraint filtering
• Global constraints
• Grammar constraints

With the introduction of the Regular Membership Constraint, a new line of research has opened where constraints are based on formal languages. This paper is taking the next step, namely to investigate constraints based on grammars higher up in the Chomsky hierarchy. We devise a time- and space-efficient incremental arc-consistency algorithm for context-free grammars, investigate when logic combinations of grammar constraints are tractable, show how to exploit non-constant size grammars and reorderings of languages, and study where the boundaries run between regular, context-free, and context-sensitive grammar filtering.

• 出版日期2010-1