𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bilateral locally testable languages

✍ Scribed by Pedro Garcı́a; José Ruiz; Manuel Vazquez de Parga

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
218 KB
Volume
299
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 the order of appearance of those segments when we scan the preÿxes and the su xes of x. In this paper, we also characterize the syntactic semigroup of BLT languages in terms of the equations of the variety they belong to, as well as in terms of the join of two previously studied varieties.

📜 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

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

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

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.