IJCAI 87-VOLUME 2

Proceedings of the lentil International Joint Conference

on Artificial Intelligence

Volume 2   August 23-28,1987

CONTENTS

NATURAL LANGUAGE                                                                                                                                                               

 1) Feedback as a Coindexing Mechanism in Connectionist Architectures

    Mark A. Jones              602

 2) A Microfeature-based Scheme for Modelling Semantics

     Lawrence A. Bookman          611

 3) Parallel Parsing for Unification Grammars

     Andrew Haas                     615

 4) The Preliminary Results of a Mandarin Dictation Machine Based Upon Chinese Natural Language Analysis

     Un-shan Lee, Chiu-yu Tseng, K.J. Chen, and James Huang         619

 5) Modified Caseframe Parsing for Speech Understanding Systems

    Massimo Poesio and Claudio Rullent    622

 6) Combining Discourse Strategies to Generate Descriptions to Users  Along a Naive/Expert Spectrum                                                                   

     Cecile L Paris                 626

 7) Discourse Consistency and Many-Sorted Logic

     Jean Veronis                 633

 8) Intonation and the Intentional Structure of Discourse

     J. Hirschberg, D. Utman, J. Pierrehumbert, and G.Ward          636

 9) A Computational Model of Referring

     Douglas Appelt and Amichai Kronfeld                          640

10) Representation and Interpretation of Determiners in Natural Language 

     Barbara Di Eugenio and Leonardo Lesmo      648

11)  A Framework for Incremental Syntactic Tree Formation                          

     Gerard Kempen                          655  

12)  Incremental Interpretation and Combinatory Categorial Grammar            

     NichoiasJ. Haddock                                       661

13)Dependency Propagation: A Unified Theory of Sentence  Comprehension and Generation                                                      

      Koiti Hasida and Svun Isizaki                              664

14) A Parsing System Based on Logic Programming                          

      Yuil Matsumoto and Ryoichi Sugimura                                 671

15) A Knowledge Framework for Natural Language Analysis                     

     PaulS. Jacobs                      675

16)Combining Prediction, Syntactic Analysis and Semantic Analysis in Chinese Sentence Analysis   

    YimingYan             679

17)Building Natural Language Interfaces forRule-based Expert Systems

     Galina Datskovsky Moerdler, Kathleen R. McKeown,ana J. Robert Ensor         682

18)Understanding System Specifications Written inNatural Language

    John J. Qranacki, Jr., Alice C. Parker, and Yigal Arena                                         688

19)An Equipment Model and its Role in the Interpretation of Noun Phrases  

     Tomasz Ksiezyk, Ralph Grishman, and John Sterling             692

20)Naive Mechanics Comprehension and Invention in EDISON                 

    Michael G. Dyer, Margot Flowers, and Jack Hodges             696

21)Blackboard-based Dependency Parsing                                             

   K. valkonen, H. Jappinen, and A. Lehtola                    700

22)A Formalism and Environment for theDevelopment of a Large Grammar of English

    Ted Briscoe, Claire Qrover, Bran Boguraav, andJohn Carrol                          703

23)A Semantic Expert Using an Online StandardDictionary                         

    Jean-Louis Binot and Karen Jensen                            709

24)Interactive Vocabulary Acquisition in XTRA                                                      

   Chenchmina Quo                                715

25)The Universal Parser Architecture forKnowledge-based Machine Translation   

   Maseru Tomita and Jaime Q. Carbonell                         718

26)Direct Memory Access Translation                                                              

     Hideto Tomabechi                            722

27)Representing Space for Practical Reasoning                                            

     Margaret M. Fleck                                     728

28)Recovering Surface Shape from Boundary                                                 

   Gang Xu and Saburo Tsuji                              731

29)Recovering Three Dimensional Shape from a Single Image of Curved Objects        

   Jltendra Malik                                   734

30)Combining Sources of Information in Vision I. Computing Shape from Shading and Motion

    John (Yiannls) Aloimonos                     738

31)Image Reconstruction from Zero-Crossings                                                                         

  Su-shing Chen                        742

32)An Optimal Scale for Edge Detection  

    Da vl Qelger and Tomaso Poggio        745

 

33) Feature Selection in Colour Images for Token Matching       

     Leonie S. Dreschler-Flscher and Frank Qnutzmann           749

34) The Use of Color in Highlight Identification

      Ron Qershon, Allan D. Jepson, and John K. Tsotsos        752

35) Computing Color Constant Descriptors in Images ...

      Ron Qershon, Allan D. Jepson, and John K. Tsotsos          755

36) Color Algorithms for a General Vision System

     Glenn Healey and Thomas O. Blnford             759   

37) Recognition in 2D Images of 3D Objects from Large Model Bases Using Prediction Hierarchies

      J. Brian Burns and Leslie J. Kitchen            763

38) A Shape Representation Based on Geometric Topology: Bumps, Gaussian Curvature, and the Topological Zodiac

     A. Peter Blicher                767

39) Process Recovery

      Michael Leyton               771

