scientific article; zbMATH DE number 7104930

MaRDI QIDQ5232904

Gökalp Demirci, Abuzer Yakaryılmaz, A. C. Cem Say, Klaus Reinhardt, Mika Hirvensalo

Publication date: 13 September 2019

Full work available at URL: https://arxiv.org/abs/1407.0334

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

quantum computinginteractive proof systemsalternationunary languagesemptiness problemprivate alternationcounter automatarealtime computation

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items

Unnamed Item

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superiority of exact quantum automata for promise problems
• The complexity of debate checking
• Unbounded-error quantum computation with small space bounds
• On the complexity of minimizing probabilistic and quantum automata
• Characterizations of one-way general quantum finite automata
• The complexity of two-player games of incomplete information
• Quantum automata and quantum grammars
• Quantum alternation
• New Results on the Minimum Amount of Useful Space
• Finite State Verifiers with Constant Randomness
• The Minimum Amount of Useful Space: New Results and New Directions
• Quantum Finite Automata: A Modern Introduction
• Unary Languages Recognized by Two-Way One-Counter Automata
• The Knowledge Complexity of Interactive Proof Systems
• Alternation
• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• ON THE EQUIVALENCE OF TWO-WAY PUSHDOWN AUTOMATA AND COUNTER MACHINES OVER BOUNDED LANGUAGES
• Quantum Computability
• Quantum Alternation
• One-Counter Verifiers for Decidable Languages
• Decidable and Undecidable Problems about Quantum Automata
• Two Families of Languages Related to ALGOL