IJCAI _1985-VOLUME 2

Proceedings of the Ninth International Joint Conference on Artificial Intelligence

IJCAI-85  VOLUME-2

CONTENTS

LOGIC PROGRAMMING

Logic Programming 1

Prolog-ELF Incorporating Fuzzy Logic

Mitsuru Ishizuka and Naoki Kanai    701

Type Inference in Prolog and Its Application

Tadashi Kanamori and Kenji Horiuchi     704

Term Description: A Simple Powerful Extension to Prolog Data Structures

Hideyuki Nakashima      708

Interpreting Descriptions in a Prolog-based Knowledge Representation System

Randy Goebel        711

Retrospective Zooming: A Knowledge Based Tracking and Debugging Methodology for Logic Programming

Marc Eisenstadt        717

Prolog Control Rules

Lee Naish       720

Logic Programming 2

A Logic Program Schema and Its Applications

Takashi Yokomori          723

Concurrency in Proof Normalization and Logic Programming

Shjgeki Goto          726

Prolog Extensions Based on Tableau Calculus

Wolfgang SchOnfeld         730

A Predicate Connection Graph Based Logic with Flexible Control

Richard Whitney, Darrel J. VanBuer, Donald P. McKay,Dan Kogan, Lynette Hirschman,and Rebecca Davis           733

Incorporating Generalization Heuristics into Verification of Prolog Programs

HirohisaSeki               737

A Logic Programming and Verification System for Recursive Quantificational Logic

Frank M. Brown and Peiya Liu             742

NATURAL LANGUAGE

Natural Language 1

A New Kind of Finite-State Automaton: Register Vector Grammar

Glenn David Blank                  749

An Efficient Context-free Parsing Algorithm for Natural Languages

MasaruTomita              756

Unrestricted Gapping Grammars

Fred Popowich 765

Parsing with Assertion Sets and Information Monotonicity

G. Edward Barton, Jr. and Robert C. Berwick               769

Natural Language 2

Weighted Interaction of Syntax and Semantics in Natural Language Analysis

Leonardo Lesmo and Pietro Torasso            772

Syntax, Preference, and Right Attachment

Yorick Wilks, Xiuming Huang, and Dan Fass               779

Controlling Search in Flexible Parsing

Steve Minton, Philip J. Hayes, and Jill Fain                785

Grammatical Relations as the Basis for Natural Language Parsing and Text Understanding

Samual Bayer, Leonard Joseph,and Candace Kalish          788

Natural Language 3

The Role of Perspective in Responding to Property Misconceptions

Kathleen F. McCoy           791

Tailoring Explanations for the User

Kathleen R. McKeown, Myron Wish,and Kevin Matthews           794

Description-directed Natural Language Generation

David D. McDonald and James D. Pustejovsky       799

Natural Language 4

Tense, Aspect, and Cognitive Representation of Time

Kenneth Man-kam Yip       806

Lexical Ambiguity as a Touchstone for Theories of Language Analysis

Lawrence Birnbaum         815

VOX—An Extensible Natural Language Processor

Amnon Meyers              821

Partial Constraints in Chinese Analysis

Yiming Yang, Shuji Doshita,and Toyoaki Nishida            826

Natural Language 5

Grammatical Functions, Discourse, Referents, and Quantification

Uwe Reyle               829

Discourse Structure and the Proper Treatment of Interruptions

Barbara J. Grosz and Candace L. Sidner                832

Evaluating Importance: A Step Towards Text Summarization

Danilo Fum, Giovanni Guida, and Carlo Tasso            840

 Understanding Analogies in Editorials

Stephanie E. August and Michael G. Dyer      845

Natural Language 6

Integrating Text Planning and Production in Generation

Eduard H. Hovy         848

Be Brief, Be to the Point, Be Seated or Relevant Responses in Man/Machine Conversation

Anne Vilnat and Gerard Sabah         852

SAPHIR + RESEDA: A New Approach to Intelligent Data Base Access

Bernard Euzenat, Bernard Normier,Antione Ogonowski, and Gian Pier Zarri        855

Researcher: An Experimental Intelligent Information System

Michael Lebowitz       858

Natural Language 7

A Parallel-Process Model of On-Line Inference Processing

Kurt R Eiselt        863

New Approaches to Parsing Conjunctions Using Prolog

Sandiway Fong and Robert C. Berwick       870

On the Use of a Taxonomy of Time-Frequency Morphologies for Automatic Speech Recognition

Renato De Mori and Mathew Palakal         877

Reversible Automata and Induction of the English Auxiliary System

Robert C. Berwick and Samuel F. Pilato        880

DP-matching: With or Without Phonemes?

Shigeyoshi Kitazawa, Masa-aki Ishikawa,and Shuji Doshita       883

PERCEPTION

Perception 1

