Dana Angluin

According to our database, Dana Angluin authored at least 99 papers between 1976 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

What Formal Languages Can Transformers Express? A Survey.

Lena Strobl, William Merrill, Gail Weiss, David Chiang, Dana Angluin

Trans. Assoc. Comput. Linguistics, 2024

Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages.

Dana Angluin, Dana Fisman

Log. Methods Comput. Sci., 2024

Transformers as Transducers.

Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, Ashish Sabharwal

CoRR, 2024

2023

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

Lena Strobl, William Merrill, Gail Weiss, David Chiang, Dana Angluin

CoRR, 2023

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

Dana Angluin, David Chiang, Andy Yang

CoRR, 2023

Learning of Regular Languages by Recurrent Neural Networks? (Mainly Questions).

Dana Angluin

Proceedings of the International Conference on Grammatical Inference, 2023

2022

Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity.

Yiding Hao, Dana Angluin, Robert Frank

Trans. Assoc. Comput. Linguistics, 2022

Representing Regular Languages of Infinite Words Using Mod 2 Multiplicity Automata.

Dana Angluin, Timos Antonopoulos, Dana Fisman, Nevin George

Proceedings of the Foundations of Software Science and Computation Structures, 2022

2021

Regular <i>ω</i>-languages with an informative right congruence.

Dana Angluin, Dana Fisman

Inf. Comput., 2021

2020

The power of random counterexamples.

Dana Angluin, Tyler Dohrn

Theor. Comput. Sci., 2020

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

Dana Angluin, Dana Fisman

CoRR, 2020

Polynomial Identification of ømega-Automata.

Dana Angluin, Dana Fisman, Yaara Shoval

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.

Dana Angluin, Timos Antonopoulos, Dana Fisman

Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

2019

Query learning of derived ωω\omega-tree languages in polynomial time.

Dana Angluin, Timos Antonopoulos, Dana Fisman

Log. Methods Comput. Sci., 2019

2018

Families of DFAs as Acceptors of ω-Regular Languages.

Dana Angluin, Udi Boker, Dana Fisman

Log. Methods Comput. Sci., 2018

Regular omega-Languages with an Informative Right Congruence.

Dana Angluin, Dana Fisman

Proceedings of the Proceedings Ninth International Symposium on Games, 2018

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

Dana Angluin, Timos Antonopoulos, Dana Fisman

CoRR, 2018

Context-Free Transductions with Neural Stacks.

Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel, Andrew Benz, Simon Mendelsohn

Proceedings of the Workshop: Analyzing and Interpreting Neural Networks for NLP, 2018

2017

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

Dana Angluin, Leonor Becerra-Bonache

Artif. Intell., 2017

Query Learning of Derived Omega-Tree Languages in Polynomial Time.

Dana Angluin, Timos Antonopoulos, Dana Fisman

Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016

Learning regular omega languages.

Dana Angluin, Dana Fisman

Theor. Comput. Sci., 2016

Families of DFAs as Acceptors of omega-Regular Languages.

Dana Angluin, Udi Boker, Dana Fisman

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

Network construction with subgraph connectivity constraints.

Dana Angluin, James Aspnes, Lev Reyzin

J. Comb. Optim., 2015

Learning Regular Languages via Alternating Automata.

Dana Angluin, Sarah Eisenstat, Dana Fisman

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Learning a Random DFA from Uniform Strings and State Information.

Dana Angluin, Dongqu Chen

Proceedings of the Algorithmic Learning Theory - 26th International Conference, 2015

2014

Effective storage capacity of labeled graphs.

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

Inf. Comput., 2014

2013

On the learnability of shuffle ideals.

Dana Angluin, James Aspnes, Sarah Eisenstat, Aryeh Kontorovich

J. Mach. Learn. Res., 2013

Mutation systems.

Dana Angluin, James Aspnes, Raonne Barbosa Vargas

Int. J. Comput. Math., 2013

Learning and verifying quantified boolean queries by example.

Azza Abouzied, Dana Angluin, Christos H. Papadimitriou, Joseph M. Hellerstein, Avi Silberschatz

Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

2012

On the Learnability of Shuffle Ideals.

Dana Angluin, James Aspnes, Aryeh Kontorovich

