On the Power of Non-deterministic Quantum Finite Automata(<特集>Special Issue on Selected Papers from LA Symposium)
スポンサーリンク
概要
- 論文の詳細を見る
The class NQP was proposed as the class of problems that are solvable by non-deterministic quantum Turing machines in polynomial time. In this paper, we introduce non-deterministic quantum finite automata in which the same non-determinism as in non-deterministic quantum Turing machines is applied. We compare non-deterministic quantum finite automata with the classical counterparts, and show that (unlike the case of classical finite automata) the class of languages recognizable by non-deterministic quantum finite automata properly contains the class of all regular languages.
- 社団法人電子情報通信学会の論文
- 2002-02-01
著者
-
Hamaguchi K
Osaka Univ. Toyonaka‐shi Jpn
-
Hamaguchi Kiyoharu
The Graduate School Of Information Science And Technology Osaka University
-
Hamaguchi Kiyoharu
Department Of Bioinformatic Engineering Guraduate School Of Information Science And Technology Osaka
-
Kashiwabara Toshinobu
The Graduate School Of Information Science And Technology Osaka University
-
Kashiwabara Toshinobu
Department Of Bioinformatic Engineering Guraduate School Of Information Science And Technology Osaka
-
Kashiwabara Toshinobu
The Department Of Information And Computer Sciences Osaka University
-
Nakanishi Masaki
The Graduate School Of Information Science Nara Institute Of Science And Technology
-
Nakanishi Masaki
Graduate School Of Information Science Nara Institute Of Science And Technology
-
INDOH Takao
Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka Un
-
Indoh Takao
Department Of Informatics And Mathematical Science Graduate School Of Engineering Science Osaka Univ
-
Nakanishi Masaki
Nara Institute Of Technology
関連論文
- Enhancement of Mutation Frequency with Nucleotide Triphosphate Analogs in PCR Random Mutagenesis
- Verifying Signal-Transition Consistency of High-Level Designs Based on Symbolic Simulation(Special Issue on Test and Verification of VLSI)
- Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synthesis(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
- Look Up Table Compaction Based on Folding of Logic Functions(Special Section on VLSI Design and CAD Algorithms)
- Robust Quantum Algorithms Computing OR with ε-Biased Oracles(Quantum Computing,Foundations of Computer Science)
- A Partially Explicit Method for Efficient Symbolic Checking of Language Containment (Special Section on VLSI Design and CAD Algorithms)
- Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique(System Level Design,VLSI Design and CAD Algorithms)
- Regular Temporal Logic Expressively Equivalent to Finite Automata and Its Application to Logic Design Verification
- Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs
- Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition(Computation and Computational Models)
- On the Power of Non-deterministic Quantum Finite Automata(Special Issue on Selected Papers from LA Symposium)
- An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division (Special Section on Discrete Mathematics and Its Applications)
- A Representation Diagram for Maximal Independent Sets of a Graph(Special Section on Discrete Mathematics and Its Applications)
- Multi-Party Quantum Communication Complexity with Routed Messages
- The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
- Automatic Generation of Java-Based, Database-Independent Query API
- Automatic Generation of Java-Based, Database-Independent Query API