Software product line engineering is a common method for designing complex software systems. Feature modeling is the most common approach to specify product lines. A feature model is a feature diagram (a special tree of features) plus some crosscutting constraints. Feature modeling languages are grouped into basic and cardinality-based models. The common understanding of the semantics of feature models is a Boolean semantics. We discuss a major deficiency of this semantics and fix it by applying, in turn, modal logic, the theory of multisets, and formal language theory. In order to adequately represent the semantics of basic models, we propose a Kripke semantics and show that basic feature modeling needs a modal rather than Boolean logic. We propose two multiset based theories for cardinality-based feature diagrams, called flat and hierarchical semantics. We show that the hierarchical semantics of a given cardinality-based diagram captures all information in the diagram. We also charac- terize sets of multisets, which can provide a hierarchical semantics of some diagrams. We provide three different reduction processes going from a cardinality-based diagram to an appropriate regular expression. As for crosscutting constraints, we propose a formal language interpretation of them. We also characterize some existing analysis operations over feature models in terms of operations on the corresponding languages and discuss the relevant decidability problems. / Thesis / Doctor of Philosophy (PhD)

Η ραγδαία ανάπτυξη που παρουσιάστηκε τα τελευταία χρόνια σε διάφορους τομείς της πληροφορικής με την αύξηση της ισχύος επεξεργασίας και της δυνατότητας αποθήκευσης ενός τεράστιου όγκου δεδομένων έδωσε νέα ώθηση στον τομέα διαχείρισης, αναζήτησης, σύνοψης και εξαγωγής της πληροφορίας από ένα βίντεο. Για την διαχείριση αυτής της πληροφορίας αναπτύχθηκαν τεχνικές περίληψης βίντεο. Η περίληψη ενός βίντεο υπό μορφή μιας στατικής ακολουθίας χαρακτηριστικών καρέ, μειώνει τον απαραίτητο όγκο της πληροφορίας που απαιτείται σε συστήματα αναζήτησης, ενώ διαμορφώνει την βάση για την αντιμετώπιση του σημασιολογικού περιεχομένου του σε εφαρμογές ανάκτησης. Το ερευνητικό αντικείμενο της παρούσας διδακτορικής διατριβής αναφέρεται σε τεχνικές αυτόματης περίληψης βίντεο με χρήση της θεωρίας γράφων, για την ανάπτυξη μη επιβλεπόμενων αλγόριθμων ομαδοποίησης. Κάθε καρέ της ακολουθίας του βίντεο δεν αντιμετωπίζεται ως ένα διακριτό στοιχείο, αλλά λαμβάνεται υπόψη ο βαθμός συσχέτισης μεταξύ τους. Με αυτόν τον τρόπο το πρόβλημα της ομαδοποίησης ανάγεται από μια τυπική διαδικασία αναγνώρισης ομάδων σε ένα σύστημα ανάλυσης της δομής που περιέχεται στο σύνολο των δεδομένων. Ακόμη παρουσιάζεται μια νέα τεχνική βελτίωσης του βαθμού ομοιότητας των καρέ, η οποία βασίζεται στο θεωρητικό φορμαλισμό τεχνικών ημί-επιβλεπόμενης εκμάθησης, με χρήση όμως αλγόριθμων δυναμικής συμπίεσης, για την αναπαράσταση του οπτικού περιεχομένου τους. Τα αναλυτικά πειραματικά αποτελέσματα που παρατίθενται, αποδεικνύουν την βελτίωση της απόδοσης των προτεινόμενων μεθόδων σε σχέση με γνωστές τεχνικές περίληψης. Τέλος, προτείνονται κάποιες μελλοντικές κατευθύνσεις έρευνας στο αντικείμενο που πραγματεύεται η παρούσα διατριβή, με άμεσες επεκτάσεις στο πεδίο ανάκτησης εικόνας και βίντεο. / The rapid development witnessed in the recent years enabling the storage and processing of a huge amount of data, in various fields of computer technology and image/video understanding, has given new impetus to the field of video manipulation, browsing, indexing, and retrieval. Video summarization, as a static sequence of key frames, reduces the amount of information required for video searching, while provides the basis for understanding the semantic content in video retrieval applications. The research subject of this doctoral thesis is the incorporation of graph theory and unsupervised clustering algorithms in Automatic Video Summarization applications of large video sequences. In this context, every frame from a video sequence is not processed as a discrete element, but the relations between the frames are considered. Thus, the clustering problem is transformed from a typical computation procedure, to the problem of data structure analysis. Detailed experimental results demonstrate the performance improvement provided by the proposed methods in comparison with well-known video summarization techniques from the literature. Finally, future research directions are proposed, directly applicable to the fields of image and video retrieval.