Ομιλητής: Έλλη Αναστασιάδη.
Ημέρα: 01-10-2018, 17:00
Μέρος: 1.1.31, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ (παλιό κτίριο)
Σύνοψη
Στην παρακάτω διπλωματική μελετάμε το Πρόβλημα Ελέγχου Μοντέλου υπό Παραμετρικές Συνθήκες. Ο κύριος στόχος είναι να προσδιορισθεί η επίδραση μιας αύξησης στις λογικές δυνατότητες διατύπωσης στην πολυπλοκότητα του ελέγχου τους πάνω σε γραφήματα. Στον τομέα αυτόν υπάρχουν ήδη κάποια ανεξάρτητα αποτελέσματα που φαίνεται να επιδεικνύουν μια αντιστρόφως ανάλογη σχέση αλλά μόνο σε μια διαισθητική μορφή και χωρίς παραπάνω ανάλυση. Αυτή η σχέση προκύπτει από τις διαφορετικές παραμέτρους που είναι απαραίτητες για να κατηγοριοποιήσουν μια Λογική σαν FPT (= Υπολογίσιμη υπό σταθερή παράμετρο ). Από την μεριά των γραφημάτων επιδιώκουμε να εκφράσουμε το όριο μεταξύ των στιγμιοτύπων στα οποία ο έλεγχος κλάσεων ιδιοτήτων είναι γρήγορος και εκείνων στα οποία δεν είναι. Για αυτό το στόχο χρησιμοποιούνται αποσυνθέσεις των γραφημάτων και ιδιότητες των διαφορετικών παραμέτρων ώστε να καθιερωθεί είτε μια ιεραρχία μεταξύ τους είτε για να εξαχθούν πληροφορίες για το πλήθος των παραμετρικά φραγμένων στιγμιοτύπων. Από την θεωρητική μεριά της υπολογισιμότητας θα χρησιμοποιηθούν παραμετρικά κυκλώματα για να προβλεφθούν τέτοιου είδους σχέσεις μεταξύ Λογικών κλάσεων διαφορετικής περιγραφικής ικανότητας.