Author name cluster

Charles Paperman

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.

8 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 2018 Journal Article

Classes of languages generated by the Kleene star of a word

Laure Daviaud
Charles Paperman

In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form u ⁎, where u is a word. We provide effective equational characterisations of these classes, i. e. one can decide using our descriptions whether a given regular language belongs or not to each of them.

Details DOI

Highlights Conference 2016 Conference Abstract

Continuity: a study of transduction composability

Olivier Carton
Charles Paperman

A function is continuous for a class of languages V if its inverse maps elements of V back to V. Semantically, this means that if we are provided a circuit for a language L in V, then putting the function at the input level results in a language that is still in V. This notion has been used with different values of V to characterize the transductions computable in classes of low complexity. Here, we report on problems focusing only on this notion over transductions; we provide decidability properties and characterize continuity through some natural algebraic properties. Unpublished joint work with Olivier Carton and Charles Paperman.

Details

Highlights Conference 2016 Conference Abstract

Schema validation via streaming circuits

Charles Paperman

XML schema validation can be performed in constant memory in the streaming model if and only if the schema admits only trees of bounded depth—an acceptable assumption from the practical view-point. In this talk I will present a refinement of the streaming model that take into account that data can be streamed block-by-block, rather then letter-by-letter. Therefore, it provides opportunities to speed up the computation by parallelizing the processing of each block. For this purpose I will introduce a new fine-grained parallel model of computation: the *streaming circuits*. This model process words of arbitrary length in blocks of fixed size, passing constant amount of information between blocks. It allows us to transfer fundamental results about the circuit complexity of regular languages to the setting of streaming schema validation, which leads to effective constructions of streaming circuits of depth logarithmic in the block size, or even constant under certain assumptions on the input schema.

Details

CSL Conference 2015 Conference Paper

Finite-Degree Predicates and Two-Variable First-Order Logic

Charles Paperman

We consider two-variable first-order logic on finite words with a fixed number of quantifier alternations. We show that all languages with a neutral letter definable using the order and finite-degree predicates are also definable with the order predicate only. From this result we derive the separation of the alternation hierarchy of two-variable logic on this signature. Replacing finite-degree by arbitrary numerical predicates in the statement would entail a long standing conjecture on the circuit complexity of the addition function. Thus, this result can be viewed as a uniform version of this circuit lower bound.

Details

Highlights Conference 2015 Conference Abstract

Finite-Degree Predicates and Two-Variable First-Order Logic

Charles Paperman

In this talk, I will resent two new results about the expressivity of two-variable first-order logic over finite words equipped with arbitrary numerical predicates. This fragment of logic is equivalent to languages recognized by linear size and constant depth boolean circuit. I will focus on the so-called Crane Beach conjecture for FO^2. Proving the Crane Beach conjecture in this context would improve on a known lower bound for addition, stating that the function of addition is not computable by circuits of constant depth with a linear number of wires. First we will explain how languages with a neutral letter definable in two-variable logic with arbitrary numerical predicates can be defined using only the linear order and the following predicates: •The class F of finite-degree predicates, that is, binary predicates that are relations over integers and such that each vertex of their underlying infinite directed graph has a finite degree. •A predicate called MSB0, true of positions x and y if the binary decomposition of y is obtained by zeroing the most significant bit of x. Then, a Crane Beach result will be presented for the restricted signature containing < and F predicates. Thus, this a result which is one predicate shy from showing the Crane Beach conjecture for FO^2.

Details

Highlights Conference 2014 Conference Abstract

Adding Modular Predicates

Charles Paperman

The decision problem for a given class of regular languages consists in deciding, given a regular language, whether or not it belongs to this class. Solving the decision problem for various fragments of monadic second order is a well-studied problem on regular languages. Fragments of logic are usually defined in terms of their quantifier complexity (Σ n -classes) or number of variables allowed in the formulae. Another possible parameter is to impose restrictions on the numerical predicates in the signature. There are essentially three basic groups of such predicates: the linear order, the local predicates LOC and the modular predicates MOD. In this talk, we will presents generic algorithmic procedure for the enrichement of a fragment by modular predicates, depending on algebraic assumptions on the initial fragment.

PDF Details

Highlights Conference 2013 Conference Abstract

On properties of logical sentences with arbitrary monadic predicates

Nathanaël Fijalkow
Charles Paperman

In this talk, we introduce two properties for logical sentences using arbitrary numerical predicates: the Straubing property and the Crane Beach property. Both properties state that formulae defining simple languages do not need to use arbitrary complicated predicates, where simple either means regular or with a neutral letter. We restrict our attention to monadic predicates, and show that both properties hold in a strong syntactical sense. 11: 12 11: 36 Coffee break

PDF Details