Two-way and one-way quantum and classical automata with advice for online minimization problems
DOI10.1016/J.TCS.2022.02.026OpenAlexW4283580379MaRDI QIDQ2139057FDOQ2139057
Authors: Aliya Khadieva, Mansur Ziatdinov, Ilnaz Mannapov, Dmitry Kravchenko, Alexander Rivosh, 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
Recommendations
online algorithmsautomataquantum computationstreaming algorithmstwo-way automataonline minimization problems
Cites Work
- Two-way finite automata with quantum and classical states.
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- Title not available (Why is that?)
- On the Advice Complexity of Online Problems
- Branching Programs and Binary Decision Diagrams
- Online computation with advice
- Extension of the hierarchy for \(k\)-OBDDs of small width
- Exponential separations for one-way quantum communication complexity, with applications to cryptography
- Superiority of exact quantum automata for promise problems
- Online Computation with Advice
- Quantum branching programs and space-bounded nonuniform quantum complexity
- Competitive Analysis of Aggregate Max in Windowed Streaming
- Competitive analysis of maintaining frequent items of a stream
- How Much Information about the Future Is Needed?
- The string guessing problem as a method to prove lower bounds on the advice complexity
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- New size hierarchies for two way automata
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- On the computational power of probabilistic and quantum branching program
- The Frequent Items Problem in Online Streaming Under Various Performance Measures
- Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Classical and Quantum Computations with Restricted Memory
- Quantum online algorithms with respect to space and advice complexity
- Width hierarchy for \(k\)-OBDD of small width
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- On the power of randomness versus advice in online computation
- Quantum finite automata: a modern introduction
- Quantum online streaming algorithms with logarithmic memory
- Nondeterministic unitary OBDDs
Cited In (5)
- Mirrors and memory in quantum automata
- Quantum algorithm for dynamic programming approach for DAGs and applications
- Time efficient implementation for online \(k\)-server problem on trees
- Quantum versus classical online streaming algorithms with logarithmic size of memory
- The fast algorithm for online \(k\)-server problem on trees
This page was built for publication: Two-way and one-way quantum and classical automata with advice for online minimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2139057)
