Minimal forbidden subwords

Motivated by a study of similar problems stated for factors of words, we study forbidden subwords of a language or a word. A procedure for obtaining the set of all words avoiding a given set of subwords is presented. On the other hand, an algorithm for computing the set of minimal forbidden subwords...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2004-12, Vol.92 (5), p.211-218
Main Authors: PETKOVIE, Tatjana, CIRIC, Miroslav, BOGDANOVIC, Stojan
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Automata
Automata. Abstract machines. Turing machines
Combinatorics on words
Computer science
control theory
systems
Data compression
Data processing. List processing. Character string processing
Exact sciences and technology
Formal languages
Language theory and syntactical analysis
Languages
Memory organisation. Data processing
Orders of words
Software
Studies
Subwords
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Motivated by a study of similar problems stated for factors of words, we study forbidden subwords of a language or a word. A procedure for obtaining the set of all words avoiding a given set of subwords is presented. On the other hand, an algorithm for computing the set of minimal forbidden subwords for a word is given. The case of a two-letter alphabet appears to be particularly interesting and it is considered separately.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2004.09.001