Paper Info
Title
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata
Abstract
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.
Year
DOI
Venue
2001
10.1007/3-540-44693-1_7
STACS
Keywords
Field
DocType
sufficient condition,open problem,languages recognizable,quantum finite automaton,1-way quantum finite automata,binary boolean operation,regular language,finite automata
Discrete mathematics,Quantum finite automata,Combinatorics,Nondeterministic finite automaton,Nested word,Deterministic finite automaton,Computer science,Deterministic pushdown automaton,Regular language,Probabilistic automaton,ω-automaton
Conference
ISBN
Citations 
PageRank 
3-540-41695-1
19
0.90
References 
Authors
12
3
Name
Order
Citations
PageRank
Andris Ambainis12000183.24
Arnolds Kikusts2773.71
Maris Valdats3201.64