Dana Angluin

NeurIPS Conference 2024 Conference Paper

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

• Andy Yang
• David Chiang
• Dana Angluin

The expressive power of transformers over inputs of unbounded size can be studied through their ability to recognize classes of formal languages. In this paper, we establish exact characterizations of transformers with hard attention (in which all attention is focused on exactly one position) and attention masking (in which each position only attends to positions on one side). With strict masking (each position cannot attend to itself) and without position embeddings, these transformers are expressively equivalent to linear temporal logic (LTL), which defines exactly the star-free languages. A key technique is the use of Boolean RASP as a convenient intermediate language between transformers and LTL. We then take numerous results known for LTL and apply them to transformers, showing how position embeddings, strict masking, and depth all increase expressive power.

I&C Journal 2021 Journal Article

Regular ω-languages with an informative right congruence

• Dana Angluin
• Dana Fisman

A regular language is almost fully characterized by its right congruence relation. The same does not hold for regular ω-languages. The right congruence of a regular ω-language may not be informative enough; many regular ω-languages have a trivial right congruence, and in general it is not always possible to define an ω-automaton recognizing a given language that is isomorphic to its right congruence. The weak regular ω-languages do have fully informative right congruences. That is, any weak regular ω-language can always be recognized by a deterministic B u ¨ chi automaton that is isomorphic to its right congruence. Weak regular ω-languages reside in the lower levels of the expressiveness hierarchy of regular ω-languages. Are there more expressive sub-classes of regular ω-languages that have fully informative right congruences? Can we characterize the class of languages that have trivial right congruences? In this paper we try to place some additional pieces of this big puzzle.

CSL Conference 2020 Conference Paper

Strongly Unambiguous Büchi Automata Are Polynomially Predictable With Membership Queries

• Dana Angluin
• Timos Antonopoulos
• Dana Fisman

A Büchi automaton is strongly unambiguous if every word w ∈ Σ^ω has at most one final path. Many properties of strongly unambiguous Büchi automata (SUBAs) are known. They are fully expressive: every regular ω-language can be represented by a SUBA. Equivalence and containment of SUBAs can be decided in polynomial time. SUBAs may be exponentially smaller than deterministic Muller automata and may be exponentially bigger than deterministic Büchi automata. In this work we show that SUBAs can be learned in polynomial time using membership and certain non-proper equivalence queries, which implies that they are polynomially predictable with membership queries. In contrast, under plausible cryptographic assumptions, non-deterministic Büchi automata are not polynomially predictable with membership queries.

TCS Journal 2020 Journal Article

The power of random counterexamples

• Dana Angluin
• Tyler Dohrn

Learning a target concept from a finite n × m concept space requires Ω ( n ) proper equivalence queries in the worst case. We propose a variation of the usual equivalence query in which the teacher is constrained to choose counterexamples randomly from a known probability distribution on examples. We present and analyze the Max-Min learning algorithm, which identifies an arbitrary target concept in an arbitrary finite n × m concept space using at most an expected log 2 ⁡ n proper equivalence queries with random counterexamples.

GandALF Workshop 2018 Workshop Paper

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 corresponding to its right congruence, henceforth the Rightcon automaton. The same does not hold for regular omega-languages. The right congruence of a regular omega-language is not informative enough; many regular omega-languages have a trivial right congruence, and in general it is not always possible to define an omega-automaton recognizing a given language that is isomorphic to the rightcon automaton. The class of weak regular omega-languages does have an informative right congruence. That is, any weak regular omega-language can always be recognized by a deterministic Büchi automaton that is isomorphic to the rightcon automaton. Weak regular omega-languages reside in the lower levels of the expressiveness hierarchy of regular omega-languages. Are there more expressive sub-classes of regular omega languages that have an informative right congruence? Can we fully characterize the class of languages with a trivial right congruence? In this paper we try to place some additional pieces of this big puzzle.

AIJ Journal 2017 Journal Article

A model of language learning with semantics and meaning-preserving corrections

• Dana Angluin
• Leonor Becerra-Bonache

