@inproceedings{dc9ed382342745218e03187d85d7f2a4,

title = "Polynomial-time identification of an extension of very simple grammars from positive data",

abstract = "The class of very simple grammars is known to be polynomialtime identifiable in the limit from positive data. This paper introduces an extension of very simple grammars called right-unique simple grammars, and presents an algorithm that identifies right-unique simple grammars in the limit from positive data. The learning algorithm possesses the following three properties. It computes a conjecture in polynomial time in the size of the input data if we regard the cardinality of the alphabet as a constant. It always outputs a grammar which is consistent with the input data. It never changes the conjecture unless the newly provided example contradicts the previous conjecture. The algorithm has a sub-algorithm that solves the inclusion problem for a superclass of right-unique simple grammars, which is also presented in this paper.",

author = "Ryo Yoshinaka",

year = "2006",

doi = "10.1007/11872436_5",

language = "English",

isbn = "3540452648",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "45--58",

booktitle = "Grammatical Inference",

address = "Germany",

note = "8th International Colloquium on Grammatical Inference, ICGI 2006 ; Conference date: 20-09-2006 Through 22-09-2006",

}