:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Strobl, Lena, Angluin, Dana, Chiang, David, Rawski, Jonathan, Sabharwal, Ashish
Format:	Preprint
Published:	2024
Subjects:	Formal Languages and Automata Theory Machine Learning
Online Access:	https://arxiv.org/abs/2404.02040
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Simulating Hard Attention Using Soft Attention
by: Yang, Andy, et al.
Published: (2024)

What Formal Languages Can Transformers Express? A Survey
by: Strobl, Lena, et al.
Published: (2023)

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
by: Yang, Andy, et al.
Published: (2023)

Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages
by: Angluin, Dana, et al.
Published: (2022)

Exact Expressive Power of Transformers with Padding
by: Merrill, William, et al.
Published: (2025)

The Illusion of State in State-Space Models
by: Merrill, William, et al.
Published: (2024)

Transformers in Uniform TC$^0$
by: Chiang, David
Published: (2024)

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't
by: Svete, Anej, et al.
Published: (2026)

Why Are Linear RNNs More Parallelizable?
by: Merrill, William, et al.
Published: (2026)

Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
by: Yang, Andy, et al.
Published: (2024)

Reversible Pebble Transducers
by: Dartois, Luc, et al.
Published: (2025)

Length Generalization Bounds for Transformers
by: Yang, Andy, et al.
Published: (2026)

Approximate Problems for Finite Transducers
by: Filiot, Emmanuel, et al.
Published: (2025)

Partial Answer of How Transformers Learn Automata
by: Zhang, Tiantian
Published: (2025)

Finite-valued Streaming String Transducers
by: Filiot, Emmanuel, et al.
Published: (2024)

Attributed Tree Transducers for Partial Functions
by: Maneth, Sebastian, et al.
Published: (2024)

Reversible Transducers over Infinite Words
by: Dartois, Luc, et al.
Published: (2024)

Composing Copyless Streaming String Transducers
by: Alur, Rajeev, et al.
Published: (2022)

Minimizing Streaming String Transducers: An algebraic approach
by: Benalioua, Yahia Idriss, et al.
Published: (2026)

Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids
by: Aristote, Quentin
Published: (2024)

Transducing Language Models
by: Snæbjarnarson, Vésteinn, et al.
Published: (2026)

Certified Symbolic Finite Transducers: Formalization and Applications to String Analysis
by: Kan, Shuanglong, et al.
Published: (2025)

A Regular and Complete Notion of Delay for Streaming String Transducers
by: Filiot, Emmanuel, et al.
Published: (2022)

The Counting Power of Transformers
by: Sälzer, Marco, et al.
Published: (2025)

Knee-Deep in C-RASP: A Transformer Depth Hierarchy
by: Yang, Andy, et al.
Published: (2025)

Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers
by: Gallot, Paul, et al.
Published: (2023)

Deciding whether an Attributed Translation can be realized by a Top-Down Transducer
by: Maneth, Sebastian, et al.
Published: (2023)

A Diamond Structure in the Transducer Hierarchy
by: Kaufmann, Noah
Published: (2021)

Sampling from Your Language Model One Byte at a Time
by: Hayase, Jonathan, et al.
Published: (2025)

Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination
by: Okudono, Takamasa, et al.
Published: (2024)

PDFA Distillation via String Probability Queries
by: Baumgartner, Robert, et al.
Published: (2024)

Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretation
by: Chen, Boqi, et al.
Published: (2024)

Extending AALpy with Passive Learning: A Generalized State-Merging Approach
by: von Berg, Benjamin, et al.
Published: (2025)

Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing
by: Kuriyama, Takayuki
Published: (2026)

Deconstructing Subset Construction -- Reducing While Determinizing
by: Nicol, John, et al.
Published: (2025)

Learning Reward Machines from Partially Observed Policies
by: Shehab, Mohamad Louai, et al.
Published: (2025)

Stochastic Alignments: Matching an Observed Trace to Stochastic Process Models
by: Li, Tian, et al.
Published: (2025)

A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks
by: Dhayalkar, Sahil Rajesh
Published: (2025)

Active Learning of Symbolic Automata Over Rational Numbers
by: Hagedorn, Sebastian, et al.
Published: (2025)

Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete
by: Dumitru, Radu Cosmin, et al.
Published: (2026)