N. Tanida, POLYNOMIAL-TIME INFERENCE OF PARALLELED EVEN MONOGENIC PURE CONTEXT-FREE LANGUAGES, IEICE transactions on information and systems, E81D(3), 1998, pp. 261-270
We introduce a subclass of context-free languages, called pure context
-free (PCF) languages, which is generated by context-free grammars wit
h only one type of symbol (i.e., terminals and nonterminals are not di
stinguished), and consider the problem of identifying paralleled even
monogenic pure context-free (pem-PCF) languages, PCF languages with re
stricted and enhanced Features, from positive data only. In this paper
we show that the problem of identifying the class of pem-PCF language
s is reduced to the problem of identifying the class of monogenic PCF
(mono-PCF), whose identifiability was shown in [11], by decomposing ea
ch string of pem-PCF languages. Then, with its result, we show that th
e class of pem-PCF languages is polynomial time identifiable in the li
mit from positive data. Further, we refer to properties of its identif
ication algorithm.