δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο




2009 (EL)
Υπολογισιμότητα με μεμβράνες
Membrane computing

Μελίδης, Θεοδόσιος Χρήστου

Η Μεμβρανική Υπολογιστική ξεκίνησε ως κλάδος έχοντας κυρίως δυο προκλήσεις να αντιμετωπίσει: να ελέγξει αν οι αναφορές σχετικά με τους υπολογισμούς (computations) που λαμβάνουν χώρα σε ένα κύτταρο είναι σχήμα λόγου ή πραγματικά έχουν μια αντιστοιχία σε μαθηματική βάση, και μια πιο φιλόδοξη έχοντας ως βάση την εμπειρία από άλλους κλάδους της Φυσικής Υπολογιστικής (Natural Computing) να θεμελειώσει ένα υπολογιστικό μοντέλο εμπνευσμένο από τη δομή και λειτουργία του κυττάρου. Με βάση την τελευταία επιδίωξη η παρούσα διπλωματική εργασία φιλοδοξεί να παρουσιάσει μεμβρανικά υπολογιστικά μοντέλα και την υπολογιστική τους ισχύ. Τα μεμβρανικά συστήματα, με σύμβολα-αντικείμενα και αλυσίδες- αντικείμενα, μελετήθηκαν στη [18] που κυκλοφόρησε σαν ένα TUCS Research report το Νοέμβριο του 1998. Αλλά ας κάνουμε μια μικρή ιστορική αναδρομή για το πώς φτάσαμε εδώ. Διάφορες σχετικές ιδέες είχαν διατυπωθεί προηγουμένως. Ανάμεσα σε αυτές αναφέρουμε την Chemical Abstract Machine, CHAM, εισήχθη στην [4], αλλά με διαφορετικούς προσανατολισμούς και εργαλεία. Επίσης η επεξεργασία multiset είναι ο κύριος στόχος των Γάμα γλωσσών (Gamma language) (πρώτη αναφορά στο [3]). Τέλος αξίζει να επισημάνουμε ότι ο παραλληλισμός και η κατανεμημένη οργάνωση μιας rewriting ή recognizing μηχανής είναι παλιά ζητήματα στη θεωρία τυπικών γλωσσών και στη θεωρία αυτομάτων (L συστήματα, συστήματα γραμματικών, regulated rewriting κ.α). Τα μεμβρανικά συστήματα μπορούν να θεωρηθούν ως συνέχεια των πεδίων αυτών. II Στη συνέχεια παρουσιάζουμε πιο αναλυτικά το αντικείμενο της διπλωματικής εργασίας. Είναι απαραίτητο να ξεκινήσουμε κάνοντας αναφορά σε κάποια στοιχεία της θεωρίας τυπικών γλωσσών. Πρωταρχικής σημασίας είναι η λεγόμενη ιεραρχία του Chomsky, FIN REG CF CS RE, όπου έχουμε διαδοχικά τις οικογένειες των πεπερασμένων, αναγνωρίσιμων, context-free, context-sensitive και recursively enumerable γλωσσών. Η οικογένεια RE των γλωσσών που αναγνωρίζονται από μηχανές Turing κατέχουν σύμφωνα και με την Turing-Church thesis το υψηλότερο επίπεδο αλγοριθμικής πολυπλοκότητας. Βασικό εργαλείο για τη συνέχεια είναι η context-free γραμματική πινάκων, που ορίζεται από την τετράδα G= (N, T, S, M), όπου M είναι ένα πεπερασμένο σύνολο πινάκων και τα υπόλοιπα στοιχεία είναι όμοια με μιας κοινής context-free γραμματικής. Ως πίνακας ορίζεται μία ακολουθία context-free κανόνων της μορφής (u1→ v1, . . .,un→ vn) που εφαρμόζονται ο ένας μετά τον άλλο, ακολουθώντας τη σειρά εμφάνισης τους στον πίνακα. Τέλος αναφέρουμε ως επέκταση του βασικού ορισμού, την context-free γραμματική πινάκων με έλεγχο εμφάνισης. Μια τέτοια γραμματική είναι της μορφής G= (N, T, S, M, F), όπου (N, T, S, M) μία context-free γραμματική πινάκων και F ένα σύνολο από το M. Για w= w1, z= wn+1  (N  T)* η παραγωγή w  z ορίζεται για ένα πίνακα (u1→ v1, . . .,un→ vn)  M, αν για όλα τα 1 i n, συμβαίνει (a) wi= wi′uiwi′′, wi+1= wi′viwi′′, για wi′, wi′′  (N  T)*, ή (b) wi= wi+1, όταν το ui δεν εμφανίζεται στο wi και ο κανόνας ui→ vi εμφανίζεται στο F (για λεπτομέρειες στο [6]). Στο [9] οι Păun και Freund βελτιώνουν υπάρχοντα αποτελέσματα (βλέπε [20]) σχετικά με το πλήθος των μη-τερματικών συμβόλων (terminal) που απαιτούνται σε μια γραμματική πινάκων με έλεγχο εμφάνισης. Συγκεκριμένα απαιτούνται τέσσερα μη-τερματικά III σύμβολα από τα οποία τα τρία χρησιμοποιούνται στην κατάσταση ελέγχου κατάστασης (appearance checking mode) ή δύο μη-τερματικά σύμβολα στην κατάσταση ελέγχου εμφάνισης αλλά στην περίπτωση αυτή δε μπορούμε να φράξουμε το συνολικό πλήθος των μη-τερματικών συμβόλων (η λεγόμενη ισχυρή δυαδική κανονική μορφή, strong binary normal form). Τα κύρια συστατικά ενός μεμβρανικού συστήματος είναι τρία: η μεμβρανική δομή (membrane structure), τα σύνολα των αντικειμένων που περιέχονται σε αυτή (στο παρόν πόνημα θα αναφερθούμε σε σύμβολα- αντικείμενα και αλυσίδες-αντικείμενα), και οι εξελικτικοί κανόνες (evolution rules). Συγκεκριμένα αν θεωρήσουμε το σύνολο MS των μεμβρανικών δομών, τότε αυτό παράγεται από το αλφάβητο { [, ]} με τον εξής αναδρομικό τρόπο: το []  MS, αν μ1, . . ., μn  MS για n 1, τοτε [μ1 . . .μn]  MS, και μόνο αυτά τα στοιχεία περιέχονται στο MS. Ας προχωρήσουμε όμως στον ορισμό του μεμβρανικού συστήματος με σύμβολα-αντικείμενα (αλλιώς Π σύστημα). Ένα Π σύστημα βαθμού n είναι μια κατασκευή Π= (V, μ, w1, . . ., wn, R1, . . ., Rn, i0), όπου V είναι ένα αλφάβητο και μ μια μεμβρανική δομή αποτελούμενη από n μεμβράνες αριθμημένες μία προς μία με ετικέτες (labels) 1, . . ., n. Τα wi,για 1 i n, είναι αλυσίδες συμβόλων που περιέχονται στις αντίστοιχες περιοχές 1, . . ., n και απεικονίζουν multisets πάνω στο V. Τα Ri, για 1 i n, είναι πεπερασμένα σύνολα εξελικτικών κανόνων πάνω στο V και είναι της μορφής u→ v, όπου u  V και v  VTAR, με TAR= {here, out}  {inj / 1 j n} (για TAR= here, out, inj τα σύμβολα του u προστίθενται στο multiset της ίδιας μεμβράνης, της αμέσως εξωτερικής και της εσωτερικής με ετικέτα j αντίστοιχα). Τέλος η ετικέτα i0  {1, . . .,n} δείχνει τη μεμβράνη εξόδου (output IV membrane), τη μεμβράνη δηλαδή που παίρνουμε τα αποτελέσματα των υπολογισμών. Ας δούμε όμως τη λειτουργία ενός μεμβρανικού συστήματος με σύμβολα-αντικείμενα. Οι μεταβάσεις (transitions) από μια κατάσταση σε μια άλλη γίνονται εφαρμόζοντας εξελικτικούς κανόνες σε όλα τα σύμβολα, σε όλα τα multisets και σε όλες τις μεμβράνες του συστήματος. Η εφαρμογή αυτή των κανόνων γίνεται με μη-προσδιοριστό και με το μέγιστο δυνατόν τρόπο (όλα τα αντικείμενα που μπορούν να αντιστοιχηθούν σε κάποιον κανόνα αντιστοιχίζονται). Στη συνέχεια θα αναφέρουμε κάποια είδη μεμβρανικών συστημάτων. Συστήματα που περιέχουν κανόνες u→ v, όπου το u περιέχει περισσότερα του ενός σύμβολα, ονομάζονται συνεργατικά (cooperative), αλλιώς λέγονται μη-συνεργατικά. Επίσης, μία περίπτωση συνεργατικών συστημάτων είναι τα καταλυτικά συστήματα. Σε αυτά τα συστήματα υπάρχει ένα επιπλέον σύνολο K V, το σύνολο των καταλυτών, και οι εξελικτικοί κανόνες μπορούν επιπλέον να είναι της μορφής cu→ cv, όπου c  K, u  VK και v  (VK)TAR. Ας εξετάσουμε τώρα την ‘παραγωγική’ ικανότητα των συστημάτων που μόλις ορίσαμε (βλέπε [7], [18], [19]). Ορίζουμε με NOPm(a, tar) την οικογένεια των συνόλων των φυσικών αριθμών που παράγονται από Π συστήματα με σύμβολα αντικείμενα βαθμού το πολύ m 1 με a  {Coo, nCoo}, όπου tar συμβολίζει τον τρόπο επικοινωνίας μεταξύ των μεμβρανών όπως περιγράφτηκε πιο πάνω. Τα παρακάτω συμπεράσματα προκύπτουν από τον ορισμό του Π συστήματος: NOPm(a, tar) NOPm+1(a, tar), για κάθε m 1 και a  {Coo, nCoo, Cat}, όπως επίσης NOP*(nCoo, tar) NOP*(Cat, tar) NOP*(Coo, tar), όπου * σημειώνουμε όταν ο βαθμός του συστήματος δε V φράσσεται. Το Theorem 2.1 (βλέπε [7]) δίνει ένα κάτω φράγμα στο βαθμό του συστήματος NOP*(a, tar) αποδεικνύοντας ότι είναι ισοδύναμο με το NOP2(a, tar). Στην απόδειξη χρησιμοποιούμε μια εύχρηστη τεχνική στην οποία η περιοχή που βρίσκεται το αντικείμενο μπορεί να προσδιοριστεί από ένα δείκτη της ετικέτας της, οπότε έχουμε κάτω φράγμα το 2 (επειδή χρειαζόμαστε και μια μεμβράνη εξόδου) Στο [19] αποδεικνύεται ότι στην περίπτωση των μη-συνεργατικών συστημάτων ο βαθμός του συστήματος φράσσεται στο 1 και επιπλέον ισχύει NOP1(nCoo)= NCF. Σε αυτήν την περίπτωση κάνουμε χρήση CD γραμματικών και της ιδιότητάς τους CD2(t)= CF. Το Theorem 3.2 αποδεικνύει τη μεγάλη υπολογιστική ισχύ των συνεργατικών συστημάτων. Για την ακρίβεια τα συνεργατικά συστήματα μπορούν να παράγουν την οικογένεια των recursively enumerable γλωσσών χρησιμοποιώντας μάλιστα μία μόνο μεμβράνη. Στην απόδειξη χρησιμοποιούμε γραμματικές πινάκων με έλεγχο εμφάνισης. Ας σημειώσουμε εδώ ότι μία non-context free γραμματική δε μπορεί να προσομοιωθεί από ένα μεμβρανικό σύστημα με άμεσο τρόπο όπως για τις context free γραμματικές. Σε αυτές τις γραμματικές οι εξελικτικοί κανόνες σχετίζονται με αλυσίδες συμβόλων που δε μπορούν να προσομοιωθούν από multisets σε μεμβρανικά συστήματα. Ο λόγος που αναφέραμε παραπάνω είναι ένας από τους οποίους μας οδηγούν στο να ορίσουμε κάποιες νέες παραμέτρους. Συγκεκριμένα αναφέρουμε την πράξη του dissolving μιας μεμβράνης και τη σχέση προτεραιότητας (priority) μεταξύ των κανόνων σε κάθε μεμβράνη. Σε συστήματα που χρησιμοποιούν την πράξη dissolving οι εξελικτικοί κανόνες έχουν τη μορφή που ξέρουμε ή τη μορφή u→ vδ, όπου δ είναι η πράξη του dissolving.Το dissolving μιας μεμβράνης σημαίνει ουσιαστικά ότι η μεμβράνη αυτή παύει να υφίσταται, όλα τα αντικείμενα που VI περιέχονται σε αυτή γίνονται στοιχεία της αμέσως εξωτερικής μεμβράνης και οι εξελικτικοί κανόνες της αφαιρούνται από το σύστημα. Στο σημείο αυτό παραθέτουμε ένα ενδιαφέρον παράδειγμα ([5]) επίλυσης ενός προβλήματος αποφασισιμότητας. Τέλος στα πρότυπα των διατεταγμένων γραμματικών (ordered grammars) (βλέπε [6]) ορίζουμε τη χρήση προτεραιοτήτων σε μεμβρανικά συστήματα ως εξής: ένας κανόνας r1: u1→ v1 από κάποιο Ri του συστήματος Π χρησιμοποιείται σε μία μετάβαση αν και μόνο αν δεν υπάρχει κανόνας r2: u2→ v2 στο Ri τέτοιος ώστε να μπορεί να χρησιμοποιηθεί την ίδια στιγμή και r2> r1. Ας εξετάσουμε λοιπόν τώρα την ισχύ των συστημάτων που εισάγαμε παραπάνω. Θεωρούμε εδώ τις οχτώ παρακάτω περιπτώσεις: με ή χωρίς την πράξη του dissolving, με ή χωρίς συνεργασία, και με ή χωρίς προτεραιότητες. Στο [7] έχει δειχθεί ότι στην περίπτωση του συνεργατικού συστήματος με προτεραιότητες αρκεί ο βαθμός να είναι 2 (που ισχύει και για συστήματα με πράξη dissolving). Επίσης από το Theorem 2.1 βγάζουμε συμπεράσματα για τα συστήματα NOP*(Coo, nPri, nδ), NOP*(nCoo, Pri, nδ). Συγκεντρωτικά (και με συμβατικούς συμβολισμούς) έχουμε: (Coo, Pri, δ), (Coo, Pri, nδ) → (βαθμός ένα) RE (nCoo, nPri, nδ) → (βαθμός ένα) NCF (Coo, nPri, nδ), (nCoo, Pri, nδ) → (βαθμός δύο) (nCoo, Pri, δ), (nCoo, nPri, δ), (Coo, nPri, δ)→ΑΝΟΙΧΤΑ ΖΗΤΗΜΑΤΑ Η περίπτωση συστημάτων που χρησιμοποιούν multisets ως στοιχεία επεξεργασίας κρίνεται μάλλον ανεπαρκής από μαθηματικής απόψεως, αφού η φύση τους επιτρέπει να πραγματεύονται μόνο αριθμητικά προβλήματα. Στα επόμενα λοιπόν θα θεωρούμε αντικείμενα τα οποία θα περιγράφονται από πεπερασμένες αλυσίδες πάνω σε ένα δοσμένο πεπερασμένο αλφάβητο (όπως συμβαίνει για πρωτεΐνες, DNA, VII RNA κ.α). Συγκεκριμένα θα ασχοληθούμε με τις περιπτώσεις των αναγραμματικών μεμβρανικών συστημάτων (rewriting membrane systems), splicing συστημάτων, συστημάτων εισαγωγής-απαλοιφής (insertion-deletion) και contextual συστημάτων. Οι δύο πρώτες περιπτώσεις εισήχθησαν στο [18] (με ένα διαφορετικό ορισμό για την περίπτωση των splicing συστημάτων). Στη συνέχεια θα εξετάσουμε την περίπτωση των αναγραμματικών μεμβρανικών συστημάτων. Είναι λοιπόν μια κατασκευή της μορφής Π= (V, Τ, μ, M1, . . . ,Mm, (R1, ρ1), . . . ,(Rm, ρm)), με τη διαφορά από πριν ότι αντί για multisets έχουμε γλώσσες, δηλαδή Mi V*, για 1 i m. Ας σημειώσουμε ότι ορίσαμε την εκτεταμένη (extended) μορφή όπου συμπληρώσαμε ένα τερματικό αλφάβητο (terminal) T V. Μία λέξη w  V*, αποτέλεσμα ενός υπολογισμού του Π συστήματος, γίνεται δεκτή αν w  Τ*. Τα Ri, για 1 i n, είναι πεπερασμένα σύνολα context-free εξελικτικών κανόνων της μορφής X→ (u, tar), με X  V, u  V*, tar  {here, out, in}. Ορίζουμε με LSPm(rw, in) την οικογένεια των γλωσσών που παράγονται από μη-εκτεταμένα αναγραμματικά συστήματα βαθμού το πολύ m 1, χρησιμοποιώντας αναγραμματικούς κανόνες και την ένδειξη προορισμού (target indication) που ορίσαμε προηγουμένως (προσθέτουμε Ε για την εκτεταμένη περίπτωση και όπου χρειάζεται δ, pri). Στο Theorem 3.1 αποδεικνύουμε ότι η οικογένεια LSP*(rw, tar) δεν περιέχει την οικογένεια των context-free γλωσσών και σε συνδυασμό με το Example 3.1 (σύστημα δύο μεμβρανών που παράγει non-context free γλώσσες) συνάγουμε το αποτέλεσμα του Corollary 3.1: το σύνολο CF είναι μη συγκρίσιμο με όλες τις οικογένειες LSPm(rw, a), για m 2. Για την εκτεταμένη περίπτωση έχουμε καλύτερα συμπεράσματα, και πιο VIII συγκεκριμένα όπως βλέπουμε στο [19] ισχύει CF= ELSP1(rw). Στη συνέχεια δίνονται δύο θεωρήματα τα οποία αποδεικνύουν ότι τα συστήματα που θεωρήσαμε ως τώρα είναι υπολογιστικά ανεπαρκή και μπορούν να παράγουν το πολύ την οικογένεια MAT. Πιο συγκεκριμένα παρουσιάζεται μια βελτίωση του Lemma 4 του [18] που δίνει ένα πάνω όριο για τις οικογένειες [E]LSP*(rw, tar) και ακολουθεί ο αντίστροφος εγκλεισμός MATλ ELSP4(rw, in) (βλέπε [8]). Για να ξεπεράσουμε τις δυσκολίες που αναφέρθηκαν προηγουμένως θα χρησιμοποιήσουμε συστήματα με προτεραιότητες μεταξύ των κανόνων τους. Πράγματι, προσθέτοντας μια σχέση προτεραιότητας πετυχαίνουμε υπολογιστική πληρότητα (computational completeness) ακόμα και σε συστήματα με δύο μεμβράνες και χωρίς τη χρήση τερματικού αλφαβήτου. Ας σημειώσουμε εδώ ότι η ισότητα LSP3(rw, in, pri)= RE δίνεται στο [18] και η βελτίωση του συμπεράσματος που παραθέτουμε δίνεται στο [16]. Κάνοντας σχετικές αναφορές ας σημειώσουμε ότι η 2-κανονική μορφή για αναγραμματικά συστήματα εισήχθη στα [22], [23] όπως επίσης ανάλογες κανονικές μορφές δίνονται στο [14]. Στη συνέχεια θα χρησιμοποιήσουμε την πράξη splicing recombination του DNA για να ορίσουμε τα splicing συστήματα. Ένα splicing σύστημα βαθμού m 1 είναι μια κατασκευή της μορφής Π= (V, T, μ, M1, . . ., Mm, R1, . . .,Rm), όπου Ri, 1 i m είναι πεπερασμένα σύνολα εξελικτικών κανόνων της μορφής (r; tar1, tar2), όπου r= u1u2$u3u4 είναι ένας κανόνας splicing στο V, τα σύμβολα , $ δεν ανήκουν στο V και tar1, tar2  {here, in, out}. Η διάμετρος ενός τέτοιου συστήματος Π ορίζεται από το dia(Π)= (n1, n2, n3, n4) αν ni= max{ ui / (u1u2$u3u4; tar1, tar2)  Rj, 1 j m, IX tar1, tar2  {here, in, out}}, 1 i 4. Ορίζουμε τέλος ως ΕLSPm(spl, in, (n1, n2, n3, n4)) την οικογένεια γλωσσών L(Π) που παράγεται από splicing μεμβρανικά συστήματα βαθμού το πολύ m 1, χρησιμοποιώντας την ένδειξη προορισμού here, in, out, και για διάμετρο αντίστοιχα για κάθε ni μικρότερο από (n1, n2, n3, n4). Η καθολικότητα (universality) των splicing συστημάτων επιτυγχάνεται στο [18] για τέσσερις μεμβράνες. Το αποτέλεσμα αυτό βελτιώνεται για τρεις μεμβράνες στο [21] και για δύο μεμβράνες στο [17], όπου ορίζεται και η διάμετρος του splicing κανόνα. Από αυτή τη σκοπιά, τα αποτελέσματα από το [17] βελτιώνονται στο [10], όπου και μπορεί να βρεθεί η απόδειξη του Theorem 3.6. Στο τελευταίο αυτό θεώρημα χρησιμοποιούμε μία τεχνική δανεισμένη από τα H συστήματα, την τεχνική του “rotate and simulate”. Ένας άλλος τρόπος επεξεργασίας αλυσίδων αντικειμένων είναι μέσω ενός contextual συστήματος, μιας κατασκευής Π= (V, T, μ, M1, . . ., Mm, R1, . . ., Rm), (στην εκτεταμένη μορφή και βαθμού m 1), με ίδια λειτουργία όπως πριν και κανόνες που έχουν τη μορφή: (C, (u, v); tar)a (για adjoining κανόνες) ή (C, (u, v); tar)e (για erasing κανόνες), όπου tar  {here, in, out} είναι μία ένδειξη προορισμού. Επίσης προσθέτουμε ότι ένα contextual σύστημα είναι βάρους (n1, n2; n3, n4) αν το στοιχείο (u, v) κάθε adjoining κανόνα έχει u  n1 και v  n2, και για κάθε στοιχείο (u, v) κάθε erasing κανόνα ισχύει u  n3 και v  n4. Τελειώνοντας, παραθέτουμε δύο αποτελέσματα πληρότητας, το δεύτερο βελτιώνει το βάρος του πρώτου συστήματος έχοντας όμως το μειονέκτημα ότι προσθέτει στο σύστημα μία επιπλέον μεμβράνη. X Κλείνοντας, αναφέρουμε τα συστήματα εισαγωγής-εξαγωγής. Χρησιμοποιούν κανόνες εισαγωγής-εξαγωγής οι οποίοι έχουν ένα είδος δυϊκότητας με τους contextual adjoining-erasing κανόνες. Οι εξελικτικοί κανόνες είναι της μορφής (u, x, v; tar)a και (u, x, v; tar)e για κανόνες εισαγωγής και εξαγωγής αντίστοιχα. Tο βάρος ενός τέτοιου συστήματος είναι (n1, n2; n3, n4) αν n1= max{ x / (u, x, v; tar)a  Ri, 1 i m}, n2= max{ u / (u, x, v; tar)a  Ri or (v, x, u; tar)a  Ri, 1 i m}, n3= max{ x / (u, x, v; tar)e  Ri, 1 i m}, n4= max{ u / (u, x, v; tar)e  Ri or (v, x, u; tar)e  Ri, 1 i m}. Συστήματα με δύο μεμβράνες δεν είναι αρκετά ισχυρά. Πιο συγκεκριμένα το Theorem 3.9 αναφέρει ότι με χρήση μόνο κανόνων εισαγωγής μπορούμε να παράγουμε non-context-free γλώσσες και το Theorem 3.10 (βλέπε [13]) ότι συστήματα με κανόνες εισαγωγής και εξαγωγής ταυτόχρονα χαρακτηρίζουν τις CF γλώσσες. Χρησιμοποιώντας συστήματα με λίγο μεγαλύτερο βάρος μία μεμβράνη αρκεί για να παράγουμε τις recursively enumerable γλώσσες. Τέλος μειώνοντας το βάρος έχουμε το ίδιο επιθυμητό αποτέλεσμα αλλά το τίμημα είναι βαρύ, η αύξηση σε τέσσερα του βαθμού του συστήματος.
We consider P systems with symbol-objects and string-objects. We examine their power and capacity to generate computably enumerable languages. In the former case, we conclude that the non-cooperative systems are not as powerful as the cooperative ones, and in particular we prove that catalytic systems with priorities and of degree two are equivalent to Turing machines. For string-object systems two membranes and priorities suffice for simulating Turing machines, as well. We also mention to an important result for splicing systems of diameter (1, 2, 2, 1), as well as the cases of contextual and insertion-deletion systems.

