Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2013-05-31
Συγγραφέας:
Μίσιος Αριστοτέλης
Στοιχεία επιβλεπόντων καθηγητών:
Π. Ροντογιάννης Αναπλ. Καθηγ., Χ. Καπούτσης Επίκ. Καθηγ.
Πρωτότυπος Τίτλος:
Computability and complexity of two-way finite automata
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Υπολογισιμότητα και πολυπλοκότητα πεπερασμένων αυτομάτων
Περίληψη:
Υπολογισιμότητα πεπερασμένων αυτοματων μιας κεφαλής και ισοδυναμία αυτών.
Κλάσεις πολυπλοκότητας αυτομάτων, πληρότητα, αναγωγές, σχέσεις με πολυπλοκότητα
μηχανών τιούρινγκ. Αναζήτηση αναγωγής για την πληρότητα προβλημάτων με σταθερή
είσοδο.
Λέξεις-κλειδιά:
Υπολογισιμότητα, Πολυπλοκότητα, Αυτόματα, Μη ντετερμινισμός
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
17
