Logo image
Se connecter
On Some Interesting Ternary Formulas
Acte de colloque

On Some Interesting Ternary Formulas

Pascal Ochem et Matthieu Rosenfeld
LNCS, Vol.10432, pp.30-35
LNCS
WORDS 2017 - 11th International Conference on Combinatorics on Words (Montreal, Canada, 11/09/2017–15/09/2017)
15/08/2017

Résumé

Combinatorics on words Pattern avoidance
We show that, up to renaming of the letters, the only infinite ternary words avoiding the formula ABCAB.ABCBA.ACB.BAC (resp. ABCA.BCAB.BCB.CBA) have the same set of recurrent factors as the fixed point of $0->012,1->02,2->1$Also, we show that the formula ABAC.BACA.ABCA is 2-avoidable. Finally, we show that the pattern ABACADABCA is unavoidable for the class of $C_4$-minor-free graphs with maximum degree 3. This disproves a conjecture of Grytczuk.

Fichiers et liens (1)

url
Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Logo image