A Paradigm for Efficient Subset Recognition
Abstract
The notion of a finite-state automation is examined with regard to problems involving the recognition of sets rather than strings. More precisely, this paper is concerned with the application of the methodology of automata theory to the general problem of efficiently determining whether a set A (or possible a subset of A) is a subset of a set of sets S. The following contributions result from this examination: (1) The traditional notion of a finite-state automation is shown to be impractical for use in set recognition; (2) Set-expressions, which are roughly analogous to regular expressions, are formally defined as a notation for describing member-qualified sets or classes of sets; (3) A set-recognizing automation (SRA) is formally defined and an algorithm is presented for its construction from a given set-expression; and (4) More powerful forms of SRA's; are developed which may have important practical applications in the area of artificial intelligence. In particular, the subset machine is developed for the fast processing of a restricted class of IF-THEN rules. Algorithm descriptions as well as LISP routines are provided. (Author) (kr)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1990
- Accession Number
- ADA227694
Entities
People
- Jeffrey Uhlmann
Organizations
- United States Naval Research Laboratory