Dana Angluin

Orcid: 0000-0002-6907-2999

Affiliations:
  • Yale University


According to our database1, Dana Angluin authored at least 98 papers between 1976 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
What Formal Languages Can Transformers Express? A Survey.
Trans. Assoc. Comput. Linguistics, 2024

Transformers as Transducers.
CoRR, 2024

2023
Transformers as Recognizers of Formal Languages: A Survey on Expressivity.
CoRR, 2023

Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages.
CoRR, 2023

Learning of Regular Languages by Recurrent Neural Networks? (Mainly Questions).
Proceedings of the International Conference on Grammatical Inference, 2023

2022
Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity.
Trans. Assoc. Comput. Linguistics, 2022

Representing Regular Languages of Infinite Words Using Mod 2 Multiplicity Automata.
Proceedings of the Foundations of Software Science and Computation Structures, 2022

2021
Regular <i>ω</i>-languages with an informative right congruence.
Inf. Comput., 2021

2020
The power of random counterexamples.
Theor. Comput. Sci., 2020

Polynomial time algorithms for inclusion and equivalence of deterministic omega acceptors.
CoRR, 2020

Polynomial Identification of ømega-Automata.
Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2020

Strongly Unambiguous Büchi Automata Are Polynomially Predictable With Membership Queries.
Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

2019
Query learning of derived ωω\omega-tree languages in polynomial time.
Log. Methods Comput. Sci., 2019

2018
Families of DFAs as Acceptors of ω-Regular Languages.
Log. Methods Comput. Sci., 2018

Regular omega-Languages with an Informative Right Congruence.
Proceedings of the Proceedings Ninth International Symposium on Games, 2018

Query learning of derived ω-tree languages in polynomial time.
CoRR, 2018

Context-Free Transductions with Neural Stacks.
Proceedings of the Workshop: Analyzing and Interpreting Neural Networks for NLP, 2018

2017
A model of language learning with semantics and meaning-preserving corrections.
Artif. Intell., 2017

Query Learning of Derived Omega-Tree Languages in Polynomial Time.
Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016
Learning regular omega languages.
Theor. Comput. Sci., 2016

Families of DFAs as Acceptors of omega-Regular Languages.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015
Network construction with subgraph connectivity constraints.
J. Comb. Optim., 2015

Learning Regular Languages via Alternating Automata.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Learning a Random DFA from Uniform Strings and State Information.
Proceedings of the Algorithmic Learning Theory - 26th International Conference, 2015

2014
Effective storage capacity of labeled graphs.
Inf. Comput., 2014

2013
On the learnability of shuffle ideals.
J. Mach. Learn. Res., 2013

Mutation systems.
Int. J. Comput. Math., 2013

Learning and verifying quantified boolean queries by example.
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

2012
On the Learnability of Shuffle Ideals.
Proceedings of the Algorithmic Learning Theory - 23rd International Conference, 2012

2011
An Overview of How Semantics and Corrections Can Help Language Learning.
Proceedings of the 2011 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, 2011

Effects of Meaning-Preserving Corrections on Language Learning.
Proceedings of the Fifteenth Conference on Computational Natural Language Learning, 2011

2010
Optimally learning social networks with activations and suppressions.
Theor. Comput. Sci., 2010

Storage Capacity of Labeled Graphs.
Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

Lower Bounds on Learning Random Structures with Statistical Queries.
Proceedings of the Algorithmic Learning Theory, 21st International Conference, 2010

Inferring Social Networks from Outbreaks.
Proceedings of the Algorithmic Learning Theory, 21st International Conference, 2010

2009
Learning Acyclic Probabilistic Circuits Using Test Paths.
J. Mach. Learn. Res., 2009

Learning a circuit by injecting values.
J. Comput. Syst. Sci., 2009

Learning Finite Automata Using Label Queries.
Proceedings of the Algorithmic Learning Theory, 20th International Conference, 2009

2008
Self-stabilizing population protocols.
ACM Trans. Auton. Adapt. Syst., 2008

Learning large-alphabet and analog circuits with value injection queries.
Mach. Learn., 2008

Learning a hidden graph using O(logn) queries per edge.
J. Comput. Syst. Sci., 2008

Fast computation by population protocols with a leader.
Distributed Comput., 2008

A simple population protocol for fast robust approximate majority.
Distributed Comput., 2008

Learning Meaning Before Syntax.
Proceedings of the Grammatical Inference: Algorithms and Applications, 2008

