The aim of this paper is to show how Formal Concept Analysis can be used for the bene t of clone theory. More precisely, we show how a recently developed duality theory for clones can be used to dualize clones over bounded lattices into the framework of Formal Concept Analysis, where they can be investigated with techniques very di erent from those that universal algebraists are usually armed with. We also illustrate this approach with some small examples.

Currently, the bulk of applications of Formal Concept Analysis (FCA) in software engineering have focussed on software maintenance and re-engineering. In this thesis we broaden the approach by applying FCA to a number of early-phase activities within the software engineering life-cycle. With respect to the requirements engineering phase, a case study is presented comparing two class hierarchies that model aspects of a mass-transit railway ticketing system. The first hierarchy was produced for an existing Object-Z specification of the system while the second was derived using FCA. Contrasting the two hierarchies revealed that they were essentially the same, however, the differences highlighted specification artefacts in the existing hierarchy. With respect to the design phase, the thesis discusses the use of FCA for the navigation and visualisation of Formal Specifications written in Z. In response to the continued call for formal methods tool support, we implement and explore a prototype specification browser that exploits the abstractions afforded by FCA. The research hypothesis is an integrated architecture for navigating formal specifications using FCA. This architecture is realised using ZML and ToscanaJ to produce a practical research tool. The thesis also includes the first broad survey of FCA in the domain of software engineering and an FCA-based methodology for surveying academic literature in general.

Currently, the bulk of applications of Formal Concept Analysis (FCA) in software engineering have focussed on software maintenance and re-engineering. In this thesis we broaden the approach by applying FCA to a number of early-phase activities within the software engineering life-cycle. With respect to the requirements engineering phase, a case study is presented comparing two class hierarchies that model aspects of a mass-transit railway ticketing system. The first hierarchy was produced for an existing Object-Z specification of the system while the second was derived using FCA. Contrasting the two hierarchies revealed that they were essentially the same, however, the differences highlighted specification artefacts in the existing hierarchy. With respect to the design phase, the thesis discusses the use of FCA for the navigation and visualisation of Formal Specifications written in Z. In response to the continued call for formal methods tool support, we implement and explore a prototype specification browser that exploits the abstractions afforded by FCA. The research hypothesis is an integrated architecture for navigating formal specifications using FCA. This architecture is realised using ZML and ToscanaJ to produce a practical research tool. The thesis also includes the first broad survey of FCA in the domain of software engineering and an FCA-based methodology for surveying academic literature in general.

Currently, the bulk of applications of Formal Concept Analysis (FCA) in software engineering have focussed on software maintenance and re-engineering. In this thesis we broaden the approach by applying FCA to a number of early-phase activities within the software engineering life-cycle. With respect to the requirements engineering phase, a case study is presented comparing two class hierarchies that model aspects of a mass-transit railway ticketing system. The first hierarchy was produced for an existing Object-Z specification of the system while the second was derived using FCA. Contrasting the two hierarchies revealed that they were essentially the same, however, the differences highlighted specification artefacts in the existing hierarchy. With respect to the design phase, the thesis discusses the use of FCA for the navigation and visualisation of Formal Specifications written in Z. In response to the continued call for formal methods tool support, we implement and explore a prototype specification browser that exploits the abstractions afforded by FCA. The research hypothesis is an integrated architecture for navigating formal specifications using FCA. This architecture is realised using ZML and ToscanaJ to produce a practical research tool. The thesis also includes the first broad survey of FCA in the domain of software engineering and an FCA-based methodology for surveying academic literature in general.

Currently, the bulk of applications of Formal Concept Analysis (FCA) in software engineering have focussed on software maintenance and re-engineering. In this thesis we broaden the approach by applying FCA to a number of early-phase activities within the software engineering life-cycle. With respect to the requirements engineering phase, a case study is presented comparing two class hierarchies that model aspects of a mass-transit railway ticketing system. The first hierarchy was produced for an existing Object-Z specification of the system while the second was derived using FCA. Contrasting the two hierarchies revealed that they were essentially the same, however, the differences highlighted specification artefacts in the existing hierarchy. With respect to the design phase, the thesis discusses the use of FCA for the navigation and visualisation of Formal Specifications written in Z. In response to the continued call for formal methods tool support, we implement and explore a prototype specification browser that exploits the abstractions afforded by FCA. The research hypothesis is an integrated architecture for navigating formal specifications using FCA. This architecture is realised using ZML and ToscanaJ to produce a practical research tool. The thesis also includes the first broad survey of FCA in the domain of software engineering and an FCA-based methodology for surveying academic literature in general.

