Efficient Context-Free Grammar Constraints

Serdar Kadioglu, Meinolf Sellmann

With the introduction of constraints based on finite automata a new line of research has opened where constraints are based on formal languages. Recently, constraints based on grammars higher up in the Chomsky hierarchy were introduced. We devise a time- and space-efficient incremental arc-consistency algorithm for context-free grammars. Particularly, we show how to filter a sequence of monotonically tightening problems in cubic time and quadratic space. Experiments on a scheduling problem show orders of magnitude improvements in time and space consumption.

Subjects: 15.2 Constraint Satisfaction; 9.2 Computational Complexity

Submitted: Apr 14, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.