Buchumschlag

Transformers as Transducers

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Strobl, Lena, Angluin, Dana, Chiang, David, Rawski, Jonathan, Sabharwal, Ashish
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Formal Languages and Automata Theory Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Simulating Hard Attention Using Soft Attention
von: Yang, Andy, et al.
Veröffentlicht: (2024)

What Formal Languages Can Transformers Express? A Survey
von: Strobl, Lena, et al.
Veröffentlicht: (2023)

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
von: Yang, Andy, et al.
Veröffentlicht: (2023)

Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages
von: Angluin, Dana, et al.
Veröffentlicht: (2022)

Exact Expressive Power of Transformers with Padding
von: Merrill, William, et al.
Veröffentlicht: (2025)

Transformers in Uniform TC$^0$
von: Chiang, David
Veröffentlicht: (2024)

The Illusion of State in State-Space Models
von: Merrill, William, et al.
Veröffentlicht: (2024)

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't
von: Svete, Anej, et al.
Veröffentlicht: (2026)

Why Are Linear RNNs More Parallelizable?
von: Merrill, William, et al.
Veröffentlicht: (2026)

Reversible Pebble Transducers
von: Dartois, Luc, et al.
Veröffentlicht: (2025)

Approximate Problems for Finite Transducers
von: Filiot, Emmanuel, et al.
Veröffentlicht: (2025)

Finite-valued Streaming String Transducers
von: Filiot, Emmanuel, et al.
Veröffentlicht: (2024)

Attributed Tree Transducers for Partial Functions
von: Maneth, Sebastian, et al.
Veröffentlicht: (2024)

Reversible Transducers over Infinite Words
von: Dartois, Luc, et al.
Veröffentlicht: (2024)

Composing Copyless Streaming String Transducers
von: Alur, Rajeev, et al.
Veröffentlicht: (2022)

Partial Answer of How Transformers Learn Automata
von: Zhang, Tiantian
Veröffentlicht: (2025)

Minimizing Streaming String Transducers: An algebraic approach
von: Benalioua, Yahia Idriss, et al.
Veröffentlicht: (2026)

Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
von: Yang, Andy, et al.
Veröffentlicht: (2024)

Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids
von: Aristote, Quentin
Veröffentlicht: (2024)

Certified Symbolic Finite Transducers: Formalization and Applications to String Analysis
von: Kan, Shuanglong, et al.
Veröffentlicht: (2025)

A Regular and Complete Notion of Delay for Streaming String Transducers
von: Filiot, Emmanuel, et al.
Veröffentlicht: (2022)

Length Generalization Bounds for Transformers
von: Yang, Andy, et al.
Veröffentlicht: (2026)

Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers
von: Gallot, Paul, et al.
Veröffentlicht: (2023)

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

Transducing Language Models
von: Snæbjarnarson, Vésteinn, et al.
Veröffentlicht: (2026)

A Diamond Structure in the Transducer Hierarchy
von: Kaufmann, Noah
Veröffentlicht: (2021)

Knee-Deep in C-RASP: A Transformer Depth Hierarchy
von: Yang, Andy, et al.
Veröffentlicht: (2025)

The Counting Power of Transformers
von: Sälzer, Marco, et al.
Veröffentlicht: (2025)

Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination
von: Okudono, Takamasa, et al.
Veröffentlicht: (2024)

PDFA Distillation via String Probability Queries
von: Baumgartner, Robert, et al.
Veröffentlicht: (2024)

Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretation
von: Chen, Boqi, et al.
Veröffentlicht: (2024)

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

Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing
von: Kuriyama, Takayuki
Veröffentlicht: (2026)

Deconstructing Subset Construction -- Reducing While Determinizing
von: Nicol, John, et al.
Veröffentlicht: (2025)

Learning Reward Machines from Partially Observed Policies
von: Shehab, Mohamad Louai, et al.
Veröffentlicht: (2025)

Stochastic Alignments: Matching an Observed Trace to Stochastic Process Models
von: Li, Tian, et al.
Veröffentlicht: (2025)

A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks
von: Dhayalkar, Sahil Rajesh
Veröffentlicht: (2025)

Active Learning of Symbolic Automata Over Rational Numbers
von: Hagedorn, Sebastian, et al.
Veröffentlicht: (2025)

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

SMT-Based Active Learning of Weighted Automata
von: Ferreira, Tiago, et al.
Veröffentlicht: (2026)