The Smallest Automaton Recognizing the Subwords of a Text
Explore this paper's citation graph
Summary
It is demonstrated that the smallest partial DFA for the set of all subwords of a given word w, Iwl>2, has at most 21w(-2 states and 3(wl-4 transition edges, independently of the alphabet size).
- Type
- article
- Published
- 1985-01-01
- Cited by
- 375
- References
- 28
- OpenAlex
- https://openalex.org/W1972770363
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:13277581
Keywords
Alphabet, Combinatorics, Word (group theory), Mathematics, Deterministic finite automaton
References
- Linear size finite automata for the set of all subwords of a word - an outline of results
- Linear searching for a square in a word
- J.E.Hopcroft, J.D. Ullman 著, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, A5変形版, X+418, \6,670, 1979
- String Matching in Real Time
- Fast Pattern Matching in Strings
- Introduction to Automata Theory, Languages and Computation
- Efficient On-Line Construction and Correction of Position Trees
- Linear Algorithm for Data Compression via String Matching
- Optimal Off-Line Detection of Repetitions in a String
- Detection of periodicities and string-matching in real time
- Building a complete inverted file for a set of text files in linear time
- Linear automaton transformations
- A method for detecting structure in polygons
- Efficient string matching
- A Space-Economical Suffix Tree Construction Algorithm
- A fast string searching algorithm
- PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric
- Linear Pattern Matching Algorithms
- Optimal Factor Transducers
- String-Matching in Real Time: Some Properties of the Data Structure
Cited by
- Discovering related DNA sequences via mutual information
- Conservative extraction of over-represented extensible motifs
- Suffix trees and their applications in string algorithms
- Analyse statistique de la structure des automates représentant des dictionnaires électroniques
- Program and Data Specialization Principles, Applications, and Self-Application
- Search Problems for Speech and Audio Sequences
- Sequence Comparisons via Algorithmic Mutual Information
- A Hybrid Indexing Method for Approximate String Matching
- Sparse compact directed acyclic word graphs
- Automates et algorithmes sur les mots
- Construction of the CDAWG for a Trie
- Proceedings of the Scientific Data Compression Workshop
- An Introduction to Data Structures and Algorithms
- Noiseless compression using non-Markov models
- Fully-online construction of suffix trees and DAWGs for multiple texts
- Searching for Ephemeral Subsequences in Strings
- Algorithms for Memory Hierarchies
- Recherches de motifs et de similarités en bioinformatique : modélisations, solutions logicielles et matérielles
- Faster Compact On-Line Lempel-Ziv Factorization
- Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding
Related papers
- Hyper-minimizing minimized deterministic finite state automata
- Finite State Machine and Its Application to the String Searching
- Deterministic finite automata with recursive calls and DPDAs
- Research of Constructing Algorithm to Create D~2FA
- Application and Research of Finite State Automata in Pattern Matching
- A Memory-efficient ε-Removal Algorithm for Weighted Acyclic Finite-State Automata
- Deriving Tests with Guaranteed Fault Coverage for Input / Output Automata
- Fundamental results for learning deterministic extended finite state machines from queries