BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Matthieu Rosenfeld

Matthieu Rosenfeld contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete MathematicsFormal Languages and Automata Theory

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2023arXiv

Reconstructing words using queries on subwords or factors

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 $w$ of length $n$ over an alphabet of cardinality $k$, $w$ can be reconstructed from the number of occurrences as subwords (or scattered factors) of $O(k^2\sqrt{n\log_2(n)})$ words. Two previous upper bounds obtained by S. S. Skiena and G. Sundaram are also slightly improved: one when considering information on the existence of subwords instead of on the numbers of their occurrences, and, the other when considering information on the existence of factors.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

It is undecidable whether the growth rate of a given bilinear system is 1

We show that there exists no algorithm that decides for any bilinear system $(B,v)$ if the growth rate of $(B,v)$ is $1$. This answers a question of Bui who showed that if the coefficients are positive the growth rate is computable (i.e., there is an algorithm that outputs the sequence of digits of the growth rate of $(B,v)$). Our proof is based on a reduction of the computation of the joint spectral radius of a set of matrices to the computation of the growth rate of a bilinear system. We also use our reduction to deduce that there exists no algorithm that approximates the growth rate of a bilinear system with relative accuracy $\varepsilon$ in time polynomial in the size of the system and of $\varepsilon$. Our two results hold even if all the coefficients are nonnegative rationals.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge

We show that for every graph $G$ and every graph $H$ obtained by subdividing each edge of $G$ at least $O(\log |V(G)|)$, $H$ is nonrepetitively 3-colorable. In fact, we show that $O(\log π'(G))$ subdivisions per edge are enough, where $π'(G)$ is the nonrepetitive chromatic index of $G$. This answers a question of Wood and improves a similar result of Pezarski and Zmarz that stated the existence of at least one 3-colorable division with a linear number of subdivision vertices per edge.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Another approach to non-repetitive colorings of graphs of bounded degree

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 of non-repetitive colorings and we use it to improve upper-bounds relating different non-repetitive numbers to the maximal degree of a graph. It seems that there should be other interesting applications to the presented approach. In terms of upper-bound our approach seems to be as strong as entropy-compression, but the proofs are more elementary and shorter. The application we provide in this paper are upper bounds for graphs of maximal degree at most $Δ$: a minor improvement on the upper-bound of the non-repetitive number, a $4.25Δ+o(Δ)$ upper-bound on the weak total non-repetitive number and a $ Δ^2+\frac{3}{2^\frac{1}{3}}Δ^{\frac{5}{3}}+ o(Δ^{\frac{5}{3}})$ upper-bound on the total non-repetitive number of graphs. This last result implies the same upper-bound for the non-repetitive index of graphs, which improves the best known bound.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

How far away must forced letters be so that squares are still avoidable?

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. We show that as long as forced positions are at distance at least 19 (resp. 3, resp. 2) from each other then we can avoid squares over 3 letters (resp. 4 letters, resp. 6 or more letters). We can also deduce exponential lower bounds on the number of solutions. For our main Theorem to be applicable, we need to check the existence of some languages and we explain how to verify that they exist with a computer. We hope that this technique could be applied to other avoidability questions where the good approach seems to be non-constructive (e.g., the Thue-list coloring number of the infinite path).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the binomial equivalence classes of finite words

Two finite words $u$ and $v$ are $k$-binomially equivalent if, for each word $x$ of length at most $k$, $x$ appears the same number of times as a subsequence (i.e., as a scattered subword) of both $u$ and $v$. This notion generalizes abelian equivalence. In this paper, we study the equivalence classes induced by the $k$-binomial equivalence with a special focus on the cardinalities of the classes. We provide an algorithm generating the $2$-binomial equivalence class of a word. For $k \geq 2$ and alphabet of $3$ or more symbols, the language made of lexicographically least elements of every $k$-binomial equivalence class and the language of singletons, i.e., the words whose $k$-binomial equivalence class is restricted to a single element, are shown to be non context-free. As a consequence of our discussions, we also prove that the submonoid generated by the generators of the free nil-$2$ group on $m$ generators is isomorphic to the quotient of the free monoid $\{ 1, \ldots , m\}^{*}$ by the $2$-binomial equivalence.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The growth rate over trees of any family of set defined by a monadic second order formula is semi-computable

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, independent sets or irredundant sets. Bounds on the number of sets of any such family of sets are interesting from a combinatorial point of view and have algorithmic applications. Many such bounds on different families of sets over different classes of graphs are already provided in the literature. In particular, Rote recently showed that the number of minimal dominating sets in trees of order $n$ is at most $95^{\frac{n}{13}}$ and that this bound is asymptotically sharp up to a multiplicative constant. We build on his work to show that what he did for minimal dominating sets can be done for any family of sets definable by a monadic second order formula. We first show that, for any monadic second order formula over graphs that characterizes a given kind of subset of its vertices, the maximal number of such sets in a tree can be expressed as the \textit{growth rate of a bilinear system}. This mostly relies on well known links between monadic second order logic over trees and tree automata and basic tree automata manipulations. Then we show that this "growth rate" of a bilinear system can be approximated from above.We then use our implementation of this result to provide bounds on the number of independent dominating sets, total perfect dominating sets, induced matchings, maximal induced matchings, minimal perfect dominating sets, perfect codes and maximal irredundant sets on trees. We also solve a question from D. Y. Kang et al. regarding $r$-matchings and improve a bound from Górska and Skupień on the number of maximal matchings on trees. Remark that this approach is easily generalizable to graphs of bounded tree width or clique width (or any similar class of graphs where tree automata are meaningful).

0 citations0 reviewsNo code linkedOpen access