One-way reversible and quantum finite automata with advice

DOI10.1016/j.ic.2014.10.003zbMath1309.68125arXiv1208.6092OpenAlexW2962766591MaRDI QIDQ476173

Tomoyuki Yamakami

Publication date: 28 November 2014

Published in: Information and Computation, Language and Automata Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

context-free languageregular languageadvicequantum finite automatonquantum advicerandomized advicereversible finite automatonrewritable tape

Mathematics Subject Classification ID

Related Items (10)

Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ Reversible computation in term rewriting ⋮ Classically time-controlled quantum automata ⋮ Pseudorandom generators against advised context-free languages ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Quantum Pushdown Automata with Garbage Tape ⋮ How does adiabatic quantum computation fit into quantum automata theory? ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ Quantum State Complexity of Formal Languages ⋮ Advice hierarchies among finite automata

Cites Work

• Unnamed Item
• Immunity and pseudorandomness of context-free languages
• Turing machines that take advice
• Quantum information and the PCP theorem
• Pseudorandom generators against advised context-free languages
• An application of quantum finite automata to interactive proof systems
• An NP-complete language accepted in linear time by a one-tape Turing machine
• Quantum automata and quantum grammars
• Quantum computation with write-only memory
• Amount of nonconstructivity in deterministic finite automata
• Constant-space quantum interactive proofs against multiple provers
• Polynomial time quantum computation with advice
• Multiple Usage of Random Bits in Finite Automata
• Limitations of Quantum Advice and One-Way Communication
• Characterizations of 1-Way Quantum Finite Automata
• Dense quantum coding and quantum finite automata
• Automata that take advice
• The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract)
• Inference of Reversible Languages
• Finite Automata with Advice Tapes
• Implementation and Application of Automata
• SOFSEM 2004: Theory and Practice of Computer Science

This page was built for publication: One-way reversible and quantum finite automata with advice