10 citations · 15 across the 9 of their papers we have counts for
9 papers
Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages
Dana Angluin, Dana Fisman
A characteristic sample for a language and a learning algorithm is a finite sample of words labeled by their membership in such that for any sample $T \s…
Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity
Yiding Hao, Dana Angluin, Robert Frank
This paper analyzes three formal models of Transformer encoders that differ in the form of their self-attention mechanism: unique hard attention (UHAT); generalized unique hard att…
Polynomial time algorithms for inclusion and equivalence of deterministic omega acceptors
Dana Angluin, Dana Fisman
The class of omega languages recognized by deterministic parity acceptors (DPAs) or deterministic Muller acceptors (DMAs) is exactly the regular omega languages. The inclusion prob…
Regular omega-Languages with an Informative Right Congruence
Dana Angluin, Dana Fisman
A regular language is almost fully characterized by its right congruence relation. Indeed, a regular language can always be recognized by a DFA isomorphic to the automaton correspo…
Context-Free Transductions with Neural Stacks
Yiding Hao, William Merrill, Dana Angluin +4
This paper analyzes the behavior of stack-augmented recurrent neural network (RNN) models. Due to the architectural similarity between stack RNNs and pushdown transducers, we train…
Query learning of derived -tree languages in polynomial time
Dana Angluin, Timos Antonopoulos, Dana Fisman
We present the first polynomial time algorithm to learn nontrivial classes of languages of infinite trees. Specifically, our algorithm uses membership and equivalence queries to le…