Infinite and standard computation with unconventional and quantum methods using automata

Abstract

The 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.

Η εκπόνηση της παρούσας διατριβής αφορά το πεδίο της Θεωρητικής Επιστήμης Υπολογιστών ή Θεωρητικής Πληροφορικής. Αφορά κατά κύριο λόγο τη χρήση “Μη συμβατικών” μεθόδων υπολογισμού, όπως ο υπολογισμός με αυτόματα μεμβράνες και ο υπολογισμός με κβαντικά αυτόματα. Η θεωρία αυτομάτων είναι υποπεδίο της θεωρίας υπολογισμού και στην εργασία αυτή μελετάμε κυρίως παραλλαγές αυτομάτων που δεν ανήκουν στα καθιερωμένα μοντέλα, αλλά αντίθετα έχουν σχέση με αυτό που λέμε “Μη συμβατικές” μέθοδοι υπολογισμού. Η κύρια παραλλαγή των αυτομάτων που ανήκει στη Θεωρία Υπολογισμού και η οποία μελετάται στην παρούσα διατριβή αφορά τα αυτόματα που δέχονται εισόδους άπειρου μήκους. Αυτά τα αυτόματα ονομάζονται ω-αυτόματα. Στην παρούσα εργασία τα συνδέουμε με τον μηχανισμό επερωτήσεων σε ιστούς Διασυνδεδεμένων Δεδομένων, οι οποίοι μπορεί να είναι άπειροι σε μέγεθος. Η έρευνα των εναλλακτικών ή μη συμβατικών μεθόδων υπολογισμού ξεκίνησε λόγω των φυσικών ορίων των υλικών και των μεθόδων που χρησιμοποιούνται στις τρέχουσες υπολογιστικές τεχνολογίες. Ως εκ τούτου, υπάρχειμία συνεχής προσπάθεια για περαιτέρω εξερεύνηση της πιθανότητας χρήσης τέτοιων μεθόδων και υλικών για υπολογιστικούς σκοπούς. Πέρα από τα εμπνευσμένα από τη βιολογία μοντέλα υπολογισμού, όπως είναι τα συστήματα μεμβρανών, η εξερεύνηση κβαντικών υπολογιστικών μεθόδων έχει προσελκύσει αρκετή προσοχή, τόσο στον ακαδημαϊκό χώρο, όσο και τη βιομηχανία. Συνολικά, στην παρούσα διατριβή, προσπαθούμε να φωτίσουμε αυτές τις εναλλακτικές μεθόδους υπολογισμού που λειτουργούν με έναν μη συμβατικό, μη καθιερωμένο τρόπο. Παρουσιάζουμε τόσο το θεωρητικό υπόβαθρο και την τρέχουσα βιβλιογραφία σχετικά με τις έννοιες με τις οποίες καταπιάνεται αυτή η εργασία, όσο και την λεπτομερή συνεισφορά του συγγραφέα, όπως αυτή έχει προκύψει μέσα από διάφορες ήδη δημοσιευμένες εργασίες. Η ορολογία που χρησιμοποιούμε σε όλη την έκταση της διατριβής δηλώνεται ρητά όπου και όταν αυτό απαιτείται. Συνολικά, χρησιμοποιούμε τον όρο “ standard” (“καθιερωμένο”) για τον χαρακτηρισμό του υπολογισμού και των αντίστοιχων αρχιτεκτονικών και μοντέλων που ανήκουν σε ήδη εγκαθιδρυμένες υπολογιστικές δομές, όπως οι μηχανές Turing, τα πεπερασμένα αυτόματα κτλ. Οι όροι “classical” (κλασικός) και “conventional” (“συμβατικός”) υπολογισμός αναφέρονται στην ίδια έννοια και χρησιμοποιούνται, επίσης, στη βιβλιογραφία. Ομοίως, επιλέγουμε τη χρήση του όρου “unconventional” (“μη συμβατικού”) και όχι άλλους όρους που συναντώνται ισοδύναμα στη βιβλιογραφία, όπως “alternative” (εναλλακτικός) και “non-standard” (μη καθιερωμένος).Η διατριβή χωρίζεται σε 3 κύρια μέρη. Το πρώτο από αυτά ασχολείται με τη συσχέτιση κατάλληλων παραλλαγών αυτομάτων με τη διαδικασία επερωτήσεων πάνω σε Ιστούς Διασυνδεδεμένων Δεδομένων. Το δεύτερο κομμάτι αφορά τη χρήση αυτόματων μεμβρανών και την πρόταση κβαντικών αυτομάτων με άπειρες εισόδους. Το τελευταίο τμήμα της διατριβής εμπεριέχει τη συζήτηση και τον σχολιασμό των αποτελεσμάτων μας, καθώς και κατευθύνσεις για μελλοντική έρευνα, μαζί με την παρουσίαση πιθανών εφαρμογών των παραπάνω.