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.

Grantor dc:publisher

Università degli Studi di Milano

Year dc:date

2024

Author dc:creator

• RAUCCI, PRISCILLA

Contributors dc:contributor

• supervisor: C. Mereghetti ; co-supervisor: B. Palano ; coordinator: R. Sassi
• P. Raucci
• MEREGHETTI, CARLO
• SASSI, ROBERTO

• Automata theory
• Computational capacity
• Translucent input letter
• Deterministic pushdown automata
• Quantum finite state automata
• Unary regular languages
• Settore INFO-01/A - Informatica

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

http://dx.doi.org/10.13130/raucci-priscilla_phd2024-12-05
10.13130/raucci-priscilla_phd2024-12-05

OAI identifier oai:identifier

oai:air.unimi.it:2434/1125954