Inhalt

•  
   Abstract
•  
   Acknowledgements
•  
   Contents
•  
  1 Introduction
•  
   1.1 The streaming model
•  
   1.2 The sliding window model
•  
   1.3 Outline
•  
  2 Preliminaries
•  
   2.1 Basic notation
•  
   2.2 Words, languages, monoids
•  
   2.3 Automata and regular languages
•  
   2.4 Context-free languages
•  
   2.5 Rational transductions
•  
  3 The sliding window model
•  
   3.1 Streaming algorithms
•  
   3.2 Fixed-size sliding window model
•  
   3.3 Variable-size sliding window model
•  
   3.4 Alternative characterizations
•  
   3.5 Related complexity measures
•  
   3.6 Connection to language growth
•  
   3.7 Closure properties
•  
   3.8 Remarks
•  
  4 Regular languages
•  
   4.1 Space trichotomy
•  
   4.2 Characterization of the space classes
•  
   4.3 The uniform problem
•  
   4.4 Deciding the space complexity
•  
   4.5 Conclusion
•  
  5 Rational functions
•  
   5.1 Suffix expansions
•  
   5.2 Finite index right congruences
•  
   5.3 Regular look-ahead
•  
   5.4 Critical tuples in Rt
•  
   5.5 Well-behaved transducers
•  
   5.6 Space trichotomy
•  
   5.7 Conclusion
•  
  6 Randomized sliding window algorithms
•  
   6.1 Randomized streaming algorithms
•  
   6.2 Space quatrochotomy
•  
   6.3 The Bernoulli counter
•  
   6.4 Suffix-free languages
•  
   6.5 Lower bounds with two-sided error
•  
   6.6 Lower bounds in the variable-size model
•  
   6.7 Lower bounds with one-sided error
•  
   6.8 Conclusion
•  
  7 Sliding window property testing
•  
   7.1 Introduction
•  
   7.2 Sliding window testers for regular languages
•  
   7.3 Trivial languages
•  
   7.4 Upper bounds
•  
   7.5 Lower bounds
•  
   7.6 Conclusion
•  
  8 Strict correctness
•  
   8.1 Introduction
•  
   8.2 Derandomization
•  
   8.3 Polynomially long streams
•  
   8.4 Conclusion
•  
  9 Context-free languages
•  
   9.1 Introduction
•  
   9.2 Below logarithmic space
•  
   9.3 Above logarithmic space
•  
   9.4 Deterministic one-counter languages
•  
   9.5 Conclusion
•  
  10 Visibly pushdown languages
•  
   10.1 Visibly pushdown automata
•  
   10.2 Description of the Myhill-Nerode classes
•  
   10.3 Proof strategy
•  
   10.4 Reduction to transducers
•  
   10.5 Bounded overapproximation
•  
   10.6 Conclusion
•  
   11 Conclusion
•  
  Resulting publications
•  
   Relevant for this thesis
•  
   Other publications
•  
   Bibliography