Imagen de Portada

$\rm P$ has polynomial-time finite-state verifiers

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Gezer, M. Utkan, Say, A. C. Cem
Formato:	Preprint
Publicado:	2023
Materias:	Computational Complexity F.1.2; F.1.1; F.4.3
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On some Classes of Reversible 2-head Automata
por: Nagy, Benedek, et al.
Publicado: (2025)

A LOCAL View of the Polynomial Hierarchy
por: Reiter, Fabian
Publicado: (2023)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
por: Kawałek, Piotr, et al.
Publicado: (2026)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
por: Esparza, Javier, et al.
Publicado: (2025)

Imperative process algebra and models of computation
por: Middelburg, C. A.
Publicado: (2022)

Turn Complexity of Context-free Languages, Pushdown Automata and One-Counter Automata
por: Pighizzini, Giovanni
Publicado: (2026)

A point to set principle for finite-state dimension
por: Mayordomo, Elvira
Publicado: (2022)

Lexicographic transductions of finite words
por: Filiot, Emmanuel, et al.
Publicado: (2025)

Identity Testing for Stochastic Languages
por: Agarwal, Smayan, et al.
Publicado: (2025)

Orbit-finite linear programming
por: Ghosh, Arka, et al.
Publicado: (2023)

A correspondence between the time and space complexity
por: Latkin, Ivan V.
Publicado: (2023)

On Repetitive Finite Automata with Translucent Words
por: Mráz, František, et al.
Publicado: (2025)

On the Boolean Closure of Deterministic Top-Down Tree Automata
por: Löding, Christof, et al.
Publicado: (2024)

On Minimization and Learning of Deterministic $ω$-Automata in the Presence of Don't Care Words
por: Löding, Christof, et al.
Publicado: (2022)

Recognizing Numbers
por: Gaba, Pranshu, et al.
Publicado: (2025)

Probabilistic Finite Automaton Emptiness is undecidable
por: Rote, Günter
Publicado: (2024)

Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata
por: Bojańczyk, Mikołaj, et al.
Publicado: (2021)

Probabilistic Finite Automaton Emptiness is Undecidable for a Fixed Automaton
por: Rote, Günter
Publicado: (2024)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
por: Anand, Emile, et al.
Publicado: (2024)

On the formalization of the notion of a concurrent algorithm
por: Middelburg, C. A.
Publicado: (2024)

Formalizing the notions of non-interactive and interactive algorithms
por: Middelburg, C. A.
Publicado: (2024)

Regular Expressions with Backreferences: Polynomial-Time Matching Techniques
por: Schmid, Markus L.
Publicado: (2019)

A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings
por: Grabolle, Gustav
Publicado: (2022)

Catalytic Computing and Register Programs Beyond Log-Depth
por: Alekseev, Yaroslav, et al.
Publicado: (2025)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
por: Bajaj, Divya, et al.
Publicado: (2026)

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

Geometric Characterization of Context-Free Intersections via the Inner Segment Dichotomy
por: Silva, Jorge Miguel
Publicado: (2026)

Modelling Distributed Applications with Mixed-Choice Stateful Typestates
por: Parrinha, Francisco, et al.
Publicado: (2026)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
por: Conneryd, Jonas, et al.
Publicado: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
por: Håstad, Johan, et al.
Publicado: (2022)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
por: de Rezende, Susanna F., et al.
Publicado: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
por: de Rezende, Susanna F., et al.
Publicado: (2024)

Supercritical Tradeoffs for Monotone Circuits
por: Göös, Mika, et al.
Publicado: (2024)

Learning real-time one-counter automata using polynomially many queries
por: Mathew, Prince, et al.
Publicado: (2024)

Complex Event Recognition with Symbolic Register Transducers: Extended Technical Report
por: Alevizos, Elias, et al.
Publicado: (2024)

Probabilistic Shoenfield Machines
por: Bujok, Maksymilian, et al.
Publicado: (2024)

Decidability of membership problems for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ and singular matrices
por: Diekert, Volker, et al.
Publicado: (2019)

A Myhill-Nerode Type Characterization of 2detLIN Languages
por: Nagy, Benedek
Publicado: (2025)

The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory
por: Luo, Wei
Publicado: (2026)

Finitely Presentable Higher-Dimensional Automata and the Irrationality of Process Replication
por: Basold, Henning, et al.
Publicado: (2023)