Learning conjunctive grammars and contextual binary feature grammars

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)


Approaches based on the idea generically called distributional learning have been making great success in the algorithmic learning of context-free languages and their extensions. We in this paper show that conjunctive grammars are also learnable by a distributional learning technique. Conjunctive grammars are context-free grammars enhanced with conjunctive rules to extract the intersection of two languages. We also compare our result with the closely related work by Clark et al. (JMLR 2010) on contextual binary feature grammars (CBFGs). Our learner is stronger than theirs. In particular our learner learns every exact CBFG, while theirs does not. Clark et al. emphasized the importance of exact CBFGs but they only conjectured there should be a learning algorithm for exact CBFGs. This paper shows that their conjecture is true.

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 9th International Conference, LATA 2015, Proceedings
EditorsAdrian-Horia Dediu, Carlos Martín-Vide, Enrico Formenti, Bianca Truthe
PublisherSpringer Verlag
Number of pages13
ISBN (Electronic)9783319155784
Publication statusPublished - 2015
Event9th International Conference on Language and Automata Theory and Applications, LATA 2015 - Nice, France
Duration: 2015 Mar 22015 Mar 6

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference9th International Conference on Language and Automata Theory and Applications, LATA 2015


  • Algorithmic learning
  • Distributional Learning
  • Grammatical inference


Dive into the research topics of 'Learning conjunctive grammars and contextual binary feature grammars'. Together they form a unique fingerprint.

Cite this