Non-symmetric completion as a topological foundation for denotational semantics, the complexity analysis of programs, and Russell-Wiener' s theory of continuous-time

Abstract

This dissertation develops a coherent theory of completion processes at the intersection of mathematics and theoretical computer science,aimed at making explicit limits,convergences, and structures that remain implicit in asymmetric and continuous settings. It begins with the introduction and construction of the U-completion for quasi-uniformspaces, based on U-Cauchy nets, U-cuts and U-completeness, thereby solving the long-standing non-symmetric completion problem and providing a stable theoretical foundation. Building on this, the Λ-completion unifies the classical approaches of MacNeille, Dedekind and Doitchinov into a universal framework, offering a general method for understanding and comparing completion theories. The study then applies Scott topology to program complexity analysis by introducing the measure Cov(K), defined as the minimal number of Scott-open sets required to covera Scott-compact set K. This invariant quantifies informational cost and branching, is preserved under Scott-continuous semantic maps, and satisfies controlled upper boundsunder recursion and parallel composition, thus bridging semantics-sensitive reasoning with classical time and space complexity classes. In parallel, a unified model of continuous time is developed, grounded in event structures and oriented quasi-uniformities of past and future. By leveraging both the U-completion and the Λ-completion via cuts, the continuum κ(K) emerges with separability and an order–topology isomorphism to the real interval, while the use of dual numbers introduces infinitesimals for modeling duration. The dissertation concludes with a synthesis of these results and demonstrates applications in theoretical computer science, real-time and hybrid systems, and machine learning. Overall, it highlights completeness as a foundational principle that unites mathematical constructions and computational practices, extending the tools for analyzing complexityand temporal dynamics.

Η διατριβή αυτή αναπτύσσει μια συνεκτική θεωρία συμπληρώσεων (completion processes) στη διασταύρωση μαθηματικών και θεωρητικής πληροφορικής, με στόχο να καταστήσει ρητά όρια,συγκλίσεις και δομές που παραμένουν λανθάνουσες σε ασύμμετρα και συνεχή περιβάλλοντα. Η εργασία ξεκινά με την εισαγωγή και κατασκευή της U-συμπλήρωσης για quasi-uniform χώρους, μέσω U-Cauchy δικτύων, U-τομών και U-πληρότητας, επιλύοντας το μακροχρόνιο πρόβλημα της μη συμμετρικής συμπλήρωσης και παρέχοντας ένα σταθερό θεωρητικό υπόβαθρο. Στη συνέχεια, η Λ-συμπλήρωση ενοποιεί τις κλασικές προσεγγίσεις των MacNeille, Dedekind και Doitchinov σε ένα καθολικό πλαίσιο, προσφέροντας γενική μέθοδο για την κατανόηση και σύγκριση θεωριών συμπλήρωσης. Η μελέτη προχωρά με την εφαρμογή της τοπολογίας του Scott στην ανάλυση πολυπλοκότητας προγραμμάτων, εισάγοντας το μέτρο Cov(K), ορισμένο ως τον ελάχιστο αριθμό Scott-ανοικτώνσυνόλων που καλύπτουν ένα Scott-συμπαγές K. Το μέτρο αυτό ποσοτικοποιεί το πληροφοριακό κόστος και τη διακλάδωση, διατηρείται υπό Scott-συνεχείς σημασιολογικούς μετασχηματισμούς και ικανοποιεί ελεγχόμενα άνω φράγματα υπό αναδρομή και παράλληλη σύνθεση, γεφυρώνοντας τη σημασιολογική θεώρηση με τις κλασικές κλάσεις πολυπλοκότητας χρόνου και χώρου. Παράλληλα, αναπτύσσεται ένα ενιαίο μοντέλο συνεχούς χρόνου, βασισμένο σε event structures και προσανατολισμένες quasi-uniformities παρελθόντος/μέλλοντος. Αξιοποιώντας τόσο την U-completion όσο και τη Λ-completion μέσω τομών, προκύπτει το συνεχές κ(K) με ιδιότητες διαχωρισιμότητας και ισομορφία τάξης–τοπολογίας με το πραγματικό διάστημα, ενώ η χρήση dualnumbers εισάγει απειροστά για την αποτύπωση διάρκειας. Η διατριβή ολοκληρώνεται με μια σύνθεση των αποτελεσμάτων και την ανάδειξη εφαρμογών στη θεωρητική πληροφορική, τα συστήματα πραγματικού χρόνου, τα υβριδικά μοντέλα καιτη μηχανική μάθηση. Συνολικά, αναδεικνύει την έννοια της πληρότητας ως θεμελιώδη αρχή που συνδέει μαθηματικές κατασκευές και υπολογιστικές πρακτικές, επεκτείνοντας τα εργαλεία ανάλυσης της πολυπλοκότητας και της χρονικής δυναμικής.