Cover Image

Algorithms for Weighted Pushdown Automata

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Butoi, Alexandra, DuSell, Brian, Vieira, Tim, Cotterell, Ryan, Chiang, David
Format:	Preprint
Published:	2022
Subjects:	Computation and Language
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Bearing Syntactic Fruit with Stack-Augmented Neural Networks
by: DuSell, Brian, et al.
Published: (2025)

Training Neural Networks as Recognizers of Formal Languages
by: Butoi, Alexandra, et al.
Published: (2024)

Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns
by: DuSell, Brian, et al.
Published: (2023)

On the Proper Treatment of Tokenization in Psycholinguistics
by: Giulianelli, Mario, et al.
Published: (2024)

The Foundations of Tokenization: Statistical and Computational Concerns
by: Gastaldi, Juan Luis, et al.
Published: (2024)

PILA: A Historical-Linguistic Dataset of Proto-Italic and Latin
by: Bothwell, Stephen, et al.
Published: (2024)

On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
by: Nowak, Franz, et al.
Published: (2024)

Information Locality as an Inductive Bias for Neural Language Models
by: Someya, Taiga, et al.
Published: (2025)

From Language Models over Tokens to Language Models over Characters
by: Vieira, Tim, et al.
Published: (2024)

Explorability in Pushdown Automata
by: Bedi, Ayaan, et al.
Published: (2025)

Language Models over Canonical Byte-Pair Encodings
by: Vieira, Tim, et al.
Published: (2025)

Pre$^3$: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation
by: Chen, Junyi, et al.
Published: (2025)

Visual Execution and Validation of Finite-State Machines and Pushdown Automata
by: Morazán, Marco T., et al.
Published: (2025)

The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
by: Yamakami, Tomoyuki
Published: (2021)

Better Estimation of the Kullback--Leibler Divergence Between Language Models
by: Amini, Afra, et al.
Published: (2025)

Direct Preference Optimization with an Offset
by: Amini, Afra, et al.
Published: (2024)

On the Proper Treatment of Units in Surprisal Theory
by: Kiegeland, Samuel, et al.
Published: (2026)

A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
by: Guha, Shibashis, et al.
Published: (2021)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

Automating the Analysis of Parsing Algorithms (and other Dynamic Programs)
by: Vieira, Tim, et al.
Published: (2025)

An $\mathbf{L^*}$ Algorithm for Deterministic Weighted Regular Languages
by: Pasti, Clemente, et al.
Published: (2024)

Syntactic Control of Language Models by Posterior Inference
by: Xefteri, Vicky, et al.
Published: (2025)

Variational Best-of-N Alignment
by: Amini, Afra, et al.
Published: (2024)

Input-Driven Pushdown Automata with Translucent Input Letters
by: Kutrib, Martin, et al.
Published: (2025)

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

Prefix Parsing is Just Parsing
by: Pasti, Clemente, et al.
Published: (2026)

Structured Voronoi Sampling
by: Amini, Afra, et al.
Published: (2023)

Characterizing the Expressivity of Local Attention in Transformers
by: Li, Jiaoda, et al.
Published: (2026)

Exact Hard Monotonic Attention for Character-Level Transduction
by: Wu, Shijie, et al.
Published: (2019)

Low-Resource Named Entity Recognition with Cross-Lingual, Character-Level Neural Conditional Random Fields
by: Cotterell, Ryan, et al.
Published: (2024)

Cross-lingual, Character-Level Neural Morphological Tagging
by: Cotterell, Ryan, et al.
Published: (2017)

Characterizing the Expressivity of Fixed-Precision Transformer Language Models
by: Li, Jiaoda, et al.
Published: (2025)

A Formal Perspective on Byte-Pair Encoding
by: Zouhar, Vilém, et al.
Published: (2023)

Efficiently Computing Susceptibility to Context in Language Models
by: Liu, Tianyu, et al.
Published: (2024)

Transformers Can Represent $n$-gram Language Models
by: Svete, Anej, et al.
Published: (2024)

Exploring the Linear Subspace Hypothesis in Gender Bias Mitigation
by: Vargas, Francisco, et al.
Published: (2020)

Towards Explainability in Legal Outcome Prediction Models
by: Valvoda, Josef, et al.
Published: (2024)

Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing
by: Vieira, Tim
Published: (2026)

On the Representational Capacity of Recurrent Neural Language Models
by: Nowak, Franz, et al.
Published: (2023)

Probability Distributions Computed by Autoregressive Transformers
by: Yang, Andy, et al.
Published: (2025)