Cover Image

Prefix Parsing is Just Parsing

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pasti, Clemente, Opedal, Andreas, O'Donnell, Timothy J., Cotterell, Ryan, Vieira, Tim
Format:	Preprint
Published:	2026
Subjects:	Computation and Language Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Computational Model for Parsing Expression Grammars
by: Rubtsov, Alexander, et al.
Published: (2024)

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

A Fast Algorithm for Computing Prefix Probabilities
by: Nowak, Franz, et al.
Published: (2023)

A Close Analysis of the Subset Construction
by: Baburin, Ivan, et al.
Published: (2024)

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

Integrating Supertag Features into Neural Discontinuous Constituent Parsing
by: Mielczarek, Lukas
Published: (2024)

An Algebraic View of the Expressivity of Recurrent Language Models
by: Nowak, Franz, et al.
Published: (2026)

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

A GLR-like Parsing Algorithm for Three-Valued Interpretations of Boolean Grammars with Strong Negation
by: Adrián, Patrik, et al.
Published: (2024)

Commutative algebras of series
by: Clemente, Lorenzo
Published: (2026)

Unique Hard Attention: A Tale of Two Sides
by: Jerad, Selim, et al.
Published: (2025)

Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
by: Kociumaka, Tomasz, et al.
Published: (2014)

Cost Automata, Safe Schemes, and Downward Closures
by: Barozzini, David, et al.
Published: (2020)

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

Context-Free Recognition with Transformers
by: Jerad, Selim, et al.
Published: (2026)

Inform: From Compartmental Models to Stochastic Bounded Counter Machines
by: Leys, Tim, et al.
Published: (2024)

Transformers are Inherently Succinct
by: Bergsträßer, Pascal, et al.
Published: (2025)

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

Benchmarking Testing in Automated Theorem Proving
by: Kim, Jongyoon, et al.
Published: (2026)

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems
by: Roop, Partha, et al.
Published: (2026)

Autoformalization in the Wild: Assessing LLMs on Real-World Mathematical Definitions
by: Zhang, Lan, et al.
Published: (2025)

LangSAT: A Novel Framework Combining NLP and Reinforcement Learning for SAT Solving
by: Pan, Muyu, et al.
Published: (2025)

Consistent Autoformalization for Constructing Mathematical Libraries
by: Zhang, Lan, et al.
Published: (2024)

Directed Regular and Context-Free Languages
by: Ganardi, Moses, et al.
Published: (2024)

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

A Bionic Natural Language Parser Equivalent to a Pushdown Automaton
by: Wei, Zhenghao, et al.
Published: (2024)

Comparing Spoken Languages using Paninian System of Sounds and Finite State Machines
by: Prabhu, Shreekanth M, et al.
Published: (2023)

Recursive numeral systems are highly regular and easy to process
by: Prasertsom, Ponrawee, et al.
Published: (2025)

Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Length
by: Lan, Nur, et al.
Published: (2024)

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

Reachability in symmetric VASS
by: Kamiński, Łukasz, et al.
Published: (2025)

Tutorial: $φ$-Transductions in OpenFst via the Gallic Semiring
by: Cognetta, Marco, et al.
Published: (2025)

Self-Replicating Mechanical Universal Turing Machine
by: Lano, Ralph P.
Published: (2024)

Automata-based constraints for language model decoding
by: Koo, Terry, et al.
Published: (2024)

Cluster automata
by: Kornai, András
Published: (2025)

A* shortest string decoding for non-idempotent semirings
by: Gorman, Kyle, et al.
Published: (2022)

TuringQ: Benchmarking AI Comprehension in Theory of Computation
by: Zahraei, Pardis Sadat, et al.
Published: (2024)

Tokenization as Finite-State Transduction
by: Cognetta, Marco, et al.
Published: (2024)

MASA: LLM-Driven Multi-Agent Systems for Autoformalization
by: Zhang, Lan, et al.
Published: (2025)