scientific article; zbMATH DE number 801745

Publication date: 3 October 1995

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

complexity measures string matching algorithms pattern matching algorithms compression techniques text algorithmic techniques

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Combinatorics on words (68R15) Theory of compilers and interpreters (68N20) Distributed algorithms (68W15) Computing methodologies for text processing; mathematical typography (68U15)

Related Items

Swap and mismatch edit distance, Efficient algorithms for Lempel-Ziv encoding, Pattern-matching problems for 2-dimensional images described by finite automata, Algorithms for subsequence combinatorics, An aperiodicity problem for multiwords, A Fast Suffix Automata Based Algorithm for Exact Online String Matching, Extreme Witnesses and Their Applications, Random Deterministic Automata, ZIV-LEMPEL AND CROCHEMORE FACTORIZATIONS OF THE GENERALIZED PERIOD-DOUBLING WORD, Run-Length Encoded Nondeterministic KMP and Suffix Automata, A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String, A weak approach to suffix automata simulation for exact and approximate string matching, Full sets of pictures to encode pictures, Accelerating Boyer Moore Searches on Binary Texts, Searching for Gapped Palindromes, Quantum algorithm for lexicographically minimal string rotation, Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions, Towards optimal packed string matching, Compact suffix automata representations for searching long patterns, Detecting the morphic images of a word : improving the general algorithm, Languages with mismatches, Partial words and the critical factorization theorem revisited, Equations on partial words, Worst Case Efficient Single and Multiple String Matching in the RAM Model, Algorithms for Indexing Highly Similar DNA Sequences, Generalized function matching, Simple Real-Time Constant-Space String Matching, Primitive partial words, Forty Years of Text Indexing, Approximation algorithms for maximum two-dimensional pattern matching, Words and special factors, Unnamed Item, NR‐grep: a fast and flexible pattern‐matching tool, Unnamed Item, Unnamed Item, Approximate periods of strings, Simple and flexible detection of contiguous repeats using a suffix tree, Recovering Repetitive Sub-functions from Observations, Detecting regularities on grammar-compressed strings, Unnamed Item, Verifiable Pattern Matching on Outsourced Texts, Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence, Generalizations of suffix arrays to multi-dimensional matrices., Synchronized Regular Expressions, Efficient dynamic dictionary matching with DAWGs and AC-automata, Bit-parallel ($\delta ,\gamma$)-matching and suffix automata, Practical algorithms for transposition-invariant string-matching, Compressed automata for dictionary matching, Fast distance multiplication of unit-Monge matrices, Space-efficient representation of truncated suffix trees, with applications to Markov order estimation, On the complexity of pattern matching for highly compressed two-dimensional texts., Collage system: A unifying framework for compressed pattern matching., Approximate pattern matching and transitive closure logics., A new regular grammar pattern matching algorithm., On maximal suffixes and constant-space linear-time versions of KMP algorithm., A fast algorithm for stereo matching, Tight bounds on the complexity of the Apostolico-Giancarlo algorithm, Two-dimensional pattern matching with rotations, Scaled and permuted string matching, Average complexity of exact and approximate multiple string matching, Closed Ziv-Lempel factorization of the $m$-bonacci words, Accelerating Boyer-Moore searches on binary texts, The Range Automaton: an efficient approach to text-searching, Faster subsequence recognition in compressed strings, Efficient parameterized string matching, A time and space efficient data structure for string searching on large texts, Faster two-dimensional pattern matching with rotations, Periodicity in rectangular arrays, Testing primitivity on partial words, An automata-theoretic approach to the word problem for $\omega$-terms over R, String-matching with OBDDs, A unifying look at the Apostolico--Giancarlo string-matching algorithm, Compact directed acyclic word graphs for a sliding window, Equivalence of simple functions, An improved algorithm for solving the banded cyclic string-to-string correction problem, Abelian-primitive partial words, Simple real-time constant-space string matching, On-line construction of position heaps, A note on a simple computation of the maximal suffix of a string, Periodicity, morphisms, and matrices., Conjugacy and episturmian morphisms., Application of Lempel-Ziv factorization to the approximation of grammar-based compression., Generalizations of suffix arrays to multi-dimensional matrices., Truncated suffix trees and their application to data compression., On the structure of compacted subword graphs of Thue-Morse words and their applications, On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns, Overlap matching., A compact representation of nondeterministic (suffix) automata for the bit-parallel approach, Complexity-compression tradeoffs in lossy compression via efficient random codebooks and databases, Combinatorics of periods in strings., Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Algorithmic complexity of protein identification: Combinatorics of weighted strings, Fast profile matching algorithms - A survey, Periods and binary words, Optimal pattern matching algorithms, A faster quick search algorithm, siEDM: an efficient string index and search algorithm for edit distance with moves, Text searching allowing for inversions and translocations of factors, Automata for solid codes, Generalized pattern matching and periodicity under substring consistent equivalence relations, Efficient computation of maximal anti-exponent in palindrome-free strings, Verifiable pattern matching on outsourced texts, Description and analysis of a bottom-up DFA minimization algorithm, Algorithms for finding a most similar subforest, Some theoretical challenges in digital geometry: a perspective, On-line construction of compact directed acyclic word graphs, Linear time algorithms for finding and representing all the tandem repeats in a string, On word equations in one variable, Ternary directed acyclic word graphs, Linear-time computation of local periods, Improving the bit-parallel NFA of Baeza-Yates and Navarro for approximate string matching, The wide window string matching algorithm, Partial words and the critical factorization theorem, On the complexity of decidable cases of the commutation problem of languages, Space efficient search for maximal repetitions, On suffix extensions in suffix trees, On z-factorization and c-factorization of standard episturmian words, Parameterized matching on non-linear structures, Improving practical exact string matching, On the size of Boyer-Moore automata, Inverse Lyndon words and inverse Lyndon factorizations of words, Semi-local longest common subsequences in subquadratic time, Extreme witnesses and their applications, Efficient pattern matching in elastic-degenerate strings, On special families of morphisms related to $\delta $-matching and don't care symbols, Disjunctive partial deduction of a right-to-left string-matching algorithm, How many squares can a string contain?, Fully-online suffix tree and directed acyclic word graph construction for multiple texts, Discovering subword associations in strings in time linear in the output size, Alphabet-independent optimal parallel search for three-dimensional patterns, Optimal representation in average using Kolmogorov complexity, Unbordered partial words, An average-case optimal one-variable pattern language learner, Approximate string matching on Ziv--Lempel compressed text, Searching for gapped palindromes, Parallel construction and query of index data structures for pattern matching on square matrices, The exact number of squares in Fibonacci words, Constant-space string-matching in sublinear average time, Average-optimal string matching, Approximate string matching using factor automata, Normal forms of quasiperiodic strings, Asymptotic estimation of the average number of terminal states in DAWGs, Tree pattern matching with a more general notion of occurrence of the pattern., A speed-up for the commute between subword trees and DAWGs., Cut and paste, Compact recognizers of episode sequences, Regular biosequence pattern matching with cellular automata, Discovering instances of poetic allusion from anthologies of classical Japanese poems, Discovering characteristic expressions in literary works., Efficient string matching based on a two-step simulation of the suffix automaton