From Regular to Strictly Locally Testable Languages

Details From Regular to Strictly Locally Testable Languages From Regular to Strictly Locally Testable Languages

2011-08-18

arxiv.org/abs/1108.3626v1

EPTCS 63, 2011, pp. 103-111

Computer Science

Formal Languages and Automata Theory

In Proceedings WORDS 2011, arXiv:1108.3412

Scientific paper

10.4204/EPTCS.63.14

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.

Affiliated with

Also associated with

No associations

Rating

From Regular to Strictly Locally Testable Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with From Regular to Strictly Locally Testable Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and From Regular to Strictly Locally Testable Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-180600