Learning Regular Sets from Queries and Counterexamples

By Dana Angluin. 1987

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

Citations in the corpus

Neural GPUs Learn Algorithms (2015, methodology): “To learn binary addition in this representation it therefore sufﬁces to ﬁnd a regular expression or an automaton that accepts this language, which can be done with a variant of Anguin’s algorithm (Angluin, 1987).”
Neural Program Synthesis with Priority Queue Training (2018, methodology): “Traditional approaches (e.g., Muggleton & de Raedt (1994); Angulin (1987)) typically do not make use of machine learning and therefore require domain specific knowledge about the programming languages and hand-crafted heuristics to speed up the underlying combinatorial search.”
Semi-Supervised Clustering with User Feedback (2003, background): “1, our system could easily be viewed as a practical application of learning by counterexamples [1] – one of the earliest and most powerful forms of active learning studied in the theory community.”
MAPO: Mining and Recommending API Usage Patterns (2009, methodology): “To mine automata, some approaches [4, 5, 21] use the Angluin’s algorithm [6], and other approaches [9, 11, 14, 28, 31, 36] adopt various customized techniques.”
Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples (2017, methodology): “We only provide a brief and informal description of the algorithm; for further details see (Angluin, 1987; Berg et al., 2005).”
Wrapper induction: Efficiency and expressiveness (2000, methodology): “, using the regular expression ‘ [1-9][0-9]+ ’ to identify country codes.”
Improving Generalization with Active Learning (1994, background): “Much work in formal learning theory has been directed to the study of queries (see, e.g., Angluin 1986; Valiant, 1984), but only very recently have queries been examined with respect to their role in improving generalization behavior.”
Selective Sampling In Natural Language Learning (1995, background): “While this approach provides proven computational advantages (Angluin, 1987), it is usually not applicable to natural language problems, for which it is very difficult to construct synthetically meaningful and informative examples.”
Covariance in Unsupervised Learning of Probabilistic Grammars (2010, methodology): “The field of grammatical inference also includes algorithms and methods for learning thestructure of a (formal) language generator or grammar (Angluin, 1988; de la Higuera, 2005; Clark and Thollard, 2004; Clark et al., 2008,inter alia).”
Program Synthesis Using Natural Language (2015, methodology): “The classic L* algorithm [3], a PBE system for describing a regular language, has the well-known drawback of requiring too many examples.”
Queries and concept learning (1988, methodology): “Angluin (1987d) has described an algorithm for identifying regular sets using equivalence and membership queries.”
Gradient calculations for dynamic recurrent neural networks: a survey (1995, background): “In particular, grammar learning, although intriguing and progressing rapidly [43], [44], [45], [46], [47], [48], [49], typically involves recurrent neural networks as components of more complex systems, and also at present is inferior in practice to discrete algorithmic techniques [50], [51].”
Compositional Generalization via Neural-Symbolic Stack Machines (2020, methodology): “Faced with this challenge similar to unsupervised parsing and grammar induction [2, 11, 5], we leverage the similarities between the execution traces to induce the latent categorical information.”
A bibliographical study of grammatical inference (2005, methodology): “With this systemAngluin proves that regular languages can be identified with only a polynomial amount of queries [28]: the proposed algorithm is calledL∗.”
A survey of safety and trustworthiness of deep neural networks: Verification, testing, adversarial attack and defence, and interpretability (2018, background): “[Weiss et al., 2018] extends the L* automata learning algorithm [Angluin, 1987] to work with recurrent neural networks (RNNs).”