6533b86dfe1ef96bd12c9da2

RESEARCH PRODUCT

Words and Patterns

Sergio SalemiAntonio Restivo

subject

Set (abstract data type)Discrete mathematicsStructure (mathematical logic)Regular languageRelation (database)Binary numberComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Natural orderPartially ordered setComputer Science::Formal Languages and Automata TheoryWord (computer architecture)Mathematics

description

In this paper some new ideas, problems and results on patterns are proposed. In particular, motivated by questions concerning avoidability, we first study the set of binary patterns that can occur in one infinite binary word, comparing it with the set of factors of the word. This suggests a classification of infinite words in terms of the "difference" between the set of its patterns and the set of its factors. The fact that each factor in an infinite word can give rise to several distinct patterns leads to study the set of patterns of a single finite word. This set, endowed with a natural order relation, defines a poset: we investigate the relationships between the structure of such a poset and the combinatorial properties of the word. Finally we show that the set of patterns of the words in a regular language is a regular language too.

yearjournalcountryeditionlanguage
2002-01-01
https://doi.org/10.1007/3-540-46011-x_9