Inductive Inference of Monogenic Pure Context-free Languages
作者： Noriyuki Tanida , Takashi Yokomori
关键词:
摘要: This paper concerns a subclass of context-free languages, called pure contextfree which is generated by grammar with only one type symbol (i.e., terminals and nonterminals are not distinguished), investigates the problem identifying from positive data restricted class monogenic languages (mono-PCF in short). The mono-PCF incomparable to regular languages. We show that polynomial time identifiable data. That is, there an algorithm that, given language L, identifies data, generating grammar) satisfying property for updating conjecture bounded O(N3), where N sum lengths all provided. contrast another result this PCF limit
springer.com
elsevier.com
sci-hub.st 参考文章(15)
Erkki Mäkinen, On Pure Context-Free Languages and Left Szilard Languages Fundamenta Informaticae. ,vol. 15, pp. 86- 89 ,(1991) , 10.3233/FI-1991-15107
E Mark Gold, Language identification in the limit Information & Computation. ,vol. 10, pp. 447- 474 ,(1967) , 10.1016/S0019-9958(67)91165-5
Erkki Mäkinen, The grammatical inference problem for the Szilard languages of linear grammars Information Processing Letters. ,vol. 36, pp. 203- 206 ,(1990) , 10.1016/0020-0190(90)90074-8
A.K. Joshi, S.R. Kosaraju, H.M. Yamada, String adjunct grammars: I. Local and distributed adjunction Information & Computation. ,vol. 21, pp. 93- 116 ,(1972) , 10.1016/S0019-9958(72)90051-4
Armen Gabrielian, Pure grammars and pure languages International Journal of Computer Mathematics. ,vol. 9, pp. 3- 16 ,(1981) , 10.1080/00207168108803224
Takeshi Shinohara, Inductive inference from positive data is powerful conference on learning theory. pp. 97- 110 ,(1990) , 10.5555/92571.92593
Rajeev Motwani, John E. Hopcroft, Jeffrey D. Ullman, Rotwani, Introduction to Automata Theory, Languages, and Computation ,(1979)
Dana Angluin, Inductive inference of formal languages from positive data Information & Computation. ,vol. 45, pp. 117- 135 ,(1980) , 10.1016/S0019-9958(80)90285-5
Erkki Mäkinen, A note on pure grammars Information Processing Letters. ,vol. 23, pp. 271- 274 ,(1986) , 10.1016/0020-0190(86)90085-2
Klaus P. Jantke, Monotonic and non-monotonic inductive inference algorithmic learning theory. ,vol. 8, pp. 349- 360 ,(1991) , 10.1007/BF03037092