Jewels of Stringology
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Searching and sorting (68P10) Formal languages and automata (68Q45) Combinatorics on words (68R15) Computing methodologies for text processing; mathematical typography (68U15) Nonnumerical algorithms (68W05) Parallel algorithms in computer science (68W10) Analysis of algorithms (68W40)
Efficient algorithms for matching a text sample against a given text are not only theoretically interesting; they also have many important applications, ranging from basic text editor functions, over look-up operations in dictionaries, to alignment problems for DNA sequences. In their new book, the authors present some algorithmic jewels of this field, starting from textbook classics like the Knuth-Morris-Pratt and Boyer-Moore algorithms, then moving on to two-dimensional and parallel algorithms. One can only agree with the authors that such jewels deserve to shine. On the other hand, it is not so clear which group of readers profit most from this collection. Students may find the -- seemingly smooth -- text hard to read at some places, whereas the experienced reader can always resort to the excellent book on text algorithms by the same authors [Text algorithms. New York, NY: Oxford Univ. Press (1994; Zbl 0844.68101)]. Still, the book is a valuable addition to the field.
- Unbordered partial words
- Repetitions in strings: algorithms and combinatorics
- On regular tree languages and deterministic pushdown automata
- Validating the Knuth-Morris-Pratt failure function, fast and online
- Efficient algorithms for shortest partial seeds in words
- Lempel-Ziv data compression on parallel and distributed systems
- Computing the longest previous factor
- On the maximum number of cubic subwords in a word
- On-line construction of compact directed acyclic word graphs
- The wide window string matching algorithm
- Solving string problems on graphs using the labeled direct product
- k-approximate quasiperiodicity under Hamming and edit distance
- Gray codes for Fibonacci \(q\)-decreasing words
- On modification of Boyer-Moore-Horspool's algorithm for tree pattern matching in linearised trees
- Experimental evaluation of algorithms for computing quasiperiods
- Block trees
- Automata for solid codes
- On trace inclusion optimization problems
- Efficient counting of square substrings in a tree
- Distance measures for biological sequences: some recent approaches
- Compressed string-matching in standard Sturmian words
- String periods in the order-preserving model
- Universal reconstruction of a string
- Efficient dynamic dictionary matching with DAWGs and AC-automata
- An efficient variable-to-fixed length encoding using multiplexed parse trees
- Tree template matching in ranked ordered trees by pushdown automata
- The number of runs in a string
- Indexing factors with gaps
- A space efficient direct access data structure
- Palindromic decompositions with gaps and errors
- Order-preserving matching
- Languages with mismatches
- Relational codes of words
- Freeness of partial words
- Parsing with a finite dictionary
- Longest repeats with a block of \(k\) don't cares
- On del-robust primitive words
- Locally compressed suffix arrays
- Asymptotic behaviour of the maximal number of squares in standard Sturmian words
- Unbordered pictures: properties and construction
- Time-optimal top-k document retrieval
- Simple real-time constant-space string matching
- Sparse and truncated suffix trees on variable-length codes
- Efficient seeds computation revisited
- Polynomial-time approximation algorithms for weighted LCS problem
- Efficient and secure generalized pattern matching via Fast Fourier Transform
- FRIEZES, STRINGS AND CLUSTER VARIABLES
- Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
- Tuning the Zhu-Takaoka string matching algorithm and experimental results.
- Implementation of directed acyclic word graph.
- scientific article; zbMATH DE number 2131247 (Why is no real title available?)
- Arbology: trees and pushdown automata
- V-order: new combinatorial properties \& a simple comparison algorithm
- String Periods in the Order-Preserving Model
- Fast algorithms for abelian periods in words and greatest common divisor queries
- Universal reconstruction of a string
- Non-expandable non-overlapping sets of pictures
- Sturmian and Episturmian Words
- Compatibility relations on codes and free monoids
- Equations on partial words
- An Extension of the Lyndon Schützenberger Result to Pseudoperiodic Words
- Usefulness of directed acyclic subword graphs in problems related to standard Sturmian words
- Extracting powers and periods in a word from its runs structure
- Simple real-time constant-space string matching
- Efficient seed computation revisited
- A linear time algorithm for consecutive permutation pattern matching
- On the structure of compacted subword graphs of Thue-Morse words and their applications
- Forbidden traces and forbidden subtraces
- Asynchronous trace-matching automata
- A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
- scientific article; zbMATH DE number 801745 (Why is no real title available?)
- scientific article; zbMATH DE number 828444 (Why is no real title available?)
- The greedy approach to dictionary-based static text compression on a distributed system
- Unweighted and weighted hyper-minimization
- Fast algorithm for partial covers in words
- Boosting pattern matching performance via k-bit filtering
- Improved space-time tradeoffs for approximate full-text indexing with one edit error
- New simple efficient algorithms computing powers and runs in strings
- Simple tree pattern matching for trees in the prefix bar notation
- Computing the number of cubic runs in standard Sturmian words
- On new algorithms of mutual transformation of string schemes
- Constructing words with high distinct square densities
- Compressed Multiple Pattern Matching
- Computing the Antiperiod(s) of a String
- Longest unbordered factor in quasilinear time
- LZ-End Parsing in Linear Time
- A filtering technique for all pairs approximate parameterized string matching
- Detecting one-variable patterns
- Linear-size CDAWG: new repetition-aware indexing and grammar compression
- Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
- Tree template matching in ranked ordered trees by pushdown automata
- Sets of pictures avoiding overlaps
- Functional programs as compressed data
- Disjunctivity and other properties of sets of pseudo-bordered words
- Palindromic decompositions with gaps and errors
- Multidimensional term indexing for efficient processing of complex queries
- Algorithmic techniques for the polymer sciences
- Algorithms on Strings
- Indexing Circular Patterns
- Watson-Crick Conjugate and Commutative Words
This page was built for publication: Jewels of Stringology
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4451072)