Currently, the bulk of applications of Formal Concept Analysis (FCA) in software engineering have focussed on software maintenance and re-engineering. In this thesis we broaden the approach by applying FCA to a number of early-phase activities within the software engineering life-cycle. With respect to the requirements engineering phase, a case study is presented comparing two class hierarchies that model aspects of a mass-transit railway ticketing system. The first hierarchy was produced for an existing Object-Z specification of the system while the second was derived using FCA. Contrasting the two hierarchies revealed that they were essentially the same, however, the differences highlighted specification artefacts in the existing hierarchy. With respect to the design phase, the thesis discusses the use of FCA for the navigation and visualisation of Formal Specifications written in Z. In response to the continued call for formal methods tool support, we implement and explore a prototype specification browser that exploits the abstractions afforded by FCA. The research hypothesis is an integrated architecture for navigating formal specifications using FCA. This architecture is realised using ZML and ToscanaJ to produce a practical research tool. The thesis also includes the first broad survey of FCA in the domain of software engineering and an FCA-based methodology for surveying academic literature in general.

Currently, the bulk of applications of Formal Concept Analysis (FCA) in software engineering have focussed on software maintenance and re-engineering. In this thesis we broaden the approach by applying FCA to a number of early-phase activities within the software engineering life-cycle. With respect to the requirements engineering phase, a case study is presented comparing two class hierarchies that model aspects of a mass-transit railway ticketing system. The first hierarchy was produced for an existing Object-Z specification of the system while the second was derived using FCA. Contrasting the two hierarchies revealed that they were essentially the same, however, the differences highlighted specification artefacts in the existing hierarchy. With respect to the design phase, the thesis discusses the use of FCA for the navigation and visualisation of Formal Specifications written in Z. In response to the continued call for formal methods tool support, we implement and explore a prototype specification browser that exploits the abstractions afforded by FCA. The research hypothesis is an integrated architecture for navigating formal specifications using FCA. This architecture is realised using ZML and ToscanaJ to produce a practical research tool. The thesis also includes the first broad survey of FCA in the domain of software engineering and an FCA-based methodology for surveying academic literature in general.

