6533b836fe1ef96bd12a0790

RESEARCH PRODUCT

On the Class of Languages Recognizable by 1-Way Quantum Finite Automata

Andris AmbainisMaris ValdatsArnolds Kikusts

subject

Discrete mathematicsNested wordComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)0102 computer and information sciences02 engineering and technologyComputer Science::Computational Complexityω-automaton01 natural sciencesDeterministic pushdown automatonDeterministic finite automatonRegular language010201 computation theory & mathematicsProbabilistic automaton0202 electrical engineering electronic engineering information engineeringComputer Science::Programming LanguagesQuantum finite automata020201 artificial intelligence & image processingNondeterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematics

description

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.

yearjournalcountryeditionlanguage
2007-06-12
https://doi.org/10.1007/3-540-44693-1_7