We present a computational model that takes into account semantics for language learning and allows us to model meaning-preserving corrections. The model is constructed with a learner and a teacher who interact in a sequence of shared situations by producing utterances intended to denote a unique object in each situation. We test our model with limited sublanguages of 10 natural languages exhibiting a variety of linguistic phenomena. The results show that learning to a high level of performance occurs after a reasonable number of interactions. Comparing the effect of a teacher who does no correction to that of a teacher who corrects whenever possible, we show that under certain conditions corrections can accelerate the rate of learning. We also define and analyze a simplified model of a probabilistic process of collecting corrections to help understand the possibilities and limitations of corrections in our setting.

CSL Conference 2017 Conference Paper

Query Learning of Derived Omega-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 learn classes of omega-tree languages derived from weak regular omega-word languages in polynomial time. The method is a general polynomial time reduction of learning a class of derived omega-tree languages to learning the underlying class of omega-word languages, for any class of omega-word languages recognized by a deterministic Büchi acceptor. Our reduction, combined with the polynomial time learning algorithm of Maler and Pnueli [Maler and Pneuli, Inform. Comput. , 1995] for the class of weak regular omega-word languages yields the main result. We also show that subset queries that return counterexamples can be implemented in polynomial time using subset queries that return no counterexamples for deterministic or non-deterministic finite word acceptors, and deterministic or non-deterministic Büchi omega-word acceptors. A previous claim of an algorithm to learn regular omega-trees due to Jayasrirani, Begam and Thomas [Jayasrirani et al. , ICGI, 2008] is unfortunately incorrect, as shown in [Angluin, YALEU/DCS/TR-1528, 2016].

MFCS Conference 2016 Conference Paper

Families of DFAs as Acceptors of omega-Regular Languages

• Dana Angluin
• Udi Boker
• Dana Fisman

Families of DFAs (FDFAs) provide an alternative formalism for recognizing omega-regular languages. The motivation for introducing them was a desired correlation between the automaton states and right congruence relations, in a manner similar to the Myhill-Nerode theorem for regular languages. This correlation is beneficial for learning algorithms, and indeed it was recently shown that omega-regular languages can be learned from membership and equivalence queries, using FDFAs as the acceptors. In this paper, we look into the question of how suitable FDFAs are for defining omega-regular languages. Specifically, we look into the complexity of performing Boolean operations, such as complementation and intersection, on FDFAs, the complexity of solving decision problems, such as emptiness and language containment, and the succinctness of FDFAs compared to standard deterministic and nondeterministic omega-automata. We show that FDFAs enjoy the benefits of deterministic automata with respect to Boolean operations and decision problems. Namely, they can all be performed in nondeterministic logarithmic space. We provide polynomial translations of deterministic Buchi and coBuchi automata to FDFAs and of FDFAs to nondeterministic Buchi automata (NBAs). We show that translation of an NBA to an FDFA may involve an exponential blowup. Last, we show that FDFAs are more succinct than deterministic parity automata (DPAs) in the sense that translating a DPA to an FDFA can always be done with only a polynomial increase, yet the other direction involves an inevitable exponential blowup in the worst case.

TCS Journal 2016 Journal Article

Learning regular omega languages

• Dana Angluin
• Dana Fisman

We provide an algorithm for learning an unknown regular set of infinite words using membership and equivalence queries. Three variations of the algorithm learn three different canonical representations of regular omega languages using the notion of families of dfas. One is of size similar to L $, a dfa representation recently learned using L ⁎ by Farzan et al. The second is based on the syntactic forc, introduced by Maler and Staiger. The third is introduced herein. We show that the second and third can be exponentially smaller than the first, and the third is at most as large as the second, with up to a quadratic saving with respect to the second.

IJCAI Conference 2015 Conference Paper

Learning Regular Languages via Alternating Automata

• Dana Angluin
• Sarah Eisenstat
• Dana Fisman

Nearly all algorithms for learning an unknown regular language, in particular the popular L⇤ algorithm, yield deterministic finite automata. It was recently shown that the ideas of L⇤ can be extended to yield non-deterministic automata, and that the respective learning algorithm, NL⇤, outperforms L⇤ on randomly generated regular expressions. We conjectured that this is due to the existential nature of regular expressions, and NL⇤ might not outperform L⇤ on languages with a universal nature. In this paper we introduce UL⇤ — a learning algorithm for universal automata (the dual of non-deterministic automata); and AL⇤ — a learning algorithm for alternating automata (which generalize both universal and non-deterministic automata). Our empirical results illustrate the advantages and trade-offs among L⇤, NL⇤, UL⇤ and AL⇤.

