Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Learning in varieties of the form V*LI from positive data
García P., Ruiz J. Theoretical Computer Science362 (1):100-114,2006.Type:Article
Date Reviewed: Aug 17 2007

Grammatical inference refers to the process of learning grammars and languages from data. In literature, it refers to automata induction, grammar induction, and automatic language acquisition. There are applications for machine learning in syntactic pattern recognition, adaptive intelligent agents, diagnosis, computational biology, systems modeling, prediction, natural language acquisition, data mining, and knowledge discovery. This paper does not go into the details and mechanics of implementing grammatical inference, and in this sense it is not the paper on machine learning that one would expect. Instead, it is well written, mathematically impeccable, algebraic, theoretical, and, ultimately, of great importance.

It presents and discusses a class of languages called V*LI, where V is a syntactic semigroup, and LI is the variety of locally trivial semigroups. It is a general class that contains some languages that have previously been given significant research attention, such as locally testable, reversible, and dot-depth one languages. Given the sequences of words of a language or their complete presentation (positive data), the methods given in this paper unify the existing inference algorithms. This procedure generalizes the approach and is expected to be applied in related domains. As it is illustrated with figures that are complementary to the text, this formalism-packed paper is well worth the effort required to cross-reference definitions and understand the implications of the theory discussed.

Reviewer:  Goran Trajkovski Review #: CR134662 (0807-0699)
Bookmark and Share
  Featured Reviewer  
 
Algebraic Language Theory (F.4.3 ... )
 
 
Concept Learning (I.2.6 ... )
 
 
Inference Engines (I.2.3 ... )
 
 
Deduction And Theorem Proving (I.2.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Algebraic Language Theory": Date
Products of languages with counter
Weil P. Theoretical Computer Science 76(2-3): 251-260, 2001. Type: Article
Oct 1 1991
On characterizations of recursively enumerable languages
Latteux M., Turakainen P. Acta Informatica 28(2): 179-186, 1990. Type: Article
Dec 1 1991
Effective construction of the synthetic algebra of a recognizable series on trees
Bozapalidis S. Acta Informatica 28(4): 351-363, 1991. Type: Article
May 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy