• Introduction
  • Basics
    • Context-free grammars
    • Earley-Parsing
    • RNA
    • Stochastic context-free grammars
    • SCFGs for secondary structure prediction
    • Semiring Parsing
    • RNA-RNA Interaction
    • Multiple context-free grammars
    • Stochastic multiple context-free grammars
    • Parsing of multiple context-free grammars
  • Approach
    • m-dimensional context-free grammars
      • Derivations and language
      • Effective dimension
      • Subgrammars
      • Rule Templates
      • Rule Templates in the Context of Secondary Structure Prediction
      • Inside and Outside Probabilities
    • A Grammar for RIP
      • Handling two molecules
      • GRIP
    • Secondary Structure Subgrammars
      • GSecStr—secondary structures in r
      • GSecStr—secondary structures in s
    • Earley-Parser for 2D-CFGs
      • Item-related definitions
    • One-dimensional preprocessing featuring an SCFG Earley parser
      • Outside probabilities in split grammars
    • Utilizing item values
      • Inside and outside probabilities
      • Rule probability estimates
      • Viterbi parses
    • Training with known structures
  • Implementation Design
    • Motivating observations
    • Item order
      • Choice of rule indices
      • Definition of
      • Correctness of
    • Item representation
    • Optimistic Prediction
    • Completion
    • Immediate Scanning
      • Getting rid of pre-scan items
      • Jumping over terminals
    • Late item value computation
    • Keeping probabilities in range—the 4-times-trick
      • Prediction
      • Scanning
      • Completion
      • Finalization
    • Reverse parsing
      • Item order
      • Item representation
      • Computation of reverse values
      • Scanning
      • Completion—first type
      • Completion—second type
      • 4-times-trick
  • Results
    • jackRIP—our C++ implementation of a 2D-CFG parser
    • Target Machine
    • Runtime efficiency tests
      • RNA-RNA-interaction
      • Comparison with classical Earley parsing
    • Prediction quality tests
      • Test Data
      • Prediction method
      • Quality measures
    • Prediction results
      • Data from kato2009grammatical
      • Data from andronescu2005secondary
      • Summary
  • Conclusion
    • Future Work
      • Statistical Sampling based on trained models
      • Length-Dependency
  • Appendices
  • Pseudocode
    • Collected definitions
    • Invariants
    • 1D-Earley-Forward
    • 1D-Earley-Reverse
    • 2D-Earley-Forward
    • 2D-Earley-Reverse
  • Bibliography