Identification of biRFSA languages

The task of identifying a language from a set of its words is not an easy one. For instance, it is not feasible to identify regular languages in the general case. Therefore, looking for subclasses of regular languages that can be identified in this framework is an interesting problem. One of the mos...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2006-05, Vol.356 (1), p.212-223
Main Authors: Latteux, Michel, Lemay, Aurélien, Roos, Yves, Terlutte, Alain
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Automata. Abstract machines. Turing machines
Computer Science
Computer science
control theory
systems
Exact sciences and technology
Language theory and syntactical analysis
Non-deterministic finite automata
Programming Languages
Regular inference
Residual languages
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The task of identifying a language from a set of its words is not an easy one. For instance, it is not feasible to identify regular languages in the general case. Therefore, looking for subclasses of regular languages that can be identified in this framework is an interesting problem. One of the most classical identifiable classes is the class of reversible languages, introduced by D. Angluin, also called bideterministic languages as they can be represented by deterministic automata (DFA) whose reverse is also deterministic. Residual finite state automata (RFSA) on the other hand is a class of non-deterministic automata that shares some properties with DFA. In particular, DFA are RFSA and RFSA can be much smaller. We study here learnability of the class of languages that can be represented by biRFSA: RFSA whose reverse are RFSA. We prove that this class is not identifiable in general but we present two subclasses that are learnable, the second one being identifiable in polynomial time.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2006.01.029