Browse Prior Art Database

BIBLIOGRAPHY OF COMPUTING RESEARCH LABORATORY REPORTS, 1986

IP.com Disclosure Number: IPCOM000128493D
Original Publication Date: 1987-Jan-01
Included in the Prior Art Database: 2005-Sep-16
Document File: 8 page(s) / 28K

Publishing Venue

Software Patent Institute

Related People

UM Computing Research Laboratory: AUTHOR [+3]

Abstract

This report lists, in chronological order, all reports published in 1986 by the Computing Research Laboratory of the University of Michigan. Each report is identified by the Laboratory number, author(s), title, number of pages and date. In the Bibliography which follows, there is a listing of abstracts of publications produced by the Computing Research Laboratory at The University of Michigan during 1986. These publications are available from: The Computing Research Laboratory The University of Michigan 2222 EECS Building Ann Arbor, Michigan 48109-2122 (313) 763-8000

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 16% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

BIBLIOGRAPHY OF COMPUTING RESEARCH LABORATORY REPORTS, 1986

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY CRL-TR-1-87

January 1987

Room 2222, EECS Building
Ann Arbor, Michigan 48109-2122
USA
Tele: (313)763

Abstract

This report lists, in chronological order, all reports published in 1986 by the Computing Research Laboratory of the University of Michigan. Each report is identified by the Laboratory number, author(s), title, number of pages and date. In the Bibliography which follows, there is a listing of abstracts of publications produced by the Computing Research Laboratory at The University of Michigan during 1986. These publications are available from:

The Computing Research Laboratory

The University of Michigan 2222 EECS Building
Ann Arbor, Michigan 48109-2122 (313) 763-8000

[ Abstract of: ] CRL-TR-1-86. D.J. Harkai, "Bibliography of Computing Research Laboratory Reports, l985," January 1986, 14 pages.

This report lists, in chronological order, all reports published in 1985 by the Computing Research Laboratory of the University of Michigan. Each report is identified by the Laboratory number, author(s), title, number of pages, and date.

[ Abstract of: ] CRL-TR-2-86. B.A. Nadel, "The General Consistent Labeling (or Constraint Satisfaction) Problem," January 1986, 53 pages.

University of Michigan Computing Research Laboratory Page 1 Jan 01, 1987

Page 2 of 8

BIBLIOGRAPHY OF COMPUTING RESEARCH LABORATORY REPORTS, 1986

A central Problem in Artificial Intelligence and Operations Research is the Consistent Labeling (or Constraint Satisfaction) Problem CLP. This paper formulates CLP at a level of generality far beyond that usually treated, partitions it in various ways and introduces several probability models over the equivalence classes of these partitions. One partition of CLP is into small- classes, which have the very desirable homogeneity property that most instances within a given small-class have similar complexity of solution. This is the partition sought (but not found) by Gaschnig in his thesis [ 26 ] . Small-class homogeneity means that a small-class expected-case value can be used as a good approximation to the exact-case complexity of solving individual subsumed instances of the class. Our small-class expected complexity expressions thus provide for the first time a formal means of making problem-solving decisions (regarding which search-ordering, which algorithm and even which problem representation to use) that are good on an instance-by- instance basis. Various enumerative, combinatorial and probabilistic results are derived for the partitions and the probability models introduced over CLP. Our subsequent paper [ 52 ] uses these results to derive expected-case complexities for CLP problem-solving by three important algorithms, Backtracking, Forward-Checking and word-wise Forward-Checking.

[ Abstract of: ] CRL-TR-3-86. B.A. Nadel, "Three Constrain...