Back to search

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 × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:3362690

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Κωστόπουλος Χαράλαμπος; Kostopoulos Charalampos. The Expressive Power of Higher-Order Datalog with Negation. 2023. https://pergamos.lib.uoa.gr/uoa/dl/object/3362690