Structure from Motion Without Correspondence: General Principle

Ken-ichi Kanatani         886

Unique Recovery of Motion and Optic Flow via Lie Algebras

A. Peter Blicher and Stephen M. Omohundro      889

Coarse-to-Fine Control Strategy for Matching Motion Stereo Pairs

Gang Xu, Saburo Tsuji, and Minoru Asada         892

Utilization of a Stripe Pattern for Dynamic Scene Analysis

Minoru Asada and Saburo Tsuji         895

Determining 3-D Motion of Planar Objects from Image Brightness Patterns

S. Negahdaripour and B. K. P. Horn         898

A New Method of 3-D Motion Analysis Using a Concept of Projective Geometry

Tadahiro Kitahashi and Hiroyuki Endo      902

Perception 2

Using Discrimination Graphs to Represent Visual Interpretations that are Hypothetical and Ambiguous

Jan A. Mulder       905

SIGMA: A Framework for Image Understanding-Integration of Bottom-Up and Top-Down Analysis

Takashi Matsuyama and Vincent Hwang          908

Problem-solving Strategies in a Music Transcription System

Bernard Mont-Reynaud         916

LandScan: A Natural Language and Computer Vision System for Analyzing Aerial Images

Ruzena Bajcsy, Aravind Joshi, Eric Krotkov,and Amy Zwarico      919

Learning Shape Descriptions

Jonathan H. Connell and Michael Brady         922

Perception 3

Shape from Texture

John Aliomonos and Michael J. Swain          926

Shape and Source from Shading

Michael J. Brooks and Berthold K. P. Horn          932

One-Eyed Stereo: A General Approach to Modeling 3-D Scene Geometry

Thomas M. Strat and Martin A. Fischler          937

Analyzing Oriented Patterns

Michael Kass and Andrew Witkin           944

Perception 4

Visual Recognition from Spatial Correspondence and Perceptual Organization

David G. Lowe      953

Determining Object Attitude from Extended Gaussian Images

James J. Little     960

Transformational Form Perception in 3D: Constraints, Algorithms, Implementation

Dana H. Ballard and Hiromi Tanaka          964

3-D Shape Representation by Contours

Isaac Weiss       969

Perception 5

Specular Stereo

A. Blake        973

A Parallel Matching Algorithm for Stereo Vision

Y Nishimoto and Y. Shirai      977

Optical Navigation by the Method of Differences

Bruce D. Lucas and Takeo Kanade        981

Spectral Continuity and Eye Vergence Movement

Lance R.Williams         985

A New Sense for Depth of Field

Alex P. Pentland.       988

PHILOSOPHICAL FOUNDATIONS

Philosophical Foundations 1

What Enables a Machine to Understand?

Aaron Sloman         995

In Defense of Probability

Peter Cheeseman       1002

PLANNING AND SEARCH

Planning and Search 1

Refining and Extending the Procedural Net

Mark E. Drummond           1010

The Use of Multiple Problem Decompositions in Time Constrained Planning Tasks

Stephen F. Smith and Peng Si Ow.            1013

Splicing Plans to Achieve Misordered Goals

Steven A. Vere                 1016

Nonlinear Planning: A Rigorous Reconstruction

David Chapman                  1022

Increasing Coherence in a Distributed Problem-Solving Network

Edmund H. Durfee, Victor R. Lesser,and Daniel D. Corkill           1025

An Implementation of a Multi-Agent Plan Synchronizer

Christopher Stuart                  1031

Planning and Search 2

Iterative-Deepening-A": An Optimal Admissible Tree Search

Richard E. Korf            1034 - NA

A Weighted Technique in Heuristic Search

Bo Zhang and Ling Zhang               1037

Information Acquisition in Minimal Window Search

Alexander Reinefeld, Jonathan Schaeffer, and T. A. Marsland.      1040

A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees

Daniel B. Leifker and Laveen N. Kanal.          1044

Planning and Search 3

SPAN: Integrating Problem-Solving Tactics

Daniel L. S. Berlin                        1047

Deadlines, Travel Time, and Robot Problem Solving

  David Miller, R. James Firby, and Thomas Dean            1052

Temporal Scope of Assertions and Window Cutoff

 Steven Vere                1055

Temporal Reasoning Involving Counterfactuals and Disjunctions

Thomas Dean          1060

Shallow Planning and Recovery Planning Based on the Vertical Decomposition of the Flight Domain

David C. Chen          1063

Planning and Search 4

The Anatomy of Easy Problems: A Constraint-Satisfaction Formulation

Rina Dechter and Judea Pearl          1066

An Analysis of Consecutively Bounded Depth-First Search with Applications in Automated Deduction

Mark E. Stickel and W. Mabry Tyson.         1073

Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems

Eugene C. Freuder and Michael J. Quinn                  1076

