Learning Algorithm for Relation-Substitutable Context-Free Languages

2014/09/19 by Kuriyama, Takayuki
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1409.6247

Abstract

We generalized the class of k,l-substitutable languages (Yoshinala, 2008). Each language in the generalized class is closed under a good substitutability. The substitutability is defined by a recognizable equivalence relation. We show the convergence of our generalized learning algorithm. The size of the characteristic sample is smaller than Yoshinaka's.

Related

• The Complexity of Learning Principles and Parameters Grammars
• Learning Unions of k-Testable Languages
• From Formal Language Theory to Statistical Learning: Finite Observability of Subregular Languages
• Learning Equivalence Relations on Polish Spaces
• Limit Learning Equivalence Structures