I&C Journal 2014 Journal Article

Effective storage capacity of labeled graphs

• Dana Angluin
• James Aspnes
• Rida A. Bazzi
• Jiang Chen
• David Eisenstat
• Goran Konjevod

We consider the question of how much information can be stored by labeling the vertices of a connected undirected graph G using a constant-size set of labels, when isomorphic labelings are not distinguishable. Specifically, we are interested in the effective capacity of members of some class of graphs, the number of states distinguishable by a Turing machine that uses the labeled graph itself in place of the usual linear tape. We show that the effective capacity is related to the information-theoretic capacity which we introduce in the paper. It equals the information-theoretic capacity of the graph up to constant factors for trees, random graphs with polynomial edge probabilities, and bounded-degree graphs.

JMLR Journal 2013 Journal Article

On the Learnability of Shuffle Ideals

• Dana Angluin
• James Aspnes
• Sarah Eisenstat
• Aryeh Kontorovich

PAC learning of unrestricted regular languages is long known to be a difficult problem. The class of shuffle ideals is a very restricted subclass of regular languages, where the shuffle ideal generated by a string $u$ is the collection of all strings containing $u$ as a subsequence. This fundamental language family is of theoretical interest in its own right and provides the building blocks for other important language families. Despite its apparent simplicity, the class of shuffle ideals appears quite difficult to learn. In particular, just as for unrestricted regular languages, the class is not properly PAC learnable in polynomial time if RP $\neq$ NP, and PAC learning the class improperly in polynomial time would imply polynomial time algorithms for certain fundamental problems in cryptography. In the positive direction, we give an efficient algorithm for properly learning shuffle ideals in the statistical query (and therefore also PAC) model under the uniform distribution. [abs] [ pdf ][ bib ] &copy JMLR 2013. ( edit, beta )

TCS Journal 2010 Journal Article

Optimally learning social networks with activations and suppressions

• Dana Angluin
• James Aspnes
• Lev Reyzin

In this paper we consider the problem of learning hidden independent cascade social networks using exact value injection queries. These queries involve activating and suppressing agents in the target network. We develop an algorithm that optimally learns an arbitrary social network of size n using O ( n 2 ) queries, matching the information theoretic lower bound that we prove for this problem. We also consider the case when the target social network forms a tree and show that the learning problem takes Θ ( n log ( n ) ) queries. We also give an approximation algorithm for finding an influential set of nodes in the network, without resorting to learning its structure. Finally, we discuss some limitations of our approach, and limitations of path-based methods, when non-exact value injection queries are used.

JMLR Journal 2009 Journal Article

Learning Acyclic Probabilistic Circuits Using Test Paths

• Dana Angluin
• James Aspnes
• Jiang Chen
• David Eisenstat
• Lev Reyzin

We define a model of learning probabilistic acyclic circuits using value injection queries, in which fixed values are assigned to an arbitrary subset of the wires and the value on the single output wire is observed. We adapt the approach of using test paths from the Circuit Builder algorithm (Angluin et al., 2009) to show that there is a polynomial time algorithm that uses value injection queries to learn acyclic Boolean probabilistic circuits of constant fan-in and log depth. We establish upper and lower bounds on the attenuation factor for general and transitively reduced Boolean probabilistic circuits of test paths versus general experiments. We give computational evidence that a polynomial time learning algorithm using general value injection experiments may not do much better than one using test paths. For probabilistic circuits with alphabets of size three or greater, we show that the test path lemmas (Angluin et al., 2009, 2008b) fail utterly. To overcome this obstacle, we introduce function injection queries, in which the values on a wire may be mapped to other values rather than just to themselves or constants, and prove a generalized test path lemma for this case. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

TAAS Journal 2008 Journal Article

Self-stabilizing population protocols

• Dana Angluin
• James Aspnes
• Michael J. Fischer
• Hong Jiang

