Back to search

National and Kapodistrian University of Athens

Non-constructive proof of a fixed point theorem on lexicographic lattice structures

Abstract

dc:description

Στη διπλωματική αυτή αναπτύσσουμε μια νέα, μη-κατασκευαστική απόδειξη του θεωρήματος σταθερού σημείου, που προτάθηκε από τους Α. Χαραλαμπίδη, Γ. Χατζηαγάπη, και Π. Ροντογιάννη (LICS20). Το θεώρημα αυτό αφορά στην ύπαρξη ελάχιστου σταθερού σημείου μιας κλάσης συναρτήσεων που διαθέτουν ένα περιορισμένο είδος μονοτονικότητας, και οι οποίες είναι ορισμένες σε ειδικώς δομημένα μερικώς διατεταγμένα σύνολα, τα οποία ονομάζουμε δομές λεξικογραφικού πλέγματος. Όταν το θεώρημα εφαρμόζεται σε μονοτονικές συναρτήσεις, δίνει ως ειδική περίπτωση το κλασικό θεώρημα των Knaster-Tarski. Η αρχική απόδειξη του θεωρήματος, όπως παρουσιάζεται στο LICS 2020, είναι κατασκευαστική. Η προτεινόμενη απόδειξη είναι πιο απλή από την αρχική και δίνει μια εναλλακτική διαίσθηση και περαιτέρω εμβάθυνση στο θεώρημα σταθερού σημείου. Επιπροσθέτως, αποδεικνύουμε ότι τα σύνολα των προ-σταθερών, μετα-σταθερών, και σταθερών σημείων των συναρτήσεων πάνω σε αυτές τις δομές, σχηματίζουν πλήρη πλέγματα. Οι αποδείξεις μας έχουν επαληθευτεί μέσω του Coq. Τα αποτελέσματά μας έχουν άμεσες εφαρμογές σε περιοχές της Πληροφορικής, όπου χρησιμοποιούνται μη-μονοτονικοί φορμαλισμοί, όπως στην Τεχνητή Νοημοσύνη, στο Λογικό Προγραμματισμό και στη Θεωρία Τυπικών Γλωσσών.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Χατζηαγάπης Ιωάννης
  • Chatziagapis Ioannis

Subjects

dc:subject × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:2920657

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

Χατζηαγάπης Ιωάννης; Chatziagapis Ioannis. Non-constructive proof of a fixed point theorem on lexicographic lattice structures. 2020. https://pergamos.lib.uoa.gr/uoa/dl/object/2920657