1,720,999 research outputs found
Prefix picture codes: a decidable class of two-dimensional codes.
No full textA 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 is proved that in general it is undecidable whether a finite set of picture is a code. The subclass of prefix codes is introduced and it is proved that it is decidable whether a finite set of pictures is a prefix code. Further a polynomial time decoding algorithm for finite prefix codes is given. Maximality and completeness of finite prefix codes are studied
Characterization and Measure of Infinite Two-dimensional Strong Prefix Codes
No full textA set X of rectangular pictures over an alphabet A is a two-dimensional
code if any picture over A is tilable in at most one way with pictures in X.
Finite strong prefix codes were introduced in [1] as a family of decidable two-
dimensional codes. We consider infinite strong prefix codes and give a char-
acterization 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
Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages
No full textAbstract. Recognizable two-dimensional languages (REC) are defined by tiling systems that generalize
to two dimensions non-deterministic finite automata for strings. We introduce the notion of
deterministic tiling system and the corresponding family of languages (DREC) and study its structural
and closure properties. Furthermore we show that, in contrast with the one-dimensional case,
there exist other classes between deterministic and non-deterministic families that we separate by
means of examples and decidability properties
A Family of Partial Cubes with Minimal Fibonacci Dimension
Full text linkA partial cube G is a graph that admits an isometric embedding into some hypercube Q_k. This implies that vertices of G can be labeled with binary words of length k in a way that the distance between two vertices in the graph corresponds to the Hamming distance between their labels. The minimum k for which this embedding is possible is called the isometric dimension of G, denoted idim(G). A Fibonacci cube Γ_k is the partial cube obtained by deleting all the vertices in Q_k whose labels contain word 11 as factor. It turns out that any partial cube can be always isometrically embedded also in a Fibonacci cube Γ_d. The minimum d is called the Fibonacci dimension of G, denoted fdim(G). In general, idim(G) ≤ fdim(G) ≤ 2 ⋅ idim(G) -1. Despite there is a quadratic algorithm to compute the isometric dimension of a graph, the problem of checking, for a given G, whether idim(G) = fdim(G) is in general NP-complete. An important family of graphs for which this happens are the trees. We consider a kind of generalized Fibonacci cubes that were recently defined. They are the subgraphs of the hypercube Q_k that include only vertices that avoid words in a given set S and are referred to as Q_k(S). We prove some conditions on the words in S to obtain a family of partial cubes with minimal Fibonacci dimension equal to the isometric dimension
Structure and measure of a decidable class of two-dimensional codes.
No full textA two-dimensional code is defined as a set X ⊆ Σ ∗∗ such that any picture over Σ is tilable in at most one way with pictures in X. It is in general undecidable whether a set X of pictures is a code also in the finite case. Very recently in [3] strong prefix picture codes were defined as a decidable subclass that generalizes prefix string codes. Here a characterization for strong prefix codes that results in an effective procedure to construct them is presented. As a consequence there are also proved interesting results on the measure of strong prefix codes and a connection with the family of string prefix codes
- …
