Small size quantum automata recognizing some regular languages

DOI10.1016/J.TCS.2005.03.032MaRDI QIDQ2484448zbMATHOpenAlexFDO

Authors Carlo Mereghetti, Beatrice Palano, Alberto Bertoni

Publication date 1 August 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.03.032

zbMATH Keywords

stochastic events

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum computation (81P68)

Recommendations

• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• scientific article; zbMATH DE number 2044497
• Quantum automata and periodic events
• Quantum automata for some multiperiodic languages
• Lower bounds on the size of quantum automata accepting unary languages.

Cites work

• scientific article; zbMATH DE number 4020506 (Why is no real title available?)
• scientific article; zbMATH DE number 67607 (Why is no real title available?)
• scientific article; zbMATH DE number 2040892 (Why is no real title available?)
• scientific article; zbMATH DE number 1502104 (Why is no real title available?)
• scientific article; zbMATH DE number 3204642 (Why is no real title available?)
• scientific article; zbMATH DE number 3229565 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Characterizations of 1-Way Quantum Finite Automata
• GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Probabilistic automata
• Probability Inequalities for Sums of Bounded Random Variables
• Quantum automata and quantum grammars
• Regular languages accepted by quantum automata
• Scale-sensitive dimensions, uniform convergence, and learnability

Cited in

(19)

• Promise problems solved by quantum and classical finite automata
• One-way finite automata with quantum and classical states
• Quantum automata for some multiperiodic languages
• Quantum finite automata with control language
• Some formal tools for analyzing quantum automata.
• On the power of one-way automata with quantum and classical states
• Behaviours of unary quantum automata
• Exponentially more concise quantum recognition of non-RMM regular languages
• From quantum query complexity to state complexity
• Characterizations of one-way general quantum finite automata
• On the Size of One-way Quantum Finite Automata with Periodic Behaviors
• Complexity of promise problems on classical and quantum automata
• Potential of quantum finite automata with exact acceptance
• Quantum finite automata: advances on Bertoni's ideas
• scientific article; zbMATH DE number 35744 (Why is no real title available?)
• Lower bounds on the size of quantum automata accepting unary languages.
• Size lower bounds for quantum automata
• Quantum automata and periodic events
• Preface

This page was built for publication: Small size quantum automata recognizing some regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2484448)