Solving Constraint Satisfaction Problems Using Finite State Automata


In this paper, we explore the idea of representing CSPs using techniques from formal language theory. The solution set of a CSP can be expressed as a regular language; we propose the minimized deterministic finite state automation (MDFA) recognizing this language as a canonical representation for the CSP. This representation has a number of advantages. Explicit (enumerated) constraints can be stored in lesser space than traditional techniques. Implicit constraints and networks of constraints can be composed from explicit ones by using a complete algebra of boolean operators like AND, OR, NOT, etc., applied in an arbitrary manner. Such constraints are stored in the same way as explicit constraints - by using MDFAs. This capability allows our technique to construct networks of constraints incrementally. After constructing this representation, answering queries like satisfiability, validity, equivalence, etc., becomes trivial as this representation is canonical. Thus, MDFAs serve as a means to represent constraints as well as to reason with them. While this technique is not a panacea for solving CSPs, experiments demonstrate that it is much better than previously known techniques on certain types of problems.

Publication Date


Publication Title

Proceedings Tenth National Conference on Artificial Intelligence

Number of Pages


Document Type

Article; Proceedings Paper



Personal Identifier


Socpus ID

0026961096 (Scopus)

Source API URL


This document is currently not available here.