National and Kapodistrian University of Athens
The Expressive Power of Higher-Order Datalog with Negation
Abstract
dc:descriptionΕίναι γνωστό αποτέλεσμα στη βιβλιογραφία ότι η Datalog με την υπόθεση ότι οι βάσεις δεδομένων εισόδου είναι διατεταγμένες, μπορεί να εκφράσει όλα εκείνα τα ερωτήματα που ανήκουν στην κλάση πολυπλοκότητας PTIME. Πρόσφατα, αυτό το αποτέλεσμα επεκτάθηκε και σε προγράμματα Datalog υψηλής τάξης που δεν περιέχουν άρνηση και αποδείχτηκε οτι η εκφραστικότητα αυξάνεται αυστηρά καθώς αυξάνεται και η τάξη των προγραμμάτων. Αυτή η διπλωματική μελετάει την εκφραστικότητα προγραμμάτων υψηλής τάξης Datalog όταν επιτρέπουμε άρνηση. Πιο συγκεκριμένα παρουσιάζεται μια ανάλυση της εκφραστικότητας διαφόρων εκδόσεων της υψηλής τάξης Datalog όπου κάθε φορά επιτρέπουμε ένα υποσύνολο από χαρακτηριστικά όπως η άρνηση, μερικώς εφαρμοσμένες εκφράσεις ως ορίσματα και υπαρξιακές μεταβλητές υψηλής τάξης. Σε κάθε επιλογή τέτοιων χαρακτηριστικών μελετάμε την επίδραση της αύξησης της επιτρεπόμενης τάξης των προγραμμάτων στην εκφραστικότητα της γλώσσας. Προκύπτει ότι η εκφραστικότητα δεν αυξάνεται περαιτέρω όταν εισάγουμε τον τελεστή της άρνησης. Αν όμως δεν επιτρέψουμε μερικώς εφαρμοσμένες εκφράσεις στα προγράμματά μας τότε υπάρχει σημαντική διαφορά. Οι μερικώς εφαρμοσμένες εκφράσεις στα προγράμματα δίνουν από μόνες τους την μέγιστη εκφραστικότητα της γλώσσας σε διατεταγμένες βάσεις, ενώ αν απουσιάζουν χρειαζόμαστε άρνηση με υπαρξιακές μεταβλητές για να πετύχουμε την ίδια εκφραστικότητα. Σε όλες τις άλλες περιπτώσεις η εκφραστικότητα της γλώσσας πέφτει στην κλάση PTIME ανεξαρτήτως της τάξης που επιτρέπουμε να έχουν οι τύποι στα προγράμματά μας.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Κωστόπουλος Χαράλαμπος
- Kostopoulos Charalampos
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:3362690