Automata and forbidden words

DOI10.1016/S0020-0190(98)00104-5MaRDI QIDQ293331zbMATH OpenDBLPWikidataFDO

Authors Maxime Crochemore, Filippo Mignosi, Antonio Restivo

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098001045?np=y

zbMATH Keywords

formal languagesfactor codeanti-factorial languageavoiding a wordfactor automatonfactorial languagefailure functionforbidden word

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3956447
• Automata and dictionaries.
• scientific article; zbMATH DE number 4071019
• scientific article; zbMATH DE number 1121923
• scientific article; zbMATH DE number 1222602
• scientific article; zbMATH DE number 53545
• scientific article; zbMATH DE number 130894
• scientific article; zbMATH DE number 871446
• Words and forbidden factors
• Automata and differentiable words

Cites work

• scientific article; zbMATH DE number 1972790 (Why is no real title available?)
• Complexity and special factors
• Efficient string matching
• Minimal forbidden words and symbolic dynamics
• On bispecial factors of the Thue-Morse word
• Some combinatorial properties of Sturmian words

Cited in

(45)

• Two-Sided Bounds for the Growth Rates of Power-Free Languages
• INFIX-FREE REGULAR EXPRESSIONS AND LANGUAGES
• RATIONAL APPROXIMATIONS OF POLYNOMIAL FACTORIAL LANGUAGES
• Music Corpus Analysis Using Unwords
• MINIMAL FORBIDDEN PATTERNS OF MULTI-DIMENSIONAL SHIFTS
• On overabundant words and their application to biological sequence analysis
• Fast label extraction in the CDAWG
• Growth rates of complexity of power-free languages
• Building phylogeny with minimal absent words
• Minimal forbidden words and symbolic dynamics
• One-Dimensional Tiling Semigroups and Factorial Languages
• Absent words in a sliding window with applications
• Absent subsequences in words
• scientific article; zbMATH DE number 1222602 (Why is no real title available?)
• Automata and differentiable words
• Using minimal absent words to build phylogeny
• From monomials to words to graphs.
• LANGUAGES WITH A FINITE ANTIDICTIONARY: SOME GROWTH QUESTIONS
• Fast detection of specific fragments against a set of sequences
• Generalizations of code languages with marginal errors
• Words and special factors
• Forty Years of Text Indexing
• Reverse-safe text indexing
• Absent Subsequences in Words
• Growth properties of power-free languages
• Combinatorics of minimal absent words for a sliding window
• Constructing antidictionaries of long texts in output-sensitive space
• Growth rates of power-free languages
• Words and forbidden factors
• Negative selection algorithms on strings with efficient training and linear-time classification
• Minimal forbidden subwords
• Forbidden words in symbolic dynamics
• Reducing space for index implementation.
• Internal shortest absent word queries in constant time and linear space
• Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
• Dynamic construction of an antidictionary with linear complexity
• Growth of power-free languages over large alphabets
• Some inner metric parameters of a digraph: iterated line digraphs and integer sequences
• WQO is decidable for factorial languages
• Alignment-free sequence comparison using absent words
• Generalizations of Code Languages with Marginal Errors
• Word assembly through minimal forbidden words
• Minimal absent words in rooted and unrooted trees
• Mesosome avoidance
• Linear-time computation of generalized minimal absent words for multiple strings

This page was built for publication: Automata and forbidden words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293331)