The smallest automaton recognizing the subwords of a text

DOI10.1016/0304-3975(85)90157-4zbMath0574.68070OpenAlexW1972770363WikidataQ29036151 ScholiaQ29036151MaRDI QIDQ1063423

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90157-4

zbMATH Keywords

minimal automaton partial deterministic finite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences, Speeding up two string-matching algorithms, A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences, Linear-size suffix tries, From Nerode's congruence to suffix automata with mismatches, General suffix automaton construction algorithm and space bounds, Efficient parameterized string matching, Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations, On-line construction of suffix trees, Searching subsequences, A new distance metric on strings computable in linear time, Combinatorics of minimal absent words for a sliding window, La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time), On the Structure of Consistent Partitions of Substring Set of a Word, Compressed directed acyclic word graph with application in local alignment, Efficient computation of substring equivalence classes with suffix arrays, Covering a string, On Sturmian graphs, Matching a set of strings with variable length don't cares, On-line construction of position heaps, A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String, Parameterized DAWGs: efficient constructions and bidirectional pattern searches, The palindromization map, THE STRUCTURE OF FACTOR ORACLES, On the Suffix Automaton with Mismatches, Inferring strings from position heaps in linear time, Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets, On the structure of compacted subword graphs of Thue-Morse words and their applications, String matching algorithms and automata, The parameterized suffix tray, Sturmian and Episturmian Words, Parallel construction of minimal suffix and factor automata, Dynamic construction of an antidictionary with linear complexity, Multi-pattern matching algorithm with wildcards based on bit-parallelism, Verifying and enumerating parameterized border arrays, Text searching allowing for inversions and translocations of factors, Algorithms for Indexing Highly Similar DNA Sequences, A variation on the Boyer-Moore algorithm, Approximate string-matching with $q$-grams and maximal matches, Data compression with factor automata, COMBINATORIAL CHARACTERIZATION OF THE LANGUAGE RECOGNIZED BY FACTOR AND SUFFIX ORACLES, $xkcd$-repeats: a new taxonomy of repeats defined by their context diversity, WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING, Motif patterns in 2D, Approximate string matching with suffix automata, On-line construction of compact directed acyclic word graphs, Forty Years of Text Indexing, Ternary directed acyclic word graphs, Special factors and the combinatorics of suffix and factor automata, Nearly $k$-universal words -- investigating a part of Simon's congruence, Characteristic Sturmian words are extremal for the critical factorization theorem, On suffix extensions in suffix trees, La reconnaissance des facteurs d'un mot dans un texte, A faster algorithm for matching a set of patterns with variable length don't cares, Unnamed Item, Unnamed Item, Counting Parameterized Border Arrays for a Binary Alphabet, THE DESIGN PRINCIPLES AND ALGORITHMS OF A WEIGHTED GRAMMAR LIBRARY, FORMAL MODELLING OF VIRAL GENE COMPRESSION, A brief history of parameterized matching problems, Online algorithms for constructing linear-size suffix trie, 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, Transducers and repetitions, Speeding up two string-matching algorithms, Average sizes of suffix trees and DAWGs, Minimisation of automata, EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM, Efficient dynamic dictionary matching with DAWGs and AC-automata, Normal forms of quasiperiodic strings, Constructing suffix arrays in linear time, Indexing text with approximate $q$-grams, A speed-up for the commute between subword trees and DAWGs., Reducing space for index implementation., Compact recognizers of episode sequences, Words and forbidden factors, Nearly $k$-universal words -- investigating a part of Simon's congruence, Forbidden Factors and Fragment Assembly

Uses Software

PATRICIA

Cites Work