CMU Artificial Intelligence Repository
Home INFO Search FAQs Repository Root

INTERVALS: Prolog sets-as-interval predicates

lang/prolog/code/ext/interval/
This package defines predicates for manipulating sets of integers, represented as lists of disjoint intervals. This is a compact way of representing large sets, provided that they contain few gaps between intervals. Here are two examples of the representation: Set Representation { -32768 .. 32767 } [ -32768--32767 ] { 1,3,4,5,9,10,11,12,15,16,100,101,102} [ 1--1, 3--5, 9--12, 15--16, 100--102 ] The predicates in this package include ones for forming the union, intersection, and difference of such sets, and for various operations on single intervals. For efficiency, the sets are kept in a canonical form. The intervals are disjoint, and are in ascending order, and form a minimal covering (i.e., there is no other representation of a set, using fewer intervals). There is a predicate for converting a list of arbitrary unordered intervals into a canonical form. The predicates are useful when writing programs for syntax-directed translation of character data. For example, some tag field on a line may specify that the line is a record of type R1 if the field lies in the set C1 of characters, or a record of type R2 if the field lies in the set C2 of characters, and so on. Using these predicates, one can check for ambiguous specifications by testing whether C1 and C2 overlap; and one can generate quick tests for whether some character is in C1 or C2 by knowing that the set are represented by as few intervals as possible. 
Origin:   

   src.doc.ic.ac.uk:packages/prolog-pd-software/ (146.169.2.1)
   as intervals.tar.Z
Version: 21-DEC-87 Ports: Edinburgh-compatible Prologs CD-ROM: Prime Time Freeware for AI, Issue 1-1 Author(s): Jocelyn Paine Department of Experimental Psychology Oxford University South Parks Road Oxford OX1 3UD Tel: (0865) 271444 Fax: (0865) 310447 Keywords: Authors!Paine, Oxford, Prolog!Code, Prolog!Extensions, Sets as Intervals References: ?
Last Web update on Mon Feb 13 10:33:35 1995
AI.Repository@cs.cmu.edu