Contents

• List of Figures
• List of Tables
• Introduction
  • Overview
  • Motivation
  • Contributions
  • Structure of the Thesis
  
  
• Typed Feature Structures
  • Type Hierarchies
  • Typed Feature Structure Definition
    • Example
  • Typed Feature Structures Operations
    • Subsumption
    • Unification
    • Descriptions and Most General Satisfiers
  • Extensions
    • Appropriateness
    • Well-Typed Feature Structures
    • Statically Typable Signatures
    • Structure Sharing
  • Typed Feature Structure Cuts
  
  
• Unification-Based Grammars
  • Head-Driven Phrase Structure Grammars
    • Principles of HPSG
    • The HPSG Formalism
  • Implementation Aspects
    • Compiling Grammar Rules
    • Variables in TFS Representations
    • TFS Grammar Rules
    • Encoding of TFSs
  
  
• Indexing for TFSG Parsing
  • Chart Parsing with Typed Feature Structure Grammars
    • Parsing with Typed Feature Structures
    • Bottom-Up Parsing
    • EFD Parsing
    • Parsing as Unification of MRSs
  • The Typed Feature Structure Indexing Problem
    • Difficulties for TFSG Indexing
    • Indexing Timeline
  • Indexed Chart Parsing
    • General Indexing Strategy
    • Using the Index
    • An Example
  • Previous Approaches to Indexing and Filtering TFSGs
    • HPSG Parsing with CFG Filtering
    • Quick Check
    • Rule Filtering
  • A Discussion About Optimization Approaches
    • Indexing vs. Filtering
    • Statistical vs. Non-Statistical Methods
  
  
• Indexing for Non-Parsing Applications
  • Indexing For Other TFS Applications
    • An Indexing Scheme for TFS Retrieval
    • Automaton-based Indexing for Lexical Generation
  • General Term Indexing
    • Attribute-Based Indexing
    • Set-Based Indexing
    • Tree-Based Indexing
  • Indexing in Database Systems
  
  
• TFSG Indexing through Static Analysis
  • Positional Indexing
    • Building the Index
    • Using the Index
  • Path Indexing
    • Static Analysis of Grammar Rules
    • Building the Path Index
    • Key Extraction in Path Indexing
    • Using the Path Index
  
  
• Experimental Evaluation
  • Resources
  • Prolog Data Structure
  • Experiments
    • Evaluation using the unconstrained MERGE
    • Evaluation using the constrained MERGE
    • Comparison between statistical and non-statistical optimizations
  • Evaluation on Other UBGs
    • The Alvey Grammar
    • Penn Treebank CFG
  
  
• Conclusions and Future Work
  • Conclusions
  • Future Work
  
  
• Bibliography