On Some Interesting Ternary Formulas
| Autor: | Matthieu Rosenfeld, Pascal Ochem |
|---|---|
| Přispěvatelé: | Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Srečko Brlek, Francesco Dolce, Christophe Reutenauer, Élise Vandomme, Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon), École normale supérieure de Lyon (ENS de Lyon) |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Applied Mathematics 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Fixed point [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Theoretical Computer Science Combinatorics Combinatorics on words Computational Theory and Mathematics 010201 computation theory & mathematics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Geometry and Topology Ternary operation ComputingMilieux_MISCELLANEOUS Computer Science - Discrete Mathematics Mathematics |
| Zdroj: | 11th International Conference on Combinatorics on Words WORDS WORDS, Sep 2017, Montreal, Canada. pp.30-35, ⟨10.1007/978-3-319-66396-8_4⟩ The Electronic Journal of Combinatorics The Electronic Journal of Combinatorics, Open Journal Systems, 2019, 26 (1), pp.P1.12. ⟨10.37236/7901⟩ Lecture Notes in Computer Science ISBN: 9783319663951 The Electronic Journal of Combinatorics, 2019, 26 (1), pp.P1.12. ⟨10.37236/7901⟩ |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/7901 |
| Popis: | We obtain the following results about the avoidance of ternary formulas. 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 $\texttt{0}\mapsto\texttt{012}$, $\texttt{1}\mapsto\texttt{02}$, $\texttt{2}\mapsto\texttt{1}$. The formula $ABAC.BACA.ABCA$ is avoided by polynomially many binary words and there exist arbitrarily many infinite binary words with different sets of recurrent factors that avoid it. If every variable of a ternary formula appears at least twice in the same fragment, then the formula is $3$-avoidable. The pattern $ABACADABCA$ is unavoidable for the class of $C_4$-minor-free graphs with maximum degree~$3$. This disproves a conjecture of Grytczuk. The formula $ABCA.ACBA$, or equivalently the palindromic pattern $ABCADACBA$, has avoidability index $4$. Comment: Version 1 was accepted to WORDS 2017. Version 2 contains new results in section 4 (about nice formulas) and section 6 (about palindromic patterns) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|