40) From Early Processing to Conceptual Reasoning: An Attempt to Fill the Gap

     Giovanni Adorni, Una Massone, Giulio Sandini, and Maurizio Immovilli              775

41) Probabilistic Information Fusion for Multi-Modal Image Segmentation

      Paul B. Chou and Christopher Brown              779

42) Uncertainty Reduction Paradigm Using Structural Knowledge in Line-Drawing Understanding

      Yasuo Ariki, Masashi Morimoto, and Toshiyuki Sakai                          783

43) Exploiting 2D Topology in Labeling Polyhedral Images

      Van-Due Nguyen                 787

44) Automatic Programming of Machine Vision Systems

      L.J. de Hass             790

45)Coordination of Action and Perception in a Surveillance Robot

    James L Crowley              793

46) Determining Cylindrical Shape from Contour and Shading

     Minoru Asada                  797

47) What is a 'Degenerate' View?

     John R. Kender and David G. Freudenstein         801

48) Model Invocation for Three Dimensional Scene Understanding

      Robert B. Fisher           805

49) Building a Consistent 3D Representation of a Mobile Robot Environment by Combining Multiple Stereo Views

      Nicholas Ayache and Olivier D. Faugeras  808

50) A Goal-Directed Intermediate Level Executive for Image Interpretation

       Charles A. Kohl, Allen R. Hanson, and Edward M. Riseman         811

51) A Robust Algorithm for Determining the Translation of a Rigidly Moving Surface without Correspondence, for Robotics Applications

      Anup Basu and John (Yiannis) Aloimonos      815

52) Qualitative Motion Understanding

     Wilhelm Burger and Bir Bhanu      819

53) Determination of Egomotion and Environmental Layout from Noisy Time-Varying Image Velocity in Binocular Image Sequences

    John L Barron, Allan D. Jepson, and John K. Tsotsos        822

54) Trinocular Stereovision: Recent Results

     Nicholas Ayache and Francis Lustman       826

55) Significant Feature Detection and Matching in Image Pairs

     Mark H. Singer           829

56) Stereo Matching by Hierarchical, Microcanonical Annealing

       Stephen T. Barnard         832

57) On Multi-Level Machines for Continuous Speech Recognition

      Joseph di Martino           836

58) Use of Procedural Knowledge for Automatic Speech Recognition

     Renato de Mori, Ettore Merlo, Mathew Palakal, and Jean Rouat        840

59) A Multi-Level Perception Approach to Reading Cursive Script

     Sargur N. Srihari and Radmllo M. Bozinovic          844

60) Knowledge Utilization in Handwritten Zip Code Recognition

     Jonathan J. Hull and Sargur N. Srihari       848

61) Learning Phonetic Features Using Connectionist Networks

      Raymond L Watrous and Lokendra Shastri  851

62) An Algorithm which Automatically Constructs Discrimination Graphs in a Visual Knowledge Base

     Jan A. Mulder          855

REASONING

63) Large-Scale Temporal Data Bases for Planning in Complex Domains

     Thomas Dean   860

64) Knowledge Preconditions for Actions and Plans

     Leora Morgenstem  867

65) Using Partial Global Plans to Coordinate Distributed Problem Solvers

    Edmund H. Durfee and Victor R. Lesser     875                                                    

66) Dominance and Subsumption in Constraint-Posting Planning

     Michael P. Wellman  884

67)RUM: A Layered Architecture for Reasoning with Uncertainty

    Piero P. Bonissone, Steven S. Gans, and Keith S. Decker 891

68)Reasoning with Consistent Probabilities

     Dimiter Driankov  899

69) Objective Probabilities

    Henry E. Kyburg 902

70) Variables in Hypotheses

    David Poole  905

71) Intended Models, Circumscription and Commonsense Reasoning

     WJodek W. Zadrozny  909

72) Matrix Proof Methods for Modal Logics  

     Lincoln A. Wallen 917

73)Epistemic Logics, Probability, and the Calculus of Evidence

    Enrique H. Ruspini 924

 74)Inductive Inference on the Base of Fixed Point Theory

    T. Gergely and ZS. Szabo 932

75)Foundations of Probabilistic Logic

    H. Guggenheimerand R.S. Freedman 939

76)A General Proof Method for First-Order Modal Logic

     Peter Jackson and Han Reichgelt 942

77)Performance Evaluation of the Inference Structure in Expert System

    Yang Tao, He Zhijun, and Yu Ruizhao 945

78) A Quantitative Analysis of Minimal Window Search

     Alexander Reinefeld and T.A. Marsland 951

79) Optimizing Backtrack Search for all Solutions to Conjunctive Problems

      K.S. Natarajan 955

80) Comparative Analysis

    Danlel S. Weld 959

81) Formal Theories of Action (Preliminary Report)

    Vladimir Lifschitz 966

82) An Algebraic Foundation for Truth Maintenance

      Allen L Brown, Jr., Dale E. Gaucas, and Dan Benanav 973

83) Short Time Periods

    Patrick H. Hayes and James F. Allen  981

