Arrow Research search

Author name cluster

Jean Néraud

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.

11 papers
2 author rows

Possible papers

11

TCS Journal 2023 Journal Article

Loopless algorithms to generate maximum length gray cycles wrt. k-character substitutions

  • Jean Néraud

Given a binary word relation τ onto A ⁎ and a finite language X ⊆ A ⁎, a τ-Gray cycle over X consists in a permutation ( w [ i ] ) 0 ≤ i ≤ | X | − 1 of X such that each word w [ i ] is an image under τ of the previous word w [ i − 1 ]. We define the complexity measure λ A, τ ( n ), equal to the largest cardinality of a language X having words of length at most n, and st. some τ-Gray cycle over X exists. The present paper is concerned with τ = σ k, the so-called k-character substitution, st. ( u, v ) ∈ σ k holds if, and only if, the Hamming distance of u and v is k. We present loopless (resp. , constant amortized time) algorithms for computing specific maximum length σ k -Gray cycles.

Details DOI

I&C Journal 2023 Journal Article

Topologies for error-detecting variable-length codes

  • Jean Néraud

Given a finite alphabet A and a quasi-metric d over A ⁎, we introduce the relation τ d, k ⊆ A ⁎ × A ⁎ such that ( x, y ) ∈ τ d, k holds whenever d ( x, y ) ≤ k. The error detection capability of variable-length codes is expressed in term of conditions over τ d, k. With respect to the prefix metric, the factor one, and any quasi-metric associated with some free monoid (anti-)automorphism, we prove that one can decide whether a given regular variable-length code satisfies any of those error detection constraints.

Details DOI

I&C Journal 2022 Journal Article

Variable-length codes independent or closed with respect to edit relations

  • Jean Néraud

We investigate inference of variable-length codes in other domains of computer science, such as noisy information transmission or information retrieval-storage: in such topics, traditionally mostly constant-length codewords act. The study is relied upon the two concepts of independent and closed sets: given an alphabet A and a binary relation τ ⊆ A ⁎ × A ⁎, a set X ⊆ A ⁎ is τ-independent if τ ( X ) ∩ X = ∅; X is τ-closed if τ ( X ) ⊆ X. We focus to those word relations whose images are computed by applying some peculiar combinations of deletion, insertion, or substitution. In particular, characterizations of variable-length codes that are maximal in the families of τ-independent or τ-closed codes are provided.

Details DOI

TCS Journal 2020 Journal Article

Embedding a θ-invariant code into a complete one

  • Jean Néraud
  • Carla Selmi

Let A be an arbitrary alphabet and let θ be an (anti-)automorphism of A ⁎ (by definition, such a correspondence is determinated by a permutation of the alphabet). This paper deals with sets which are invariant under θ (θ-invariant for short) that is, languages L satisfying θ ( L ) ⊆ L. We establish an extension of the famous defect theorem. With regard to the so-called notion of completeness, we provide a series of examples of finite complete θ-invariant codes. Moreover, we establish a formula which allows to embed any non-complete θ-invariant code into a complete one. As a consequence, in the family of the so-called thin θ-invariant codes, maximality and completeness are two equivalent notions.

Details DOI

TCS Journal 2008 Journal Article

Completing circular codes in regular submonoids

  • Jean Néraud

Let M be an arbitrary submonoid of the free monoid A ∗, and let X ⊆ M be a variable length code (for short a code). X is weakly M -complete iff any word in M is a factor of some word in X ∗ [J. Néraud, C. Selmi, Free monoid theory: Maximality and completeness in arbitrary submonoids, Internat. J. Algebra Comput. 13 (5) (2003) 507–516]. Given a regular submonoid M, and given an arbitrary code X ⊆ M, we are interested in the existence of a weakly M -complete code X ˆ that contains X. Actually, in [J. Néraud, Completing a code in a regular submonoid, in: Acts of MCU’2004, Lect. Notes Comput. Sci. 3354 (2005) 281–291; J. Néraud, Completing a code in a submonoid of finite rank, Fund. Inform. 74 (2006) 549–562], by presenting a general formula, we have established that, in any case, such a code X ˆ exists. In the present paper, we prove that any regular circular code X ⊆ M may be embedded into a weakly M -complete one iff the minimal automaton with behavior M has a synchronizing word. As a consequence of our result an extension of the famous theorem of Schützenberger is stated for regular circular codes in the framework of regular submonoids. We study also the behaviour of the subclass of uniformly synchronous codes in connection with these questions.

Details DOI

TCS Journal 2006 Journal Article

Completing prefix codes in submonoids

  • Jean Néraud

Let M be a submonoid of the free monoid A *, and let X ⊆ M be a variable length code (for short a code). X is weakly M-complete if any word in M is a factor of some word in X * [J. Néraud, C. Selmi, Free monoid theory: maximality and completeness in arbitrary submonoids, Internat. J. Algorithms Comput. 13(5) (2003) 507–516]. Given a code X ⊆ M, we are interested in the construction of a weakly M-complete code that contains X, if it exists. In the case where M and X are regular sets, the existence of such a code has been established [J. Néraud, Completing a code in a regular submonoid of the free monoid, in acts of MCU’2004, Lecture Notes in Computer Sciences, Vol. 3354, Springer, Berlin, 2005, pp. 281–291; J. Néraud, On the completion of codes in submonoids with finite rank, Fund. Inform. , to appear]. Actually, this result lays upon a method of construction that preserves the regularity of sets. As well known, any regular (or finite) code may be embedded into a regular (finite) prefix code that is complete in A *. In the framework of the weak completeness, we prove that the following problem is decidable: Instance: A regular submonoid M of A *, and a regular (or finite) prefix code X ⊆ M. Question: Does a weakly M-complete regular (finite) prefix code containing X exist?

Details DOI

TCS Journal 2002 Journal Article

Locally complete sets and finite decomposable codes

  • Jean Néraud
  • Carla Selmi

We are interested in the concept of locally complete set: A subset X of the free monoid is locally complete if a code Y⊂A∗ exists, with Y≠A, X∗⊂Y∗, and such that both the sets X∗ and Y∗ have the same sets of factors. Our contribution is based on the three following results: • A characterization of local completeness for very thin sets in terms of morphic images. • A polynomial time algorithm for deciding whether a finite code is locally complete. • A polynomial time algorithm for deciding whether a finite maximal code is decomposable.

Details DOI

TCS Journal 2001 Journal Article

On codes with a finite deciphering delay: constructing uncompletable words

  • Jean Néraud
  • Carla Selmi

Let X be a non-complete code with a finite deciphering delay. We prove that an uncompletable word w of length O(m2d2) exists, where d stands for the delay and m stands for the length of the longest words in X. The proof leads to an explicit construction of w. This result partially resolves a conjecture proposed by Antonio Restivo in 1979.

Details DOI

TCS Journal 1993 Journal Article

Deciding whether a finite set of words has rank at most two

  • Jean Néraud

Given a finite subset X of a free monoid A∗, we define the rank of X as r(X = min {; ∣Y∣: X ⊆ Y∗}; . The problem we study here is to decide whether or not r(X)⩽2. We propose an O(nln2 m) algorithm, where n stands for the sum of the lenghts of the words in X, and m stands for the length of the longest word.

Details DOI

MFCS Conference 1993 Conference Paper

New Algorithms for Detecting Morphic Images of a Word

  • Jean Néraud

Abstract We present efficient algorithms for two subcases of the general NP-complete problem [An 80] which consists in matching patterns with variables: matching an arbitrary one-variable pattern with constants matching a two-variable pattern

Details
v2026.09.13