4 citations · 8 across the 3 of their papers we have counts for
3 papers
cs.FL2014★ 1 cited
Boolean Circuit Complexity of Regular Languages
Maris Valdats
In this paper we define a new descriptional complexity measure for Deterministic Finite Automata, BC-complexity, as an alternative to the state complexity. We prove that for two DF…
quant-ph2000★ 4 cited
On the class of languages recognizable by 1-way quantum finite automata
Andris Ambainis, Arnolds Kikusts, Maris Valdats
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) l…
quant-ph2000★ 3 cited
The class of languages recognizable by 1-way quantum finite automata is not closed under union
Maris Valdats
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 auto…