Efficient Context-Free Grammar Constraints
Abstract
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 intro-duced. We devise a time- and space-efficient incremental arc-consistency algorithm for context-free grammars. Partic-ularly, we show how to filter a sequence of monotonically tightening problems in cubic time and quadratic space. Ex-periments on a scheduling problem show orders of magnitude improvements in time and space consumption.
Cite
Text
Kadioglu and Sellmann. "Efficient Context-Free Grammar Constraints." AAAI Conference on Artificial Intelligence, 2008.Markdown
[Kadioglu and Sellmann. "Efficient Context-Free Grammar Constraints." AAAI Conference on Artificial Intelligence, 2008.](https://mlanthology.org/aaai/2008/kadioglu2008aaai-efficient/)BibTeX
@inproceedings{kadioglu2008aaai-efficient,
title = {{Efficient Context-Free Grammar Constraints}},
author = {Kadioglu, Serdar and Sellmann, Meinolf},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2008},
pages = {310-316},
url = {https://mlanthology.org/aaai/2008/kadioglu2008aaai-efficient/}
}