This article studies self-stabilization in networks of anonymous, asynchronously interacting nodes where the size of the network is unknown. Constant-space protocols are given for Dijkstra-style round-robin token circulation, leader election in rings, two-hop coloring in degree-bounded graphs, and establishing consistent global orientation in an undirected ring. A protocol to construct a spanning tree in regular graphs using O (log D ) memory is also given, where D is the diameter of the graph. A general method for eliminating nondeterministic transitions from the self-stabilizing implementation of a large family of behaviors is used to simplify the constructions, and general conditions under which protocol composition preserves behavior are used in proving their correctness.

STOC Conference 2006 Conference Paper

Learning a circuit by injecting values

• Dana Angluin
• James Aspnes
• Jiang Chen
• Yinghua Wu

We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of the circuit's single output wire may be observed. We give polynomial time algorithms to learn (1) arbitrary circuits with logarithmic depth and constant fan-in and (2) Boolean circuits of constant depth and unbounded fan-in over AND, OR, and NOT gates. Thus, both AC0 and NC1 circuits are learnable in polynomial time in this model. Negative results show that some restrictions on depth, fan-in and gate types are necessary: exponentially many experiments are required to learn AND/OR circuits of unbounded depth and fan-in; it is NP-hard to learn AND/OR circuits of unbounded depth and fan-in 2; and it is NP-hard to learn circuits of bounded depth and unbounded fan-in over AND, OR, and threshold gates, even when the target circuit is known to contain at most one threshold gate and that threshold gate has threshold 2. We also consider the effect of adding an oracle for behavioral equivalence. In this case there are polynomial-time algorithms to learn arbitrary circuits of constant fan-in and unbounded depth and to learn Boolean circuits with arbitrary fan-in and unbounded depth over AND, OR, and NOT gates. A corollary is that these two classes are PAC-learnable if experiments are available.

JMLR Journal 2006 Journal Article

Learning a Hidden Hypergraph

• Dana Angluin
• Jiang Chen

We consider the problem of learning a hypergraph using edge-detecting queries. In this model, the learner may query whether a set of vertices induces an edge of the hidden hypergraph or not. We show that an r -uniform hypergraph with m edges and n vertices is learnable with O (2 4 r m · poly ( r,log n )) queries with high probability. The queries can be made in O (min(2 r (log m+r ) 2, (log m+r ) 3 )) rounds. We also give an algorithm that learns an almost uniform hypergraph of dimension r using O (2 O ((1+Δ/2)r) · m 1+Δ/2 · poly (log n )) queries with high probability, where Δ is the difference between the maximum and the minimum edge sizes. This upper bound matches our lower bound of Ω(( m /(1+Δ/2)) 1+Δ/2 ) for this class of hypergraphs in terms of dependence on m. The queries can also be made in O ((1+Δ) · min(2 r (log m+r ) 2, (log m+r ) 3 )) rounds. [abs] [ pdf ][ bib ] &copy JMLR 2006. ( edit, beta )

TCS Journal 2004 Journal Article

Queries revisited

• Dana Angluin

We begin with a brief tutorial on the problem of learning a finite concept class over a finite domain using membership queries and/or equivalence queries. We then sketch general results on the number of queries needed to learn a class of concepts, focusing on the various notions of combinatorial dimension that have been employed, including the teaching dimension, the exclusion dimension, the extended teaching dimension, the fingerprint dimension, the sample exclusion dimension, the Vapnik–Chervonenkis dimension, the abstract identification dimension, and the general dimension.

STOC Conference 1996 Conference Paper

Robot Navigation with Range Queries

• Dana Angluin
• Jeffery R. Westbrook
• Wenhong Zhu

STOC Conference 1992 Conference Paper

Computational Learning Theory: Survey and Selected Bibliography

• Dana Angluin

STOC Conference 1991 Conference Paper

When Won't Membership Queries Help? (Extended Abstract)

• Dana Angluin
• Michael Kharitonov

FOCS Conference 1990 Conference Paper

Learning Conjunctions of Horn Clauses (Extended Abstract)

• Dana Angluin
• Michael Frazier
• Leonard Pitt

