6533b7d0fe1ef96bd125b6d4

RESEARCH PRODUCT

Reducing Local Alphabet Size in Recognizable Picture Languages

Antonio RestivoStefano Crespi ReghizziPierluigi San Pietro

subject

Set (abstract data type)Discrete mathematicsProjection (mathematics)Property (programming)Order (ring theory)AlphabetDescriptive complexity theoryPicture languageMeasure (mathematics)Mathematics

description

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.

yearjournalcountryeditionlanguage
2021-01-01
https://doi.org/10.1007/978-3-030-81508-0_9