IJCAI   1995-VOLUME TWO

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence

Volume 2

Montreal, Quebec, Canada August 20-25, 1995

Sponsored by the

International Joint Conferences on Artificial Intelligence, Inc IJCAII)

American Association for Artificial Intelligence

Canadian Society for Computational Studies of Intelligence

Societe Canadienne pour I'etude de I intelligence par ordinateur

CONTENTS

LEARNING 1

Oversearching and Layered Search in Empirical Learning    

 R QuinLan and R M Cameron-Jones    1019

Lookahead and Pathology in Decision Tree Induction

Sreerama Murthy and Steven Salzberg   1025

LEARNING 2

On Biases in Estimating Multi-Valued Attributes 

Igor kononenko 1034

Flexibly Exploiting Prior Knowledge in Empirical Learning

Julio Ortega and Doug Fisher      1041

LEARNING 3

Using Decision Trees for Conference Resolution

Joseph F McCarthy and' Wendy G Lehnerr   1050

Intermediate Decision Trees         

Laurence B Holder   1056

LEARNING 4

Constructing Nominal X of-N Attributes

 Zijian Zheng     1064

Oblivious Decision Trees Graphs and Top Down Pruning      

Ron Kohavi and (hia-Hsin Li   1071

REINFORCEMENT AND MARKOV MODELS 1

Probabilistic Robot Navigation in Partially Observable Environments

Reid Simmons and Sven Koenig    1080

Approximating Optimal Policies for Partially Observable Stochastic Domains

Ronald Parr and Stuart Russell       1088

REINFORCEMENT AND MARKOV MODELS 2

Process-Oriented Planning and Average-Reward Opumalirv   

Craig Boutilier and Martin L Puterman         1096

Exploiting Structure in Policy Construction    

Craig Boutdier Richard Dearden, and Moises Goldszmidt      1104

REINFORCEMENT AND MARKOV MODELS 3

A Reinforcement Learning Approach to Job-shop Scheduling

Wei Zhang and Thomas G Dietierich          1114

Decomposition Techniques for Planning in Stochastic Domains

Thomas Dean and Shieu-Hong I in         1121

STATISTICAL LEARNING 1

Dependency Relationship Based Decision Combination in Multiple Classifier Systems

Hee-Joong Kang and Jin H Kim          1130

A Studv of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selectio

 Ron Kohavi 115

STATISTICAL LEARNING 2

Local learning in probabilistic networks with

hidden variables   Stuart Russell John Binder Daphne Roller and Keiji Kanazawa        1146

Extending Classical Planning to Real-World Execution with Machine Learning

Gerald Dejong and SiOtt Bennett               1153

PAC LEARNING

The Complexity of Theory Revision

Russell Grrtner 1162

Practical PAC Learning

Dale Schuurmans and Russell Graner          1169

LEARNING 5

Learning to Reason The Non Monotonic Case

Dan Roth                             1178

Generating and Solving Imperfect Information Games

Daphne Roller and Aur Pfeffer            1185

INDUCTIVE LOGIC PROGRAMMING

Covering vs Divide and-Conquer for Top-Down Induction of Logic Programs

 Hennk Bostrum                        1194

AILP Abductive Inductive Logic Programming

 Hilde Ade and Marc Denecker                  1201

LEARNING 6

Building Theories into Instantiation  

Alan M Frisch and C David Page Jr              1210

Learning One More Thing

Sebastian Thrun and Tom M Mitchell

INSTANCE BASED

Rule Induction and Instance-Based Learning A Unified Approach    

Pedro Domingos    1226

Muluresolution Instance-Based Learning              

 Kan Deng and Andrew W Moore

NATURAL LANGUAGE DISCOURSE 1

Generating Information-Sharing Subdialogues in Expert-User Consultation    

Jennifer Chu-Carroll and Sandra Carberry   1233

Generating Discourse across Several User Models Maximizing Belief while Avoiding Boredom and Overload Ingrid

 Zukerman and Richard McConachy   1261

DISCOURSE 2

The Use of Knowledge Preconditions in Language Processing

Karen E Lochbaum    1262

Integrating Gncean and Attcntional Constraints       

Rebecca J Passonneau  1267

PRESENTATION GENERATION

Generating Explanatory Captions for Information Graphics  

Vibhu 0 Mittal Steven Roth Johanna D Moore Joe Mattis and Giuseppe Caremm   1276

Ubiquitous Talker Spoken Language Interaction with Real World Objects   

 Katashi Nagao and Jun Rckimoto      1284

TENSE AND ASPECT

Dynamic Semantics for Tense and Aspect     

Mark Sttedman

Selecting Tense Aspect and Connecting Words In Language Generation

Bonnie J Dorr and Terry Gaasterland       1292

DICTIONARY CONSTRUCTION

Automatic Thesaurus Construction based on Grammatical Relations  

Tokunaga Tahenobu Iwayama Makoto and Tanaka Hozumi   1308

CRYSTAL Inducing a Conceptual Dictionary

Stephen Sodrrland, David Fisher Jonathan Aselttm and 'Wendy Lehnert   1314

STATISTICAL APPROACHES

Hierarchical Bayesian Clustering for Automatic Text Classification

Makoto Iwayama and Takenobu Tokunaga        1322

Stochastic Inversion Transduction Grammars with Application to Segmentation, Bracketing, and Alignment of Parallel Corpora   

Dekat Wu     1328

UNDERSTANDING 1

Improving Heuristic Based Temporal Analysis of Narratives wLth Aspect Determination    

Fel Song and Robin Cohen     1338

Semantic Inference in Natural Language Validating a Tractable Approach

Marc Vilaln     1346

UNDERSTANDING 2

Anaphors PPs and disambiguation process for conceptual analysis 

Saliha Azzam     1354

Discourse as a Knowledge Resource for Sentence Disambiguation

Tetsttya Nasukawa and Naohiko Uramoto    1360

UNDERSTANDING 3

A WordNei-based Algorithm for Word Sense Disambiguation

Xiaobtn Li Stan Szpakowicz, and Stan Matwin     1368

Analogy in the Large     

 Kenneth B Haast    1376

MACHINE TRANSLATION

Unification-Based Glossing         

Vasiletos   Hatzivasstloglou and Kevin Knight   1217

Filling Knowledge Gaps in a Broad Coverage Machine Translation System

Kevin Knight Ishwar Chander Matthew Haines Vasiletos Hatzivassiloglou Eduard Hovy, Masayo Jida Steve K Luk Richard Whitney, and Kenjt Yamada 1390

APPLICATIONS

A Support Tool for Writing Multilingual Instructions 

Cicile Paris Keith Vander Linden Markus Fischer Anthony Hartley, Lyn Pembenon Richard  Power and  Doma Scott  1398

Dialogue actions for natural language interfaces        

Arne Jonsson  1406

PARSING AND GENERATION

An Efficient Algorithm for Surface Generation          

Chruster Samuelsson  1414

 A Dependency-based Method for Evaluating Broad-Coverage Parsers  

 Dekang Lin

1420

 

FORMAL METHODS

 

 

 

Efficient Parametenzablc lype Expansion for Typed Feature Formalisms

Hans-Ulrtcb Krteger and Ulrtch Schdfer

1428

Integration oi Syntactic, Semantic and Contextual Information in Processing Grammatically III Formed Inputs

Osamu Imatcht and Yuji Matsumoto

1435

NONMONOTONIC REASONING

NON M0N0T0NIC REASONING 1

 

On the Relation between Argumentation and Non Monotonic Coherence Based Entailment     Claudette Cayrol

1443

How to infer from inconsistent beliefs without revising'

Salem Benferhat    Didier Dubois and Henn Prade

1449

NON M0N0T0NIC REASONING 2

 

On Decision Theoretic Foundations for Defaults        

Ronen I Brafman and Ntr Friedman

1458

Allowed Arguments            

 Michael Morreau

1466

NON M0N0T0NIC REASONING 3

 

On Specificity in Default Logic                             

Jussi Rmtaneri

1474

Specificity and Inheritance in Default Reasoning         

Sek-Mah Ian and faded Pearl

1480

NON M0N0T0NIC REASONING 4

 

Syntactic Conditional C losures lor Defeasible Reasoning        

 James P Delgrande

Sound and Efficient Non-monotonic Inference Hector        

Geffner Jimena Liopis and Gtsela Mtndez

1488

1495

NON M0N0T0NIC REASONING 5

 

ComputingCircumscriptionRevisitedPreliminaryReport  AndrzcjPamck Doberty WttoldLukaszewicz,andSzalas                                                                              

1502

Constrained and rational default logics

Artur Mikttmk and Mtroslaw Iruszczynsh

1509

NON M0N0T0NIC REASONING 6

 

On Bimodal Nonmonotonic Logics and Their Unimodal and Nonmodal Equivalents Alexander Bochman

1518

Cancelling and Overshadowing Two Types of Defeasibdity in Defeasible Deontic Logic

Leendert W N van der Torre and Yao-Hua Jan

1525

BEUEF REVISION 1

 

Belief revision, revised  Daniel Lehmann

1534

Iterated Theory Base Change A Computational Modei

Mary-Anne Williams

1541

BELIEF REVISION 2

 

Generalized Update Belief Change in Dynamic Settings

Craig Boutiher

1550

Relating Belief Revision and Circumscription

Paolo Liberatore and Marco Schaerf

1557

PLANNING UNCERTAINTY

 

Planning under uncertainty Some key issues

Gregg Collins and Louue Pryor

1567

SOLUTION QUALITY

 

Optimizing Decision Quality with Contract Algorithms     

Shlomo Zilberstein

1576

Expected Solution Quality

John Brntna Mark Drummond and Keith Swanson

1583

ALGORITHMS

 

A Critical Look at Critics in HTN Planning

Kutluhan trol Jama Hendler Dana S Nau and Reiko Tsuneto

1592

Planning with Abstraction Hierarchies can be Exponentially Less Effici

Chnster Backstrom and Peter Jonswn

1599

SEARCH 1

 

Planning with Primary Effects Experiments and Analysis

Fugene Fink and Qiang Yan

1606

Scope and Abstraction Two Criteria for Localized Planning

Amy L Lansky and Lise C Getoor

1612

SEAFICH2

 

Comparison of Methods for Improving Search Efficiency in a Partial-Order Planner

Raghavan Snntvasan and Adele t Houv

1620

Admissible Pruning Strategies based on plan minimality for Plan Space Planning

Subbarao Kambhampati

1627

Fast Planning Through Planning Graph Analysis                       

 Avrim L Blum and Merrick L Furst        1636

Planning with Sharable Resource Constraints                         

 Philippe Laborie and Malik Ghailab     1643

REAL TIME SEARCH

The Focussed D" Algorithm for Real-Time Replannig                

Anthony Stentz      1662

Real-Time Search in Non-Deterministic Domains                    

Sven Koenig and Reid G Simmons   1660

APPLICATIONS AND EVALUATION 1

AI Planning Versus Manufacturing-Operation Planning A Case Study                 

Dana S Nau Satyandra A Gupta and William C Regit   1670

Hierarchical Plan Merging with Application to Process Planning        

Bntanik and M Marrfat   1677

APPLICATIONS AND EVALUATION 2

Planning Executing Sensing and Replanning for Information Gathering            

Crajg A Knoblock     1686

Abstraction by Interchange a biliry in Resource Allocation                        

Berthe Y Choueiry, Bot Faltmgs and Ramer Weigel    1694

PLAN RECOGNITION

A Sound and Fast Goal Recognizer                                                        

Neat Lesh and Oren Etzwm     1704

Recovering Problem-Solving Activities from Query Messages                     

Yoshihtko Hayashi   1711

QUALITATIVE REASONING AND DIAGNOSIS

DIAGNOSIS 1

A Formal Framework for Representing Diagnosis Strategies in Model-Based Diagnosis Systems   

Wolfgang Nejdl Peter Frohlich and Michael Schroeder      1721

No Faults in Structure—How to Diagnose Hidden Interactions                                                   

 Claudia Bottcher     1728

Trading off the costs of inference vs probing in diagnosis          

Johan de Kleer and Olivier Raiman    1736

Diagnosing tree-decomposable circuits                               

Yousn El Fattah and Rtna Dechtcr    1742

MODELLING 1

Generating Causal Networks for Mobile Multi-Agent Systems with Qualitative Regions                    

Korchi Kurumatam      1750

Case-based Modeling with Qualitative Indices                             

Bradley Richards Boi Fairings and Peter Duxbury-Smith     1757

MODELLING 2

Using a Domain Theory to Guide Automated Modeling of Complex Physical Phenomena                       

Sui-ky Ringo Ling    1766

Modeling Time in Hybrid Systems How Fast Is Instantaneous

Yumi Iwasaki Adam Farquhar Vijay Saraswat Daniel Bobrou and \ meet Gupta      1773

SIMULATION 1

Reasoning about Fluid Motion I Finding Structures                                    

Kenneth Yip    1782

Hisstory-based Interpretation of Finite Element Simulations of Seismic Wave Fields

Ulrieh junker and Bertrand Braunschweig    1789

SIMULATION 2

Scaling up Self-Explanatory Simulators Polynomial time Compilation

Kenneth D Forbus and Brian Falkenhamer  1798

Numerical Interval Simulation Combined Qualitative and Quantitative Simulation to Bound Behaviors of Non-Monotonic Systems

 Marcos Vescovi Adam Farquhar and Yumi Iwasaki    1806

MONITORING

Device Representation and Reasoning with Affective Relations 

James M Crawford Daniel L Dvorak Diane f Litman, Anil K Muhra and Peter F Patel-Schneider    1814

Determining the Loci of Anomalies Using Minimal Causal Models   

Richard f Doyle    1821

REASONING ABOUT FUNCTION

FBRL A Function and Behavior Representation Language

 Munchiko Sasajima Yoshinobu Kitamura, Mitsuru Ikeda and Ruchiro Mizoguchi      1830

A Theory of Mapping from Structure to Function Applied to Engineering Thermodynamics                 

John O Everttt     1837

REASONING UNDER UNCERTAINTY

PROBABILITY AND ENTROPY

Minimum Cross-En cropy Reasoning A Statistical Justification                              

Manfred Jaeger      1847

Representation Dependence in Probabilistic Inference                                      

 Joseph Y Halpern and Daphne Roller    1863

IMPRECISE PROBABILITIES

Models and Algorithms for Probabilistic and Bayesian Logic   

Pierre Hansen Brigitte Jaumard   Guy-Blaise  Douanya Nguetse and Marcus Poggi de Aragao  1862

Ignorant Influence Diagrams                                            

Marco Ramom    1869

BAYES NETS

The BAT mobile Towards a Bayesian Automated Taxi               

Jeff Forbes lim Huang ketjt harmzawa and Smart Russell    1878

Adaptive Provision of Evaluation Oriented lnformation Tasks and Techniques

Anthony Jameson Ralph Schafer Joep Simom and Thomas Wets   1886

BELIEF FUNCTIONS

The Canonical Decomposition of a Weighted Belief                        

 Philippe Smets    1896

On the Representation of Nonmoniomc Relations in the Theory of Evidence                   

 Ronald R yager   1902

MULTIPLE VALUED LOGIC

The Rationality and Decidability of Fuzzy Implication                          

Cheng Xiaochun Jiang Yunfer and Liu Xuhua   1910

Possibihstic Temporal Reasoning based on Fuzzy Temporal Constraints 

Lluis Godo and Lluls Vila      1916

DECISION THEORY

Possibility Theory as a Basis for Qualitative Decision Theory                 

Dtdter Dubois and Henri Prade   1924

TEMPORAL REASONING 1

Reasoning about Noisy Sensors in the Situation Calculus               

 Fahiem Bacchus Joseph Y Halpern and Hector f Levesque    1933

A Logic for Acting Sensing and Planning                           

Paolo Traversa and Luca Spalazzs   1941

TEMPORAL REASONING 2

Reasoning about Action and Change Using Dijkstras Semantics for Programming Languages Preliminary Report

Witold Lukaszewicz and Ewa Madahnska Bugaj   1950

The Logic of Dynamic Systems                            

Michael  Thiedscher     1956

TEMPORAL REASONING 3

Dependent Fluents       

 Enrico Giunchiglia and  ladimir Lifschitz   18964

A simple Formalization of Actions Using Circumscription 

G.Neelakantan Kartha and Vladimir Lifichitz    1970

TEMPORAL REASONING 4

A Causal Theory of Ramifications and Qualifications             

 Norman McCain and Hudson Turner    1978

Embracing Causality in Specifying the Indirect Effects of Actions               

Fangzhen Lin    1985

TEMPORAL REASONING 5

Computing Ramifications by Post processing                                     

Michael Thielscher    1904

How to Progress a Database 11 The STRIPS Connection  

Fangzhen Lin and Ray Reiter    2001

TEMPORAL REASONING 6

Towards Action Prediction Using a Mental-Level Model    

Ronen I Brafman and Moshe Tennenholtz    2010

Reasoning about actions Non-deterministic effects Constraints and Qualification               

Chitta Baral     2017

PANELS

Systematic Versus Stochastic Constraint Satisfaction      

Eugene C Freuder (Chair) Rina Dechter Matthew L Ginsberg Bart Selman and Edward Tsang     2027

VERY Large Knowledge bases—Architecture vs Engineering

Jame  Hendler (Chair) Jaime Carbonell Douglas Lenat Riichtro Mizogueht Paul Rosenbloom     2033

A Philosophical Encounter                    

Aaron Sloman     2037

What has Al in Common with Philosophy               

John McCarthy     2041

VIDEOS

Description Logic in Practice A CLASSIC Application

 Deborah L McGumness and Lort Alpenti Resnick ATOT Bell Laboratories and Charles Isbell MITAI Lab   2045

Revealing Collection Structure through Information Access Interfaces  

Marti A Hearst and Jan 0 Pederson Xerox Palo Alto Research Center    2047

Advances of the DBLearn System for Knowledge Discover; in Large Databases   

Jiawei Han Yongjian Fu and Simon Tang Simon Eraser University     2049

IRV Learning to Integrate Visual Information Across Camera Movements

 Peter N Prokopowicz, University of Chicago and Paul R Cooper Northwestern University     2051

WIP From Multimedia to Intellimedia

Elisabeth Andre Wolfgang Finkler Wtnfried Graf Karin Harbusch Jochen Heinsohn Anne Kilger Bern hard Nebel Hans-Jurgen Profitlich Thomas Rist Wolfgang Wahlster (Authors of the WlP System) Andreas Butz (Video Producer) Anthony Jameson (Speaker) German Research Center for Artificial Intelligence (DFKI)  2053

Computer-aided Creative Mechanism Design                  

Boi Faltings and Run Sun, Swiss Federal Institute of Technology   2055

Learning University Mathematics   

Edmund Furse University of Glamorgan    2067

PeopIeFinder a Multimodal Multimedia Communications Tool for Interconnecting Office Staff

Innes A Ferguson and James D Davlouros   2069

 Situated Verbal Interaction in Virtual Design and Assembly

Yong Cao Bernhard Jung and Ipke Wachsmuth University of Bielefeld   2061

Multiple Perspective Interactive Video

Arun Katkere Don huramura Sated Moezzi Patrick Kelly Deborah Swanberg Kojr Wakimoto Edward Hunter Li-Cbeng Tai Shankar Chatterjee and Ramesh Jam University of California San Diego  2063

GRASPER A Permissive Planning   Robot             

 Scott Bennett SRA Corporation and Gerald Dejong University of Illinois   2065

SRICAT Sky Image Cataloging and Analysis Tool            

Usama M Fayyad JPL California Institute of Technology   2067

MUSE (Multidimtnsional User Oriented Synthetic Environment}—A New Approach to the Human-Computer Interface Using Precognitive Models of

 Perception Creve Maples and Craig Peterson   2069

Sandia National Labs A Case Based Approach to Knowledge Navigation 

kristian J Hammond and Robin Burke University of Chicago and Steven L Lytinen Depaul University      2071

Modeling Interactive Agents in ALIVE    

Pattie Maes Brute Blumberg Treivr Darrell Alex Pent land and Alan Wexelblat MIT Media Laboratory    2073