Artificial Intelligence Research Reports and Software
The University of Georgia
Artificial Intelligence
Research Reports and Software
Artificial Intelligence Programs
Graduate Studies Research Center, Room 111
Athens, Georgia 30602
aspaul@uga.cc.uga.edu
Last revised 1991 November 4
RESEARCH REPORTS
IMPORTANT NOTICE: Due to demand, we have had to institute a charge of $3
each ($5 outside the U.S.A.) for printed reports. Make checks payable to
AI Program Development Fund and be sure to give your full mailing
address when ordering. See order form at end.
Many reports are also available in electronic form. To get information
on reports available through the Internet, do the following:
unix% ftp aisun1.ai.uga.edu (or ftp 128.192.12.9)
User name: anonymous
Password: (type your email address here)
ftp> cd ai.reports
ftp> get Contents
ftp> quit
This will transmit a file named `Contents' to your computer. Procedures
will vary slightly depending on how your computer is configured. Consult
your local computer center for help.
REPORTS AVAILABLE:
AI-1991-02 (available by FTP)
Donald Nute
Tense and Conditionals
Temporal relations play an essential role in determining the truth
values of many conditional assertions. This paper explores the
possibilities for developing a formal language containing both tense and
conditional operators, and a model theory for such a language.
AI-1991-01 (available by FTP)
Gregg H. Rosenberg
SALMON: a TEMPERAMENTAL Program that Learns
This thesis introduces a new approach to machine learning that combines
aspects of semantic and connectionist systems. A sample program learns
to play a children's game of tag.
AI-1990-02 (available by FTP)
William H. Smith
Handling Constrained Clauses in Discourse Representation Theory
This report describes a Prolog program that transforms a natural
language input into a knowledge base of Prolog clauses. The key element
of the program is its ability to handle constrained clauses, i.e.,
embedded clauses whose truth evaluation is affected by the matrix
clause, such as `Carol kissed Ted' in `Bob believes Carol kissed Ted'.
AI-1990-01 (available by FTP)
Michael A. Covington
A Dependency Parser for Variable-Word-Order Languages
Most human languages allow considerably more variation of word order
than does English. This paper presents a parsing algorithm for
variable-word-order languages based on dependency grammar. Unlike
earlier dependency parsers, this one does not require constituents to be
continuous, but merely prefers them so. A Russian parser using this
algorithm has been implemented on an IBM 3090 and this paper includes an
evaluation of the suitability of the IBM 3090 architecture for natural
language processing.
AI-1989-09
David Billington
Some Results on Defeasible Logic
Defeasible Logic is defined and the intuition behind the definition is
explained. Some new results are then proved which confirm and sharpen
our intuition.
AI-1989-08 (available by FTP)
Michael A. Covington
Efficient Prolog: A Practical Guide
Properly used, Prolog is as fast as any language with comparable power.
This paper presents guidelines for using Prolog efficiently. Some of
these guidelines rely on implementation- dependent features such as
indexing and tail recursion optimization; others are matters of pure
algorithmic complexity.
AI-1989-07
John E. McEneaney
Implementing Set Theory in Prolog
This paper describes an implementation of set theory in Prolog that
avoids certain problems characteristic of the standard approach
(Bharath, 1986; Clocksin and Mellish, 1987). Two of the four basic
set-theoretic predicates in the standard approach, subset and
intersection, are shown to result in errors. The alternatives proposed
in this paper remedy these problems. The major distinguishing feature of
the implementation proposed here is the implementation of an
equivalent_sets predicate that defines list equivalence solely on the
basis of the elements in lists, regardless of their order.
AI-1989-06
W. D. Potter, A. D. Wright, A. M. Morton, and V. C. Kessler
Handling Uncertainty and Exceptions with Defeasible Dependencies
Recently, the merger of artificial intelligence techniques with database
management concepts has sparked much interest. One important area is the
development of a theory for relational database design based on
absolute, incomplete, and uncertain knowledge about the domain. The
approach presented here brings a new dimension to the traditional theory
of relational database design based solely on absolute knowledge.
Specifically, we present the foundations of a theory of defeasible
dependencies, which are closely related to functional dependencies but
allow exceptions as well as uncertain relationships between groups of
attributes to be represented.
AI-1989-05
David Billington, Koen De Coster, Donald Nute
A Modular Translation from Defeasible Nets to Defeasible Logics
Recent work in nonmonotonic logic investigates relationships between
different defeasible reasoning formalisms. Of particular interest are
inheritance reasoners with multiple inheritance and exceptions. We show
that the Skeptical Inheritance Reasoner of Horty, Thomason, and
Touretzky is equivalent to a special case of Nute's general defeasible
logic.
AI-1989-04 (available by FTP)
William H. Smith
Problems in Applying Discourse Representation Theory
This report describes discourse representation theory, both the
original, basic form and some extensions that have been suggested by
Kamp and others, and applies it to a "real" discourse in order to
indicate further extensions that will be necessary if DRT is to be used
as a complete theory of semantic representations.
AI-1989-03
David Goodman
An Implementation of an Extension to Discourse Representation Theory
This report presents a declaratively formulated model of
intra-sentential and inter-sentential anaphoric dependencies for a
fragment of the English language with syntactic and semantic structures
built from a single rule formalism. The model is based on, and contains
extensions to, Discourse Representation Theory (Kamp 1981, 1983, 1985).
Input strings are converted to discourse representation structures and
then to Prolog clauses.
AI-1989-02 (available by FTP)
Michael A. Covington
A Numerical Equation Solver in Prolog
The Prolog inference engine can be extended to solve for unknowns in
arithmetic equations such as X-1=1/X or X=cos(X), whether or not the
equations have analytic solutions. This is done by standard numerical
methods, but two features of Prolog make the implementation easy: the
ability to treat expressions as data and the ability of the program to
extend itself at run time. (Published in Computer Language, Oct. 1989,
45-51.)
AI-1989-01 (available by FTP)
Michael A. Covington
GULP 2.0: An Extension of Prolog for Unification-Based Grammar
A simple extension to Prolog facilitates implementation of
unification-based grammars by adding a new notational device, the
feature structure, whose behavior emulates graph unification. For
example, a:b..c:d represents a feature structure in which a has the
value b, c has the value d, and all other features (if any) are
undefined. The extended language is known as GULP (Graph Unification
Logic Programming); it is as powerful and concise as PATR-II and other
grammar development tools, while retaining all the versatility of
Prolog.
01-0027 (available by FTP)
Tsanming J. Chou
A Comparative Performance Study on Various Parsers Written in Prolog
01-0026
Martin Volk
Parsing German with GPSG: The Problem of Separable-Prefix Verbs
01-0025
John E. McEneaney
READ.PRO: A Pattern-Matching Approach to Perceptual Learning in Reading
01-0024 (available by FTP)
M. Covington, D. Nute, N. Schmitz, and D. Goodman
From English to Prolog via Discourse Representation Theory
01-0023 (available by FTP)
Michael A. Covington and Nora Schmitz
An Implementation of Discourse Representation Theory
01-0022
Michael A. Covington
Parsing Variable Word Order Languages With Unification-Based Dependency
Grammar
No longer available -- Use report AI-1990-01 instead.
01-0021
Michael A. Covington
GULP 1.1: An Extension of Prolog for Unification-Based Grammar
No longer available -- Use report AI-1989-01 instead.
01-0020
S. Karickhoff, A. Vellino, L. Carreira, V. McDaniel, and D. Nute
Predicting Chemical Parameters with Prolog
01-0019
Robert E. Stearns and Michael A. Covington
Prolog on the CYBERPLUS: A Feasibility Study
01-0018
Andre N. Vellino
Searching Chemical Substructures Using Prolog
01-0017
Donald Nute and Michael Lewis
A User's Manual for d-Prolog
01-0016
Michael Lewis
Defeasible Reasoning in the Expert System Shell TOPSI
01-0015
Donald Nute and Michael Covington
Implicature, Disjunction, and Non-monotonic Logic
01-0014
Michael Lewis
The Automation of a Practical Reasoning System Based on Concepts in Deontic Logic
01-0013
Donald Nute
LDR: A Logic for Defeasible Reasoning
No longer available -- See D. Nute, "Defeasible Reasoning and Decision
Support Systems," Decision Support Systems 4 (1988) 97-110.
01-0012
Michael A. Covington
Expressing Procedural Algorithms in Prolog
No longer available -- see PC Tech Journal, March 1987, or Chapter 4 of
Covington, Nute, and Vellino, Prolog Programming in Depth.
01-0009
Terry L. Rankin
Could Nonmonotonic Inference Ever Be Deductively Valid?
01-0007
Donald Nute
A Non-Monotonic Logic Based on Conditional Logic
01-0003
Terry L. Rankin
AI Artifacts and Applied Epistemology
01-0002
Donald Nute
Non-Monotonic Reasoning and Conditionals
SOFTWARE
A large archive of software is available by anonymous FTP from
aisun1.ai.uga.edu (128.192.12.9).
For those who cannot use FTP, the following software is available on IBM
PC 3.5" or 5.25" diskettes at $15 per diskette, which covers duplication
and mailing only. Please make checks payable to AI Program Development
Fund. Software is experimental and is provided "as is," without any
warranty or promise of user support. Do not order multiple copies of a
disk -- instead, order one copy, then duplicate it yourself.
Disk 1
d-Prolog source code
This is the source code for d-Prolog as described in Research Report
01-0017 above. You must have a Prolog compiler or interpreter in order
to run it. As supplied, it runs under Arity Prolog, and it runs with at
most minor modifications under ALS Prolog, Quintus Prolog, and other
Edinburgh-compatible implementations (but not Turbo Prolog). (Be sure to
request Report 01-0017 for documentation.)
Disk 2
Prolog Programming Examples
Source code for the example programs in Covington, Nute, and Vellino,
Prolog Programming in Depth. Available in 3 versions: in Arity Prolog
(as published in the book), or modified for ALS or Quintus Prolog. The
Arity version is supplied if you do not state a preference.
Disk 3
GULP source code
Source code for GULP, the unification-based grammar development tool
described in Research Report AI-1989-01. Two versions are provided on
one disk: Arity Prolog and Quintus Prolog.
Disk 4
Editors and utilities
A collection of utility programs for the IBM PC, including two
WordStar-like full-screen editors, AHED and PrEd. Users are welcome to
copy and distribute these editors to anyone free of charge. They feature
pop-up help menus and are especially suitable for use in programming
classes. Memory requirements are very small and both editors are
suitable for running as a subprocess under a Prolog interpreter or
compiler.
ORDER FORM
Make checks payable to: AI Program Development Fund
Send orders to: Artificial Intelligence Programs
The University of Georgia
Athens, GA 30602 U.S.A.
Reports ($3 each, $5 outside the U.S.A.):
[] AI-1991-02 Nute
[] AI-1991-01 Rosenberg
[] AI-1990-02 Smith
[] AI-1990-01 Covington
[] AI-1989-09 Billington
[] AI-1989-08 Covington
[] AI-1989-07 McEneaney
[] AI-1989-06 Potter
[] AI-1989-05 Billington
[] AI-1989-04 Smith
[] AI-1989-03 Goodman
[] AI-1989-02 Covington
[] AI-1989-01 Covington
[] 01-0027 Chou
[] 01-0026 Volk
[] 01-0025 McEneaney
[] 01-0024 Covington
[] 01-0023 Covington
[] 01-0022 Covington
[] 01-0020 Karickhoff
[] 01-0019 Stearns
[] 01-0018 Vellino
[] 01-0017 Nute
[] 01-0016 Lewis
[] 01-0015 Nute
[] 01-0014 Lewis
[] 01-0009 Rankin
[] 01-0007 Nute
[] 01-0003 Rankin
[] 01-0002 Nute
Disks ($15 each)
[] 1. d-Prolog source code
[] 2a. Prolog programming examples - Arity Prolog
[] 2b. Prolog programming examples - ALS Prolog
[] 2c. Prolog programming examples - Quintus Prolog
[] 3. GULP source code
[] 4. Editors and utilities
Your mailing address: ___________________________________
___________________________________
___________________________________
___________________________________
Total enclosed (U.S. funds only): ______________
Artificial Intelligence
Research Reports and Software
Artificial Intelligence Programs
Graduate Studies Research Center, Room 111
Athens, Georgia 30602
aspaul@uga.cc.uga.edu
Last revised 1991 November 4
RESEARCH REPORTS
IMPORTANT NOTICE: Due to demand, we have had to institute a charge of $3
each ($5 outside the U.S.A.) for printed reports. Make checks payable to
AI Program Development Fund and be sure to give your full mailing
address when ordering. See order form at end.
Many reports are also available in electronic form. To get information
on reports available through the Internet, do the following:
unix% ftp aisun1.ai.uga.edu (or ftp 128.192.12.9)
User name: anonymous
Password: (type your email address here)
ftp> cd ai.reports
ftp> get Contents
ftp> quit
This will transmit a file named `Contents' to your computer. Procedures
will vary slightly depending on how your computer is configured. Consult
your local computer center for help.
REPORTS AVAILABLE:
AI-1991-02 (available by FTP)
Donald Nute
Tense and Conditionals
Temporal relations play an essential role in determining the truth
values of many conditional assertions. This paper explores the
possibilities for developing a formal language containing both tense and
conditional operators, and a model theory for such a language.
AI-1991-01 (available by FTP)
Gregg H. Rosenberg
SALMON: a TEMPERAMENTAL Program that Learns
This thesis introduces a new approach to machine learning that combines
aspects of semantic and connectionist systems. A sample program learns
to play a children's game of tag.
AI-1990-02 (available by FTP)
William H. Smith
Handling Constrained Clauses in Discourse Representation Theory
This report describes a Prolog program that transforms a natural
language input into a knowledge base of Prolog clauses. The key element
of the program is its ability to handle constrained clauses, i.e.,
embedded clauses whose truth evaluation is affected by the matrix
clause, such as `Carol kissed Ted' in `Bob believes Carol kissed Ted'.
AI-1990-01 (available by FTP)
Michael A. Covington
A Dependency Parser for Variable-Word-Order Languages
Most human languages allow considerably more variation of word order
than does English. This paper presents a parsing algorithm for
variable-word-order languages based on dependency grammar. Unlike
earlier dependency parsers, this one does not require constituents to be
continuous, but merely prefers them so. A Russian parser using this
algorithm has been implemented on an IBM 3090 and this paper includes an
evaluation of the suitability of the IBM 3090 architecture for natural
language processing.
AI-1989-09
David Billington
Some Results on Defeasible Logic
Defeasible Logic is defined and the intuition behind the definition is
explained. Some new results are then proved which confirm and sharpen
our intuition.
AI-1989-08 (available by FTP)
Michael A. Covington
Efficient Prolog: A Practical Guide
Properly used, Prolog is as fast as any language with comparable power.
This paper presents guidelines for using Prolog efficiently. Some of
these guidelines rely on implementation- dependent features such as
indexing and tail recursion optimization; others are matters of pure
algorithmic complexity.
AI-1989-07
John E. McEneaney
Implementing Set Theory in Prolog
This paper describes an implementation of set theory in Prolog that
avoids certain problems characteristic of the standard approach
(Bharath, 1986; Clocksin and Mellish, 1987). Two of the four basic
set-theoretic predicates in the standard approach, subset and
intersection, are shown to result in errors. The alternatives proposed
in this paper remedy these problems. The major distinguishing feature of
the implementation proposed here is the implementation of an
equivalent_sets predicate that defines list equivalence solely on the
basis of the elements in lists, regardless of their order.
AI-1989-06
W. D. Potter, A. D. Wright, A. M. Morton, and V. C. Kessler
Handling Uncertainty and Exceptions with Defeasible Dependencies
Recently, the merger of artificial intelligence techniques with database
management concepts has sparked much interest. One important area is the
development of a theory for relational database design based on
absolute, incomplete, and uncertain knowledge about the domain. The
approach presented here brings a new dimension to the traditional theory
of relational database design based solely on absolute knowledge.
Specifically, we present the foundations of a theory of defeasible
dependencies, which are closely related to functional dependencies but
allow exceptions as well as uncertain relationships between groups of
attributes to be represented.
AI-1989-05
David Billington, Koen De Coster, Donald Nute
A Modular Translation from Defeasible Nets to Defeasible Logics
Recent work in nonmonotonic logic investigates relationships between
different defeasible reasoning formalisms. Of particular interest are
inheritance reasoners with multiple inheritance and exceptions. We show
that the Skeptical Inheritance Reasoner of Horty, Thomason, and
Touretzky is equivalent to a special case of Nute's general defeasible
logic.
AI-1989-04 (available by FTP)
William H. Smith
Problems in Applying Discourse Representation Theory
This report describes discourse representation theory, both the
original, basic form and some extensions that have been suggested by
Kamp and others, and applies it to a "real" discourse in order to
indicate further extensions that will be necessary if DRT is to be used
as a complete theory of semantic representations.
AI-1989-03
David Goodman
An Implementation of an Extension to Discourse Representation Theory
This report presents a declaratively formulated model of
intra-sentential and inter-sentential anaphoric dependencies for a
fragment of the English language with syntactic and semantic structures
built from a single rule formalism. The model is based on, and contains
extensions to, Discourse Representation Theory (Kamp 1981, 1983, 1985).
Input strings are converted to discourse representation structures and
then to Prolog clauses.
AI-1989-02 (available by FTP)
Michael A. Covington
A Numerical Equation Solver in Prolog
The Prolog inference engine can be extended to solve for unknowns in
arithmetic equations such as X-1=1/X or X=cos(X), whether or not the
equations have analytic solutions. This is done by standard numerical
methods, but two features of Prolog make the implementation easy: the
ability to treat expressions as data and the ability of the program to
extend itself at run time. (Published in Computer Language, Oct. 1989,
45-51.)
AI-1989-01 (available by FTP)
Michael A. Covington
GULP 2.0: An Extension of Prolog for Unification-Based Grammar
A simple extension to Prolog facilitates implementation of
unification-based grammars by adding a new notational device, the
feature structure, whose behavior emulates graph unification. For
example, a:b..c:d represents a feature structure in which a has the
value b, c has the value d, and all other features (if any) are
undefined. The extended language is known as GULP (Graph Unification
Logic Programming); it is as powerful and concise as PATR-II and other
grammar development tools, while retaining all the versatility of
Prolog.
01-0027 (available by FTP)
Tsanming J. Chou
A Comparative Performance Study on Various Parsers Written in Prolog
01-0026
Martin Volk
Parsing German with GPSG: The Problem of Separable-Prefix Verbs
01-0025
John E. McEneaney
READ.PRO: A Pattern-Matching Approach to Perceptual Learning in Reading
01-0024 (available by FTP)
M. Covington, D. Nute, N. Schmitz, and D. Goodman
From English to Prolog via Discourse Representation Theory
01-0023 (available by FTP)
Michael A. Covington and Nora Schmitz
An Implementation of Discourse Representation Theory
01-0022
Michael A. Covington
Parsing Variable Word Order Languages With Unification-Based Dependency
Grammar
No longer available -- Use report AI-1990-01 instead.
01-0021
Michael A. Covington
GULP 1.1: An Extension of Prolog for Unification-Based Grammar
No longer available -- Use report AI-1989-01 instead.
01-0020
S. Karickhoff, A. Vellino, L. Carreira, V. McDaniel, and D. Nute
Predicting Chemical Parameters with Prolog
01-0019
Robert E. Stearns and Michael A. Covington
Prolog on the CYBERPLUS: A Feasibility Study
01-0018
Andre N. Vellino
Searching Chemical Substructures Using Prolog
01-0017
Donald Nute and Michael Lewis
A User's Manual for d-Prolog
01-0016
Michael Lewis
Defeasible Reasoning in the Expert System Shell TOPSI
01-0015
Donald Nute and Michael Covington
Implicature, Disjunction, and Non-monotonic Logic
01-0014
Michael Lewis
The Automation of a Practical Reasoning System Based on Concepts in Deontic Logic
01-0013
Donald Nute
LDR: A Logic for Defeasible Reasoning
No longer available -- See D. Nute, "Defeasible Reasoning and Decision
Support Systems," Decision Support Systems 4 (1988) 97-110.
01-0012
Michael A. Covington
Expressing Procedural Algorithms in Prolog
No longer available -- see PC Tech Journal, March 1987, or Chapter 4 of
Covington, Nute, and Vellino, Prolog Programming in Depth.
01-0009
Terry L. Rankin
Could Nonmonotonic Inference Ever Be Deductively Valid?
01-0007
Donald Nute
A Non-Monotonic Logic Based on Conditional Logic
01-0003
Terry L. Rankin
AI Artifacts and Applied Epistemology
01-0002
Donald Nute
Non-Monotonic Reasoning and Conditionals
SOFTWARE
A large archive of software is available by anonymous FTP from
aisun1.ai.uga.edu (128.192.12.9).
For those who cannot use FTP, the following software is available on IBM
PC 3.5" or 5.25" diskettes at $15 per diskette, which covers duplication
and mailing only. Please make checks payable to AI Program Development
Fund. Software is experimental and is provided "as is," without any
warranty or promise of user support. Do not order multiple copies of a
disk -- instead, order one copy, then duplicate it yourself.
Disk 1
d-Prolog source code
This is the source code for d-Prolog as described in Research Report
01-0017 above. You must have a Prolog compiler or interpreter in order
to run it. As supplied, it runs under Arity Prolog, and it runs with at
most minor modifications under ALS Prolog, Quintus Prolog, and other
Edinburgh-compatible implementations (but not Turbo Prolog). (Be sure to
request Report 01-0017 for documentation.)
Disk 2
Prolog Programming Examples
Source code for the example programs in Covington, Nute, and Vellino,
Prolog Programming in Depth. Available in 3 versions: in Arity Prolog
(as published in the book), or modified for ALS or Quintus Prolog. The
Arity version is supplied if you do not state a preference.
Disk 3
GULP source code
Source code for GULP, the unification-based grammar development tool
described in Research Report AI-1989-01. Two versions are provided on
one disk: Arity Prolog and Quintus Prolog.
Disk 4
Editors and utilities
A collection of utility programs for the IBM PC, including two
WordStar-like full-screen editors, AHED and PrEd. Users are welcome to
copy and distribute these editors to anyone free of charge. They feature
pop-up help menus and are especially suitable for use in programming
classes. Memory requirements are very small and both editors are
suitable for running as a subprocess under a Prolog interpreter or
compiler.
ORDER FORM
Make checks payable to: AI Program Development Fund
Send orders to: Artificial Intelligence Programs
The University of Georgia
Athens, GA 30602 U.S.A.
Reports ($3 each, $5 outside the U.S.A.):
[] AI-1991-02 Nute
[] AI-1991-01 Rosenberg
[] AI-1990-02 Smith
[] AI-1990-01 Covington
[] AI-1989-09 Billington
[] AI-1989-08 Covington
[] AI-1989-07 McEneaney
[] AI-1989-06 Potter
[] AI-1989-05 Billington
[] AI-1989-04 Smith
[] AI-1989-03 Goodman
[] AI-1989-02 Covington
[] AI-1989-01 Covington
[] 01-0027 Chou
[] 01-0026 Volk
[] 01-0025 McEneaney
[] 01-0024 Covington
[] 01-0023 Covington
[] 01-0022 Covington
[] 01-0020 Karickhoff
[] 01-0019 Stearns
[] 01-0018 Vellino
[] 01-0017 Nute
[] 01-0016 Lewis
[] 01-0015 Nute
[] 01-0014 Lewis
[] 01-0009 Rankin
[] 01-0007 Nute
[] 01-0003 Rankin
[] 01-0002 Nute
Disks ($15 each)
[] 1. d-Prolog source code
[] 2a. Prolog programming examples - Arity Prolog
[] 2b. Prolog programming examples - ALS Prolog
[] 2c. Prolog programming examples - Quintus Prolog
[] 3. GULP source code
[] 4. Editors and utilities
Your mailing address: ___________________________________
___________________________________
___________________________________
___________________________________
Total enclosed (U.S. funds only): ______________
Comments
Post a Comment