0000000000895293

AUTHOR

Maris Valdats

showing 5 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

Transition Function Complexity of Finite Automata

2019

State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESState complexityFinite-state machineTheoretical computer scienceGeneral Computer ScienceComputer scienceTransition functionValue (computer science)MinificationMeasure (mathematics)Computer Science::Formal Languages and Automata TheoryAutomatonBaltic Journal of Modern Computing
researchProduct

Transition Function Complexity of Finite Automata

2011

State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.

Discrete mathematicsAverage-case complexityTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFinite-state machineDFA minimizationContinuous spatial automatonAutomata theoryQuantum finite automataDescriptive complexity theoryω-automatonComputer Science::Formal Languages and Automata TheoryMathematics
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

The class of languages recognizable by 1-way quantum finite automata is not closed under union

2000

In this paper we develop little further the theory of quantum finite automata (QFA). There are already few properties of QFA known, that deterministic and probabilistic finite automata do not have e.g. they cannot recognize all regular languages. In this paper we show, that class of languages recognizable by QFA is not closed under union, even not under any Boolean operation, where both arguments are significant.

Quantum PhysicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFOS: Physical sciencesComputer Science::Computational ComplexityQuantum Physics (quant-ph)Computer Science::Formal Languages and Automata Theory
researchProduct