Charles Paperman

Mail: charles.paperman<arobase>liafa<dot>univ-paris-diderot<dot>fr

Phone: + 33 6 24 34 08 79

Phone: + 33 6 24 34 08 79

Regular Separability of Parikh Automata.
L. Clemente, W. CzerwiĹ„ski, S. Lasota, C. Paperman, ICALP 2017

Abstract:
We investigate a subclass of languages recognized by vector
addition systems, namely languages of nondeterministic Parikh automata.
While the regularity problem (is the language of a given automaton
regular?) is undecidable for this model, we show surprising decidability
of the regular separability problem: given two Parikh automata,
is there a regular language that contains one of them and is disjoint from
the other?

Continuity and Rational Functions.
M. Cadilhac, O. Carton, C. Paperman, ICALP 2017

Abstract:
A word-to-word function is continuous for a class of languages V if its inverse maps V-languages
to V. This notion provides a basis for an algebraic study of transducers, and was integral to the
characterization of the sequential transducers computable in some circuit complexity classes.
Here, we report on the decidability of continuity for functional transducers and some standard
classes of regular languages. Previous algebraic studies of transducers have focused on the
structure of the underlying input automaton, disregarding the output. We propose a comparison
of the two algebraic approaches through two questions: When are the automaton structure and
the continuity properties related, and when does continuity propagate to superclasses?

Crevice on the Crane Beach: Finite-Degree Predicates.
M. Cadilhac, C. Paperman, LICS 2017

Abstract:
First-order logic (FO) over words is shown to be equiexpressive with FO equipped with a restricted set of numerical predicates, namely the order, a binary predicate MSB0, and the finite-degree predicates: FO[Arb] = FO[<, MSB0, Fin].
The Crane Beach Property (CBP), introduced more than a decade ago, is true of a logic if all the expressible languages admitting a neutral letter are regular.
Although it is known that FO[Arb] does not have the CBP, it is shown here that the (strong form of the) CBP holds for both FO[<, Fin] and FO[<, MSB0]. Thus FO[<, Fin] exhibits a form of locality and the CBP, and can still express a wide variety of languages, while being one simple predicate away from the expressive power of FO[Arb]. The counting ability of FO[<, Fin] is studied as an application.

Separability of Reachability Sets of Vector Addition Systems.
L. Clemente, W. CzerwiĹ„ski, S. Lasota, C. Paperman, STACS 2017

Abstract:
Given two families of sets F and G, the F separability problem
for G asks whether for two given sets U, V in G there exists a set
S in F, such that U is included in S and V is disjoint with S. We consider
two families of sets F: modular sets S subset of N^d
defined as unions of
equivalence classes modulo some natural number n in N, and unary sets.
Our main result is decidability of modular and unary separability for
the class G of reachability sets of Vector Addition Systems, Petri Nets,
Vector Addition Systems with States, and for sections thereof.

Schema validation via streaming circuits.
F. Murlak, C. Paperman and M. Pilipczuk, PODS 2016

Abstract:
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---a mild assumption from the practical view-point.

Finite-Degree Predicates and Two-Variable First-Order Logic.
C. Paperman, CSL 2015

Abstract:
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.

A Circuit Complexity Approach to Transductions.
M. Cadilhac, A. Krebs, M. Ludwig, and C. Paperman, MFCS 2015

Abstract:
Low circuit complexity classes and regular languages exhibit
very tight interactions that shade light on their respective expressiveness.
We propose to study these interactions at a functional level, by investi-
gating the deterministic rational transductions computable by constant-
depth, polysize circuits. To this end, a circuit framework of independent
interest that allows variable output length is introduced. Relying on it,
there is a general characterization of the set of transductions realizable
by circuits. It is then decidable whether a transduction is definable in
AC0 and, assuming a well-established conjecture, the same for ACC0.

Alternation Hierarchies of First Order Logic
with Regular Predicates.
L. Dartois and C. Paperman, FCT 2015

Abstract:
We investigate the decidability of the definability problem
for fragments of first order logic over finite words enriched with regular
numerical predicates. In this paper, we focus on the quantifier alternation
hierarchies of first order logic. We obtain that deciding this problem for
each level of the alternation hierarchy of both first order logic and its two-
variable fragment when equipped with all regular numerical predicates
is not harder than deciding it for the corresponding level equipped with
only the linear order.
Relying on some recent results, this proves the decidability for each level
of the alternation hierarchy of the two-variable first order fragment while
in the case of the first order logic the question remains open for levels
greater than two.

Classes of languages generated by the Kleene star of a word.
L. Daviaud and C. Paperman, MFCS 2015

Abstract:
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.

Monadic Second-Order Logic with Arbitrary Monadic Predicates.
N. Fijalkow and C. Paperman, MFCS 2014

Abstract:
We study Monadic Second-Order Logic (MSO) over finite words, extended with (non-uniform arbitrary) monadic predicates. We show that it defines a class of languages that has algebraic, automata-theoretic and machine-independent characterizations. We consider the regularity question: given a language in this class, when is it regular? To answer this, we show a substitution property and the existence of a syntactical predicate.
We give three applications. The first two are to give simple proofs of the Straubing and Crane Beach Conjectures for monadic predicates, and the third is to show that it is decidable whether a language defined by an MSO formula with morphic predicates is regular.

Two-variable first order logic with modular predicates over words. L. Dartois and C. Paperman,
STACS 2013

Abstract:
We consider first order formulae over the signature consisting of the symbols of the
alphabet, the symbol < (interpreted as a linear order) and the set MOD of modular numerical predicates. We study the expressive
power of FO^2[<,MOD], the two-variable first order logic over this signature, interpreted over finite words.
We give an algebraic characterization of the corresponding regular languages in terms of their syntactic morphisms and we also give simple unambiguous regular expressions for them.
It follows that one can decide whether a given regular language is captured by
FO^2[<,MOD]. Our proofs rely on a combination of arguments from semigroup theory (stamps),
model theory and combinatorics.