A Study of Search Methods: The Effect of Constraint Satisfaction and Adventurousness

Hans Berliner and Gordon Goetsch              1079

The Complexity of Searching Several Classes of AND/OR Graphs

Howard E. Motteler and Laveen N. Kanal           1083

ROBOTICS

Robotics 1

Terrain Navigation Through Knowledge-based Route Planning

John F. Gilmore and Antonio C. Semeco         1086

First Results in Robot Road-Following

Richard Wallace, Anthony Stentz, Charles Thorpe,Hans Maravec, William Whittaker,and Takeo Kanade              1089

A Proximity Metric for Continuum Path Planning

Charles E. Buckley and Larry J. Leifer                 1096

A Robot Planning Structure Using Production Rules

Ralph RSobek.              1103

Robotics 2

A Framework for Distributed Sensing and Control

Tom Henderson, Chuck Hansen, and Bir Bhanu.         1106

Motor Knowledge Representation

Giuseppe Marino, Pietro Morasso,and RenatoZaccaria         1110

Analysis of Uncertainties in a Structure of Parts

Alan Fleming           1113

Robotics 3

Spatial Object Perception from an Image

Radu Horaud           1116

Stereo by Two-Level Dynamic Programming

Yuichi Ohta and Takeo Kanade       1120

A Fast Method for Extraction of 3-D Information Using Multiple Stripes and Two Cameras

Tomio Echigo and Masahiko Yachida           1127

Object Recognition Using Vision and Touch

Peter Allen and Ruzena Bajcsy         1131

THEOREM PROVING

Theorem Proving 1

A New Hyperparamodulation Strategy for the Equality Relation

Younghwan Lim and Lawrence J. Henschen          1138

An Equational Approach to Theorem Proving in First-Order Predicate Calculus

Deepak Kapur and Paliath Narendran         1146

The Management of Heuristic Search in Boolean Experiments with Rue Resolution

Vincent J. Digricoli           1154

Theorem Proving 2

A Many-Sorted Calculus with Polymorphic Functions Based on Resolution and Paramodulation

Manfred Schmidt-Schauss -NA                 1162  

On the Solution of Schubert's Steamroller in Many-Sorted Logic

Anthony G. Cohn-NA      1169

A Many-Sorted Resolution Based on an Extension of a First-Order Language

K. B. Irani and D. G. Shin-NA     1175

Parallel Processing of Resolution

Takahira Yamaguchi, Yoshikazu Tezuka, and Osamu Kakusho 1178

Theorem Proving 3

Automated Deduction by Theory Resolution

Mark E. Stickel 1181

Path Resolution with Link Deletion

Neil V. Murray and Erik Rosenthal 1187

ASSIP-T: A Theorem-Proving Machine

Werner Dilger and Hans-Albert Schneider 1194

Theorem Proving 4

Designing Examples for Semantically Guided Hierarchical Deduction

Tie Cheng Wang 1201

How to Facilitate the Proof of Theorems by Using the Induction-matching, and by Generalization

Jacqueline Castaing 1208

CM-Strategy: A Methodology for Inductive Theorem Proving or Constructive Well-Generalized Proofs

Marta Franova 1214

GENERAL

Invited Talks

Discovery and Reasoning in Mathematics

Alan Bundy 1221

Building a Bridge Between Al and Robotics

Hirochika Inoue. 1231

Self-Knowledge and Self-Representation

John Perry 1238

Understanding and Automating Algorithm Design

Elaine Kant 1243

Panels

Al and Legal Reasoning

Edwina L Rissland 1254

Artificial Intelligence in the Personal Computer Environment, Today and Tomorrow

Tom J. Schwartz 1261

Artificial Intelligence and Legal Responsibility

Margaret A. Boden 1267

Computer Representation of the Law

Robert Kowalski and Marek Sergot 1269

Constitutional Law and Artificial Intelligence: The Potential Legal Recognition of Computers as "Persons'

Marshals. Willick 1271

Fifth Generation Computer Crime Law

Jay BloomBecker 1274

Responsible Computers?

YorickWilks 1279

Empowering Automatic Decision-Making Systems: General Intelligence, Responsibility, and Moral Sensibility

Henry Thompson 1281

Judgement, Policy, and the Harmony Machine

John Fox 1284

Raising the Standards of Al Products

 Alan Bundy and Richard Clutterbuck 1289

Reasoning with Uncertainty for Expert Systems

Ronald R. Yager 1295

User Modelling

D. Sleeman, Doug Appelt, Kurt Konolige, Elaine Rich, N. S. Sridharan, and Bill Swartout 1298

The US and Japan Cooperative Al Research and Development

Howard E. Jacobson 1303

Expert Systems: How Far Can They Go?

 Terry Winograd, Randall Davis, Stuart Dreyfus, and Brian Smith 1306