2010 | OriginalPaper | Buchkapitel
Polynomial Time Identification of Strict Prefix Deterministic Finite State Transducers
verfasst von : Mitsuo Wakatsuki, Etsuji Tomita
Erschienen in: Grammatical Inference: Theoretical Results and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper is concerned with a subclass of finite state transducers, called
strict prefix deterministic finite state transducers
(
SPDFST
’s for short), and studies a problem of identifying the subclass in the limit from positive data. After providing some properties of languages accepted by SPDFST’s, we show that the class of SPDFST’s is polynomial time identifiable in the limit from positive data in the sense of Yokomori.