Ionian University
Infinite and standard computation with unconventional and quantum methods using automata
Abstract
dc:descriptionThe work described in this dissertation falls into the field of the Theoretical Computer Science. It mainly concerns the use of “Unconventional” methods of computing, such as membrane and quantum automata. This dissertation concerns elements from automata theory. Automata theory is a subfield of the computation theory, and here we mainly study variants of automata that do not belong to the standard models, but they are related to the socalled “Unconventional” methods of computation.The main variant of automata that belongs to standard Theory of Computation that is studied within this dissertation includes those that receive infinite inputs, called ω- automata. Here we associate them with the querying mechanism of web of Linked Data that could be infinite in size. The research on alternative or unconventional computation methods is initiated mainly because of the apparent limits induced by the nature of the materials and the methods used in current computing technologies. Besides the bio-inspired models of computation, such as the membrane systems and automata, the exploration of quantum computing methods has drawn much attention, both in academia and industry.Overall, in this dissertation we try to shed light on these alternative computation methods, that function in an unconventional, non-standard way. We present both the background and the current literature on the concepts that are discussed in this thesis, as well as the detailed contribution of the author, as it has emerged through various already published works. We use the term “standard” to characterize the computation and the corresponding architectures and models that belong to already established computing paradigms, such as Turing machines, finite automata etc. The terms “classical” and “conventional” computation refer to the same concept and they are, also, used in literature. Similarly, we chose to use the term “unconventional” over other ones, such as “alternative” and “non-standard” that are also used by some researchers.The dissertation is divided into 3 main parts. The first one is devoted to the association of appropriate automata variants to the querying of Webs of Linked Data. The second of them concerns the use of membrane automata and the proposal of quantum automata with infinite inputs. The last part of the thesis contains the discussion of our results and the directions for future investigation, along with potential applications of the above.
Degree
thesis:*- Grantor dc:publisher
- Ionian University
- Year dc:date
- 2016
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Giannakis, Konstantinos
- Γιαννάκης, Κωνσταντίνος
Subjects
dc:subject × 14- Θεωρία υπολογισμού
- Μη συμβατικός υπολογισμός
- Κβαντικός υπολογισμός
- Θεωρία αυτομάτων
- Theory of computation
- Unconventional computation
- Quantum computation
- Automata theory
- Φυσικές Επιστήμες
- Μαθηματικά
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Mathematics
- Computer and Information Sciences
Rights
dc:rights- Statement dc:rights
-
- BY_NC_ND
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/38648