From regular to strictly locally testable languages

DOI10.4204/EPTCS.63.14MaRDI QIDQ2789519zbMATH OpenFDO

Authors Stefano Crespi Reghizzi, Pierluigi San Pietro

Publication date 1 March 2016

Published in Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.3626, http://www.emis.de/proceedings/Words2011/paper-12.html?WORDS2011.14

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: 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.

Recommendations

• From regular to strictly locally testable languages
• Regular languages as local functions with small alphabets
• Optimal estimation on the order of local testability of finite automata
• STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES
• Families of locally testable languages

Cited in

(12)

• Regular languages as local functions with small alphabets
• Right and left strongly locally testable semigroups and languages
• From regular to strictly locally testable languages
• STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES
• scientific article; zbMATH DE number 1104369 (Why is no real title available?)
• Two-Sided Strictly Locally Testable Languages
• On the generative capacity of contextual grammars with strictly locally testable selection languages
• Relations of contextual grammars with strictly locally testable selection languages
• Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars
• Local testability from words to traces, a suitable definition
• On generalized locally testable languages
• Local variable scoping and Kleene algebra with tests

This page was built for publication: From regular to strictly locally testable languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2789519)