Avoiding squares and overlaps over the natural numbers
| Autor: | Mathieu Guay-Paquet, Jeffrey Shallit |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
FOS: Computer and information sciences
Formal Languages and Automata Theory (cs.FL) Computer Science - Formal Languages and Automata Theory Natural number 68R15 Infinite alphabet 0102 computer and information sciences 01 natural sciences Theoretical Computer Science Combinatorics Morphism Integer FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics 0101 mathematics Greedy algorithm Mathematics Discrete mathematics Combinatorics on words 010102 general mathematics Function (mathematics) Lexicographical order 010201 computation theory & mathematics Pattern avoidance Combinatorics (math.CO) Computer Science::Formal Languages and Automata Theory Word (computer architecture) |
| Zdroj: | Discrete Mathematics. 309:6245-6254 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2009.06.004 |
| Popis: | We consider avoiding squares and overlaps over the natural numbers, using a greedy algorithm that chooses the least possible integer at each step; the word generated is lexicographically least among all such infinite words. In the case of avoiding squares, the word is 01020103..., the familiar ruler function, and is generated by iterating a uniform morphism. The case of overlaps is more challenging. We give an explicitly-defined morphism phi : N* -> N* that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all h,k in N with h 16 pages, 2 tables |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect