A Close Analysis of the Subset Construction

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Baburin, Ivan, Cotterell, Ryan
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Formal Languages and Automata Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Universality Frontier for Asynchronous Cellular Automata
von: Baburin, Ivan, et al.
Veröffentlicht: (2025)

On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning
von: Nowak, Franz, et al.
Veröffentlicht: (2024)

A Fast Algorithm for Computing Prefix Probabilities
von: Nowak, Franz, et al.
Veröffentlicht: (2023)

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

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

Prefix Parsing is Just Parsing
von: Pasti, Clemente, et al.
Veröffentlicht: (2026)

An Algebraic View of the Expressivity of Recurrent Language Models
von: Nowak, Franz, et al.
Veröffentlicht: (2026)

Idefix-Closed Languages and Their Application in Contextual Grammars
von: Ködding, Marvin, et al.
Veröffentlicht: (2025)

The Power-Set Construction for Tree Algebras
von: Blumensath, Achim
Veröffentlicht: (2022)

Regular Expressions with Backreferences on Multiple Context-Free Languages, and the Closed-Star Condition
von: Nogami, Taisei, et al.
Veröffentlicht: (2024)

Efficient Constructions of Finite-State Independent Normal Pairs
von: Pulari, Subin
Veröffentlicht: (2026)

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

Constructing Deterministic Parity Automata from Positive and Negative Examples
von: Bohn, León, et al.
Veröffentlicht: (2023)

Efficient Construction of Reachability Graphs for Petri Net Product Lines
von: Gómez-Martínez, Elena, et al.
Veröffentlicht: (2026)

Conservative Perception Models for Probabilistic Verification
von: Cleaveland, Matthew, et al.
Veröffentlicht: (2025)

Efficient Analysis of Polynomial Asymptotic Estimates for VASS MDPs
von: Ajdarów, Michal
Veröffentlicht: (2025)

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

Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
von: Kiefer, Stefan, et al.
Veröffentlicht: (2019)

Formalized Run-Time Analysis of Active Learning -- Coalgebraically in Agda
von: Wißmann, Thorsten
Veröffentlicht: (2026)

Static Analysis Framework for Detecting Use-After-Free Bugs in C++
von: Teodorescu, Vlad-Alexandru, et al.
Veröffentlicht: (2024)

Vulnerabilities Analysis and Secure Controlling for Unmanned Aerial System Based on Reactive Synthesis
von: Yang, Dong, et al.
Veröffentlicht: (2024)

Semiflows, Home Spaces, and Home States, Applications to the Analysis of Parameterized Petri Nets
von: Memmi, Gerard
Veröffentlicht: (2025)

Consistent Autoformalization for Constructing Mathematical Libraries
von: Zhang, Lan, et al.
Veröffentlicht: (2024)

Unique Hard Attention: A Tale of Two Sides
von: Jerad, Selim, et al.
Veröffentlicht: (2025)

Transformers are Inherently Succinct
von: Bergsträßer, Pascal, et al.
Veröffentlicht: (2025)

Corrections to A Menagerie of Timed Automata
von: Keiren, Jeroen J. A., et al.
Veröffentlicht: (2016)

A Unifying Approach to Picture Automata
von: Meeres, Yvo Ad, et al.
Veröffentlicht: (2025)

A Variety of Request-Response Specifications
von: Aiba, Daichi, et al.
Veröffentlicht: (2025)

A Factorization Theorem for Forest Algebras
von: Almagor, Shaull, et al.
Veröffentlicht: (2026)

A model of actors and grey failures
von: Bocchi, Laura, et al.
Veröffentlicht: (2022)

A Formal Approach for Tuning Stochastic Oscillators
von: Ballarini, Paolo, et al.
Veröffentlicht: (2024)

A Tree Sampler for Bounded Context-Free Languages
von: Considine, Breandan
Veröffentlicht: (2024)

FocusE: A semantic extension of FocusST
von: Spichkova, Maria
Veröffentlicht: (2025)

A General Information Extraction Framework Based on Formal Languages
von: Schmid, Markus L.
Veröffentlicht: (2025)

A Linear-time Simulation of Deterministic $d$-Limited Automata
von: Rubtsov, Alexander
Veröffentlicht: (2023)

A pumping-like lemma for languages over infinite alphabets
von: Danieli, Yoav
Veröffentlicht: (2025)

A Probabilistic Model-Checking Framework for Cognitive Assessment and Training
von: De Maria, Elisabetta, et al.
Veröffentlicht: (2026)

A Characterization of Turing Machines that Compute Primitive Recursive Functions
von: Schwartz, Daniel G.
Veröffentlicht: (2025)

A Usage-Aware Sequent Calculus for Differential Dynamic Logic
von: Dotzel, Myra, et al.
Veröffentlicht: (2023)

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