Arrow Research search

Author name cluster

Jean-Éric Pin

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.

10 papers
1 author row

Possible papers

10

TCS Journal 2025 Journal Article

Euclidean division by d in base b

  • Jean-Éric Pin

Let b ⩾ 2 be an integer. For each positive integer d, let E d, b be the Euclidean division by d in base b, that is, the function which associates to a word u in { 0, …, b − 1 } ⁎, representing an integer n in base b, the unique word of the same length as u representing the quotient of the division of n by d. We describe the pure sequential transducer realizing this function and analyze the algebraic structure of its syntactic monoid. We compute its size, describe its Green's relations and its minimum ideal. As a consequence, we show that it is a group if and only if d and b are coprime numbers, it is a p-group if and only if d is a power of p and b is congruent to 1 modulo p and it is an aperiodic monoid if and only if d divides some power of b. The uniform continuity of E d, b for the pro-group metric was studied by Reutenauer and Schützenberger in 1995. We launch a similar study for the uniform continuity of E d, b with respect to the pro-p metric, where p is a prime number.

Details DOI

TCS Journal 2019 Journal Article

Languages and formations generated by D4 and Q8

  • Jean-Éric Pin
  • Xaro Soler-Escrivà

We describe the two classes of languages recognized by the groups D 4 and Q 8, respectively. Then we show that the formations of languages generated by these two classes are the same. We also prove that these two formations are closed under inverses of morphisms, which yields a language theoretic proof of the fact that the group formations generated by D 4 and Q 8, respectively, are two equal varieties.

Details DOI

TCS Journal 2017 Journal Article

On uniformly continuous functions for some profinite topologies

  • Jean-Éric Pin
  • Pedro V. Silva

Given a variety of finite monoids V, a subset of a monoid is a V-subset if its syntactic monoid belongs to V. A function between two monoids is V-preserving if it preserves V-subsets under preimages and it is hereditary V-preserving if it is W-preserving for every subvariety W of V. The aim of this paper is to study hereditary V-preserving functions when V is one of the following varieties of finite monoids: groups, p-groups, aperiodic monoids, commutative monoids and all monoids.

Details DOI

TCS Journal 2016 Journal Article

Ultrafilters on words for a fragment of logic

  • Mai Gehrke
  • Andreas Krebs
  • Jean-Éric Pin

We give a method for specifying ultrafilter equations and identify their projections on the set of profinite words. Let B be the set of languages captured by first-order sentences using unary predicates for each letter, arbitrary uniform unary numerical predicates and a predicate for the length of a word. We illustrate our methods by giving ultrafilter equations characterising B and then projecting these to obtain profinite equations characterising B ∩ Reg. This suffices to establish the decidability of the membership problem for B ∩ Reg.

Details DOI

I&C Journal 2013 Journal Article

Regular languages and partial commutations

  • Antonio Cano
  • Giovanna Guaiana
  • Jean-Éric Pin

The closure of a regular language under a [partial] commutation I has been extensively studied. We present new advances on two problems of this area: (1) When is the closure of a regular language under [partial] commutation still regular? (2) Are there any robust classes of languages closed under [partial] commutation? We show that the class Pol ( G ) of polynomials of group languages is closed under commutation, and under partial commutation when the complement of I in A 2 is a transitive relation. We also give a sufficient graph theoretic condition on I to ensure that the closure of a language of Pol ( G ) under I-commutation is regular. We exhibit a very robust class of languages W which is closed under commutation. This class contains Pol ( G ), is decidable and can be defined as the largest positive variety of languages not containing ( a b ) ⁎. It is also closed under intersection, union, shuffle, concatenation, quotients, length-decreasing morphisms and inverses of morphisms. If I is transitive, we show that the closure of a language of W under I-commutation is regular. The proofs are nontrivial and combine several advanced techniques, including combinatorial Ramsey type arguments, algebraic properties of the syntactic monoid, finiteness conditions on semigroups and properties of insertion systems.

Details DOI

I&C Journal 2010 Journal Article

The expressive power of the shuffle product

  • Jean Berstel
  • Luc Boasson
  • Olivier Carton
  • Jean-Éric Pin
  • Antonio Restivo

There is an increasing interest in the shuffle product on formal languages, mainly because it is a standard tool for modeling process algebras. It still remains a mysterious operation on regular languages. Antonio Restivo proposed as a challenge to characterize the smallest class of languages containing the singletons and closed under Boolean operations, product and shuffle. This problem is still widely open, but we present some partial results on it. We also study some other smaller classes, including the smallest class containing the languages composed of a single word of length 2 which is closed under Boolean operations and shuffle by a letter (resp. shuffle by a letter and by the star of a letter). The proof techniques have both an algebraic and a combinatorial flavor.

Details DOI

TCS Journal 2006 Journal Article

Actions, wreath products of C -varieties and concatenation product

  • Laura Chaubard
  • Jean-Éric Pin
  • Howard Straubing

The framework of C -varieties, introduced by the third author, extends the scope of Eilenberg's variety theory to new classes of languages. In this paper, we first define C -varieties of actions, which are closely related to automata, and prove their equivalence with the original definition of C -varieties of stamps. Next, we complete the study of the wreath product initiated by Ésik and Ito by extending its definition to C -varieties in two different ways, which are proved to be equivalent. We also state an extension of the wreath product principle, a standard tool of language theory. Finally, our main result generalizes to C -varieties the algebraic characterization of the closure under product of a variety of languages.

Details DOI

TCS Journal 2005 Journal Article

A topological approach to transductions

  • Jean-Éric Pin
  • Pedro V. Silva

This paper is a contribution to the mathematical foundations of the theory of automata. We give a topological characterization of the transductions τ from a monoid M into a monoid N, such that if R is a recognizable subset of N, τ - 1 ( R ) is a recognizable subset of M. We impose two conditions on the monoids, which are fullfilled in all cases of practical interest: the monoids must be residually finite and, for every positive integer n, must have only finitely many congruences of index n. Our solution proceeds in two steps. First we show that such a monoid, equipped with the so-called Hall distance, is a metric space whose completion is compact. Next we prove that τ can be lifted to a map τ ^ from M into the set of compact subsets of the completion of N. This latter set, equipped with the Hausdorff metric, is again a compact monoid. Finally, our main result states that τ - 1 preserves recognizable sets if and only if τ ^ is continuous.

Details DOI

TCS Journal 2004 Journal Article

Shuffle on positive varieties of languages

  • Antonio Cano Gómez
  • Jean-Éric Pin

We show there is a unique maximal positive variety of languages which does not contain the language (ab)∗. This variety is the unique maximal positive variety satisfying the two following conditions: it is strictly included in the class of rational languages and is closed under the shuffle operation. It is also the largest proper positive variety closed under length preserving morphisms. The ordered monoids of the corresponding variety of ordered monoids are characterized as follows: for every pair (a, b) of mutually inverse elements, and for every element z of the minimal ideal of the submonoid generated by a and b, (abzab) ω ⩽ab. In particular this variety is decidable.

Details DOI