From Regular to Strictly Locally Testable Languages

Computer Science – Formal Languages and Automata Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-180600

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.