Author name cluster

Corentin Barloy

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

MFCS Conference 2025 Conference Paper

Dynamic Membership for Regular Tree Languages

Antoine Amarilli
Corentin Barloy
Louis Jachiet
Charles Paperman

We study the dynamic membership problem for regular tree languages under relabeling updates: we fix an alphabet Σ and a regular tree language L over Σ (expressed, e. g. , as a tree automaton), we are given a tree T with labels in Σ, and we must maintain the information of whether the tree T belongs to L while handling relabeling updates that change the labels of individual nodes in T. Our first contribution is to show that this problem admits an O(log n / log log n) algorithm for any fixed regular tree language, improving over known O(log n) algorithms. This generalizes the known O(log n / log log n) upper bound over words, and it matches the lower bound of Ω(log n / log log n) from dynamic membership to some word languages and from the existential marked ancestor problem. Our second contribution is to introduce a class of regular languages, dubbed almost-commutative tree languages, and show that dynamic membership to such languages under relabeling updates can be decided in constant time per update. Almost-commutative languages generalize both commutative languages and finite languages: they are the analogue for trees of the ZG languages enjoying constant-time dynamic membership over words. Our main technical contribution is to show that this class is conditionally optimal when we assume that the alphabet features a neutral letter, i. e. , a letter that has no effect on membership to the language. More precisely, we show that any regular tree language with a neutral letter which is not almost-commutative cannot be maintained in constant time under the assumption that the prefix-U1 problem from [Antoine Amarilli et al. , 2021] also does not admit a constant-time algorithm.

Details

I&C Journal 2022 Journal Article

A robust class of linear recurrence sequences

Corentin Barloy
Nathanaël Fijalkow
Nathan Lhote
Filip Mazowiecki

We introduce a subclass of linear recurrence sequences which we call poly-rational sequences because they are denoted by rational expressions closed under sum and product. We show that this class is robust by giving several characterisations: polynomially ambiguous weighted automata, copyless cost-register automata, rational formal series, and linear recurrence sequences whose eigenvalues are roots of rational numbers.

Details DOI

Highlights Conference 2022 Conference Abstract

The Regular Languages of First-Order Logic with One Alternation

Corentin Barloy

The regular languages with a neutral letter expressible in first-order logic with one alternation are characterized. Specifically, it is shown that if an arbitrary Sigma_2 formula defines a regular language with a neutral letter, then there is an equivalent Sigma_2 formula that only uses the order predicate. This shows that the so-called Central Conjecture of Straubing holds for Sigma_2 over languages with a neutral letter, the first progress on the Conjecture in more than 20 years. To show the characterization, lower bounds against polynomial-size depth-3 Boolean circuits with constant top fan-in are developed. The heart of the combinatorial argument resides in studying how positions within a language are determined from one another, a technique of independent interest. This is joint work with Michaël Cadilhac, Charles Paperman and Thomas Zeume.

Details

Highlights Conference 2021 Conference Abstract

Stackless Processing of Streamed Trees

Corentin Barloy

Processing tree-structured data in the streaming model is a challenge: capturing regular properties of streamed trees by means of a stack is costly in memory, but falling back to finite-state automata drastically limits the computational power. We propose an intermediate stackless model based on register automata equipped with a single counter, used to maintain the current depth in the tree. We explore the power of this model to validate and query streamed trees. Our main result is an effective characterization of regular path queries (RPQs) that can be evaluated stacklessly-with and without registers. In particular, we confirm the conjectured characterization of tree languages defined by DTDs that are recognizable without registers, by Segoufin and Vianu (2002), in the special case of tree languages defined by means of an RPQ. This is joint work with Filip Murlak and Charles Paperman.

Details

CSL Conference 2020 Conference Paper

A Robust Class of Linear Recurrence Sequences

Corentin Barloy
Nathanaël Fijalkow
Nathan Lhote
Filip Mazowiecki

Details

Highlights Conference 2020 Conference Abstract

Multidimensional linear recursive sequences and universality of unambiguous register automata

Corentin Barloy

In this work, we study the universality problem for \emph{unambiguous register automata} (URA) over equality atoms without guessing. Register automata are a generalisation of finite automata over infinite alphabets (called atoms) with the possibility of storing input data values in registers and check them for equality. A register automaton is unambiguous if, for every input word, it has at most one accepting run. The universality problem asks whether a given automaton recognizes every data word. For this model, it is known that inclusion, equivalence and universality problems are equivalent. The universality problem for nondeterministic register automata is undecidable, by a result of Kaminski and Francez. In the special case of URA, it has recently been proven to be in 2EXPSPACE by Mottet and Quaas by analysing the infinite-state system obtained by determinising the automaton. We provide an alternative approach to this problem, which goes back in spirit to the seminal work of Stearns and Hunt on unambiguous finite automata. Namely, we propose to count the number of orbits of data words accepted by the automaton, for fixed word length and number of distinct data values appearing therein. We show that the orbit counting function of a URA is \emph{bidimensional linear recursive}, i. e. , it satisfies a system of bidimensional linear recursive equations with polynomial coefficients (linrec). In the prototypical case of the counting function of the universal language over equality atoms, one gets the equation

Details