An algorithm for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses is presented. (A Horn clause is a disjunction of literals, all but at most one of which is a negated variable). The algorithm uses equivalence queries and membership queries to produce a formula that is logically equivalent to the unknown formula to be learned. The amount of time used by the algorithm is polynomial in the number of variables and the number of clauses in the unknown formula. >

TCS Journal 1989 Journal Article

Training sequences

• Dana Angluin
• William I. Gasarch
• Carl H. Smith

Intuitively, the more a machine knows the more it can learn. This intuition is formalized in a recursion theoretic framework. A formal definition of what it means for a machine to learn a finite sequence of recursive functions is presented. We prove that there are sets of sequences S, and a sequence 〈ƒ1, ƒ2, …, ƒn〉ϵ S such that in order to learn a program for ƒ i a machine must necessarily know programs for ƒ1, …, ƒi−1. Also investigated is the simultaneous inference of programs for a finite set of recursive functions.

I&C Journal 1987 Journal Article

Learning regular sets from queries and counterexamples

• Dana Angluin

The problem of identifying an unknown regular set from examples of its members and nonmembers is addressed. It is assumed that the regular set is presented by a minimally adequate Teacher, which can answer membership queries about the set and can also test a conjecture and indicate whether it is equal to the unknown set and provide a counterexample if not. (A counterexample is a string in the symmetric difference of the correct set and the conjectured set.) A learning algorithm L∗ is described that correctly learns any regular set from any minimally adequate Teacher in time polynomial in the number of states of the minimum dfa for the set and the maximum length of any counterexample provided by the Teacher. It is shown that in a stochastic setting the ability of the Teacher to test conjectures may be replaced by a random sampling oracle, EX( ). A polynomial-time learning algorithm is shown for a particular problem of context-free language identification.

STOC Conference 1980 Conference Paper

Local and Global Properties in Networks of Processors (Extended Abstract)

• Dana Angluin

This paper attempts to get at some of the fundamental properties of distributed computing by means of the following question: “How much does each processor in a network of processors need to know about its own identity, the identities of other processors, and the underlying connection network in order for the network to be able to carry out useful functions?” The approach we take is to require that the processors be designed without any knowledge (or only very broad knowledge) of the networks they are to be used in, and furthermore, that all processors with the same number of communication ports be identical. Given a particular network function, e.g., setting up a spanning tree, we ask whether processors may be designed so that when they are embedded in any connected network and started in some initial configuration, they are guaranteed to accomplish the desired function.

TCS Journal 1980 Journal Article

On counting problems and the polynomial-time hierarchy

• Dana Angluin

We consider the relation between the relativized polynomial time hierarchy and relativizations of Gill's class PP of sets recognizable in polynomial time by probabilistic Turing machines and of Valiant's class D≠P of sets polynomial time Turing reducible to functions that give the number of accepting computations of nondeterministic polynomial-time bounded Turing machines. The main result is that there exists an oracle set A such that PP A −(Π 2 P, A ∪ σ 2 P, A ) ≠ ∅, with the corollary that also D ≠P A − (Π 2 P, A ∪ σ 2 P, A ≠ ∅. The proof is an application of Baker and Selman's technique for showing that σ 2 P, A ⊆ σ 3 P, A for some oracle set A.

STOC Conference 1979 Conference Paper

Finding Patterns Common to a Set of Strings (Extended Abstract)

• Dana Angluin

STOC Conference 1977 Conference Paper

Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings

• Dana Angluin
• Leslie G. Valiant

The main purpose of this paper is to give techniques for analysing the probabilistic performance of certain kinds of algorithms, and hence to suggest some fast algorithms with provably desirable probabilistic behaviour. The particular problems we consider are: finding Hamiltonian circuits in directed graphs (DHC), finding Hamiltonian circuits in undirected graphs (UHC), and finding perfect matchings in undirected graphs (PM). We show that for each problem there is an algorithm that is extremely fast (0(n(log n) 2 ) for DHC and UHC, and 0(nlog n) for PM), and which with probability tending to one finds a solution in randomly chosen graphs of sufficient density. These results contrast with the known NP-completeness of the first two problems [2,12] and the best worst-case upper bound known of 0(n 2.5 ) for the last [9].