×

zbMATH — the first resource for mathematics

A regular language membership constraint for finite sequences of variables. (English) Zbl 1152.68573
Wallace, Mark (ed.), Principles and practice of constraint programming – CP 2004. 10th international conference, CP 2004, Toronto, Canada, September 27–October 1, 2004. Proceedings. Berlin: Springer (ISBN 978-3-540-23241-4/pbk). Lecture Notes in Computer Science 3258, 482-495 (2004).
Summary: This paper describes a global constraint on a fixed-length sequence of finite-domain variables requiring that the corresponding sequence of values taken by these variables belong to a given regular language, thereby generalizing some other known global constraints. We describe and analyze a filtering algorithm achieving generalized arc consistency for this constraint. Some comparative empirical results are also given.
For the entire collection see [Zbl 1139.68008].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI