Polynomial-Time Identification of Strictly Regular Languages in the Limit

Noriyuki TANIDA; Takashi YOKOMORI

Polynomial-Time Identification of Strictly Regular Languages in the Limit

Noriyuki TANIDA, Takashi YOKOMORI

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.1 pp.125-132

Publication Date: 1992/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)

Category

Cite this

Copy

Noriyuki TANIDA, Takashi YOKOMORI, "Polynomial-Time Identification of Strictly Regular Languages in the Limit" in IEICE TRANSACTIONS on Information, vol. E75-D, no. 1, pp. 125-132, January 1992, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_1_125/_p

Copy

@ARTICLE{e75-d_1_125,
author={Noriyuki TANIDA, Takashi YOKOMORI, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial-Time Identification of Strictly Regular Languages in the Limit},
year={1992},
volume={E75-D},
number={1},
pages={125-132},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Polynomial-Time Identification of Strictly Regular Languages in the Limit
T2 - IEICE TRANSACTIONS on Information
SP - 125
EP - 132
AU - Noriyuki TANIDA
AU - Takashi YOKOMORI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1992
AB - 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.
ER -