  A classical result (often credited to Y. Medvedev) states that every language
recognized by a finite automaton is the homomorphic image of a local language,
over a much larger so-called local alphabet, namely the alphabet of the edges
of the transition graph. Local languages are characterized by the value k=2 of
the sliding window width in the McNaughton and Papert's infinite hierarchy of
strictly locally testable languages (k-slt). We generalize Medvedev's result in
a new direction, studying the relationship between the width and the alphabetic
ratio telling how much larger the local alphabet is. We prove that every
regular language is the image of a k-slt language on an alphabet of doubled
size, where the width logarithmically depends on the automaton size, and we
exhibit regular languages for which any smaller alphabetic ratio is
insufficient. More generally, we express the trade-off between alphabetic ratio
and width as a mathematical relation derived from a careful encoding of the
states. At last we mention some directions for theoretical development and
application.
