For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Polynomial-Time Identification of Strictly Regular Languages in the Limit
Noriyuki TANIDA Takashi YOKOMORI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1992/01/25
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)
identification, strictly regular language, polynomial-time,
Full Text: PDF(614.1KB)>>
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(mN2), 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.