Two-way and one-way quantum and classical automata with advice for online 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
A comparison of performance measures for online algorithms
Extension of the hierarchy for \(k\)-OBDDs of small width
Title not available (Why is that?)
Superiority of exact quantum automata for promise problems
Online Computation with Advice
Unary probabilistic and quantum automata on promise problems
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)