rapaport@buffalo.CSNET ("William J. Rapaport") (03/13/87)
SECOND ANNUAL SUNY BUFFALO GRADUATE CONFERENCE ON COMPUTER SCIENCE
William J. Rapaport
Department of Computer Science
SUNY Buffalo
Buffalo, NY 14260
rapaport@buffalo.csnet
On 10 March 1987, the graduate students in the Department of Computer
Science at SUNY Buffalo held their second annual Graduate Conference on
Computer Science. (For a report on the first one, see SIGART No. 99,
pp. 22-24.) This time, the conference took on an international flavor,
with talks by graduate students from the University of Toronto and the
University of Rochester, in addition to talks by our own students. Once
again, the conference was flawlessly mounted. The conference was
sponsored by the SUNY Buffalo Department of Computer Science, the SUNY
Buffalo Computer Science Graduate Student Association, the SUNY Buffalo
Graduate Student Association, and the Niagara Frontier Chapter of the
ACM. Approximately 150 people from area colleges and industry attended.
A SUNY Buffalo Department of Computer Science Technical Report with
extended abstracts of the talks (James Geller & Keith Bettinger (eds.),
_UBGCSS-87: Proceedings of the Second Annual UB Graduate Conference on
Computer Science_, Technical Report 87-04, March 1987) is available by
contacting the chair of the organizing committee, Scott Campbell,
Department of Computer Science, SUNY Buffalo, Buffalo, NY 14260,
campbl@buffalo.csnet. Following are the abstracts of the talks.
Ted F. Pawlicki
SUNY Buffalo
"The Representation of Visual Knowledge"
This paper reports on preliminary research into the representation of
knowledge necessary for visual recognition. The problem is broken down
into three parts: the actual knowledge that needs to be represented,
the form that the representation should take, and how the knowledge
itself and its representation should combine to facilitate the visual
recognition task. The knowledge chosen to represent is a formalization
of the theory of Recognition by Component. The representation chosen is
a semantic network.
John M. Mellor-Crummey
University of Rochester
"Parallel Program Debugging with Partial Orders"
Parallel programs are considerably more difficult to debug than
sequential programs, because successive executions of a parallel program
often do not exhibit the same behavior. Instant Replay is a new
technique for reproducing parallel-program executions. Partial orders
of significant events are recorded during program execution and used to
enforce equivalence of execution replays. This technique (1) requires
less time and space to save information for program replay than other
methods, (2) is independent of the form of interprocess communication,
(3) provides for replay of an entire program, rather than individual
processes, (4) introduces no centralized bottlenecks, and (5) does not
require synchronized clocks or globally-consistent logical time. Some
performance results of a prototype on the BBN Butterfly [TM] Parallel
Processor will be presented, and it will be shown how Instant Replay can
be used in the debugging cycle for parallel programs.
Timothy D. Thomas and Susan J. Wroblewski
SUNY Buffalo
"Efficient Trouble Shooting in an Industrial Environment"
Our work involves designing and implementing a real-time system for
trouble shooting in an industrial environment. The system emulates the
kind of problem-solving knowledge and behavior typical of a human expert
after years of on-the-job experience. Our system, PASTE (Process
Analysis for Solving Trouble Efficiently), is to be used in a real-time
environment. It is because of this constraint that the design of an
efficient system was of great importance. PASTE has a number of
efficiency techniques that eliminate redundancy in remedy suggestion
and that decrease response time.
Ching-Huei Wang
SUNY Buffalo
"ABLS: An Object Recognition System for Locating Address Blocks on
Mail Pieces"
ABLS (Address Block Location System), a system for locating address
blocks on mail pieces, represents both a specific solution to postal
automation and a general framework for coordinating a collection of
specialized image-processing tools to opportunistically detect objects
in images. Images that ABLS deals with range from those having a high
degree of global spatial structure (e.g., carefully prepared letter mail
envelopes which conform to specifications) to those with no structure
(e.g., magazines with randomly pasted address labels). Its
problem-solving architecture is based on the blackboard model and
utilizes a dependency graph, knowledge rules, and a blackboard.
Diane Horton and Graeme Hirst
University of Toronto
"Presuppositions as Beliefs: A New Approach"
Most existing theories of presupposition implicitly assume that
presuppositions are facts and that all agents involved in a discourse
share belief in the presuppositions that it generates. We argue that
these assumptions are unrealistic and can be eliminated by treating
each presupposition as the belief of an agent. We describe a new model,
including an improved definition of presupposition, that takes this
approach. The new model is more realistic and can handle cases of
presupposition projection that could not be handled otherwise.
Norman D. Wahl and Susan E. Miller
SUNY Buffalo
"Hypercube Algorithms to Determine Geometric Properties of Digitized Pictures"
This research focuses on implementing algorithms to solve geometric
problems of digitized pictures on hypercube multiprocessors.
Specifically, in this paper, we present algorithms and paradigms for
solving the connected component labeling problem. Work is ongoing to
complete implementations of these algorithms and obtain running times on
the Intel iPSC and Ncube hypercubes. The goal of this study is to
determine under what circumstances (if any) each of the various
algorithms is most appropriate.
Deborah Walters and Ganapathy Krishnan
SUNY Buffalo
"Bottom-up Image Analysis for Color Separation"
A system for automatic color separation for use in the printing industry
is described. The goal of this research was to automate the
labor-intensive preprocessing required before a graphics system can
process the image. This system makes no assumptions about the semantic
content of the image. The processing is entirely bottom-up and is based
on image features used by the human visual system during the early
stages of processing. The image is convolved with oriented edge
operators, and the responses are stored in the Rho-Space representation.
A number of parallel operations are performed in Rho-Space, and the
image is segmented into perceptually significant parts, which can then
be colored using an interactive graphics system.
Bart Selman
University of Toronto
"Vivid Representations and Analogues"
Levesque introduced the notion of a vivid knowledge representation. A
vivid scheme contains complete knowledge in a tractable form. A closely
related concept is that of an analogical representation or analogue.
Sloman characterizes analogues as representations that are in some sense
direct models of the domain, as opposed to representations consisting of
a description in some general language. The prototypical example of an
analogical representation is a pictorial representation, which is also
an important source of vivid knowledge. We are studying these types of
representations for their possible application in computationally
tractable knowledge-representation systems. In particular, we are
studying how information in a non-analogical (or non-vivid) form can be
translated into an analogical (or vivid) form, using for example
defaults and prototypes. This talk will cover the properties of vivid
and analogical representations, a description of their relationship to
each other, and some initial ideas on the translation process.
Soteria Svorou
SUNY Buffalo
"The Semantics of Spatial Extension Terms in Modern Greek"
In recent years, there have been increasing efforts to uncover the
nature of the human mind by studying the structure of its building
blocks: concepts. Partaking in this enterprise, this study explores
the domain of spatial extension categories by looking at the way
language treats them. It shows that lexical contrasts of Modern Greek
in the domain of spatial extension reflect the perceptual strategies of
"orientation" and "Gestalt" and their interaction with the concept of
"boundedness", which speakers employ in the description of everyday
objects.
Yong Ho Jang and Hing Kai Hung
SUNY Buffalo
"Semantics of a Recursive Procedure with Parameters and Aliasing"
We consider a subset of an Algol-like programming language that
includes blocks and recursive procedures, with value and location
parameter passing. We develop the operational and denotational
semantics for both static and dynamic scope, with their different
aliasing mechanisms. The main advantage of our approach is that the
denotational semantics is compositional and can systematically handle
the various scope and aliasing features.
Josh D. Tenenberg and Leo B. Hartman
University of Rochester
"Naive Physics and the Control of Inference"
Hayes proposed the naive physics program in order eventually to
address problems involving the control of inference. At the time of the
proposal, progress toward solutions of these problems seemed impeded by
the lack of a well-defined body of knowledge of challenging size. The
building of a formally interpretable encoding of the common-sense
knowledge that people use to deal with the physical world seemed to fill
this need. It was argued that the knowledge be expressed in first-order
logic or an equivalent language in order to separate declarative
information from control information. We argue here that no finite
encoding of a formal theory can be completely separated from control
choices by virtue of there being well-defined measures of the depth of a
theorem in the deductive closure of a theory. In addition, any control
choice is a commitment to a particular set of statistical properties of
the problems an agent faces, and the measurement of such properties is
required to evaluate these choices.
Zhigang Xiang
SUNY Buffalo
"Multi-Level Model-Based Diagnostic Reasoning"
Diagnostic systems capable of reasoning from _functional_ and
_structural_ knowledge are _model-based_ systems. The uniqueness of our
work is that problems of diagnosis that need not only functional and
_logical_ structural knowledge but also _spatial_ structural knowledge
are to be the focus. Towards this goal, we propose a framework for
organizing, representing, and reasoning with an integrated knowledge
base that includes multiple levels of abstraction of the physical
system. More specifically, a physical system is decomposed into
physical and logical components. Analogical (geometrical) and
propositional (topological) spatial structural information are
associated with physical components. The latter is mutually related to
logical components. Functional relationships are established between
logical components. Logical reasoning infers the functional status of
logical components, whereas spatial reasoning performs fault
localization. The framework is carried out using semantic-network
representations. The implementation is independent of any given domain
of application. The system, when given a description of a physical
system's spatial structure, logical structure, and functional
relationships between logical components, performs logical as well as
spatial reasoning to locate faulty components, lesions, etc., from
symptoms and findings. Domain-specific examples include circuitry fault
localization and neuroanatomic localization.