Polynomial-Time Inference of Paralleled Even Monogenic Pure Context-Free Languages

Noriyuki TANIDA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.3   pp.261-270
Publication Date: 1998/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
inductive inference,  paralleled even monogenic pure context-free languages,  polynomial-time,  

Full Text: PDF(827KB)>>
Buy this Article




Summary: 
We introduce a subclass of context-free languages, called pure context-free (PCF) languages, which is generated by context-free grammars with only one type of symbol (i. e. , terminals and nonterminals are not distinguished), and consider the problem of identifying paralleled even monogenic pure context-free (pem-PCF) languages, PCF languages with restricted and enhanced features, from positive data only. In this paper we show that the ploblem of identifying the class of pem-PCF languages is reduced to the ploblem of identifying the class of monogenic PCF (mono-PCF), by decomposing each string of pem-PCF languages. Then, with its result, we show that the class of pem-PCF languages is polynomial time identifiable in the limit from positive data. Further, we refer to properties of its identification algorithm.