IJCAI 83

Proceedings of the

Tenth International Joint Conference

Volume 2

NATURAL LANGUAGE 3: GENERATION-THEORETICAL, INCLUDING SEMANTICS

Impression Monitoring in Evaluation-Oriented Dialog

 The Role of the Listener's Assumed Expectations and Values in the Generation of Informative Statements

Anthony Jameson..............................616

Shifting Meaning Representations

Karen Sparck Jones ............................621

Frame Activated Inferences in a Story Understanding Program

Peter Norvig...................................624

Structural Relations—A Case Against Case

Ingeborg Steinacker and Harald Trost.............627

NATURAL LANGUAGE 4: SPEECH RELATED AREAS

The FOPHO Speech Recognition Project

Mary O'Kane ..................................630

A System for Improving the Recognition of Fluently Spoken German Speech

Joachim Mudler................................633

Allophonic and Phonotactic Constraints Are Useful

Kenneth W. Church.............................636

A Recognition Method of Connected Spoken Words With Syntactical Constraints by Augmented Continuous DP Algorithm

Sei-ichi Nakagawa .............................639

NATURAL LANGUAGE 5: INTERFACES AND APPLICATIONS

Over-Answering Yes-No Questions: Extended Responsesin a NL Interface to a Vision System

Wolfgang Wahlster, Heinz Marburger, Anthony Jameson, and Stephan Busemann............643

Demand and Requirements for Natural LanguageSystems

Results of an Inquiry

Katharina Morik................................647

Varieties of User Misconceptions: Detection and Correction

Bonnie Lynn Webber and Eric Mays...............650

The XCALIBUR Project: A Natural Language Interface toExpert Systems

Jaime G. Carbonell, W. Mark Boggs, Michael L. Mauldin, and Peter G. Anick.............653

NATURAL LANGUAGE 6: INTERFACES AND APPLICATIONS

Towards a Computable Model of Meaning-Text Relations Within a Natural Sublanguage

Richard Kittredge and Igor Mel'Cuk................657

Q-TRANS: Query Translation Into English

Eva-Marie M. Mueckstein........................660

Understanding Natural Language Through Parallel Processing of Syntactic and Semantic Knowledge: An Application to Data Base Query

R. Comino, R. Gemello, G. Guida, C. Rullent, L. Sisto, and M. Somalvico ..................663

A Framework for Processing Corrections in Task-Oriented Dialogues

Philip J. Hayes and Jaime G. Carbonell ............668

NATURAL LANGUAGE 7: PARSING, GRAMMAR IMPLEMENTATION AND MORPHOLOGY

Graph Grammar Approach to Natural Language Parsing and Understanding

Eero Hyvonen..................................671

Articles and Resource Control

Janusz S. Bien.................................675

Activation-Based Parsing

Mark A. Jones .................................678

Two-Level Model for Morphological Analysis

Kimmo Koskenniemi............................683

A Modular Parser for French

Eric Wehrli....................................686

An Object-Oriented Parser for Text Understanding

Brian Phillips..................................690

NATURAL LANGUAGE 9: PARSING, GRAMMAR IMPLEMENTATION AND MORPHOLOGY

A PROLOG Implementation of Lexical Functional Grammar

Uwe Reyle and Werner Frey......................693

A Breadth-First Parsing Model

John Bear.....................................696

Sentence Disambiguation by a Shift-Reduce Parsing Technique

Stuart M. Shieber...............................699

Word Formation in Natural Language Processing Systems

Roy J. Byrd....................................704

A Deterministic Syntactic-Semantic Parser

Gerard Sabah and Mohamed Rady................707

A Deterministic Parser With Broad Coverage

Robert C. Berwick..............................710

NATURAL LANGUAGE 10: DISCOURSE, DIALOGUE, ETC.

Narrative Complexity Based on Summarization Algorithms

Wendy G. Lehnert..............................713

Japanese Language Semantic Analyzer Based on an Extended Case Frame Model

Akira Shimazu, Syozo Naito, and Hirosato Nomura..................717

Syntax, Semantics, and Pragmatics in Concert: An Incremental, Multilevel Approach in Reconstructing Task-Oriented Dialogues

