Author name cluster

Carla Selmi

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.

5 papers

1 author row

TCS Journal 2025 Journal Article

Tiling of toroidal arrays with pictures: Uniqueness, shift-equivalence and undecidability

Marcella Anselmo
Matteo Cavallaro
Maria Madonia
Carla Selmi

A toroidal array is a two-dimensional (2D) array of symbols in a finite alphabet where opposite sides are coincident. Alternatively, it can be figured out as a picture wrapped around a torus. Toroidal codes are finite sets of pictures which can tile any toroidal array in at most one unique way. They are the 2D counterpart of circular codes of strings. On the other hand, shift-invariant toroidal codes of pictures form a larger family of codes; here, two tilings of the same toroidal array are viewed as a single tiling when one is obtained by a shift of the other one. We prove that it is undecidable whether a finite set of pictures is a toroidal or a shift-invariant toroidal code. The problem becomes polynomially decidable for sets of cardinality one, using a combinatorial characterization of such sets. In analogy to the string case, toroidal and shift-invariant toroidal codes are investigated referring to conjugate, self-conjugate and self-covering pictures.

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 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 1996 Journal Article

Over testable languages

Carla Selmi

In this paper we give a combinatorial description of the languages that are both locally and piecewise testable. We call such languages over testable. The locally testable semigroups were discovered in the study of finite automata. The definition of locally testable semigroup is similar to that of locally testable language. If we consider words over the alphabet which is the set of all elements of a semigroup S, then such a word determines an element of S: the product of the letters of the word. A semigroup S is locally testable if whenever two words over the alphabet S have the same factors of a fixed length k and the same prefix and suffix of length k − 1, then the products of the letters of these words are equal. A natural extension of locally testable semigroups is obtained by dropping the condition about the prefix and suffix. We call such semigroups strongly locally testable. We prove in this paper that the family of strongly locally testable semigroups is exactly the intersection of the variety of locally idempotent and commutative semigroups and that of J -trivial semigroups. In particular, a language is over testable if and only if its syntactic semigroup is strongly locally testable. We use this algebraic characterization to derive a simple family of generators for the variety of over testable languages.

Details DOI