Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Bulletin of the European Association for Theoretical Computer Science

Computational Complementarity for Mealy Automata

Cristian S. Calude, Elena Calude, Cătălina Ştefănescu

Published May 1, 1998• 5 citations
OpenAlex

Abstract

In this paper we extend (and study) two computational complementary principles from Moore to Mealy automata which are finite machines possessing better “quantum-like” features. We conjecture that automata which are reversible according to Svozil do not satisfy any of these computational complementarity principles. This result is consistent with the embeddability of irreversible computations into reversible ones (via Bennett’s method, for example). Mathematica experiments confirmed this hypothesis.

Related papers

Finite automata models of quantized systems: conceptual status and outlook

Karl Svozil

Since Edward Moore, finite automata theory has been inspired by physics, in particular by quantum complementarity. We review automaton complementarity, reversible automata and the connections to generalized urn models. Recent developments in quantum information theory may have appropriate formalizations in the automaton context.

arXiv:quant-ph/0209089•Sep 15, 2002•0 citations

Quantum automata and quantum computing

Marats Golovkins

Quantum finite automata were introduced by C.Moore and J.P.Crutchfield in [MC 97] and by A.Kondacs and J.Watrous in [KW 97]. This notion is not a generalization of the deterministic finite automata, but rather a generalization of deterministic reversible (permutation) automata. In [AF 98] A.Ambainis and R.Freivalds raised the question what kind of probabilistic automata can be viewed as a special case of quantum finite automata. To answer that question and study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We give the necessary condition for a language to be recognized by PRA. We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. In these thesis we regard quantum automata, probabilistic reversible and deterministic reversible automata as reversible automata. At least two non-equivalent definitions of language recognition are used for one-way reversible finite automata in various papers. Both of these definitions have their own advantages and disadvantages, summarized in our classification of one-way reversible automata. Further, we introduce a notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite multitape automaton but not by deterministic finite multitape automata. Additionally we discover unexpected probabilistic automata recognizing complicated languages. Finally, we revise the concept of quantum pushdown automata (QPA), first introduced by C.Moore and J.P.Cruthchfield in [MC 97]. We give the definition of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [KW 97]. It is established that the unitary criteria of QPA are not equivalent to the corresponding unitary criteria of quantum Turing machines [BV 97]. We show that QPA can recognize every regular language. We also present some simple non-context-free languages recognized by QPA (hence not recognizable by deterministic and nondeterministic pushdown automata).

•Jan 1, 2002•0 citations

Superiority of one-way and realtime quantum machines and new directions

Abuzer Yakaryılmaz

In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.

arXiv:1102.3093•NCMA•Feb 15, 2011•2 citations

The Equivalence Between Quantum Mealy Automata and Quantum Moore Automata

Zhengjun Xi, Xin Wang, Yongming Li

Journal of Computer Research and Development•Sep 15, 2009•0 citations

On the Weakness of One-Way Quantum Pushdown Automata

Masaki Nakanishi

In general, quantum computation models are expected to be more powerful than classical counterparts. However, sometimes this is not the case.It is known that there exists some regular language which one-way quantum finite automata and one-way quantum counter automata cannot recognize. This is due to the restriction of reversibility which quantum models must satisfy. Thus, it is an interesting question: what kinds of quantum models suffer from/overcome the restriction? To tackle this problem, we focus on (empty-stack acceptance) one-way quantum pushdown automata, and show that there exists a regular language which one-way quantum pushdown automata cannot recognize. This implies adding a stack to one-way finite automata cannot overcome the restriction of reversibility if we adopt empty-stack acceptance as the acceptance mode.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2010•0 citations

SOME REMARKS ON QUANTUM AUTOMATA

Manfred Kudlek

A uniform mathematical description of quantum automata as quantum finite automata, quantum linear bounded automata, and quantum Turing machines is introduced, and the existence of such automata under certain circumstances is investigated. Such quantum automata are modelled by isometric rather than unitary operators, reflecting the fact that computation is primarily irreversible in contrast to physical phenomena in the microworld. The global conditions determine the local conditions of the operators.

International Journal of Foundations of Computer Science•Oct 29, 2007•0 citations
In this paper we extend (and study) two computational complementary principles from Moore to Mealy automata which are finite machines possessing better “quantum-like” features. We conjecture that automata which are reversible according to Svozil do not satisfy any of these computational complementarity principles. This result is consistent with the embeddability of irreversible computations into reversible ones (via Bennett’s method, for example). Mathematica experiments confirmed this hypothesis.
Quantum finite automata were introduced by C.Moore and J.P.Crutchfield in [MC 97] and by A.Kondacs and J.Watrous in [KW 97]. This notion is not a generalization of the deterministic finite automata, but rather a generalization of deterministic reversible (permutation) automata. In [AF 98] A.Ambainis and R.Freivalds raised the question what kind of probabilistic automata can be viewed as a special case of quantum finite automata. To answer that question and study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We give the necessary condition for a language to be recognized by PRA. We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. In these thesis we regard quantum automata, probabilistic reversible and deterministic reversible automata as reversible automata. At least two non-equivalent definitions of language recognition are used for one-way reversible finite automata in various papers. Both of these definitions have their own advantages and disadvantages, summarized in our classification of one-way reversible automata. Further, we introduce a notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite multitape automaton but not by deterministic finite multitape automata. Additionally we discover unexpected probabilistic automata recognizing complicated languages. Finally, we revise the concept of quantum pushdown automata (QPA), first introduced by C.Moore and J.P.Cruthchfield in [MC 97]. We give the definition of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of [KW 97]. It is established that the unitary criteria of QPA are not equivalent to the corresponding unitary criteria of quantum Turing machines [BV 97]. We show that QPA can recognize every regular language. We also present some simple non-context-free languages recognized by QPA (hence not recognizable by deterministic and nondeterministic pushdown automata).
In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.
In general, quantum computation models are expected to be more powerful than classical counterparts. However, sometimes this is not the case.It is known that there exists some regular language which one-way quantum finite automata and one-way quantum counter automata cannot recognize. This is due to the restriction of reversibility which quantum models must satisfy. Thus, it is an interesting question: what kinds of quantum models suffer from/overcome the restriction? To tackle this problem, we focus on (empty-stack acceptance) one-way quantum pushdown automata, and show that there exists a regular language which one-way quantum pushdown automata cannot recognize. This implies adding a stack to one-way finite automata cannot overcome the restriction of reversibility if we adopt empty-stack acceptance as the acceptance mode.
A uniform mathematical description of quantum automata as quantum finite automata, quantum linear bounded automata, and quantum Turing machines is introduced, and the existence of such automata under certain circumstances is investigated. Such quantum automata are modelled by isometric rather than unitary operators, reflecting the fact that computation is primarily irreversible in contrast to physical phenomena in the microworld. The global conditions determine the local conditions of the operators.