Buchumschlag

The Existential Theory of the Reals as a Complexity Class: A Compendium

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Schaefer, Marcus, Cardinal, Jean, Miltzow, Tillmann
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Computational Geometry Data Structures and Algorithms Formal Languages and Automata Theory Logic in Computer Science
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Data Structures for Finite Downsets of Natural Vectors: Theory and Practice
von: Cadilhac, Michaël, et al.
Veröffentlicht: (2025)

Attractors Is All You Need: Parity Games In Polynomial Time
von: van der Heijden, Rick
Veröffentlicht: (2025)

A Myhill-Nerode Theorem for Generalized Automata, with Applications to Pattern Matching and Compression
von: Cotumaccio, Nicola
Veröffentlicht: (2023)

Constant-delay enumeration for SLP-compressed documents
von: Muñoz, Martín, et al.
Veröffentlicht: (2022)

Finding Diverse Strings and Longest Common Subsequences in a Graph
von: Shida, Yuto, et al.
Veröffentlicht: (2024)

Fine-Grained Complexity of Regular Path Queries
von: Casel, Katrin, et al.
Veröffentlicht: (2021)

Hardness of Regular Expression Matching with Extensions
von: Nogami, Taisei, et al.
Veröffentlicht: (2026)

Symbolic Functional Decomposition: A Reconfiguration Approach
von: Oliveira, Mateus de Oliveira, et al.
Veröffentlicht: (2026)

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
von: Bringmann, Karl, et al.
Veröffentlicht: (2023)

Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings
von: Muñoz, Martín
Veröffentlicht: (2026)

The Complexity of Nested Reset Counter Systems
von: Balasubramanian, A. R., et al.
Veröffentlicht: (2026)

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
von: Göller, Stefan, et al.
Veröffentlicht: (2023)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
von: Shakiba, Yousef, et al.
Veröffentlicht: (2025)

Non-commutative linear logic fragments with sub-context-free complexity
von: Nishimiya, Yusaku, et al.
Veröffentlicht: (2025)

Beyond Bits: An Introduction to Computation over the Reals
von: Miltzow, Tillmann
Veröffentlicht: (2026)

Nets-within-Nets through the Lens of Data Nets
von: Di Cosmo, Francesco, et al.
Veröffentlicht: (2025)

On Higher Order Busy Beaver Function
von: Cao, Zining
Veröffentlicht: (2025)

Stochastic Process Turing Machines
von: Wolpert, David, et al.
Veröffentlicht: (2024)

Proceedings Fifteenth International Symposium on Games, Automata, Logics, and Formal Verification
von: Achilleos, Antonis, et al.
Veröffentlicht: (2024)

Reachability in Geometrically $d$-Dimensional VASS
von: Fu, Yuxi, et al.
Veröffentlicht: (2025)

From Width-Based Model Checking to Width-Based Automated Theorem Proving
von: Oliveira, Mateus de Oliveira, et al.
Veröffentlicht: (2022)

Existential Definability over the Subword Ordering
von: Baumann, Pascal, et al.
Veröffentlicht: (2022)

Tokenisation is NP-Complete
von: Whittington, Philip, et al.
Veröffentlicht: (2024)

Counting and Sampling Traces in Regular Languages
von: de Colnet, Alexis, et al.
Veröffentlicht: (2025)

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
von: Halftermeyer, Pierre
Veröffentlicht: (2026)

Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata
von: Kiefer, Stefan, et al.
Veröffentlicht: (2025)

A Framework for Universality in Physics, Computer Science, and Beyond
von: Gonda, Tomáš, et al.
Veröffentlicht: (2023)

CMSO-transducing tree-like graph decompositions
von: Campbell, Rutger, et al.
Veröffentlicht: (2024)

Weighted basic parallel processes and combinatorial enumeration
von: Clemente, Lorenzo
Veröffentlicht: (2024)

A positional $\mathbfΠ^0_3$-complete objective
von: Casares, Antonio, et al.
Veröffentlicht: (2024)

Scalable Learning of One-Counter Automata via State-Merging Algorithms
von: Guha, Shibashis, et al.
Veröffentlicht: (2025)

Rabin Games and Colourful Universal Trees
von: Majumdar, Rupak, et al.
Veröffentlicht: (2024)

The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games
von: Bhaduri, Purandar
Veröffentlicht: (2025)

Algebraic Characterizations of Classes of Regular Languages in DynFO
von: Barloy, Corentin, et al.
Veröffentlicht: (2026)

Algebraic Closure of Matrix Sets Recognized by 1-VASS
von: Manssour, Rida Ait El, et al.
Veröffentlicht: (2025)

The Complexity of Second-order HyperLTL
von: Frenkel, Hadar, et al.
Veröffentlicht: (2023)

On Classifying Continuous Constraint Satisfaction Problems
von: Miltzow, Tillmann, et al.
Veröffentlicht: (2021)

The Complexity of Generalized HyperLTL with Stuttering and Contexts
von: Regaud, Gaëtan, et al.
Veröffentlicht: (2025)

Higher-Dimensional Timed Automata for Real-Time Concurrency
von: Amrane, Amazigh, et al.
Veröffentlicht: (2024)

On The Space Complexity of Partial Derivatives of Regular Expressions with Shuffle
von: Ancona, Davide, et al.
Veröffentlicht: (2025)