ted@nmsu.edu (Ted Dunning) (01/14/91)
Recent Memoranda in Computer and Cognitive Science
For ordering technical reports listed below write to:
Memoranda Series
Computing Research Laboratory
Box 30001
New Mexico State University
Las Cruces, New Mexico 88003
USA
For further information via email, send questions to bguzman@nmsu.edu
Wilks, Y., (1990), Smolensky and Fodor on connectionism, CRL,
MCCS-86-79. ($5.00)
This note seeks to compare, in very brief compass, a current radical
argument for connectionism and a radical argument against. It is not
clear that the very same version of connectionism is defended by
Smolensky as is attacked by Fodor, but since I do not bring the two
arguments directly in contact, that will not matter. My own
inconclusive view is that the jury is still out, and that, in the
meantime, while there is no convincing evidence to believe what
Smolensky says, though one may respect it and be stimulated by it,
neither should one reject the whole enterprise on the grounds Fodor
gives. One can legitimately be, in a narrow and strict sense, an
agnostic, without giving that word the force of active disbelief it is
often made to carry.
Wilks, Y., (l988), Philosophy of Language and Artificial Intelligence,
CRL, MCCS-88-132. ($5.00)
The paper surveys the relationship between AI and the philosophy of
language. AI is normally described either as an engineering task, one
of simulating certain interesting human functions (i.e. not
arithmetic) with digital computers or, at a higher level, as an
attempt to explicate computationally the nature of intelligence. The
history of practice in AI owes far more to the Leibnizian goal of a
mechanical logic than to, say, robotics, the view of AI always taken
by cartoonists. The point of view behind the survey is probably that
of Wittgenstein's ``Philosophy leaves everything as it is''. One
might extend that, with no greater respect for philosophy, as
``Artificial Intelligence leaves philosophy as it is'', which is to
say that no philosophical consequences follow from any piece of
research in artificial intelligence and no particular philosophical
assumptions are needed to carry out such research.
Eskridge, T.C., (1988), A Continuous Approach to Analogical Reasoning,
CRL, MCCS-88-135. ($5.00)
Analogical reasoning has traditionally been separated into three
stages: selection, mapping and use. The difficulty with this approach
is that the separation of analogical reasoning into stages hinders
sharing of information between stages. This results in inefficiencies
arising from the need to re-create the information lost between
stages. Continuous analogical reasoning is an approach developed to
overcome these inefficiencies by sharing information between the three
stages and using this information to constrain selection and mapping
and improve the efficiency of the system.
Eskridge, T.C., (1988), Access in Analogical Reasoning, CRL,
MCCS-88-136. ($5.00)
Analogical access requires the location of relevant information in a
long-term memory of past experiences that can aid in the solution of a
current problem. Accessing relevant information requires a flexible
measure of similarity, that changes with the goals and context of the
agent. Once the relevant information has been found, it must be
modified to achieve the current goals. This paper discusses
analogical access in ASTRA, a computational model of analogical
reasoning and problem solving. Features of the architecture that
provide for analogical access and the procedural aspects of retrieval
are discussed. Wilks, Y., (l988), Form and content in semantics, CRL,
MCCS-88-137. ($5.00) This paper continues a strain of intellectual
complaint against the presumptions of certain kinds of formal
semantics (the qualification is important) and their bad effects on
those areas of artificial intelligence concerned with machine
understanding of human language. The paper begins with a critical
examination of Lifschitz' (out of McCarthy) use of epistemological
adequacy. The paper then moves, rather more positively, to contrast
forms of formal semantics with a possible alternative: commonsense
semantics. Finally, as an in-between case of considerable interest,
it examines various positions held by McDermott on these issues and
concludes, reluctantly, that, although he has reversed himself on the
issue, there was no time at which he was right.
Ballim, A., Wilks, Y., & Barnden, J., (l988),
Belief Ascription, Metaphor, and Intensional Identification, CRL,
MCCS-88-138. ($5.00)
This paper discusses the extension of ViewGen, an existing algorithm
for belief ascription, to the areas of speech acts, intensional object
identification and metaphor. ViewGen represents the beliefs of agents
as explicit, partitioned proposition-sets known as environments.
Environments are convenient, even essential, for addressing important
pragmatic issues of reasoning. The paper concentrates on showing that
the transfer of information in metaphors, intensional object
identification, and ordinary, non-metaphorical belief ascription can
all be seen as different manifestations of a single
environment-amalgamation process. The paper also briefly discusses
the addition of a heuristic relevance-determination procedure to
ViewGen, and justifies the partitioning approach to belief ascription.
Barnden, J., (l988), Propositional Attitudes, Polysemy and Metaphor:
Initial Report, CRL, MCCS-88-139. ($5.00)
This report summarizes initial progress on a Natural Language
Processing research project that concentrates on certain issues
concerning propositional attitudes, metaphor and polysemy, and
outlines the work that is anticipated on it. The significance of the
project lies in its novel, commonsensically powerful approach to
propositional-attitude representation for Artificial Intelligence
purposes, its support for the view of metaphor as a source of
coherence in discourse, notably in understanding talk about
propositional attitudes, and its attitude-sensitive treatment of a
general polysemy issue. In particular, propositional-attitude verbs
are themselves treated as being vague and polysemous, the polysemy
arising from the multitude of metaphors that are commonly used in
discourse for talking about mental states. The type of mental-state
discourse of primary (though not exclusive) interest is the
propositional attitude report. Such a report is a sentence, like
``Zorn hopes that Xavier's theory is faulty'', that states a belief,
wish, intention, hope or some other ``propositional attitude''. A
nested attitude report is one in which what is believed, desired,
hoped for, etc. is itself a propositional attitude, as in ``Zorn hopes
that Xavier realizes that his theory is faulty''. I focus on the
coherence between a nested attitude report and surrounding discourse.
The establishment of such coherence often mandates that the inner
attitude be given a commonsensical explication (elaboration,
expansion, decomposition), rather than be represented in one of the
more abstract, psychologically emasculated ways currently favored in
attitude-representation research. Moreover, contemporary research on
metaphor strongly suggests that these explications should be
metaphorical, using one of the many metaphors typically used by people
to reason and talk commonsensically about minds. One such metaphor is
of the mind as containing a battleground in which the combatants are
ideas and other mental entities; so the Zorn/Xavier sentence might
most coherently be understood, with respect to a given surrounding
discourse, as connoting that Zorn hopes that the idea of the theory
being faulty will win on the mental battleground. An AI natural
language processing system, able to explicate attitudes in any one of
a variety of metaphorical ways, will be built. This system, called
ATT-META, will be an extension of an existing, working program (Meta5,
by Fass) that is able to process some types of metaphorical (and
metonymic) language. ATT-META will have a default mode of
metaphorical attitude-explication, based on the mental-space metaphor
exploited by Wilks & Ballim, Fauconnier, and Maida, amongst others.
ATT-META's foundation in commonsense metaphors will allow it to avoid
a class of non-commonsensical explications of attitudes that tend to
be unwittingly introduced by various existing, well-known approaches
to attitude representation (as previous work of mine shows). ATT-META
will be specialized to dealing with two, metaphorically related,
domains: physical battle and scientific enquiry. Perfectly mundane
sentences in these domains require a metaphor-based approach to
discourse coherence.
Lawrence-Fowler, W.A., (1988), A Microcomputer Data System For Aids
Vaccine Research, CRL, MCCS-88-140. ($5.00)
An interactive data retrieval system developed by the author is being
used for management of data from the Acquired Immune Deficiency
Syndrome research and vaccine testing conducted at the NMSU Primate
Research Institute. This report discusses aspects of its development:
conceptual analysis, system specification, prototype development,
verification and testing and documentation. This project demonstrates
that it is possible to construct a central data structure for
biomedical data systems requiring it.
Cimikowski, R., (1988), Finding the Chromatic Number of Delaunay
Graphs, CRL, MCCS-88-141. ($5.00)
An "inner triangulation is a 2-connected planar graph in which every
interior face (but not necessarily the exterior) is a triangle. Such
graphs are known to include the family of proximity graphs known as
Delaunay triangulations. A characterization of 3-colorable
inner-triangulated graphs is given. A simple test for 3-colorability
of such graphs follows directly from the main result. Finally, we
present a linear-time algorithm for finding a 3-coloring, if one
exists.
Barnden, J., (l988), Towards a Paradigm Shift in Belief Representation
Methodology, CRL, MCCS-88-142. ($5.00)
Research programs must often divide issues into manageable sub-issues.
The assumption is that an approach developed to cope with a sub-issue
can later be integrated into an approach to the whole issue - possibly
after some tinkering with the sub-approach, but without affecting its
fundamental features. However, the present paper examines a case
where an AI issue has been divided in a way that is, apparently,
harmless and natural, but is, actually, fundamentally out of tune with
the realities of the issue. As a result, some approaches developed
for a certain sub-issue cannot be extended to a total approach without
fundamental modification. The issue in question is that of
representing and reasoning about people's beliefs, hopes, intentions
and other ``propositional attitudes'', and/or interpreting natural
language sentences that report propositional attitudes. Researchers
have, quite understandably, de-emphasized the problem of dealing in
detail with nested attitudes (e.g. hopes about beliefs, beliefs about
intentions about beliefs), in favour of concentrating on the sub-issue
of non-nested attitudes. Unfortunately, a wide variety of approaches
to attitudes are prone to a deep but somewhat subtle problem when they
are applied to nested attitudes. This problem can be very roughly
described as an AI system's unwitting imputation of its own arcane
``theory'' of propositional attitudes to other agents. The details of
this phenomenon have been published elsewhere by the author: the
present paper therefore merely sketches it, and concentrates instead
on the methodological lessons to be drawn, both for propositional
attitude research and, more tentatively, for AI in general. The paper
also summarizes an argument (presented more completely elsewhere) for
an approach to attitude representation based in part on metaphors of
mind that are commonly used by people. This proposed new research
direction should ultimately coax propositional attitude research out
of the logical armchair and into the psychological laboratory.
Slator, B., (l988), Lexical Semantics and Preference Semantics
Analysis, (Ph.D. Thesis), CRL, MCCS-88-143. ($15.00)
This dissertation describes a computational system for the analysis of
English prose under the Preference Semantics theory of language
understanding. The two main areas of investigation are these:
* the design and implementation a series of programs for extracting
semantic information from a machine-readable dictionary, with this
semantic information in a form suitable for use by a subsequent
semantic analysis program, and
* the design and implementation of a semantic analysis program that
accepts short English texts and creates a corresponding representation
from them. The resulting representation is in a suitable form, such
that other Artificial Intelligence programs can use it as a knowledge
source.
Coombs, M.J. & Hartley, R.T., (1988), Design of a Software Environment
For Tactical Situation Development, CRL, MCCS-88-144.
This paper concerns the development of a prototype Tactical Situation
Development Environment (TSDE) which will aid intelligence analysts to
construct and evaluate future situational projections and will support
this function by maintaining appropriate models of the current
situation. Conventional automated problem solvers have failed in
these tasks because they are deterministic, being designed to solve
pre-determined problems using pre-defined sets of knowledge and data.
They are unable to accommodate the uncertainty and dynamic events
characteristic of the realistic battlefield. In contrast, we have
employed a general-purpose automated problem solving architecture -
Model Generative Reasoning (MGR) - designed for information processing
in noisy and ill-specified problem domains. The MGR architecture is
currently being developed for a number of military information
integration applications, including meteorological data fusion,
situation analysis and deception planning.
Barnden, J.A., (1988), Conposit, A Neural Net System for High-Level
Symbolic Processing: Overview of Research and Description of
Register-Machine Level, CRL, MCCS-88-145. ($5.00)
High-level cognitive information processing reasoning, planning,
semantic and inferential aspects of natural language understanding,
and so on presents a recognized challenge to connectionism. A
promising approach is to encode short-term symbolic data structures in
connectionist systems by means of two unusual techniques, here called
Relative-Position Encoding and Pattern-Similarity Association. These
techniques enable a connectionist/neural-net system named Conposit to
accomplish rule following, variable binding, and construction and
analysis of complex, temporary, symbolic data structures. In
Conposit's Relative-Position Encoding, complex temporary data
structuring is achieved by placing symbols (patterns of activity) in
registers (neural/connectionist subnetworks). The set of registers is
structured as a two-dimensional array, in which it is mainly the
temporary relative positioning of symbols that embodies the structure
of short-term data. The report describes Conposit in detail at the
register-machine level, and summarizes a suggested connectionist
implementation of the register machine, leaving a detailed account of
the connectionist implementation to be presented in another report.
The present report also explains the research strategies under which
Conposit is being developed. Part of the intention in developing
Conposit is for it to act as heuristic guidance in the future
development of models of high-level cognitive information processing
in the brain. Tentative suggestions have been made elsewhere about
implementation of Conposit in cortical neural networks. Though crude
and heuristic, these suggestions allow reasonable timing hypotheses
(e.g. about speed and distance of travel of the neural signals) to be
included in Conposit simulations.
Eskridge, T.C., (1988), Principles of Continuous Analogical Reasoning,
CRL, MCCS-88-146. ($5.00)
This paper presents evidence supporting the view of analogical
reasoning as a continuous process. The phrase Continuous Analogical
Reasoning refers to the continuous flow of information between the
three processes in analogical reasoning: selection, mapping and
evaluation. This paper presents the motivations behind the
development of the continuous analogical reasoning approach, along
with evidence of the interactions between stages from the
psychological community. Implications for Discrete Analogical
Reasoning systems are discussed. The implementation of a continuous
analogical reasoning system called ASTRA is presented and discussed in
terms of the interactions between stages.
Fowler, R.H. & Dearholt, D.W., (l989), Pathfinder Networks in
Information Retrieval, CRL, MCCS-89-147. ($5.00)
We have developed information retrieval systems that apply an
empirically derived network representation, Pathfinder networks
(PFNETs), to several aspects of the retrieval process. PFNETs are used
to provide refinements to relatively well understood IR techniques,
such as retrieval based on document networks, as well as explore
somewhat novel applications, including the direct, graphic
manipulation of information structures. PFNETs are used to provide
efficient, automatically derived graph representations for natural
language text that retain some of the advantages of richer, but less
tractable, representations. The different associational networks in
the system provide the user multiple paths of access to information
items.
Zhao, Z., (l989), Edge Detection with Q-B-Spline Operator, CRL,
MCCS-89-148. ($5.00)
NO ABSTRACT
Schvaneveldt, R., (1989), Proximities, Networks, and Schemata, CRL,
MCCS-89-149. ($5.00)
This paper examines the representation of schemata in networks
(weighted graphs) and the use of activation to instantiate the
schemata in particular contexts. The following questions are of
interest: (1) Can direct judgments of co-occurrence provide the basis
for such networks? (2) Are the (nearly) complete networks of the
connectionist variety essential, or will sparse networks such as
Pathfinder networks suffice? (3) How critical are the particular
concepts included and the particular activation procedures?
Fowler, R.H., Slator, B.M., & Balogh, I., (1989),
On Psychological Plausibility in Artificial Intelligence, CRL,
MCCS-89-150. ($5.00)
The Artificial Intelligence literature is liberally laced with claims
about cognitive reality. Sometimes these are strong claims that cite
empirical psychological evidence; but more often these claims take the
form of weak appeals to ``psychological plausibility.'' To examine the
nature and scientific status of these claims, AI research is
characterized along a particular dimension, cast as the
``psychological evidence line.'' Then, some ideas about theory in AI
are examined, especially the thorny notion of ``models'' in AI
theories: what does it mean to use human intellect as a model in an AI
theory, or in an AI program? Then, as is so often the case, further
light is shed by an historical characterization, giving evidence for a
particular grouping of ``camps'' in AI, according to how psychological
evidence ``matters'' to them. These discussions set the scene,
finally, for an examination of the role (really, roles) that
psychological plausibility actually plays in AI; and this leads
naturally into a discussion, and some conclusions, about which of
these roles are appropriate, and which are not.
Harary, F., Graham, N., Livingston, M., & Stout, Q.F., (1990),
Subcube Fault-Tolerance in Hypercubes, CRL, MCCS-89-151. ($5.00)
We consider the problem of determining the minimum number of faulty
processors, k(n,m), and of faulty links, (n,m), in an n -dimensional
hypercube computer so that every m -dimensional subcube is faulty.
Best known lower bounds for k(n,m) and (n,m) are proved, several new
recursive inequalities and new upper bounds are established, their
asymptotic behavior for fixed m and for fixed n - m are analyzed, and
their exact values are determined for small n and m . Most of the
methods employed show how to construct sets of faults attaining the
bounds. An extensive survey of related work is also included, showing
connections to resource allocation, k -independent sets, and
exhaustive testing.
Barnden, J., (1989), Neural-Net Implementation of Complex
Symbol-Processing in a Mental Model Approach to Syllogistic Reasoning,
CRL, MCCS-89-154. ($3.00)
A neural net system called ``Conposit'' is described. Conposit
performs rule-based manipulation of very short term, complex symbolic
data structures. This paper concentrates on a simulated version of
Conposit that embodies core aspects of Johnson-Laird's mental model
theory of syllogistic reasoning. This Conposit version is not
intended to be a psychological theory, but rather to act as a test and
demonstration of the power and flexibility of Conposit's unusual
connectionist techniques for encoding the structure of data.
Barnden, J., (1989), Belief, Metaphorically Speaking, CRL,
MCCS-89-155. ($5.00)
The central claim of the paper concerns AI systems that attempt to
represent propositional attitudes in realistic situations, and
particularly in situations portrayed in natural language discourse.
The claim is that the system, in order to achieve a coherent, useful
view of a situation, must often ascribe, to outer agents, views of
inner agents' attitudes that are based on rich explications in terms
of commonsense metaphorical views of mind. This elevates the
emasculated metaphors based on notions of world, situation, container,
and so on that underlie propositional attitude representation
proposals to the status of explicitly-used, rich metaphors. A system
can adopt different patterns of commonsense inference about attitudes
by choosing different metaphors. The current stage of development of
a detailed representation scheme based on the claim is described. The
scheme allows different metaphors to be used for the explication of
attitudes at different levels in a nested-attitude situation.
Guo, C-M., (1989), Constructing A Machine Tractable Dictionary From
Longman Dictionary of Contemporary English, (Ph.D. Thesis), CRL,
MCCS-89-156. ($7.00)
It is the purpose of this research to design a machine-tractable
dictionary (henceforth MTD) from Longman Dictionary of Contemporary
English (henceforth LDOCE). The MTD is intended to be a basic
facility for a whole spectrum of natural language processing tasks.
The research adopts a compositional-reduction approach to obtain a
formalized set of definitions of sense entries in a nested predicate
form, where the predicates are a set of "seed sense". The focus of
this research is on the derivation of these "seed senses" and their
utilization in the construction of the MTD.
The Construction of the proposed MTD involves the following four
steps:
1: Determine the "defining senses" of LDOCE, i.e., those
world senses that are used in the definition of the meaning of 2,137
``controlled words'' of LDOCE,
2: Derive the ``seed senses'' of LDOCE. The ``seed senses" are a
subset of the defining sense which are sufficient to define senses of
Step 1. The seen senses are taken as a natural set semantic
primitives derived from LDOCE;
3: Hand-code the initial knowledge base for the natural set of
semantic primitives derived from LDOCE;
4: Construct a MTD for the controlled words and the rest of LDOCE
words by means of bootstrapping process is a process of knowledge
acquisition from dictionary definition text.
Step 1 of the construction process has been completed. A total of
3,860 defining senses have been determined. Step 2 of the
construction process has also been completed. A total of 3,280 word
senses are found to be the seed senses of LDOCE. These seed senses
are taken as a natural set of semantic primitives derived from the
dictionary. The feasibility of Steps 3 and 4 of the construction
process have been demonstrated with implemented examples. What
remains to be accomplished is to complete Steps 3 and 4 to build a
full-sized MTD from LDOCE using as guidelines the results of initial
implementation of the two steps.
Harary, F., (l989), Generalized Ramsey Theory for Graphs XVI: Reduced
Ramsey Numbers, CRL, MCCS-89-157. ($3.00)
NO ABSTRACT
Soderlund, C.A. & Pfeiffer, J.J., (l989), Electric Tinkertoys User's
Manual, CRL, MCCS-89-158. ($5.00)
This software package provides the datatype and associated functions
necessary to build 3-D models. The user may build models from
entities which represent points, segments, polygons and objects. A
library of functions is provided to create, delete, traverse, and
return information about the contents of a model. The library also
contains computer vision specific functions to manipulate
transformation matrices for image analysis. The system features a
consistent representation of two and three dimensional objects.
Harary, F., Kim, S-r., & Roberts, F.S., (l989), Extremal Competition
Numbers as a Generalization of Turan's Theorem, CRL, MCCS-89-159. ($5.00)
NO ABSTRACT
Harary, F., (l989), The Edge-Distinguishing Chromatic Number of Paths
and Cycles, CRL, MCCS-89-160. ($5.00)
NO ABSTRACT
Harary, F., (l989), The graph of a boolean function, CRL,
MCCS-89-161. ($5.00)
NO ABSTRACT
Harary, F., (l989), On Meshy Trees, CRL, MCCS-89-162. ($5.00)
NO ABSTRACT
Harary, F., (l989), Kingmaker, Kingbreaker, And The Other Games Played
On A Tournament, CRL, MCCS-89-163. ($5.00)
NO ABSTRACT
Dunning, T., Farwell, D., Guthrie, L., & Helmreich, S., (l989),
Theoretical and Applied Aspects of Reversible Prolog Programs, CRL,
MCCS-89-164. ($5.00)
Given a one-to-one function f with a computable inverse and a Prolog
predicate P which computes f (that is, the goal p(x,Y) succeeds with
Y=y if and only if f (x) = y), we can ask the following questions:
1) Can the same predicate compute the inverse function (does the goal
p(X,y) succeed with X=x if and only if f(x) = y)?
2) Can the predicate determine that a pair (x,y) belongs to the graph
of a function? (does the goal p(x,y) succeed if and only if f (x) =
y)?
3) Can the predicate determine that a pair (x,y) does not belong to
the graph of the function? (does p(x,y) fail if f (x) = y) and
4) Can the predicate generate pairs (x,y) for which f (x) = y when
given the goal p(X,Y).
These are certainly sensible questions to ask and it is easy to
exhibit programs which have any combination of the properties implied
by questions 1 through 4. We formalize these properties, extend them
to binary predicates (relations in the mathematical sense), and also
give some results on the relationships between them. We describe an
interesting application in the area of natural language processing
where these properties hold. In the development of this machine
translation system, which translates sentences between any pair of
five languages, these properties have, in fact, been a central
concern. Finally, we give some useful heuristics for constructing
natural language processing programs which possess these properties.
Wanying, J., (l989), An Experiment of Technical Text Reproduction, CRL,
MCCS-89-165. ($5.00)
This study presents a method by which a system can reproduce a
technical text via discourse structure computed from original text.
The research approach engages two concepts: text comprehension and
text generation. Text comprehension is denoted by the construction of
a discourse tree and the generation of rhetorical sentences. Text
generation is a procedure by which a new narrative can be delineated
from the discourse tree.
Hartley, R.T. & Coombs, M., (l989), Reasoning with Graph Operations,
CRL, MCCS-89-166. ($5.00)
Problem solving is an analog to scientific method, wherein abduction
and deduction operate in a cyclic fashion to generate and refine a
series of hypotheses that purport to explain the observed data. Model
Generative Reasoning implements this cycle through a family of
operations on representations based on conceptual graphs. Specialize,
the operator that implements abduction generates alternative
hypotheses. Fragment removes potential incoherences from hypotheses,
while preserving coherence with the observations. This is seen as a
form of deduction with the aim of allowing more hypotheses to be
generated in the next cycle.
McKevitt, P. & Ogden, W.C., (1989), Wizard-of-Oz dialogues in the
computer operating systems domain, CRL, MCCS-89-167. ($l0.00)
A Wizard-of-Oz experiment was conducted for 14 subjects in the
computer operating systems domain. The Wizard-of-Oz technique is one
where subjects interact with a computer through typed dialogue and are
told that they are conversing with the computer. Subjects utterances
are sent to another monitor where an expert or ``Wizard'' sends back a
reply to the subject monitor. The experiment is described, and a set
of 14 log files of data is reported.
Coombs, M. J., Fields, C. A., & Hartley, R. T., (1989),
A Brief Overview of the Model Generative Reasoning (MGR) Problem
Solving Architecture, CRL, MCCS-89-168. ($5.00)
The MGR architecture was designed for symbolic problem solving in task
environments where data are noisy and problems are ill-defined. MGR
is an operator-based, shared memory system which integrates knowledge
representation techniques from artificial intelligence (AI) and
control concepts from systems theory. MGR-based systems are
abductive, being concerned with finding the best explanatory
hypotheses for available data, and formally related to the
structure-determined approach to problem solving.
Aidinejad, H., Johannes, E., & Balogh I.L., (l989),
Line Extraction from Images Using Chain Codes, CRL, MCCS-89-169. ($5.00)
A method for extracting straight lines from images using chain codes
is presented. The main feature of this method is that it finds long
straight lines in a time efficient manner. Chain codes are first
generated from an edge image, then the chains are partitioned into
sub-chains that are edge segments that form a straight line. Two
heuristics are used for determining the splitting points, one examines
a fixed portion of the chain the other looks at varying lengths of the
chain.
Williams, S.L. & Bertini, A., (l989), GIGS - A Graphical Interface
for Genomic Sequencing Final Report, CRL, MCCS-89-170. ($l0.00)
NO ABSTRACT
Ball, J.T., (l990), A Consideration of PROLOG, CRL, MCCS-90-l7l. ($5.00)
Previous analyses of Prolog as a programming language have adopted
both theoretical and empirical perspectives. Additionally, the
uniqueness of the language has elicited many subjective comments. The
result is an inconsistent collection of often contradictory
statements. Within this muddle, this paper attempts to outline a more
consistent statement of the usefulness of Prolog as a programming
language. The analysis is mostly empirical and considers the features
of Prolog which have or will prove useful for specific applications
areas. A discussion of similarities and differences between Prolog
and Lisp is also presented. Finally, some subjective statements about
the future of Prolog are considered.
Ball, J.T., (1990), UNIX Help Systems with Natural Language
Interfaces, CRL, MCCS-90-172. ($5.00)
The UNIX help domain has been the domain of choice for the development
of several natural language interface (NLI) projects. This paper
discusses the advantages and problems associated with the development
of such projects. As a case study, the UNIX Consultant (UC) project
is considered in some depth. The question of whether or not major
changes to UC have resulted in an improved system is addressed.
Soderlund, C.A., Shanmugam, P., & Fields, C.A., (1990),
gm User's Manual, Version 1.O alpha, 1 January 1990, CRL,
MCCS-90-173. ($5.00)
This document describes gene modeler (gm), a fully-automated software
system for the analysis of anonymous genomic DNA sequence data. gm
integrates conventional pattern analysis methods for locating
functional sites and performing statistical analyses of sequence
regions with geometric model-building to generate descriptions of
candidate genes contained within a sequence. The gm system also
includes menu, a menu-driven shell from which the pattern analysis
programs used by gm can be run interactively, and gmwin, a graphic
interface for displaying models build by gm. The gm system is
implemented entirely in C, with graphics based on X-windows version
11, and is intended for use on Unix workstations.
Barnden, J., (l990), Naive Metaphysics: A Metaphor Based
Approach To Propositional Attitude Representation (Unabridged
Version), CRL, MCCS-90-174. ($5.00)
In real natural language discourse, belief states and other mental
states are often described by appeal to a wide variety of rich
commonsensical models of mind. For instance, ideas are often cast as
being at different places within the mind, conceived of as a physical
space. There are many common enrichments of this commonsense model.
There are also other distinctly different models. The models of mind
that are used in discourse often play a crucial role in the coherence
of the discourse, since one's expectations about the inferences that a
mentioned agent may have made from his or her beliefs are often
strongly influenced by what commonsense model is being used to
describe the belief states. Markedly different patterns of expected
inference are supported by different models. Accordingly, we argue
that an AI system for understanding realistic discourse should use
mental-state representations that are directly based on commonsense
models of mind. We look in some detail at one such representation
scheme that is currently under development. The approach elevates the
emasculated commonsense models that are implicit in previous
propositional attitude (mental state) representation proposals to the
status of rich, explicitly used models. Since commonsense models of
mind are usually metaphorical, the approach forges a tight link
between propositional attitude representation and metaphor processing.
It can also be considered a specific application of the view of
investigators such as Hobbs, Carbonell, Lakoff and Johnson that
metaphor processing should play a crucial role in the understanding of
natural language. The approach can be described as "naive
metaphysics" by analogy to the notion of "naive physics".
Harary, F., (1990), Extremal Results on the Geodetic Number of a
Graph, CRL, MCCS-90-175. ($5.00)
The geodetic number, g(G), of a connected graph G is the minimum
number of points in a set S such that each point of G is either in S
or is on a geodesic joining a pair of points in S. We characterize
those graphs G for which g(G) = 2, p-l, or p. We also determine g(G)
for various classes of graphs including the cycles and unicyclic
graphs, complete bipartite and complete multipartite graphs, and
prisms. We then solve several extremal problems involving g(G) by
determining the maximum and minimum values for g(G) among graphs
having p points and q lines, as well as the minimum when both p and q
are given.
Roseborrough, M.J. & Ball, J.T., (l990), Phase I Development of an ULTRA
Interface, CRL, MCCS-90-176. ($5.00)
With the increased interest in the ULTRA Machine Translation System,
both from users and visitors to the CRL, a need has developed to
better illustrate its capabilities. In this paper we discuss the
application of X windows to develop a user interface to ULTRA.
Harary, F., (l990), On Graphs with Signed Inverses, CRL, MCCS-90-177.
($3.00)
A graph G is called invertible if its adjacency matrix A has an
inverse which is the adjacency matrix of some graph H . All such
graphs were shown by Harary and Minc to have the form . We now
introduce signed invertible (or briefly s-invertible) graphs G as
those whose inverse H is a signed graph. We identify two infinite
classes of s-invertible graphs: the paths of even order, and the
corona of any graph with . We then characterize s-invertible trees.
McKevitt, P., (l990), Data acquisition for natural language
interfaces, CRL, MCCS-90-178. ($5.00)
Natural language interfaces are computer programs which enable a human
user to interact with the computer through typed natural languages
like English. One of the most pressing problems in the development of
natural language interfaces is that of getting a program to work over
a respectable set of utterances. This is called the brittleness
problem . The problem occurs for even the simplest natural language
interfaces in limited domains. The problem is centrally one of
coverage, that is, coverage of language use and world knowledge, the
latter being less crucial in limited domains. The study of pragmatics
in natural language involves understanding natural language utterances
in their context, including the phenomena of anaphor or reference,
ellipsis, speech acts, and topic and focus. Recent empirical work has
shown that the most pressing problem in natural language interfaces is
not the processing of syntax, or even semantics, but pragmatics. This
is called the pragmatics problem . It is argued here that a major
millstone around the neck of natural language interfaces is that much
research tackles the problem by construction-intensive methods rather
than through data-intensive methods. A data-intensive method for the
design, development and testing of a natural language interfaces is
proposed, and results from an initial experiment are discussed. It is
argued that data-intensive methods will help in solving the
brittleness and pragmatics problems of today's natural language
interfaces.
Pan, Z. & McKevitt, P., (1990), OUI - A User Interface for OSCON, CRL,
MCCS-90-179. ($5.00)
OUI (OSCON User Interface) is a program developed to provide a
flexible, user-friendly, and efficient user interface for the OSCON
(Operating System CONsultant) system. OSCON is a natural language
interface implemented in Prolog which answers, in English, English
queries about computer operating systems. Queries are typed by the
user at the keyboard and the OUI interface passes these queries to
OSCON which provides answers in English. OUI is built as an
application of the X Window System using X Toolkit. OUI enables users
to type and edit queries easily with the facility of the mouse for
positioning. Design motivations, layout, operation, and
implementation paradigms are described.
Wilks, Y. & Hartley, R., (1990), Belief Ascription and Model Generative
Reasoning: joining two paradigms to a robust parser of messages, CRL,
MCCS-90-180. ($5.00)
This paper discusses the extension of ViewGen, a program for belief
ascription, to the area of intensional object identification with
applications to battle environments, and its combination in a overall
system with MGR, a Model-Generative Reasoning system, and PREMO a
semantics-based parser for robust parsing of noisy message data.
ViewGen represents the beliefs of agents as explicit, partitioned
proposition-sets known as environments. Environments are convenient,
even essential, for addressing important pragmatic issues of
reasoning. The paper concentrates on showing that the transfer of
information in intensional object identification and belief ascription
itself can both be seen as different manifestations of a single
environment-amalgamation process. The entities we shall be concerned
with will be ones, for example, the system itself believes to be
separate entities while it is computing the beliefs and reasoning of a
hostile agent that believes them to be the same entity (e.g. we
believe enemy radar shows two of our ships to be the same ship, or
vice-versa. The KAL disaster should bring the right kind of scenario
to mind). The representational issue we address is how to represent
that fictional single entity in the belief space of the other agent,
and what content it should have given that it is an amalgamation of
two real entities.
A major feature of the paper is our work on embedding within the
ViewGen belief-and-point-of-view system the knowledge representation
system of our MGR reasoner, and then bringing together the multiple
viewpoints offered by ViewGen with the multiple representations of
MGR. The fusing of these techniques, we believe, offers a very strong
system for extracting message gists from texts and reasoning about
them.
McKevitt, P. & Ogden, W.C., (l990), OSWIZ II: Wizard-of-Oz dialogues
in the computer operating systems domain, CRL, MCCS-90-181. ($ll.00)
A Wizard-of-Oz experiment was conducted for 12 subjects in the
computer operating systems domain. The Wizard-of-Oz technique is one
where subjects interact with a computer and are told that they are
conversing with the computer. Subject utterances are sent to another
monitor where an expert or "Wizard" sends back a reply to the subject
monitor. The experiment described here is in the computer operating
systems domain and the medium of communication is typed written
interactive dialogue. This technique has two improvements on a
previous experiment (see Mc Kevitt and Ogden l989). First, tasks are
presented as pictures rather than in English to reduce biasing of user
queries. Second, wizard responses are selected and edited from a menu
which increases wizard response time. The experiment is described,
and a set of 12 log files of data is reported.
Harary, F. & Livingston, M., (l990), Domination and Independent
Domination Numbers for Hypercubes Are Not Always Equal, CRL,
MCCS-90-182. ($3.00)
The domination number a and the independent number a ' are trivially
seen to be equal for the smallest hypercubes with n L< 4. However we
find for that a = 7 and a ' = 8. The exact values of a and a ' are
not known for all larger hypercubes. However an infinite family of
hypercubes are observed to satisfy a = a ' . Several unsolved
problems readily suggest themselves.
Iverson, E. & Hartley, R., (1990), Metabolizing Music, CRL,
MCCS-90-183. ($3.00)
The paper introduces Metamuse, a program that analyzes a piece of
music by breaking it into its component parts and then reassembling it
into a similar piece. This is done through autocatalytic set theory,
which effectively allows portions of a string to break apart other
portions, much like a conventional chemical reaction. The end result
of this process is a set of substrings that reflect the overall
structure in that they are biased towards repetitive patterns present
within the piece as a whole. The autocatalytic process can then be
run in reverse until a target goal is reached. Metamuse allows for a
certain degree of evolution, since strings are allowed to copy
themselves after catalyzing a reaction, with mutations sometimes
occurring as a result. In this way a fitness metric is introduced
such that strings which catalyze a number of reactions will be deemed
more fit than others. Strings which are unable to catalyze reactions
are excluded from the autocatalytic set and not allowed to replicate.
In this way, self-organizing behavior can be simulated, thereby
allowing for variations of a musical piece to be constructed in a
non-deterministic manner.
Coombs, M.J., Hartley, R.T., & Pfeiffer, H.D., (l990),
Developing Computing Technology for Modeling Enemy Intentions using
Environmental and Doctrinal Information, CRL, MCCS-90-184. ($3.00)
Intelligence analysis is a complex task in need of automated support.
However, conventional AI approaches have proved too deterministic for
application in the uncertain data environments that characterize the
intelligence analysis. This paper discusses a novel, "generative"
approach to support using the CRL Model Generative Reasoning (MGR)
general-purpose, problem solving system designed for information
processing in noisy and ill-specified problem domains.
Cohen, M.S. & Julian, W.H., (1990), Optical Multi-wave Resonances and
Generalized Volume Holography, CRL, MCCS-90-185. ($5.00)
We exhibit the information-processing capabilities of the first few
terms that arise in the amplitude expansion for resonant scattering in
a medium with a delay nonlinearity (generalized volume-hologram). We
begin by showing how the physics of intensity-dependent charge
transport near a two-photon resonance gives both delayed quadratic and
quartic nonlinearities. After reviewing the utility for matrix
"associative memories" exhibited by the delayed quadratic nonlinearity
(the ordinary Gabor hologram), we examine the role of the quartic
nonlinearity, which is a fourth rank tensor. The symmetries of this
tensor determine the information processing abilities (via multilinear
correlations) of the medium in an optical computing paradigm. We find
multiple basins of stability, Jordan strings, and cycles as possible
dynamical behaviors for the medium. We indicate how each corresponds
to an information processing task: multiple basins to
multi-associative memory, Jordan strings and cycles to chain
(sequence) memory and to group invariant pattern recognition. We
briefly indicate how branching processes may be implemented by the
fourth-rank mode coupling tensor.
Barnden, J. & Srinivas, K., (1990), Encoding Techniques for Complex
Information Structures in Connectionist Systems, CRL, MCCS-90-186. ($5.00)
Two general information-encoding techniques called ``relative-position
encoding'' and ``pattern-similarity association'' are presented. They
are claimed to be a convenient basis for the connectionist
implementation of complex, short-term information processing of the
sort needed in commonsense reasoning, semantic/pragmatic
interpretation of natural language utterances, and other types of
high-level cognitive processing. The relationships of the techniques
to other connectionist information-structuring methods, and also to
methods used in computers, are discussed in detail. The rich
inter-relationships of these other connectionist and computer methods
are also clarified. We detail the particular, simple forms that the
relative-position encoding and pattern-similarity association
techniques take in our own connectionist system, called Conposit, in
order to clarify some issues and to provide evidence that the
techniques are indeed useful in practice.
Barnden, J. & Srinivas, K., (l990), Overcoming Rule-Based Rigidity and
Connectionist Limitations through Massively-Parallel Case-Based
Reasoning, CRL, MCCS-90-187. ($5.00)
Symbol manipulation as used in traditional Artificial Intelligence has
been criticized by neural net researchers for being excessively
inflexible and sequential. On the other hand, the application of
neural net techniques to the types of high-level cognitive processing
studied in traditional artificial intelligence presents major problems
as well. We claim that a promising way out of this impasse is to
build neural net models that accomplish massively parallel case-based
reasoning. Case-based reasoning, which has received much attention
recently, is essentially the same as analogy-based reasoning, and
avoids many of the problems leveled at traditional artificial
intelligence. Further problems are avoided by doing many strands of
case-based reasoning in parallel, and by implementing the whole system
as a neural net. In addition, such a system provides an approach to
some aspects of the problems of noise, uncertainty and novelty in
reasoning systems. We are accordingly modifying our current neural
net system (Conposit), which performs standard rule-based reasoning,
into a massively parallel case-based reasoning version.
Wilks, Y. & Farwell, D., (1990), A White Paper on Research in
Pragmatics-based Machine Translation, CRL, MCCS-90-188. ($5.00)
The Computing Research Laboratory (CRL) at New Mexico State University
proposes to investigate develop and extend a pragmatics-based approach
to Machine Translation (MT), hopefully within a cooperative,
multi-site, MT project. The central objective is to integrate natural
language processing (NLP) techniques in the areas of the pragmatics of
belief ascription, natural language semantics, large-scale meaning
extraction, and parsing into a unified, explicit, robust machine
system, one which is initially machine-aided, using the techniques to
be described here, but later fully automatic.
Candelaria de Ram, S., (1990), Real-world sensors, meaning, or
mentalese, CRL, MCCS-90-189. ($5.00)
Fundamental problems in Artificial Intelligence (AI) stem from
founding the field on the Fallacy of Inductive Inversion: Descriptive
explanations [do not] run the system. If explanatory rules (e.g., the
rule of gravity, I/O rules, grammar rules, representations) are ad
hoc, then is the AI enterprise hopeless, or is there a proper basis
for computational intelligence? AI may become a viable science
(Cognitive Science, perhaps) by viewing its work within this
data-connected paradigm instead of as an abstract formal enterprise,
and by adding sensors/effectors besides keyboards and screens for
string display. By supplying perceptual grounding for the formal
concepts over which computing is done amounting to recognizing that
sensitivity is a necessary property for cognitive understanding (and
thus intelligence) I propose that the fallacy can be undone:
Real-world phenomena run themselves, and computers should be seen as
part of them and not a system apart. Result: a system comprised of
grounded concepts rather than syntactic terms, with necessary
procedural semantics. In contrast, systems in the traditional-logic,
model-theoretic paradigm, have infinities of sufficient models but no
evaluation procedure within the system. (Evaluation by external
omniscience is dualist.) More, from sensitivity a cognitive system
may attain capacities for expression, surprise, and comprehension
which, in their strongest form, become art.
Proceedings on the Fifth Rocky Mountain Conference on Artificial
Intelligence (RMCAI-90), CRL, MCCS-89-191. ($20.00)
Wilks, Y. & Fass, D., (1990), Preference Semantics: a family
history, CRL, MCCS-90-194. ($5.00)
The paper discusses the origins and structure of Preference Semantics
(PS) a procedural system for extracting the meaning structure of
natural language texts, based on notions of coherence and ``maximal
semantic density.'' The basic representational structures and
procedures of PS are described as well as the forms the notions have
taken in the work of others.
Wilks, Y., (l990), Where am I coming from: The reversibility of
analysis and generation in natural language processing, CRL,
MCCS-90-195. ($3.00)
The two general issues discussed in this paper are:
a) the symmetry (or otherwise) of analysis and generation in natural
language processing, and
b) what structures could, or should, generation come from?
The paper considers arguments for and against symmetry from a range of
historical and contemporary points of view, and concludes,
reluctantly, that the arguments against symmetry are probably
fallacious. I say reluctantly because believers in semantics-based
parsing of natural language (like the present author) have always
tended to assume (without sufficient examination) that the two
processes are not symmetrical. On issue (b) the difficulty of giving
any theory-independent characterization of the structure from which
generation is done suggests initially that generation cannot be an
independent task. However, if the answer to (a) above is that the
processes are symmetrical, then (it will follow on the arguments of
this paper) that neither is natural language analysis, and we should
base NLP within integrated tasks rather than either of these
(inseparable) pseudo-tasks.
Coombs, M.J., Pfeiffer, H.D., & Hartley, R.T., (l990), e-MGR: An
Architecture for Symbolic Plasticity, CRL, MCCS-90-196. ($5.00)
The e-MGR architecture was designed for symbolic problem solving in
task environments where data are noisy and problems are ill-defined.
e-MGR is an operator-based, shared memory system which integrates
problem solving ideas from symbolic artificial intelligence (AI) and
adaptive systems research.
Hartley, R.T., (l990), Algorithms for the substrate of MGR,
CRL, MCCS-90-197. ($3.00)
NO ABSTRACT
Schvaneveldt, R., Goldsmith, T., & McMahon, D., (l990), Tactical
Air Combat Intelligent Trainer (TACIT), CRL, MCCS-90-198. ($5.00)
This report reviews work completed on the Tactical Air Combat
Intelligent Trainer (TACIT). This work has focused on two areas: (a)
the development of Artificial Neural Network (ANN) models that select
Air Combat Maneuvers (ACM); and (b) the development of these decision
models as a training tool via the construction of a PC based
simulation of ACM. We have built preliminary decision models that
incorporate knowledge about air-combat maneuvers and components of
maneuvers as well as rudimentary knowledge about maneuver planning and
situational awareness. These models have grown out of earlier
modeling efforts (ACES). The ANN models attempt to improve overall
performance of the decision models and to support development of an
intelligent training device. A second effort focuses on simulating
flight dynamics of high performance fighter aircraft and the
development of a computer interface that displays appropriate ACM
information.
Soderlund, C.A., (l990), A Critique of Concurrency Control
Constructs, CRL, MCCS-90-199. ($5.00)
The intentions of this paper are twofold: to show the relations of
concurrency control constructs with architectures, operating systems
and programming languages, and to provide a fine-grain comparison of
concurrency control techniques for the shared-memory model. An
underlying theme is the relationship between message passing and
shared memory concepts.
Oliver-Rodriguez, J.C., (l990), Understanding the back-propagation
algorithm, CRL, MCCS-90-200. ($5.00)
Back-propagation addresses basically a non-linear
pattern-classification problem, that is explained in terms of
operations in a vector space. The algorithm uses an instructional
learning scheme, by which performance feedback is assimilated by the
network. The particular learning rule used in the computations is
formally derived as a natural development of other rules used in
linear networks, and the usefulness of internally-coded
representations is mapped out for two solutions to the X-OR problem.
A Common-Lisp implementation is discussed and detailed graphical
displays show the behavior of the algorithm during the course of the
learning process.
Farwell, D. & Wilks, Y., (l990), Ultra: a Multi-lingual Machine
Translator, CRL, MCCS-90-202. ($5.00)
Ultra (universal language translator) is a multi-lingual, interlingual
machine translation system currently under development at the
Computing Research Laboratory at New Mexico State University. It
currently translates between five languages (Chinese, English, German,
Japanese, Spanish) with vocabularies in each language based on about
10,000 word senses. It makes use of recent AI, linguistic and logic
programming techniques bringing current research into product form.
The major design criteria are that the system be robust and general
purpose with simple to use utilities for customization to suit the
real and precise needs of particular users.
Its special features include:
* a multi-lingual system with a language-independent (interlingual)
system for representing expressions as elements of linguistic acts;
* bidirectional, Prolog grammars for each language incorporating
semantic and pragmatic constraints;
* use of relaxation techniques to provide robustness by giving
preferred or ``near miss'' translations;
* language-independent semantic and pragmatic procedures for sense
disambiguation, anaphor resolution, and the recovery of elided
information;
* access to large machine dictionaries in all five languages to give
rapid up-scaling of size and coverage;
* use of menus in an emacs editing environment for easy interaction,
including editing, and message preparation in specific domains (e.g.,
business letters, pro-forma memoranda, telexes, parts orders).
Wilks, Y., Barnden, J., & Wang, J., (l990), Your metaphor or mine:
belief ascription and metaphor interpretation, CRL, MCCS-90-205. ($5.00)
ViewGen, an algorithm and program for belief ascription, represents
the beliefs of agents as explicit, partitioned proposition-sets known
as environments. A way of extending ViewGen to the interpretation of
metaphor, and in particular to the comprehension of metaphor within
the belief spaces of particular agents, has been described elsewhere.
The paper reports the recent implementation of this extension, as well
as summarizing the argument for the claim that ordinary
non-metaphorical belief ascription and the transfer of information in
metaphors can both be seen as different manifestations of a single
environment-amalgamation process, one in which explicitly metaphorical
amalgamations are triggered by "preference breaking" in the sentence
being processed. This requires a consideration of the scoping of
metaphor with respect to belief contexts, analogous to the scoping of
quantification and definite descriptions with respect to such
contexts. The approach of assimilating metaphor to belief ascription
is contrasted with Hobbs' attempt to assimilate metaphor
interpretation to abduction. As a topic of ongoing and future work,
the issue of mixed metaphor, of two distinct types, is briefly
addressed.