Two-way and one-way quantum and classical automata with advice for online minimization problems
From MaRDI portal
Publication:2139057
DOI10.1016/j.tcs.2022.02.026OpenAlexW4283580379MaRDI QIDQ2139057
Ilnaz Mannapov, Dmitry Kravchenko, Alexander Rivosh, Aliya Khadieva, Mansur Ziatdinov, Ramis Yamilov, Kamil Khadiev
Publication date: 17 May 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2022.02.026
automataonline algorithmsquantum computationstreaming algorithmstwo-way automataonline minimization problems
Related Items (4)
Quantum versus classical online streaming algorithms with logarithmic size of memory ⋮ Quantum algorithm for dynamic programming approach for DAGs and applications ⋮ Mirrors and memory in quantum automata ⋮ The fast algorithm for online \(k\)-server problem on trees
Cites Work
- Unnamed Item
- Unnamed Item
- Extension of the hierarchy for \(k\)-OBDDs of small width
- Superiority of exact quantum automata for promise problems
- Competitive analysis of maintaining frequent items of a stream
- A comparison of performance measures for online algorithms
- Online computation with advice
- Quantum online algorithms with respect to space and advice complexity
- The string guessing problem as a method to prove lower bounds on the advice complexity
- Width hierarchy for \(k\)-OBDD of small width
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Unary probabilistic and quantum automata on promise problems
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- Quantum branching programs and space-bounded nonuniform quantum complexity
- Two-way finite automata with quantum and classical states.
- New size hierarchies for two way automata
- Quantum online streaming algorithms with logarithmic memory
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Nondeterministic unitary OBDDs
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- On the computational power of probabilistic and quantum branching program
- Quantum Finite Automata: A Modern Introduction
- The Frequent Items Problem in Online Streaming Under Various Performance Measures
- On the Power of Randomness versus Advice in Online Computation
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- Competitive Analysis of Aggregate Max in Windowed Streaming
- Online Computation with Advice
- On the Advice Complexity of Online Problems
- Branching Programs and Binary Decision Diagrams
- Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
- How Much Information about the Future Is Needed?
- Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
- Classical and Quantum Computations with Restricted Memory
This page was built for publication: Two-way and one-way quantum and classical automata with advice for online minimization problems