info:eu-repo/semantics/masterThesis
Postgraduate Thesis / Μεταπτυχιακή Εργασία

Psystem
Contextual adjoining-erasing rule
Splicing
Γραμματική πινάκων
Membrane structure
Matrix grammar
Αναγραμματικό σύστημα
Rewriting system
Μεμβρανική δομή
Σύστημα Π.

Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (EL)
Aristotle University of Thessaloniki (EN)

2009
2009-12-14T11:59:29Z


Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης, Σχολή Θετικών Επιστημών, Τμήμα Μαθηματικών

This record is part of 'IKEE', the Institutional Repository of Aristotle University of Thessaloniki's Library and Information Centre found at http://ikee.lib.auth.gr. Unless otherwise stated above, the record metadata were created by and belong to Aristotle University of Thessaloniki Library, Greece and are made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license (http://creativecommons.org/licenses/by-sa/4.0). Unless otherwise stated in the record, the content and copyright of files and fulltext documents belong to their respective authors. Out-of-copyright content that was digitized, converted, processed, modified, etc by AUTh Library, is made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license (http://creativecommons.org/licenses/by-sa/4.0). You are kindly requested to make a reference to AUTh Library and the URL of the record containing the resource whenever you make use of this material.
info:eu-repo/semantics/openAccess



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.