✦ LIBER ✦

Locally testable languages

✍ Scribed by Yechezkel Zalcstein

Publisher: Elsevier Science
Year: 1972
Tongue: English
Weight: 877 KB
Volume: 6
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(72)80020-5

No coin nor oath required. For personal study only.

✦ Synopsis

This paper studies the locally testable languages (or "events") introduced by McNaughton and Papert. We characterize these languages by means of their syntactic semigroups and obtain wreath product and direct product decompositions for these semigroups. As a by-product of our study, we find an algebraic characterization of A. Ginzburg's generalized definite languages.

📜 SIMILAR VOLUMES

Bilateral locally testable languages

✍ Pedro Garcı&#x0301;a; José Ruiz; Manuel Vazquez de Parga 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 218 KB

We give an algebraic characterization of a new variety of languages that will be called bilateral locally testable languages and denoted as BLT. Given k ¿ 0, the membership of a word x to a BLT (k-BT) language can be decided by means of exploring the segments of length k of x, as well as considering

Families of locally testable languages

✍ Pascal Caron 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 177 KB

## Kim, McNaughton and McCloskey have produced a polynomial time algorithm in order to test if a deterministic automaton recognizes a locally testable language. We provide a characterization in terms of automata for the strictly locally testable languages and for the strongly locally testable lang

Right and left locally testable language

Right and left locally testable languages

✍ Pedro Garcı́a; José Ruiz 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 127 KB

The aim of this paper is to give a deÿnition as well as an algebraic characterization of two new varieties of languages that will be referred to as right (respectively left) locally testable languages and denoted as RLT (resp. LLT). Both families strictly contain the class of locally testable langua

Splicing representations of strictly loc

Splicing representations of strictly locally testable languages

✍ Tom Head 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 711 KB

The relationship between the family SH of simple splicing languages, which was recently introduced by Mateescu et al. and the family X7' of strictly locally testable languages is clarified by establishing an ascending hierarchy of families {SiH: i > -1) of splicing languages for which SH = SI H and

Smoothing and compression with stochasti

Smoothing and compression with stochastic -testable tree languages

✍ Juan Ramón Rico-Juan; Jorge Calera-Rubio; Rafael C. Carrasco 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 394 KB

A proof of Simon's theorem on piecewise

A proof of Simon's theorem on piecewise testable languages

✍ Peter M. Higgins 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 587 KB

We give a new proof of the Theorem of I. Simon that a language is piecewise testable if and only if it is recognized by a finite F-trivial monoid. Our proof is based on representations by certain types of decreasing mappings.