𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Learning approximately regular languages with reversible languages

✍ Scribed by Satoshi Kobayashi; Takashi Yokomori

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
490 KB
Volume
174
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

In this note, we consider the problem of learning approximately regular languages in the limit from positive data using the class of k-reversible languages. The class of k-reversible languages was introduced by Angluin (1982), and proved to be efficiently identifiable in the limit from positive data only. We show that Angluin's learning algorithm for the class of k-reversible languages can be readily adopted for the approximate identification of regular languages from positive data. Considering the negative result on the exact identifiability by Gold (1967), this approximation approach would be one of the best we could hope for learning the class of regular languages from positive data only.

πŸ“œ SIMILAR VOLUMES

Efficient implementation of regular lang
Efficient implementation of regular languages using reversed alternating finite automata
✍ K. Salomaa; X. Wu; S. Yu πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 93 KB

Alternating ΓΏnite automata (AFA) provide a natural and succinct way to denote regular languages. We introduce a bit-wise representation of reversed AFA (r-AFA) transition functions and describe an e cient implementation method for r-AFA and their operations using this representation. Experiments hav

Refutable language learning with a neigh
Refutable language learning with a neighbor system
✍ Yasuhito Mukouchi; Masako Sato πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 239 KB

We consider inductive language learning and machine discovery from examples with some errors. In the present paper, the error or incorrectness we consider is the one described uniformly in terms of a distance over strings. Firstly, we introduce a notion of a recursively generable distance over strin

Reflections on foreign language study fo
Reflections on foreign language study for students with language learning problems: research, issues, and challenges
✍ Leonore Ganschow; Richard L. Sparks πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 123 KB

The study of foreign language (FL) learning for individuals who have found learning to read and write in their first language extremely problematic has been an under-researched area throughout the world. Since the 1980s, Leonore Ganschow and Richard Sparks have conducted pioneering research into the