Manfred Gehrke................................721

Event Models for Recognition and Natural Language Description of Events in Real-World Image Sequences

Bernd Neumann and Hans-Joachim Novak.........724

Automatic Construction of a Knowledge Base by Analysing Texts in Natural Language

Werner Frey, Uwe Reyle, and Christian Rohrer......727

Why Good Writing Is Easier to Understand

John H. Clippinger, Jr., and David D. McDonald......730

Planning and Search

PLANNING AND SEARCH 3

Representation in a Domain-Independent Planner

David E.Wilkins................................733

Planning Using a Temporal World Model

James F. Allen and Johannes A. Koomen...........741

The Use of Meta-Level Control for Coordination in a Distributed Problem Solving Network

Daniel D. Corkill and Victor R. Lesser..............748

PLANNING AND SEARCH 1

The Statistical Inference Method in Heuristic Search Techniques

Ling Zhang and Bo Zhang........................757

Searching to Variable Depth in Computer Chess

Hermann Kaindl................................760

Relative Efficiency of Alpha-Beta Implementations

 T. A. Marsland.................................763

Strategies of Cooperation in Distributed Problem Solving

Stephanie Cammarata, David McArthur, and Randall Steeb ................767

A Universal Weak Method:

 Summary of Results

John E. Laird and Allen Newell ...................771

A Wrinkle on Satisficing Search Problems

Jeffrey A. Barnett and Don Cohen.................774

PLANNING AND SEARCH 2

A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm

Marco Valtorta.................................777

Characterizing Search Spaces

Roy Rada.....................................780

On A* as a Special Case of Ordered Search

Marcel J. Schoppers............................783

Optimal Searches From and and Ornodes

Jeffrey A. Barnett ..............................786

A—An Efficient Near Admissible Heuristic Search Algorithm

Malik Ghallab and Dennis G. Allard................789

Robotics

ROBOTICS 1: KEYNOTE ADDRESS

Address by Marc Raibert ..................Unpublished

ROBOTICS 2: MOTION PLANNING AND TRACKING

Resolving Observer Motion by Object Tracking

John Hallam...................................792

A Subdivision Algorithm Configuration Space for Findpath With Rotation

Rodney A. Brooks and Tomes Lozano-Perez........799

An Algorithm for Moving a Computer-Controlled Manipulator While Avoiding Obstacles

Eugene Grechanovsky and I. Sh. Pinsker...........807

ROBOTICS/VISION: ROBOT PROGRAMMING

A Framework for Handling Vision Data in an Object Level Robot Language—RAPT

BaolinYin.....................................814

Robot Programming by Inductive Learning

Bruno Dufay and Jean-Claude Latombe

ROBOTICS 1

Towards Automatic Error Recovery in Robot Programs

Maria Gini and Giuseppina Gini...................821

Knowledge Based Error Recovery in Industrial Robots

M. H. Lee, D. P. Barnes, and N. W. Hardy...........824

ROBOTICS 3: MOBILE ROBOTS AND PROGRAMMING

A Parallel Processor Algorithm for Robot Route Planning

 C. M. Witkowski................................827

A Distributed Control System for the CMU Rover

 Alberto Elfes and Sarosh N. Talukdar..............830

Concurrent Programming of Intelligent Robots

Yutaka Kanayama..............................834

Model Structuring and Concept Recognition: Two Aspects of Learning for a Mobile Robot

Jean-Paul Laumond ............................839

***Not received in time for publication

Reasoning About the Spatial Relationships Derived From a RAPT Program for Describing Assembly by a Robot

D. F. Corner, A. P. Ambler, and R. J. Popplestone...........842

Systems Support

Lisp-in-Lisp: High Performance and Portability

Rodney A. Brooks; Richard P. Gabriel; and Guy L Steele, Jr.....................845

Architecture and Applications of DADO: A Large-Scale Parallel Computer for Artificial Intelligence

Salvatore J. Stolfo, Daniel Miranker, and David Elliot Shaw...............................850

STROBE: Support for Structured Object Knowledge Representation

Reid G. Smith..................................855

