QUANTUM AND TRANSLUCENT PARADIGMS IN AUTOMATA THEORY: A STUDY ON COMPUTATIONAL CAPABILITIES

Within the realm of automata theory, various models differ on their processing mechanisms and computational paradigms. This study investigates two computational paradigms, recently introduced in the literature: quantum and translucency. Specifically, we investigate Quantum Finite State Automata (QFAs) and Deterministic Pushdown Automata with Translucent Letters (DPDAwtl’s). QFAs can be regarded as classical finite state automata using quantum phenomena as computational primitives. We study their computational and descriptional power, with particular emphasis on unary language recognition. Frameworks for recognising unary languages by Latvian QFAs (LQFAs) and QFAs with Control Language (QFCs) are developed. Moreover, decidability questions related to periodicity in measure-once QFAs, measure-many QFAs, LQFAs, and QFCs are analyzed. For DPDAwtl’s - which extend traditional deterministic pushdown automata by incorporating the ability of skipping input characters - we assess their computational power, comparing their language recognition capabilities with that of other well-know language acceptors and generators. This research allows the understanding of these new paradigms, providing deeper insights into their implications in formal language theory and potential applications.