3 citations · 9 across the 16 of their papers we have counts for
8 papers · 1 filter
Reconstructing words using queries on subwords or factors
Gwenaël Richomme, Matthieu Rosenfeld
We study word reconstruction problems. Improving a previous result by P. Fleischmann, M. Lejeune, F. Manea, D. Nowotka and M. Rigo, we prove that, for any unknown word of lengt…
It is undecidable whether the growth rate of a given bilinear system is 1
Matthieu Rosenfeld
We show that there exists no algorithm that decides for any bilinear system if the growth rate of is . This answers a question of Bui who showed that if the coef…
The growth rate over trees of any family of set defined by a monadic second order formula is semi-computable
Matthieu Rosenfeld
Monadic second order logic can be used to express many classical notions of sets of vertices of a graph as for instance: dominating sets, induced matchings, perfect codes, independ…
How far away must forced letters be so that squares are still avoidable?
Matthieu Rosenfeld
We describe a new non-constructive technique to show that squares are avoidable by an infinite word even if we force some letters from the alphabet to appear at certain occurrences…
Bisplit graphs satisfy the Chen-Chvátal conjecture
Laurent Beaudou, Giacomo Kahn, Matthieu Rosenfeld
In this paper, we give a lengthy proof of a small result! A graph is bisplit if its vertex set can be partitioned into three stable sets with two of them inducing a complete bipart…
On some interesting ternary formulas
Pascal Ochem, Matthieu Rosenfeld
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 (…
Avoidability of formulas with two variables
Pascal Ochem, Matthieu Rosenfeld
In combinatorics on words, a word over an alphabet is said to avoid a pattern over an alphabet of variables if there is no factor of such that wher…
Avoidability of long -abelian repetitions
Michaël Rao, Matthieu Rosenfeld
We study the avoidability of long -abelian-squares and -abelian-cubes on binary and ternary alphabets. For , these are Mäkelä's questions. We show that one cannot avoid…