𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Right and left locally testable languages

✍ Scribed by Pedro Garcı́a; José Ruiz

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
127 KB
Volume
246
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 languages. Given k¿0, the membership of a word x to a RLT (k-RT) language can be decided by means of exploring the preÿx and su x of length k -1 of x and the segments of length k, as well as considering the order of appearance of those segments when we scan the preÿxes of x. Membership of x to a k-LT can be decided in a similar way, but we have to change the word "preÿxes" for "su xes" in the above description. In this paper we also show that S is a syntactic semigroup of a k-RT (resp. k-LT) language if and only if the local subsemigroups of S are idempotents and right (resp. left) repetition free.

📜 SIMILAR VOLUMES

Locally testable languages
Locally testable languages
✍ Yechezkel Zalcstein 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 877 KB

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 algeb

Bilateral locally testable languages
Bilateral locally testable languages
✍ Pedro Garcı́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
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

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