Le traitement automatique de documents consiste en la transformation dans un format compréhensible par un système informatique de données présentes au sein de documents et compréhensibles par l'Homme. L'analyse de document et la compréhension de documents sont les deux phases du processus de traitement automatique de documents. Étant donnée une image de document constituée de mots, de lignes et d'objets graphiques tels que des logos, l'analyse de documents consiste à extraire et isoler les mots, les lignes et les objets, puis à les regrouper au sein de blocs. Les différents blocs ainsi formés constituent la structure géométrique du document. La compréhension de documents fait correspondre à cette structure géométrique une structure logique en considérant des liaisons logiques (à gauche, à droite, au-dessus, en-dessous) entre les objets du document. Un système de traitement de documents doit être capable de : (i) localiser une information textuelle, (ii) identifier si cette information est pertinente par rapport aux autres informations contenues dans le document, (iii) extraire cette information dans un format compréhensible par un programme informatique. Pour la réalisation d'un tel système, les difficultés à surmonter sont liées à la variabilité des caractéristiques de documents, telles que le type (facture, formulaire, devis, rapport, etc.), la mise en page (police, style, agencement), la langue, la typographie et la qualité de numérisation du document. Dans ce mémoire, nous considérons en particulier des documents numérisés, également connus sous le nom d'images de documents. Plus précisément, nous nous intéressons à la localisation d'informations textuelles au sein d'images de factures, afin de les extraire à l'aide d'un moteur de reconnaissance de caractères. Les factures sont des documents très utilisés mais non standards. En effet, elles contiennent des informations obligatoires (le numéro de facture, le numéro siret de l'émetteur, les montants, etc.) qui, selon l'émetteur, peuvent être localisées à des endroits différents. Les contributions présentées dans ce mémoire s'inscrivent dans le cadre de la localisation et de l'extraction d'informations textuelles fondées sur des régions identifiées au sein d'une image de document.Tout d'abord, nous présentons une approche de décomposition d'une image de documents en sous-régions fondée sur la décomposition quadtree. Le principe de cette approche est de décomposer une image de documents en quatre sous-régions, de manière récursive, jusqu'à ce qu'une information textuelle d'intérêt soit extraite à l'aide d'un moteur de reconnaissance de caractères. La méthode fondée sur cette approche, que nous proposons, permet de déterminer efficacement les régions contenant une information d'intérêt à extraire.Dans une autre approche, incrémentale et plus flexible, nous proposons un système d'extraction d'informations textuelles qui consiste en un ensemble de régions prototypes et de chemins pour parcourir ces régions prototypes. Le cycle de vie de ce système comprend cinq étapes:- Construction d'un jeu de données synthétiques à partir d'images de factures réelles contenant les informations d'intérêts.- Partitionnement des données produites.- Détermination des régions prototypes à partir de la partition obtenue.- Détermination des chemins pour parcourir les régions prototypes, à partir du treillis de concepts d'un contexte formel convenablement construit.- Mise à jour du système de manière incrémentale suite à l'insertion de nouvelles données / Document processing is the transformation of a human understandable data in a computer system understandable format. Document analysis and understanding are the two phases of document processing. Considering a document containing lines, words and graphical objects such as logos, the analysis of such a document consists in extracting and isolating the words, lines and objects and then grouping them into blocks. The subsystem of document understanding builds relationships (to the right, left, above, below) between the blocks. A document processing system must be able to: locate textual information, identify if that information is relevant comparatively to other information contained in the document, extract that information in a computer system understandable format. For the realization of such a system, major difficulties arise from the variability of the documents characteristics, such as: the type (invoice, form, quotation, report, etc.), the layout (font, style, disposition), the language, the typography and the quality of scanning.This work is concerned with scanned documents, also known as document images. We are particularly interested in locating textual information in invoice images. Invoices are largely used and well regulated documents, but not unified. They contain mandatory information (invoice number, unique identifier of the issuing company, VAT amount, net amount, etc.) which, depending on the issuer, can take various locations in the document. The present work is in the framework of region-based textual information localization and extraction.First, we present a region-based method guided by quadtree decomposition. The principle of the method is to decompose the images of documents in four equals regions and each regions in four new regions and so on. Then, with a free optical character recognition (OCR) engine, we try to extract precise textual information in each region. A region containing a number of expected textual information is not decomposed further. Our method allows to determine accurately in document images, the regions containing text information that one wants to locate and retrieve quickly and efficiently.In another approach, we propose a textual information extraction model consisting in a set of prototype regions along with pathways for browsing through these prototype regions. The life cycle of the model comprises five steps:- Produce synthetic invoice data from real-world invoice images containing the textual information of interest, along with their spatial positions.- Partition the produced data.- Derive the prototype regions from the obtained partition clusters.- Derive pathways for browsing through the prototype regions, from the concept lattice of a suitably defined formal context.- Update incrementally the set of protype regions and the set of pathways, when one has to add additional data.

Cette thèse propose une nouvelle approche de découverte de signatures de familles (et superfamilles) d'enzymes. Dans un premier temps, étant donné un échantillon aligné de séquences appartenant à une même famille, cette approche infère des grammaires algébriques caractérisant cette famille. Pour ce faire, de nouveaux principes de généralisation et de nouvelles classes de langages ont été introduites sur la base de la substituabilité locale. Un algorithme a également été développé à cet effet qui produit une grammaire réduite, conservant la structuration des exemples, d'un langage substituable. Dans un second temps, ce manuscrit présente une méthode de classification des séquences d'une superfamille en familles à l'aide d'une analyse de concepts formels basée sur l'alignement des séquences qui permet la détection de nouvelles familles et la découverte des motifs fonctionnels pour améliorer les signatures précédentes. / This thesis proposes a new approach to discover signatures of families (and superfamilies) enzymes. At first, given a sample of aligned sequences belonging to the same family, this approach infers context-free grammars characteristic of this family. To do this, new principles of generalization and new classes have been introduced based on substitutability. An algorithm has also been developed for this purpose, which produces a reduced grammar able to retain the structure of examples. In a second step, this manuscript presents a method for classification of a superfamily sequences into families with a formal concept analysis based on alignement sequences allowing detection of new families and the discovery of patterns to improve functional previous signatures.

Zur einfacheren Entwicklung von technischen Systemen werden heutzutage vielfach funktionsblockorientierte Modellierungssprachen wie MATLAB/Simulink verwendet, die ein System als Netzwerk von miteinander verbundenen Funktionsblöcken darstellen. Aufgrund wechselnder Anforderungen entstehen dabei viele Modellvarianten, die nicht mehr effizient verwaltet werden können. Eine Lösung hierfür ist der Einsatz von Produktlinien, bei dem alle Varianten zusammengefasst und in wiederverwendbare Bestandteile zerlegt werden. Die Einzelvarianten werden dabei nur noch bei Bedarf aus diesen Bestandteilen zusammengesetzt. Die Erstellung dieser Produktlinien ist jedoch mit hohem manuellen Aufwand verbunden, besonders wenn vorhandene Modelle wiederverwendet werden sollen. Dies verhindert oft die Einführung dieses Paradigmas. Das Ziel der Dissertation war es deshalb, diese Migration vorhandener Modellvarianten und damit die Erstellung der Produktlinien zu automatisieren. Hierzu wurde eine Migrationsschrittfolge vorgeschlagen: Mithilfe eines Model-Matching-Ansatzes werden zuerst Gemeinsamkeiten und Unterschiede zwischen den Modellen identifiziert und daraus ein zusammengefasstes Modell und sogenannte Features abgeleitet. Mithilfe der Formalen Begriffsanalyse werden daraufhin die Abhängigkeiten zwischen diesen Features extrahiert und daraus ein Feature-Modell erstellt. Feature-Modell und zusammengefasstes Modell bilden dabei eine Produktlinie, die exakt die vorgegebenen Modellvarianten beschreibt.