IEICE Trans - Polynomial-Time Identification of Strictly Regular Languages in the Limit

Polynomial-Time Identification of Strictly Regular Languages in the Limit

Noriyuki TANIDA  Takashi YOKOMORI

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.1   pp.125-132
Publication Date: 1992/01/25
Online ISSN:
DOI:
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
Category:
Keyword:
identification,  strictly regular language,  polynomial-time,

Full Text: PDF(614.1KB)>>

Summary:
This paper concerns a subclass of regular languages, called strictly regular languages, and studies the problem of identifying the class of strictly regular languages in the limit from positive data. We show that the class of strictly regular languages (SRLs) is polynomial time identifiable in the limit from positive data. That is, there is an algorithm that, for any strictly regular language L, identifies a finite automaton accepting L, called a strictly deterministic finite automaton (SDFA) in the limit from positive data, satisfying the property that the time for updating a conjecture is bounded by O(mN²), where m is the cardinality of the alphabet for L and N is the sum of lengths of all positive data provided. This is in contrast with the fact that the class of regular languages is not identifiable in the limit from positive data.