2007
The VC dimension of k-fold union.
Inf. Process. Lett., 2007

The computational power of population protocols.
Distributed Comput., 2007

2006
Learning a Hidden Hypergraph.
J. Mach. Learn. Res., 2006

Computation in networks of passively mobile finite-state sensors.
Distributed Comput., 2006

Stably computable predicates are semilinear.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

Stabilizing Consensus in Mobile Networks.
Proceedings of the Distributed Computing in Sensor Systems, 2006

2005
Fast construction of overlay networks.
Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

On the Power of Anonymous One-Way Communication.
Proceedings of the Principles of Distributed Systems, 9th International Conference, 2005

Stably Computable Properties of Network Graphs.
Proceedings of the Distributed Computing in Sensor Systems, 2005

2004
Queries revisited.
Theor. Comput. Sci., 2004

Learning and Mathematics.
Proceedings of the Grammatical Inference: Algorithms and Applications, 2004

Learning a Hidden Graph Using O(log n) Queries Per Edge.
Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003
Learning from Different Teachers.
Mach. Learn., 2003

2001
Robot localization in a grid.
Inf. Process. Lett., 2001

2000
Robot Navigation with Distance Queries.
SIAM J. Comput., 2000

1997
Malicious Omissions and Errors in Answers to Membership Queries.
Mach. Learn., 1997

Teachers, Learners and Black Boxes.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

Learning Markov Chains with Variable Memory Length from Noisy Output.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996
A 1996 Snapshot of Computational Learning Theory.
ACM Comput. Surv., 1996

Robot Navigation with Range Queries.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995
Inferring Finite Automata with Stochastic Output Functions and an Application to Map Learning.
Mach. Learn., 1995

When Won't Membership Queries Help?
J. Comput. Syst. Sci., 1995

1994
Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle.
Mach. Learn., 1994

Learning with Malicious Membership Queries and Exceptions (Extended Abstract).
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993
Learning Read-Once Formulas with Queries.
J. ACM, 1993

1992
Learning Conjunctions of Horn Clauses.
Mach. Learn., 1992

Computational Learning Theory: Survey and Selected Bibliography
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991
When Won't Membership Queries Help? (Extended Abstract)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Learning Monotone DNF with an Incomplete Membership Oracle.
Proceedings of the Fourth Annual Workshop on Computational Learning Theory, 1991

1990
Negative Results for Equivalence Queries.
Mach. Learn., 1990

Learning Conjunctions of Horn Clauses (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Learning Conjunctions of Horn Clauses (Abstract).
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989
Training Sequences.
Theor. Comput. Sci., 1989

Equivalence Queries and Approximate Fingerprints.
Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

1988
Learning With Hints.
Proceedings of the First Annual Workshop on Computational Learning Theory, 1988

1987
Learning Regular Sets from Queries and Counterexamples
Inf. Comput., November, 1987

Learning From Noisy Examples.
Mach. Learn., 1987

Queries and Concept Learning.
Mach. Learn., 1987

1984
Regular Prefix Relations.
Math. Syst. Theory, 1984

1983
Inductive Inference: Theory and Methods.
ACM Comput. Surv., 1983

1982
Inference of Reversible Languages.
J. ACM, 1982

Two Notions of Correctness and Their Relation to Testing.
Acta Informatica, 1982

1981
A Note on the Number of Queries Needed to Identify Regular Languages
Inf. Control., October, 1981

Finite common coverings of pairs of regular graphs.
J. Comb. Theory B, 1981

1980
Inductive Inference of Formal Languages from Positive Data
Inf. Control., May, 1980

On Counting Problems and the Polynomial-Time Hierarchy.
Theor. Comput. Sci., 1980

On Relativizing Auxiliary Pushdown Machines.
Math. Syst. Theory, 1980

Finding Patterns Common to a Set of Strings.
J. Comput. Syst. Sci., 1980

Local and Global Properties in Networks of Processors (Extended Abstract)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings.
J. Comput. Syst. Sci., 1979

A Note on a Construction of Margulis.
Inf. Process. Lett., 1979

Finding Patterns Common to a Set of Strings (Extended Abstract)
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978
On the Complexity of Minimum Inference of Regular Sets
Inf. Control., December, 1978

1976
The four Russians' algorithm for boolean matrix multiplication is optimal in its class.
SIGACT News, 1976


  Loading...