Cover Image

Locality Testing for NFAs is PSPACE-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Amarilli, Antoine, Monet, Mikaël, De Pretto, Rémi
Format:	Preprint
Published:	2025
Subjects:	Formal Languages and Automata Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Complexity of Language Membership for Probabilistic Words
by: Amarilli, Antoine, et al.
Published: (2025)

Locality and Centrality: The Variety ZG
by: Amarilli, Antoine, et al.
Published: (2021)

RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems
by: Jin, Hyundong, et al.
Published: (2025)

A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata
by: Amarilli, Antoine, et al.
Published: (2024)

Skyline Operators for Document Spanners
by: Amarilli, Antoine, et al.
Published: (2023)

Constant-Time Dynamic Enumeration of Word Infixes in a Regular Language
by: Amarilli, Antoine, et al.
Published: (2026)

Out-of-Order Membership in Regular Languages
by: Amarilli, Antoine, et al.
Published: (2026)

Dynamic Membership for Regular Tree Languages
by: Amarilli, Antoine, et al.
Published: (2025)

Linear Time Subsequence and Supersequence Regex Matching
by: Amarilli, Antoine, et al.
Published: (2025)

A Dichotomy Theorem for Automatic Structures
by: Cuvelier, Antoine, et al.
Published: (2026)

The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
by: Daviaud, Laure, et al.
Published: (2023)

Controller Synthesis for Parametric Timed Games
by: Dahlsen-Jensen, Mikael Bisgaard, et al.
Published: (2025)

On-The-Fly Algorithm for Reachability in Parametric Timed Games (Extended Version)
by: Dahlsen-Jensen, Mikael Bisgaard, et al.
Published: (2024)

Random Testing of Model Checkers for Timed Automata with Automated Oracle Generation
by: Manini, Andrea, et al.
Published: (2025)

Black-box Testing Liveness Properties of Partially Observable Stochastic Systems
by: Esparza, Javier, et al.
Published: (2023)

Finite maximal codes and factorizations of cyclic groups
by: De Felice, Clelia
Published: (2022)

Designing and Comparing RPQ Semantics
by: Marsault, Victor, et al.
Published: (2026)

GrappaRE -- A Tool for Efficient Graph Recognition Based on Finite Automata and Regular Expressions
by: De Rosa, Mattia, et al.
Published: (2025)

A Probabilistic Model-Checking Framework for Cognitive Assessment and Training
by: De Maria, Elisabetta, et al.
Published: (2026)

Hyper-Minimization for Deterministic Register Automata
by: Li, Yong, et al.
Published: (2026)

Unveiling the connection between the Lyndon factorization and the Canonical Inverse Lyndon factorization via a border property
by: Bonizzoni, Paola, et al.
Published: (2024)

Resolving Nondeterminism by Chance
by: Paul, Soumyajit, et al.
Published: (2025)

Word-Representable Graphs and Locality of Words
by: Böll, Philipp, et al.
Published: (2025)

The Algebras for Automatic Relations
by: Morvan, Rémi
Published: (2024)

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

A General Information Extraction Framework Based on Formal Languages
by: Schmid, Markus L.
Published: (2025)

Statistical process discovery
by: Cry, Pierre, et al.
Published: (2025)

Reasoning about Rare-Event Reachability in Stochastic Vector Addition Systems via Affine Vector Spaces
by: Jeppson, Joshua, et al.
Published: (2025)

Hyper pattern matching
by: Waga, Masaki, et al.
Published: (2025)

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

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

Componentwise Automata Learning for System Integration (Extended Version)
by: Fujinami, Hiroya, et al.
Published: (2025)

Universality Frontier for Asynchronous Cellular Automata
by: Baburin, Ivan, et al.
Published: (2025)

Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata
by: Mazowiecki, Filip, et al.
Published: (2025)

Frequency Automata: A novel formal model of hybrid systems in combined time and frequency domains
by: Kim, Moon, et al.
Published: (2025)

Castor Ministerialis
by: Hercher, Christian
Published: (2025)

Semiflows, Home Spaces, and Home States, Applications to the Analysis of Parameterized Petri Nets
by: Memmi, Gerard
Published: (2025)

Unambiguisability and Register Minimisation of Min-Plus Models
by: Almagor, Shaull, et al.
Published: (2025)

Passive Learning of Lattice Automata from Recurrent Neural Networks
by: Slimi, Jaouhar, et al.
Published: (2025)

An Automata-Based Method to Formalize Psychological Theories -- The Case Study of Lazarus and Folkman's Stress Theory
by: Finkel, Alain, et al.
Published: (2025)