Cover Image

Computational Complexity of Model-Checking Quantum Pushdown Systems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lin, Deren, Lin, Tianrong
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science Computational Complexity 68Q15, 03B25
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Probabilistic $ω$-Pushdown Systems, and $ω$-Probabilistic Computational Tree Logic
by: Lin, Deren, et al.
Published: (2022)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2024)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
by: Kátay, Tamás, et al.
Published: (2023)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

A Minimal Substitution Basis for the Kalmár Elementary Functions
by: Prunescu, Mihai, et al.
Published: (2025)

Exploring P versus NP
by: Tang, Jian-Gang
Published: (2022)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

From Gödel incompleteness to the consistency of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2026)

The complexity of being monitorable
by: Camerlo, Riccardo, et al.
Published: (2026)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

Model-Checking PCTL Properties of Stateless Probabilistic Pushdown Systems
by: Lin, Deren, et al.
Published: (2014)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Choiceless Polynomial Space
by: Ferrarotti, Flavio, et al.
Published: (2024)

Games, mobile processes, and functionss -- alternating, concurrent, and well-bracketed semantics
by: Jaber, Guilhem, et al.
Published: (2025)

Finite model theory for pseudovarieties and universal algebra: preservation, definability and complexity
by: Ham, Lucy, et al.
Published: (2022)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

Some derivations among Logarithmic Space Bounded Counting Classes
by: Janaki, V., et al.
Published: (2023)

Quantum Random Self-Modifiable Computation
by: Fiske, Michael Stephen
Published: (2018)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Optimal Simultaneous Byzantine Agreement, Common Knowledge and Limited Information Exchange
by: van der Meyden, Ron
Published: (2025)

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Flexible constraint satisfiability and a problem in semigroup theory
by: Jackson, Marcel
Published: (2015)

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
by: Kattermann, David, et al.
Published: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

Semi-Algebraic Proof Systems for QBF
by: Beyersdorff, Olaf, et al.
Published: (2025)

Finitely Bounded Homogeneity Turned Inside-Out
by: Rydval, Jakub
Published: (2021)

Refutability as Recursive as Provability
by: Cattabriga, Paola
Published: (2024)

Provability in BI's Sequent Calculus is Decidable
by: Gheorghiu, Alexander, et al.
Published: (2021)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Descriptive Complexity of Sensitivity of Cellular Automata
by: Favereau, Tom, et al.
Published: (2025)

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Why the classes P and NP are not well-defined finitarily
by: Anand, Bhupinder Singh
Published: (2024)

Arithmetics within the Linear Time Hierarchy
by: Pollett, Chris
Published: (2025)

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