NFA propagator for regular constraint with explanations

Bachelor thesis (2025)

Authors

J. Gvozdiovas Electrical Engineering, Mathematics and Computer Science

Contributors

E. Demirović Algorithmics - EEMCS (mentor)
M.L. Flippo Algorithmics - EEMCS (mentor)
B.P. Ahrens Programming Languages - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science
More Info
expand_more

Published Date

30-01-2025

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

The regular constraint offers good balance between expressiveness and cost. Despite potential exponential blow-up, existing approaches use deterministic automata. Furthermore, the area of combining conflict-driven learning with regular is unexplored. We combine learning with non-determinism, to produce an NFA-based propagator with explanations, and compare its performance against decomposition of the constraint. Experimental results on Nonogram
instances indicate that our specialized propagator is significantly better than decomposing regular constraint.

Files

Paper.pdf
(pdf | 0.382 Mb)
Unknown license