Contents
1. Introduction
1.1. Terminology
2. The Labeled Path Case: Indexing Compressed Text
2.1. The Entropy Model: Compressed Suffix Arrays
2.2. The Repetitive Model
3. Indexing Labeled Graphs and Regular Languages
3.1. Graph Compression
3.2. Conditional Lower Bounds
3.3. Hypertext Indexing
3.4. Prefix Sorting: Model and Terminology
3.5. Indexing Labeled Trees
3.6. Further Generalizations
3.7. Wheeler Graphs
3.8. p-sortable Automata
4. Conclusions and Future Challenges