On the Size of One-way Quantum Finite Automata with Periodic Behaviors

DOI10.1051/ita:2002014zbMath1013.68088OpenAlexW2136295829MaRDI QIDQ4800259

Carlo Mereghetti, Beatrice Palano

Publication date: 9 July 2003

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2002__36_3_277_0

zbMATH Keywords

measure-once one-way quantum finite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Descriptive complexity and finite models (68Q19)

Related Items (9)

From Quantum Query Complexity to State Complexity ⋮ Exponentially more concise quantum recognition of non-RMM regular languages ⋮ GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA ⋮ The complexity of minimum difference cover ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ Small size quantum automata recognizing some regular languages ⋮ Some formal tools for analyzing quantum automata. ⋮ Characterizations of one-way general quantum finite automata ⋮ Quantum finite automata with control language

Cites Work

• Quorums from difference covers
• Quantum automata and quantum grammars
• Two-way finite automata with quantum and classical states.
• Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
• Characterizations of 1-Way Quantum Finite Automata
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A Note on Restricted Difference Bases
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Size of One-way Quantum Finite Automata with Periodic Behaviors