84) Theorem Proving Under Uncertainty— A Possibility Theory-based Approach .

     Dldier Dubois, Jerome Lang, and Henri Prade 984

85) An Incremental Theorem Prover

     Murray Shanahan  987

86) Complete Inference Rules for the Cancellation Laws

    Jieh Hsiang, Michael Rusinowitch, and Ko Sakai 990

87)Constructive Second-Order Proofs in Logical Databases

    Michel de Rougemont 993

88)Domain Abstraction and Limited Reasoning

   Tomasz Imielinksi  997

89) The Abstraction/Implementation Model of Problem Reformulation

     Michael R. Lowry 1004

90)Preserving Consistency Across Abstraction Mappings

   Josh D. Tenenberg 1011

91)Combining Bodies of Dependent Information

    Robert Hummel and Larry M. Manevitz 1015

92)Subgoal Ordering and Goal Augmentation for Heuristic Problem Solving

    Keki B. Irani and Jie Cheng 1018

93)Goal Conflict Concerns

    Marc Luria  1025

94) Controlling Constraint Propagation

    Anne Colhnot and Claude Le Rape 1032

95) An Investigation of Opportunistic Constraint Satisfaction in Space Planning

     Can A. Baykan and Mark S. Fox 1035

96)Universal Plans for Reactive Robots in Unpredictable Environments

     M.J. Schoppers  1039

97)Contingency Planning for an Autonomous Land Vehicle

    Theordore A. Linden and Jay Glicksman 1047

98)The Pipelining Transformation on Plans for Manufacturing Cells with Robots

    Erik Sandewall 1055

99) A Probabilistic Framework for Resource-Constrained Multi-Agent Planning

      Nicola Muscettola and Stephen F Smith 1063

100)Path Planning Through Time and Space in Dynamic Domains

      Marc G. Slack and David P. Miller 1067

101)Generate, Test and Debug:Combining Associational Rules and Causal Models

    Reid Simmons and Randall Davis  1071

102) Troubleshooting: When Modeling is the Trouble (paper unavailable) P. Dague

103)Taming Intractible Branching in Qualitative Simulation

     Benjamin Kuipers and Charles Chiu 1079

104)Towards Continuous Process Supervision

     Philippe Caloud  1086

105)Explicit Integration of Goals in Heuristic Algorithm Design

      J. MostowandK. Voigt 1090

106)The Generation of Explanations within Evidential Reasoning Systems

      Thomas M. Strat 1097

107)An Improved Constraint-Propagation Algorithm for Diagnosis

     Hector Geffner and Judea Pearl  1105

108)Computational Complexity of Hypothesis Assembly

Dean Allemang, Michael C. Tanner, Tom Bylander, and John Josephson 1112

ROBOTICS

109)Finding Collision-Free Smooth Trajectories for a Non-Holonomic Mobile Robot

     Jean-Paul Laumond  1120

110)Creature Design with the Subsumption Architecture

      Jonathan H. Connell 1124

111)Visual Path Planning by a Mobile Robot

      Saburo Tsuji and Jiang Yu Zheng 1127

112)The Mixed Approach for Motion Planning:Learning Global Strategies from a Local Planner

      Faverjon and P. Tournassoud 1131

113)TINA: The Sheffeild AIVRU Vision System

     J. Porrlll, S.B. Pollard, T.P. Pridmore, J.B. Bo wen, J.E.W. May hew, and J. P. Frisby 1138

114) Object Identification from Parallel Light Stripes

    Bijan Arbab   1145

115)Locating Polyhedral Objects from Edge Point Data

      Gary Silverman, Roger Tsai, and Mark Lavin 1149

116)Grasp Planning from Human Prehension

      Thea Iberall         1153

117)A Parallel Blackboard System for Robot Control

     Hugo Velthuijsen, Ben J. Lippolt, and Jeanette C. Vonk         1157

PANELS AND INVITED TALKS

118)Parallel Inference Machines

      Wolfgang Bibel, Chair         1162

119)Pointing, Language and the Visual World: Towards Multimodal Input and Output for Natural Language Dialog Systems

       Wolfgang Wahlster, Chair         1163

   A Unifying Framework for Machine Learning (abstract unavailable) Gerald DeJong, Chair

120)The Commercialization of Al Part 1: The User Viewpoint

      Bruce G. Johnson, Chair         1164

     Part 2: The Vendor Viewpoint

      Harry Reinstein, Chair         1164

Part 3: The Technology Challenge

Jan Aikins. Chair         1165

121)Some Challenges for Intelligent Tutoring Systems

      D. Sleeman         1166

122)Artificial 3D Vision

       Olivier D. Faugeras 1169

123)The New Grammar Formalisms—A Tutorial Survey

    (abstract) Gerald Gazdar 1172

124)On the Thresholds of Knowledge

      Douglas B. Lenat and Edward A. Feigenbaum 1  173

      Computer Architectures for Al Problem-Solving (paper unavailable) Hideo Aiso -NA

125)Towards a Functional Architecture for Intelligence Based on Generic Information Processing Tasks

     B.Chandrasekaran 1183

      126)  INDEX