Title

Solving Constraint Satisfaction Problems Using Finite State Automata

Abstract

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

12-1-1992

Publication Title

Proceedings Tenth National Conference on Artificial Intelligence

Number of Pages

453-458

Document Type

Article; Proceedings Paper

Identifier

scopus

Personal Identifier

scopus

Socpus ID

0026961096 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0026961096

This document is currently not available here.

Share

COinS