Large-Scale System Development in Several Lisp Environments

Sanjai Narain, David McArthur, and Philip Klahr.....859

Demonizing Production Systems

Giuliano Pacini and Franco Turini.................862

Theorem Proving

THEOREM PROVING 3: KEYNOTE ADDRESS

Automated Reasoning: Real Uses and Potential Uses

 L. Wos..................867

THEOREM PROVING 2

Negative Hyper-Resolution for Proving Statements Containing Transitive Relations

Tamas Gergely and Konstantin Vershinin..........877

A Many-Sorted Calculus Based on Resolution and Paramodulation

Christoph Walther..............................882

Using Examples to Generate Instantiations of Set Variables

W. W. Bledsoe.................................892

THEOREM PROVING/AUTOMATIC PROGRAMMING

Semantic Paramodulation for Horn Sets

William W. McCune and Lawrence J. Henschen.....902

Church-Rosser Properties of Weakly Terminating Term Rewriting Systems

Jean-Pierre Jouannaud, Helene Kirchner, and Jean-Luc Remy ..................909

THEOREM PROVING 1

TERMINATOR

Grigorios Antoniou and Hans Jurgen Ohlbach ......916

Towards an Advanced Implementation of the Connection Method

Wolfgang Bibel, Elmar Eder, and Bertram Fronhoefer.....................920

A Superposition Oriented Theorem Prover

L Fribourg....................................923

Temporal Reasoning and Termination of Programs

Luis Farinas-del-Cerro ..........................926

Trivializing the Proof of Trivial Theorems

Y. Kodratoff and J. Castaing .....................930

Computer-Aided Studies of All Possible Shortest Single Axioms for the Equivalential Calculus

J. A. Kalman and J. G. Peterson...................933

THEOREM PROVING 3

Equality Reasoning in Clause Graphics

Karl-Hans Blasius..............................936

Associative-Commutative Rewriting

Nachum Dershowitz, Jien Hsiang, N. Alan Josephson, and David A. Plaisted .............940

Vision

VISION 1: MOTION AND CORRESPONDENCE

Constraints for the Estimation of Displacement Vector Fields From Image Sequences

Hans-Hellmut Nagel............................945

The Viewer's Place in Theories of Vision

R. I. D. Cowie..................................952

Correspondence in Line Drawings of Multiple Views of Objects

Charles Thorpe and Steven Shafer................959

VISION 3: SURFACES AND SHAPE

A New Conceptually Attractive and Computationally Effective Approach to Shape From Shading

B. Cernuschi-Frias, R. M. Bolle, and D. B. Cooper.................966

An Extremum Principle for Shape From Contour

Michael Brady and Alan Yuille....................969

Fractal-Based Description

Alex P. Pentland ...............................973

VISION 4: OBJECT MODELS AND RECOGNITION

Prism Trees: A Hierarchical Representation for 3-D Objects

O. D. Faugeras and J. Ponce .....................982

Using Surfaces and Object Models to Recognize Partially Obscured Objects

Robert B. Fisher................................989

A 3-D Recognition and Positioning Algorithm Using Geometrical Matching Between Primitive Surfaces

O. D. Faugeras and M. Hebert....................996

ROBOTICS/VISION: ROBOT PROGRAMMING

Optimization Approaches to the Problem of Edge Linking With a Focus on Parallel Processing

M. D. Diamond, N. Narasimhamurthi, and

S. Ganapathy.................................1003

VISION 2: PERCEPTUAL ORGANIZATION

Machine Perception of Linear Structure

Martin A. Fischler and Helen C. Wolf .............1010

Perceptual Organization and the Curve Partitioning Problem

M. A. Fischler and R. C. Bolles...................1014

Scale-Space Filtering

Andrew P. Witkin..............................1019

What Is Perceptual Organization For?

Andrew P. Witkin and Jay M. Tenenbaum..........1023

VISION 5: MOTION PERCEPTION

Sensor Motion and Relative Depth From Difference Fields of Optic Flows

J. H. Rieger and D. T. Lawton....................1027

Inferring Motion of Cylindrical Object From Shape Information

Minoru Asada and Saburo Tsuji..................1032