Zobrazeno 1 - 10
of 261
pro vyhledávání: '"Ochem, Pascal"'
Autor:
Badkobeh, Golnaz, Ochem, Pascal
An interesting phenomenon in combinatorics on words is when every recurrent word satisfying some avoidance constraints has the same factor set as a morphic word. An early example is the Hall-Thue word, fixed point of the morphism $\texttt{0}\to\textt
Externí odkaz:
http://arxiv.org/abs/2312.10757
We study infinite binary words that contain few distinct palindromes. In particular, we classify such words according to their critical exponents. This extends results by Fici and Zamboni [TCS 2013]. Interestingly, the words with 18 and 20 palindrome
Externí odkaz:
http://arxiv.org/abs/2311.13003
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 25:3 special issue ICGT'22, Special issues (May 17, 2024) dmtcs:10805
This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these graphs have arbitrary large chromatic number, while being triangle-free.
Externí odkaz:
http://arxiv.org/abs/2301.03865
Autor:
Currie, James, Dvořaková, L'ubomíra, Ochem, Pascal, Opočenská, Daniela, Rampersad, Narad, Shallit, Jeffrey
The complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. We study infinite binary words $\bf w$ that avoid sufficiently large complementary factors; that is, if $x$ is a factor of $\bf w$ then
Externí odkaz:
http://arxiv.org/abs/2209.09598
Autor:
Baranwal, Aseem, Currie, James, Mol, Lucas, Ochem, Pascal, Rampersad, Narad, Shallit, Jeffrey
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 25:2, Combinatorics (September 6, 2023) dmtcs:10063
The (bitwise) complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. An $\textit{antisquare}$ is a nonempty word of the form $x\, \overline{x}$. In this paper, we study infinite binary words that
Externí odkaz:
http://arxiv.org/abs/2209.09223
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 25:2, Automata, Logic and Semantics (October 16, 2023) dmtcs:9919
We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manne
Externí odkaz:
http://arxiv.org/abs/2207.10171
We study the properties of the ternary infinite word p = 012102101021012101021012 ... , that is, the fixed point of the map h:0->01, 1->21, 2->0. We determine its factor complexity, critical exponent, and prove that it is 2-balanced. We compute its a
Externí odkaz:
http://arxiv.org/abs/2206.01776
The Thue number $\pi(G)$ of a graph $G$ is the minimum number of colors needed to color $G$ without creating a square on a path of $G$. For a graph class $C$, $\pi(C)$ is the supremum of $\pi(G)$ over the graphs $G\in C$. The Thue number has been inv
Externí odkaz:
http://arxiv.org/abs/2106.01521
Autor:
Domenech, Antoine, Ochem, Pascal
In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is said to avoid a pattern $p$ over an alphabet $\Delta$ if there is no factor $f$ of $w$ such that $f=h(p)$ where $h:\Delta^*\to\Sigma^*$ is a non-erasing morphism. A pattern $p$ is sai
Externí odkaz:
http://arxiv.org/abs/2105.04673
Autor:
Brause, Christoph, Golovach, Petr, Martin, Barnaby, Ochem, Pascal, Paulusma, Daniël, Smith, Siani
We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively
Externí odkaz:
http://arxiv.org/abs/2104.10593