0000000000517178

AUTHOR

Arnolds Kikusts

showing 3 related works from this author

On the class of languages recognizable by 1-way quantum finite automata

2000

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.

Quantum PhysicsComputer Science::Programming LanguagesFOS: Physical sciencesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Computer Science::Computational ComplexityQuantum Physics (quant-ph)Computer Science::Formal Languages and Automata Theory
researchProduct

Exact results for accepting probabilities of quantum automata

2001

One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this paper, we determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recognized by a QFA with probability at most 0.7726...

General Computer ScienceFOS: Physical sciences0102 computer and information sciences02 engineering and technologyUnitary transformationComputer Science::Computational Complexity01 natural sciencesTheoretical Computer ScienceCombinatoricsQuantum measurementFormal languageQuantum computation0202 electrical engineering electronic engineering information engineeringQuantum finite automataMathematicsQuantum computerQuantum PhysicsFinite-state machineMarkov chainExact resultsTransformation (function)010201 computation theory & mathematics020201 artificial intelligence & image processingQuantum Physics (quant-ph)Finite automataComputer Science::Formal Languages and Automata TheoryComputer Science(all)Theoretical Computer Science
researchProduct

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

2007

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.

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
researchProduct