3 citations · 9 across the 16 of their papers we have counts for
20 papers
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…
Finding lower bounds on the growth and entropy of subshifts over countable groups
Matthieu Rosenfeld
We give a lower bound on the growth of a subshift based on a simple condition on the set of forbidden patterns defining that subshift. Aubrun et Al. showed a similar result based o…
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…
Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters
Matthieu Rosenfeld
We consider two games between two players Ann and Ben who build a word together by adding alternatively a letter at the end of the shared word. In the nonrepetitive game, Ben wins…
Avoiding large squares in trees and planar graphs
Daniel Gonçalves, Pascal Ochem, Matthieu Rosenfeld
The Thue number of a graph is the minimum number of colors needed to color without creating a square on a path of . For a graph class , is the supremum…
Avoiding squares over words with lists of size three amongst four symbols
Matthieu Rosenfeld
In 2007, Grytczuk conjecture that for any sequence of alphabets of size there exists a square-free infinite word such that for all , the -th letter…
Avoiding Square-Free Words on Free Groups
Golnaz Badkobeh, Tero Harju, Pascal Ochem +1
We consider sets of factors that can be avoided in square-free words on two-generator free groups. The elements of the group are presented in terms of 0,1,2,3 such that 0 and 2 (re…
Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge
Matthieu Rosenfeld
We show that for every graph and every graph obtained by subdividing each edge of at least , is nonrepetitively 3-colorable. In fact, we show that $…
Robust Secure UAV Communications with the Aid of Reconfigurable Intelligent Surfaces
Li Sixian, Duo Bin, Marco Di Renzo +2
This paper investigates a novel unmanned aerial vehicles (UAVs) secure communication system with the assistance of reconfigurable intelligent surfaces (RISs), where an UAV and a gr…
Another approach to non-repetitive colorings of graphs of bounded degree
Matthieu Rosenfeld
We propose a new proof technique that aims to be applied to the same problems as the Lovász Local Lemma or the entropy-compression method. We present this approach in the context o…
Nice formulas, -formulas, and palindrome patterns
Pascal Ochem, Matthieu Rosenfeld
We characterize the formulas that are avoided by every -free word for some . We study the avoidability index of formulas whose fragments are of the form . The largest…
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…
On the binomial equivalence classes of finite words
Marie Lejeune, Michel Rigo, Matthieu Rosenfeld
Two finite words and are -binomially equivalent if, for each word of length at most , appears the same number of times as a subsequence (i.e., as a scattered…
Bounding the number of -dominating sets in trees, forests and graphs of bounded pathwidth
Matthieu Rosenfeld
The notion of -dominating set generalizes many notions including dominating set, induced matching, perfect codes or independent sets. Bounds on the maximal number of such (m…
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…
Avoiding two consecutive blocks of same size and same sum over
Michaël Rao, Matthieu Rosenfeld
A long standing question asks whether is uniformly 2-repetitive [Justin 1972, Pirillo and Varricchio, 1994], that is, whether there is an infinite sequence over a fini…
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…