zbMATH — the first resource for mathematics

Global grammar constraints. (English) Zbl 1160.68560
Benhamou, Frédéric (ed.), Principles and practice of constraint programming – CP 2006. 12th international conference, CP 2006, Nantes, France, September 25–29, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-46267-5/pbk). Lecture Notes in Computer Science 4204, 751-755 (2006).
Summary: Global constraints are an important tool in the constraint toolkit. Unfortunately, whilst it is usually easy to specify when a global constraint holds, it is often difficult to build a good propagator. One promising direction is to specify global constraints via grammars or automata. For example, the Regular constraint permits us to specify a wide range of global constraints by means of a DFA accepting a regular language, and to propagate this constraint specification efficiently and effectively. More precisely, the Regular constraint ensures that the values taken by a sequence of variables form a string accepted by the DFA. In this paper, we consider how to propagate such grammar constraints and a number of extensions.
For the entire collection see [Zbl 1141.68004].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
Full Text: DOI