@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",
}