8Artificial 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 October 7 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 not us for further help. We do not deliver reports by email. AI-1991-01 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 2 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 3 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. 4 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. 5 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. 6 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 7 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. 8 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-01 Rosenberg [] 01-0027 Chou [] 01-0017 Nute [] AI-1990-02 Smith [] 01-0026 Volk [] 01-0016 Lewis [] AI-1990-01 Covington [] 01-0025 McEneaney [] 01-0015 Nute [] AI-1989-09 Billington [] 01-0024 Covington [] 01-0014 Lewis [] AI-1989-08 Covington [] 01-0023 Covington [] 01-0009 Rankin [] AI-1989-07 McEneaney [] 01-0022 Covington [] 01-0007 Nute [] AI-1989-06 Potter [] 01-0020 Karickhoff [] 01-0003 Rankin [] AI-1989-05 Billington [] 01-0019 Stearns [] 01-0002 Nute [] AI-1989-04 Smith [] 01-0018 Vellino [] AI-1989-03 Goodman [] AI-1989-02 Covington [] AI-1989-01 Covington 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): ______________