Proceedings of the Algorithmic Learning Theory - 23rd International Conference, 2012

2011

An Overview of How Semantics and Corrections Can Help Language Learning.

Dana Angluin, Leonor Becerra-Bonache

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.

Dana Angluin, Leonor Becerra-Bonache

Proceedings of the Fifteenth Conference on Computational Natural Language Learning, 2011

2010

Optimally learning social networks with activations and suppressions.

Dana Angluin, James Aspnes, Lev Reyzin

Theor. Comput. Sci., 2010

Storage Capacity of Labeled Graphs.

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

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

Lower Bounds on Learning Random Structures with Statistical Queries.

Dana Angluin, David Eisenstat, Leonid Kontorovich, Lev Reyzin

Proceedings of the Algorithmic Learning Theory, 21st International Conference, 2010

Inferring Social Networks from Outbreaks.

Dana Angluin, James Aspnes, Lev Reyzin

Proceedings of the Algorithmic Learning Theory, 21st International Conference, 2010

2009

Learning Acyclic Probabilistic Circuits Using Test Paths.

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

J. Mach. Learn. Res., 2009

Learning a circuit by injecting values.

Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu

J. Comput. Syst. Sci., 2009

Learning Finite Automata Using Label Queries.

Dana Angluin, Leonor Becerra-Bonache, Adrian-Horia Dediu, Lev Reyzin

Proceedings of the Algorithmic Learning Theory, 20th International Conference, 2009

2008

Self-stabilizing population protocols.

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

ACM Trans. Auton. Adapt. Syst., 2008

Learning large-alphabet and analog circuits with value injection queries.

Dana Angluin, James Aspnes, Jiang Chen, Lev Reyzin

Mach. Learn., 2008

Learning a hidden graph using O(logn) queries per edge.

Dana Angluin, Jiang Chen

J. Comput. Syst. Sci., 2008

Fast computation by population protocols with a leader.

Dana Angluin, James Aspnes, David Eisenstat

Distributed Comput., 2008

A simple population protocol for fast robust approximate majority.

Dana Angluin, James Aspnes, David Eisenstat

Distributed Comput., 2008

Learning Meaning Before Syntax.

Dana Angluin, Leonor Becerra-Bonache

Proceedings of the Grammatical Inference: Algorithms and Applications, 2008

2007

The VC dimension of k-fold union.

David Eisenstat, Dana Angluin

Inf. Process. Lett., 2007

The computational power of population protocols.

Dana Angluin, James Aspnes, David Eisenstat, Eric Ruppert

Distributed Comput., 2007

2006

Learning a Hidden Hypergraph.

Dana Angluin, Jiang Chen

J. Mach. Learn. Res., 2006

Computation in networks of passively mobile finite-state sensors.

Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, René Peralta

Distributed Comput., 2006

Stably computable predicates are semilinear.

Dana Angluin, James Aspnes, David Eisenstat

Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

Stabilizing Consensus in Mobile Networks.

Dana Angluin, Michael J. Fischer, Hong Jiang

Proceedings of the Distributed Computing in Sensor Systems, 2006

2005

Fast construction of overlay networks.

Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu, Yitong Yin

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.

Dana Angluin, James Aspnes, David Eisenstat, Eric Ruppert

Proceedings of the Principles of Distributed Systems, 9th International Conference, 2005

Stably Computable Properties of Network Graphs.

Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, Hong Jiang, René Peralta

Proceedings of the Distributed Computing in Sensor Systems, 2005

2004

Queries revisited.

Dana Angluin

Theor. Comput. Sci., 2004

Learning and Mathematics.

Dana Angluin

Proceedings of the Grammatical Inference: Algorithms and Applications, 2004

Learning a Hidden Graph Using O(log n) Queries Per Edge.

Dana Angluin, Jiang Chen

Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003

Learning from Different Teachers.

Dana Angluin, Martins Krikis

Mach. Learn., 2003

2001

Robot localization in a grid.

Chinda Wongngamnit, Dana Angluin

Inf. Process. Lett., 2001

2000

Robot Navigation with Distance Queries.

Dana Angluin, Jeffery R. Westbrook, Wenhong Zhu

SIAM J. Comput., 2000

1997

Malicious Omissions and Errors in Answers to Membership Queries.

