A Uniform Computational Model
for Natural Language Parsing and Generation

PhD thesis by Günter Neumann , University of Saarbrücken, 1994

Supervisors: Prof. Dr. H. Uszkoreit, Prof. Dr. W. Wahlster

• Contents
• List of Figures
• Introduction
  • The Goals of the Thesis
    • A novel uniform tabular algorithm
    • A performance model based on uniform processing.
    • Implementation
    • Towards a competence-based performance model of natural language
  • Overview
• Current Approaches in Reversible Systems
  • Arguments for Reversible Natural Language Processing
    • Psycholinguistic Motivations
    • Engineering and Computational Motivations
      • Consistency
      • Non-redundancy
      • Portability and Flexibility
    • Adaptability to Language Use of Others
    • Possible Arguments against Reversibility
  • A Classification Scheme for Reversible Systems
  • Problems with Existing Approaches
    • The Uniform Architecture of Shieber
    • The Head-driven Approach of Van Noord and Shieber et al.
    • Gerdemann's Earley Style Processing Scheme
    • Summary
• Linguistic and Formal Foundations
  • Constraint-based Grammars
  • Constraint Logic Programming
    • Constraint Languages and Relational Extensions
      • Constraint Language
      • Relational Extension
      • Definite clauses
      • Operational semantics
    • The Constraint Language
      • Feature Description
      • Feature Graphs
      • Interpretation of Constraints
  • Specification of Constraint-based Grammars in
    • Form of grammar rules and lexical entries
    • Representation of phonological information
    • Representation of semantic information
    • Representation of grammatical derivations
    • Readable notation
  • Parsing and Generation
    • Restricted parsing problem
  • Conclusion
• A Uniform Tabular Algorithm for Parsing and Generation
  • Overview of Earley Deduction
    • Blocking new lemmas
    • Use of a restrictor
  • Generalizing Pereira and Warren's Earley Deduction Scheme
  • A Data-driven Selection Function
  • A Data Structure for Lemmas
    • Specification of Goals
  • The Inference Algorithm
    • Prediction
    • Completion
  • An Agenda-based Control Regime
    • Scheduling the tasks of an agenda
  • Performing Parsing and Generation
  • Indexing Derived Clauses
  • A Uniform Indexing Mechanism
  • Extending the Un-indexed Version to an Indexed Version
  • A Parsing and Generation Example
  • Processing of Empty Heads
    • Parsing
    • Generation
  • Properties
    • General flow of control
    • Top-down versus bottom-up
    • Coherence and completeness
    • Termination
    • On-line
    • Uniform indexing mechanism
    • Agenda-based control
  • Implementation
    • Representation of grammar and lexical entries
    • Representation of item sets
    • The selection function
    • Inference rules
    • The agenda control
  • Item Sharing Between Parsing and Generation
    • The Basic Idea
    • Adaptation of the Uniform Tabular Algorithm
    • An Object-Oriented Architecture
    • Implementation
  • Conclusion
• A Performance Model based on Uniform Processing
  • The Modular Status of Natural Language Systems
  • Natural Language Systems and Reversible Grammars
  • Monitoring and Revision
    • The Monitoring Model of Levelt
      • Discussion
    • The Anticipation Feedback Loop Mode
      • Discussion
    • Text Revision
      • Discussion
  • A Blueprint of the New Model
    • What does this model contribute to system design?
  • Monitoring and Revision with Reversible Grammars
    • Locating Ambiguity with Derivation Trees
    • Overview of the Monitored Generation Strategy
    • Marking a Derivation Tree
    • Changing the Ambiguous Parts
    • Redefining Locality
    • Simple Attachment Example
    • Some More Examples
    • Properties and Implementation
      • Properties
      • Implementation
  • Generation of Paraphrases
    • A Naive Version
    • A More Suitable Strategy
    • A Suitable Strategy
    • A Simple Example
    • Properties
  • Incremental Interleaving of Parsing and Generation
    • Basic Problems of Incremental Monitoring
    • A Look-Back Strategy
    • Performing Revision Within the Uniform Algorithm
    • Performing Ambiguity Checks within the Uniform Algorithm
      • Determination of Context
      • Check ambiguity
    • Using Shared Items during Incremental Monitoring
    • Implementation
    • Properties of the Incremental Method
  • Conclusion
• Summary and Future Directions
  • Summary
  • Future Directions
    • Application of Explanation-Based Learning for Efficient Processing of Constraint-based Grammars
    • Further Important Directions
      • Using Preference-based Strategies.
      • Processing of Elliptical Utterances.
      • Fully Incremental Text Processing.
    • Cognitive Processing
      • Aspects of Cognitive Parsing
      • Aspects of Cognitive Generation
• A Sample Grammar
• References
• About this document ...