Imagen de Portada

NL Is Strictly Contained in P

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Flum, Santiago, Montoya, J. Andres
Formato:	Preprint
Publicado:	2023
Materias:	Formal Languages and Automata Theory 03D15
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Run supports and initial algebra supports of weighted automata
por: Droste, Manfred, et al.
Publicado: (2024)

Sparse regular subsets of the reals
por: Bell, Jason, et al.
Publicado: (2023)

A Dichotomy for $k$-automatic expansions of Presburger Arithmetic
por: Bell, Jason, et al.
Publicado: (2025)

Entropy of pebble automata and space complexity
por: Montoya, J. Andres
Publicado: (2026)

Languages given by Finite Automata over the Unary Alphabet
por: Czerwiński, Wojciech, et al.
Publicado: (2023)

Characterizing normality via automata and random matrix products
por: Bienvenu, Laurent, et al.
Publicado: (2026)

On the Intersection Problem for Quantum Finite Automata
por: Benso, Andrea, et al.
Publicado: (2024)

The Polynomial Hierarchy does not collapse
por: Czerwinski, Reiner
Publicado: (2024)

Bridging Chaos Game Representations and $k$-mer Frequencies of DNA Sequences
por: He, Haoze, et al.
Publicado: (2025)

Descriptional Complexity of Finite Automata -- Selected Highlights
por: Salomaa, Arto, et al.
Publicado: (2023)

Corrections to A Menagerie of Timed Automata
por: Keiren, Jeroen J. A., et al.
Publicado: (2016)

Subword enumeration up to stack-sorting equivalence
por: Campbell, John M., et al.
Publicado: (2026)

Low complexity binary words avoiding $(5/2)^+$-powers
por: Currie, James, et al.
Publicado: (2025)

Computing the k-binomial complexity of generalized Thue--Morse words
por: Golafshan, M., et al.
Publicado: (2024)

Mapping words to powers by morphisms
por: Saarela, Aleksi
Publicado: (2025)

A Connection Between Unbordered Partial Words and Sparse Rulers
por: Saarela, Aleksi, et al.
Publicado: (2024)

Mapped Exponent and Asymptotic Critical Exponent of Words
por: Foster, Eva, et al.
Publicado: (2025)

Group Actions and Some Combinatorics on Words with $\mathbf{vtm}$
por: Machacek, John
Publicado: (2025)

The Shortest Interesting Binary Words
por: Fici, Gabriele
Publicado: (2024)

Mining Diamonds in labeled Transition Systems
por: van Spaendonck, P. H. M., et al.
Publicado: (2025)

Stratifiable formulae are not context-free
por: Ryan-Smith, Calliope
Publicado: (2023)

Multidimensional tilings and MSO logic
por: Pallen, Rémi, et al.
Publicado: (2025)

Rauzy dimension and finite-state dimension
por: Becher, Verónica, et al.
Publicado: (2024)

On Some Complexity Results for Even Linear Languages
por: Cojocaru, Liliana
Publicado: (2024)

The Expansion Problem for Infinite Trees
por: Blumensath, Achim
Publicado: (2023)

Mata, a Fast and Simple Finite Automata Library (Technical Report)
por: Chocholatý, David, et al.
Publicado: (2023)

Simulation Limitations of Affine Cellular Automata
por: Hudcová, Barbora, et al.
Publicado: (2023)

On the Expressive Power of Regular Expressions with Backreferences
por: Nogami, Taisei, et al.
Publicado: (2023)

Safety and Liveness of Quantitative Properties and Automata
por: Boker, Udi, et al.
Publicado: (2023)

Note on dissecting power of regular languages
por: Rukavicka, Josef
Publicado: (2023)

Optimal Approximate Minimization of One-Letter Weighted Finite Automata
por: Lacroce, Clara, et al.
Publicado: (2023)

Checking History-Determinism is NP-hard for Parity Automata
por: Prakash, Keya
Publicado: (2023)

Closure Properties of General Grammars -- Formally Verified
por: Dvorak, Martin, et al.
Publicado: (2023)

A Linear-time Simulation of Deterministic $d$-Limited Automata
por: Rubtsov, Alexander
Publicado: (2023)

Reset thresholds of transformation monoids
por: Rystsov, Igor, et al.
Publicado: (2023)

Closure and Decision Properties for Higher-Dimensional Automata
por: Amrane, Amazigh, et al.
Publicado: (2023)

Deciding Linear Height and Linear Size-to-Height Increase for Macro Tree Transducers
por: Gallot, Paul, et al.
Publicado: (2023)

Constructing Deterministic Parity Automata from Positive and Negative Examples
por: Bohn, León, et al.
Publicado: (2023)

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

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