Accession Number : AD0718994

Title :   Networks of Constraints: Fundamental Properties and Applications to Picture Processing,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Montanari,Ugo

Report Date : JAN 1971

Pagination or Media Count : 57

Abstract : The problem of representation and handling of constraints is here considered, mainly for picture processing purposes. A systematic specification and utilization of the available constraints could significantly reduce the amount of search in picture recognition. On the other hand, formally stated constraints can be embedded in the syntactic productions of picture languages. Only binary constraints are treated here, but they are represented in full generality as binary relations. Constraints among more than two variables are then represented as networks of simultaneous binary relations. In general, more than one equivalent (i.e., representing the same constraint) network can be found: a minimal equivalent network is shown to exist, and its computation is shown to solve most practical problems about constraint handling. No exact solution for this central problem was found. Anyway, constraints are treated algebraically, and the solution of a system of linear equations in this algebra provides an approximation of the minimal network. This solution is then proved exact in special cases, e.g., for tree-like and series parallel networks and for classes of relations for which a distributive property holds. This latter condition is satisfied in cases of practical interest. (Author)

Descriptors :   (*COMPUTER PROGRAMMING, *PATTERN RECOGNITION), MATHEMATICAL MODELS, DATA PROCESSING, COMPUTER LOGIC, BINARY ARITHMETIC, ALGORITHMS, GRAPHICS, THEOREMS

Subject Categories : Computer Programming and Software
      Computer Hardware
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE