✦ LIBER ✦

Families of locally testable languages

✍ Scribed by Pascal Caron

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 177 KB
Volume: 242
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(98)00332-6

No coin nor oath required. For personal study only.

✦ Synopsis

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 languages, two subclasses of locally testable languages. These two characterizations lead us to polynomial time algorithms for testing these families of languages.

📜 SIMILAR VOLUMES

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

✍ 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

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

McNaughton families of languages

✍ M. Beaudry; M. Holzer; G. Niemann; F. Otto 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 410 KB

In 1988 the Church-Rosser languages were introduced by McNaughton et al. as those languages that are recognized by ÿnite, length-reducing and con uent string-rewriting systems using extra non-terminal symbols. Here we generalize this concept by considering classes of languages that are obtained by o

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.