Charles Paperman
Mail: charles.paperman<arobase>liafa<dot>univ-paris-diderot<dot>fr
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.