A recognizable picture language is defined as the projection of a local picture language defined by a set of two-by-two tiles, i.e. by a strictly-locally-testable (SLT) language of order 2. The family of recognizable picture languages is also defined, using larger k by k tiles, k&gt; 2, by the projection of the corresponding SLT language. A basic measure of the descriptive complexity of a picture language is given by the size of the SLT alphabet using two-by-two tiles, more precisely by the so-called alphabetic ratio of sizes: SLT-alphabet/picture-alphabet. We study how the alphabetic ratio changes moving from two to larger tile sizes, and we obtain the following result: any recognizable picture language over an alphabet of size n is the projection of an SLT language over an alphabet of size 2n. Moreover, two is the minimal alphabetic ratio possible in general. This result reproduces into two dimensions a similar property (known as Extended Medvedev’s theorem) of the regular word languages, concerning the minimal alphabetic ratio needed to define a language by means of a projection of an SLT word language.

### Reducing Local Alphabet Size in Recognizable Picture Languages

#### Abstract

A recognizable picture language is defined as the projection of a local picture language defined by a set of two-by-two tiles, i.e. by a strictly-locally-testable (SLT) language of order 2. The family of recognizable picture languages is also defined, using larger k by k tiles, k> 2, by the projection of the corresponding SLT language. A basic measure of the descriptive complexity of a picture language is given by the size of the SLT alphabet using two-by-two tiles, more precisely by the so-called alphabetic ratio of sizes: SLT-alphabet/picture-alphabet. We study how the alphabetic ratio changes moving from two to larger tile sizes, and we obtain the following result: any recognizable picture language over an alphabet of size n is the projection of an SLT language over an alphabet of size 2n. Moreover, two is the minimal alphabetic ratio possible in general. This result reproduces into two dimensions a similar property (known as Extended Medvedev’s theorem) of the regular word languages, concerning the minimal alphabetic ratio needed to define a language by means of a projection of an SLT word language.
##### Scheda breve Scheda completa Scheda completa (DC)
2021
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-3-030-81507-3
978-3-030-81508-0
File in questo prodotto:
File
978-3-030-81508-0_9.pdf

Accesso riservato

: Publisher’s version
Dimensione 436.71 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11311/1233581`