Author name cluster

Maria Madonia

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

1 author row

TCS Journal 2025 Journal Article

Density of k-ary words with 0, 1, 2 - error overlaps

Marcella Anselmo
Manuela Flores
Maria Madonia

An overlap, or border, of a word is a prefix that is equal to the suffix of the same length. An overlap with q errors is a prefix which has distance q from the suffix of the same length; here, 0-error overlaps are classic ones. Unbordered, or bifix-free, words are a central notion in combinatorics on words and have a prominent role in many related areas, such as pattern matching or frame synchronization. On the other hand, words with 2-error overlaps arose as a characterization of isometric words, a notion recently introduced in the framework of hypercubes and their isometric subgraphs. This paper investigates the density of words with 0, 1, 2-error overlaps, where the words are taken over a generic k-ary alphabet, k ≥ 2, and the distance they refer to is the Hamming or the Lee distance. Estimates on the limit density values are provided and compared in the case of binary and quaternary alphabets.

Details DOI

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

On k-ary n-cubes and isometric words

Marcella Anselmo
Manuela Flores
Maria Madonia

The k-ary n-cubes are a generalization of the hypercubes to alphabets of cardinality k, with k ≥ 2. More precisely, a k-ary n-cube is a graph with k n vertices associated to the k-ary words of length n. Given a k-ary word f, the k-ary n-cube avoiding f is the subgraph obtained deleting those vertices which contain f as a factor. When such a subgraph is isometric to the cube, for any n ≥ 1, the word f is said isometric. A binary word f is isometric if and only if it is Ham-isometric, i. e. , for any pair of f-free binary words u and v, u can be transformed in v by complementing the bits on which they differ and generating only f-free words. The case of a k-ary alphabet, with k ≥ 2, is here investigated. From k ≥ 4, the isometricity in terms of cubes is no longer captured by the Ham-isometricity, but by the Lee-isometricity. Then, Ham-isometric and Lee-isometric k-ary words are characterized in terms of their overlaps with errors. The minimal length of two words which witness the non-isometricity of a word f is called its index. The index of f is bounded in terms of its length and the bounds are shown tight by examples.

Details DOI

I&C Journal 2020 Journal Article

Characterization and measure of infinite two-dimensional strong prefix codes

Marcella Anselmo
Dora Giammarresi
Maria Madonia

A set X ⊆ Σ + + of rectangular pictures over an alphabet Σ is a two-dimensional code if any picture over Σ is tilable in at most one way with pictures in X. Finite strong prefix codes were introduced as a family of decidable two-dimensional codes. We consider infinite strong prefix codes and give a characterization for the maximal ones based on the iterated extensions. Moreover, we study some properties related to the measure of these codes of pictures and prove some connections with the codes of strings.

Details DOI

TCS Journal 2019 Journal Article

Full sets of pictures to encode pictures

Marcella Anselmo
Dora Giammarresi
Maria Madonia

A picture, or two-dimensional (2D) string, is a rectangular array of symbols over a finite alphabet. In this paper, we introduce the notion of fullness for sets of strings and sets of pictures. Fullness is a local counterpart of completeness. While in 1D fullness coincides with completeness, in 2D complete sets of pictures are a subset of full ones. This new notion allows introducing the encoding of a picture. The definition of encoding is based on the one of cutting decomposition. If a set of pictures X is full then any picture has an encoding over X; furthermore, the encoding is unique if X is a univocally full set. Univocally full sets coincide with the maximal strong prefix codes of pictures that were recently introduced. At last, we show an encoding algorithm for pictures, which relies on a new tree data structure to represent univocally full sets.

Details DOI

TCS Journal 2017 Journal Article

Non-expandable non-overlapping sets of pictures

Marcella Anselmo
Dora Giammarresi
Maria Madonia

