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

スポンサーリンク

概要

• 論文の詳細を見る

• 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), whose identifiability was shown in [11], 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 idenitification algorithm.

• 社団法人電子情報通信学会の論文
• 1998-03-25

著者

• Tanida Noriyuki

  The Faculty Of Economics Kansai University

関連論文

• Polynomial-Time Identification of Strictly Regular Languages in the Limit
• Polynomial-Time Inference of Paralleled Even Monogenic Pure Context-Free Languages

スポンサーリンク