Source author record

Gwenaël Richomme

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Formal Languages and Automata Theory

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

preprint2016arXiv

Avoidability of circular formulas

Clark has defined the notion of $n$ -avoidance basis which contains the avoidable formulas with at most $n$ variables that are closest to be unavoidable in some sense. The family $C_i$ of circular formulas is such that $C_1=AA$ , $C_2=ABA.BAB$ , $C_3=ABCA.BCAB.CABC$ and so on. For every $i\le n$ , the $n$ -avoidance basis contains $C_i$ . Clark showed that the avoidability index of every circular formula and of every formula in the $3$ -avoidance basis (and thus of every avoidable formula containing at most 3 variables) is at most 4. We determine exactly the avoidability index of these formulas.

preprint2016arXiv

Greedy palindromic lengths

In [A. Frid, S. Puzynina, L.Q. Zamboni, \textit{On palindromic factorization of words}, Adv. in Appl. Math. 50 (2013), 737-748], it was conjectured that any infinite word whose palindromic lengths of factors are bounded is ultimately periodic. We introduce variants of this conjecture and prove this conjecture in particular cases. Especially we introduce left and right greedy palindromic lengths. These lengths are always greater than or equals to the initial palindromic length. When the greedy left (or right) palindromic lengths of prefixes of a word are bounded then this word is ultimately periodic.

preprint2016arXiv

Periodicity in Rectangular Arrays

We discuss several two-dimensional generalizations of the familiar Lyndon-Schutzenberger periodicity theorem for words. We consider the notion of primitive array (as one that cannot be expressed as the repetition of smaller arrays). We count the number of m x n arrays that are primitive. Finally, we show that one can test primitivity and compute the primitive root of an array in linear time.

preprint2015arXiv

Comparison of Coverability and Multi-Scale Coverability in One and Two Dimensions

A word is quasiperiodic (or coverable) if it can be covered with occurrences of another finite word, called its quasiperiod. A word is multi-scale quasiperiodic (or multi-scale coverable) if it has infinitely many different quasiperiods. These notions were previously studied in the domains of text algorithms and combinatorics of right infinite words. We extend them to infinite pictures (two-dimensional words). Then we compare the regularity properties (uniform recurrence, uniform frequencies, topological entropy) of quasiperiodicity with multi-scale quasiperiodicity, and we also compare each of them with its one-dimensional counterpart. We also study which properties of quasiperiods enforce properties on the quasiperiodic words.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Gwenaël Richomme

Research overview

Is this your work?

5 publications

Reconstructing words using queries on subwords or factors

Avoidability of circular formulas

Greedy palindromic lengths

Periodicity in Rectangular Arrays

Comparison of Coverability and Multi-Scale Coverability in One and Two Dimensions

See the researcher in context

Building this map preview