Dana Angluin, Martins Krikis, Robert H. Sloan, György Turán

Mach. Learn., 1997

Teachers, Learners and Black Boxes.

Dana Angluin, Martins Krikis

Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

Learning Markov Chains with Variable Memory Length from Noisy Output.

Dana Angluin, Miklós Csürös

Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996

A 1996 Snapshot of Computational Learning Theory.

Dana Angluin

ACM Comput. Surv., 1996

Robot Navigation with Range Queries.

Dana Angluin, Jeffery R. Westbrook, Wenhong Zhu

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.

Thomas L. Dean, Dana Angluin, Kenneth Basye, Sean P. Engelson, Leslie Pack Kaelbling, Evangelos Kokkevis, Oded Maron

Mach. Learn., 1995

When Won't Membership Queries Help?

Dana Angluin, Michael Kharitonov

J. Comput. Syst. Sci., 1995

1994

Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle.

Dana Angluin, Donna K. Slonim

Mach. Learn., 1994

Learning with Malicious Membership Queries and Exceptions (Extended Abstract).

Dana Angluin, Martins Krikis

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993

Learning Read-Once Formulas with Queries.

Dana Angluin, Lisa Hellerstein, Marek Karpinski

J. ACM, 1993

1992

Learning Conjunctions of Horn Clauses.

Dana Angluin, Michael Frazier, Leonard Pitt

Mach. Learn., 1992

Computational Learning Theory: Survey and Selected Bibliography

Dana Angluin

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

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

Dana Angluin, Michael Kharitonov

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Learning Monotone DNF with an Incomplete Membership Oracle.

Dana Angluin, Donna K. Slonim

Proceedings of the Fourth Annual Workshop on Computational Learning Theory, 1991

1990

Negative Results for Equivalence Queries.

Dana Angluin

Mach. Learn., 1990

Learning Conjunctions of Horn Clauses (Extended Abstract)

Dana Angluin, Michael Frazier, Leonard Pitt

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Learning Conjunctions of Horn Clauses (Abstract).

Dana Angluin, Michael Frazier, Leonard Pitt

Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989

Training Sequences.

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

Theor. Comput. Sci., 1989

Equivalence Queries and Approximate Fingerprints.

Dana Angluin

Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

1988

Learning With Hints.

Dana Angluin

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

1987

Learning Regular Sets from Queries and Counterexamples

Dana Angluin

Inf. Comput., November, 1987

Learning From Noisy Examples.

Dana Angluin, Philip D. Laird

Mach. Learn., 1987

Queries and Concept Learning.

Dana Angluin

Mach. Learn., 1987

1984

Regular Prefix Relations.

Dana Angluin, Douglas N. Hoover

Math. Syst. Theory, 1984

1983

Inductive Inference: Theory and Methods.

Dana Angluin, Carl H. Smith

ACM Comput. Surv., 1983

1982

Inference of Reversible Languages.

Dana Angluin

J. ACM, 1982

Two Notions of Correctness and Their Relation to Testing.

Timothy A. Budd, Dana Angluin

Acta Informatica, 1982

1981

A Note on the Number of Queries Needed to Identify Regular Languages

Dana Angluin

Inf. Control., October, 1981

Finite common coverings of pairs of regular graphs.

Dana Angluin, A. Gardiner

J. Comb. Theory B, 1981

1980

Inductive Inference of Formal Languages from Positive Data

Dana Angluin

Inf. Control., May, 1980

On Counting Problems and the Polynomial-Time Hierarchy.

Dana Angluin

Theor. Comput. Sci., 1980

On Relativizing Auxiliary Pushdown Machines.

Dana Angluin

Math. Syst. Theory, 1980

Finding Patterns Common to a Set of Strings.

Dana Angluin

J. Comput. Syst. Sci., 1980

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

Dana Angluin

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979

Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings.

Dana Angluin, Leslie G. Valiant

J. Comput. Syst. Sci., 1979

A Note on a Construction of Margulis.

Dana Angluin

Inf. Process. Lett., 1979

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

Dana Angluin

Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978

On the Complexity of Minimum Inference of Regular Sets

Dana Angluin

Inf. Control., December, 1978

1976

The four Russians' algorithm for boolean matrix multiplication is optimal in its class.

Dana Angluin

SIGACT News, 1976