The non-overlapping sets of pictures are sets such that no two pictures in the set (properly) overlap. They are the generalization to two dimensions of the cross-bifix-free sets of strings. Non-overlapping sets of pictures are non-expandable when no other picture can be added without violating the property. We propose a general construction method for non-expandable non-overlapping (NENO) sets based on some structural properties of NENO sets. As an application, we show a first example of a family of NENO sets.

Details DOI

I&C Journal 2017 Journal Article

Picture codes and deciphering delay

Marcella Anselmo
Dora Giammarresi
Maria Madonia

A set X of pictures over an alphabet Σ is a code if any picture over Σ is tilable in at most one way with pictures in X. The codicity problem is in general undecidable. Recently, the prefix picture codes were introduced as a decidable subclass of codes that generalize the prefix string codes. In the string theory, the finite deciphering delay sets are some interesting codes which coincide with the prefix codes when the delay is equal to 0. An analogous notion is introduced for the picture codes and it is proved that the codes with deciphering delay k form a decidable class of picture codes which includes interesting examples and special cases.

Details DOI

TCS Journal 2017 Journal Article

Two-dimensional comma-free and cylindric codes

Marcella Anselmo
Maria Madonia

A two-dimensional code of pictures is defined as a set X ⊆ Σ ⁎ ⁎ such that any picture over Σ is tilable in at most one way with pictures in X. It has been proved that it is undecidable whether a finite set of pictures is a code. Here we introduce two classes of picture codes: the comma-free codes and the cylindric codes, with the aim of generalizing the definitions of comma-free (or self-synchronizing) code and circular code of strings. The properties of these classes are studied and compared, in particular in relation to maximality and completeness. As a byproduct, we introduce self-covering pictures and study their periodicity issues.

Details DOI

TCS Journal 2009 Journal Article

A computational model for tiling recognizable two-dimensional languages

Marcella Anselmo
Dora Giammarresi
Maria Madonia

Tiling systems are a well accepted model to define recognizable two-dimensional languages but they are not an effective device for recognition unless a scanning strategy for the pictures is fixed. We define a tiling automaton as a tiling system equipped with a scanning strategy and a suitable data structure. The class of languages accepted by tiling automata coincides with the REC family. In this framework it is possible to define determinism, non-determinism and unambiguity. Then (deterministic) tiling automata are compared with the other known (deterministic) automata models for two-dimensional languages.

Details DOI

TCS Journal 2009 Journal Article

Deterministic and unambiguous two-dimensional languages over one-letter alphabet

Marcella Anselmo
Maria Madonia

The paper focuses on deterministic and unambiguous recognizable two-dimensional languages with particular attention to the case of a one-letter alphabet. The family DREC(1) of deterministic languages over a one-letter alphabet is characterized as both L (DOTA)(1), the class of languages accepted by deterministic on-line tessellation acceptors, and L (2AFA)(1), the class of languages recognized by 2-way alternating finite automata. We show that there are inherently ambiguous languages and unambiguously recognizable languages that cannot be deterministically recognized even in the case of a one-letter alphabet. In particular we show that on-line tessellation acceptors are more powerful than their deterministic counterpart, even in the case of a one-letter alphabet. Finally we show that DREC(1) is complex enough not to be characterized in terms of classical operations.

Details DOI

TCS Journal 2005 Journal Article

New operations and regular expressions for two-dimensional languages over one-letter alphabet

Marcella Anselmo
Dora Giammarresi
Maria Madonia

We consider the problem of defining regular expressions to characterize the class of recognizable picture languages in the case of a one-letter alphabet. We define a diagonal concatenation and its star and consider two different families, L ( D ) and L ( CRD ), of languages denoted by regular expressions involving such operations plus classical operations. L ( D ) is characterized both in terms of rational relations and in terms of two-dimensional automata moving only right and down. L ( CRD ) is included in REC and contains languages defined by three-way automata while languages in L ( CRD ) necessarily satisfy some regularity conditions. Finally, we introduce new definitions of advanced stars expressing the necessity of conceptually different definitions for iteration.

Details DOI