Thesis (Doctoral)--Universität Hannover, 1983.

Recently, Formal Concept Analysis has proven to be an efficient method for the analysis and representation of information. However, the possibility to visualize concept hierarchies is being affected by the difficulty of drawing attractive diagrams automatically. Reducing the number of edge crossings seems to increase the readability of those drawings. This dissertation concerns with a mandatory prerequisite of this constraint, namely the characterization and visual representation of planar lattices. The manifold existing approaches and algorithms are thereby considered under a different point of view. It is well known that exactly the planar lattices (or planar posets) possess an additional order ``from left to right''. Our aim in this work is to define left-relations and left-orders more precisely and to describe several aspects of planar lattices with their help. The three approaches employed structure the work in as many parts: Left-relations on lattices allow a more efficient consideration of conjugate orders since they are uniquely determined by the sorting of the meet-irreducibles. Additionally, the restriction on the meet-irreducibles enables us to achieve an intuitive description of standard contexts of planar lattices similar to the consecutive-one property. With the help of left-relations on diagrams, planar lattices can indeed be drawn without edge crossings in the plane. Thereby, lattice-theoretically found left-orders can be detected in the graphical representation again. Furthermore, we modify the left-right-numbering algorithm in order to obtain attribute-additive and plane drawings of planar lattices. Finally, we will consider left-relations on contexts. They turn out to be fairly similar structures to the Ferrers-graphs. Planar lattices can be characterized by a property of these graphs, namely the bipartiteness. We will constructively prove this result. Subsequently, we can design an efficient algorithm that finds all non-similar plane diagrams of a lattice. / Die Formale Begriffsanalyse hat sich in den letzten Jahren als effizientes Werkzeug zur Datenanalyse und -repräsentation bewährt. Die Möglichkeit der visuellen Darstellung von Begriffshierarchien wird allerdings durch die Schwierigkeit, ansprechende Diagramme automatisch generieren zu können, beeinträchtigt. Offenbar sind Diagramme mit möglichst wenig Kantenkreuzungen für den menschlichen Anwender leichter lesbar. Diese Arbeit beschäftigt sich mit mit einer diesem Kriterium zugrunde liegenden Vorleistung, nämlich der Charakterisierung und Darstellung planarer Verbände. Die schon existierenden vielfältigen Ansätze und Methoden werden dabei unter einem neuen Gesichtspunkt betrachtet. Bekannterweise besitzen genau die planaren Verbände (bzw. planare geordnete Mengen) eine zusätzliche Ordnung "von links nach rechts". Unser Ziel in dieser Arbeit ist es, solche Links-Relationen bzw. Links-Ordnungen genauer zu definieren und verschiedene Aspekte planarer Verbände mit ihrer Hilfe zu beschreiben. Die insgesamt drei auftretenden Sichtweisen gliedern die Arbeit in ebensoviele Teile: Links-Relationen auf Verbänden erlauben eine effizientere Behandlung konjugierter Ordnungen, da sie durch die Anordnung der Schnitt-Irreduziblen schon eindeutig festgelegt sind. Außerdem erlaubt die Beschränkung auf die Schnitt-Irreduziblen eine anschauliche Beschreibung von Standardkontexten planarer Verbände ähnlich der consecutive-one property. Mit Hilfe der Links-Relationen auf Diagrammen können planare Verbände tatsächlich eben gezeichnet werden. Dabei lassen sich verbandstheoretisch ermittelte Links-Ordnungen in der graphischen Darstellung wieder finden. Weiterhin geben wir in eine Modifikation des left-right-numbering an, mit der planare Verbände merkmaladditiv und eben gezeichnet werden können. Schließlich werden wir Links-Relationen auf Kontexten betrachten. Diese stellen sich als sehr ähnlich zu Ferrers-Graphen heraus. Planare Verbände lassen sich durch eine Eigenschaft dieser Graphen, nämlich die Bipartitheit, charakterisieren. Wir werden dieses Ergebnis konstruktiv beweisen und darauf aufbauend einen effizienten Algorithmus angeben, mit dem alle nicht-ähnlichen ebenen Diagramme eines Verbandes bestimmt werden können.

Recently, Formal Concept Analysis has proven to be an efficient method for the analysis and representation of information. However, the possibility to visualize concept hierarchies is being affected by the difficulty of drawing attractive diagrams automatically. Reducing the number of edge crossings seems to increase the readability of those drawings. This dissertation concerns with a mandatory prerequisite of this constraint, namely the characterization and visual representation of planar lattices. The manifold existing approaches and algorithms are thereby considered under a different point of view. It is well known that exactly the planar lattices (or planar posets) possess an additional order ``from left to right''. Our aim in this work is to define left-relations and left-orders more precisely and to describe several aspects of planar lattices with their help. The three approaches employed structure the work in as many parts: Left-relations on lattices allow a more efficient consideration of conjugate orders since they are uniquely determined by the sorting of the meet-irreducibles. Additionally, the restriction on the meet-irreducibles enables us to achieve an intuitive description of standard contexts of planar lattices similar to the consecutive-one property. With the help of left-relations on diagrams, planar lattices can indeed be drawn without edge crossings in the plane. Thereby, lattice-theoretically found left-orders can be detected in the graphical representation again. Furthermore, we modify the left-right-numbering algorithm in order to obtain attribute-additive and plane drawings of planar lattices. Finally, we will consider left-relations on contexts. They turn out to be fairly similar structures to the Ferrers-graphs. Planar lattices can be characterized by a property of these graphs, namely the bipartiteness. We will constructively prove this result. Subsequently, we can design an efficient algorithm that finds all non-similar plane diagrams of a lattice. / Die Formale Begriffsanalyse hat sich in den letzten Jahren als effizientes Werkzeug zur Datenanalyse und -repräsentation bewährt. Die Möglichkeit der visuellen Darstellung von Begriffshierarchien wird allerdings durch die Schwierigkeit, ansprechende Diagramme automatisch generieren zu können, beeinträchtigt. Offenbar sind Diagramme mit möglichst wenig Kantenkreuzungen für den menschlichen Anwender leichter lesbar. Diese Arbeit beschäftigt sich mit mit einer diesem Kriterium zugrunde liegenden Vorleistung, nämlich der Charakterisierung und Darstellung planarer Verbände. Die schon existierenden vielfältigen Ansätze und Methoden werden dabei unter einem neuen Gesichtspunkt betrachtet. Bekannterweise besitzen genau die planaren Verbände (bzw. planare geordnete Mengen) eine zusätzliche Ordnung "von links nach rechts". Unser Ziel in dieser Arbeit ist es, solche Links-Relationen bzw. Links-Ordnungen genauer zu definieren und verschiedene Aspekte planarer Verbände mit ihrer Hilfe zu beschreiben. Die insgesamt drei auftretenden Sichtweisen gliedern die Arbeit in ebensoviele Teile: Links-Relationen auf Verbänden erlauben eine effizientere Behandlung konjugierter Ordnungen, da sie durch die Anordnung der Schnitt-Irreduziblen schon eindeutig festgelegt sind. Außerdem erlaubt die Beschränkung auf die Schnitt-Irreduziblen eine anschauliche Beschreibung von Standardkontexten planarer Verbände ähnlich der consecutive-one property. Mit Hilfe der Links-Relationen auf Diagrammen können planare Verbände tatsächlich eben gezeichnet werden. Dabei lassen sich verbandstheoretisch ermittelte Links-Ordnungen in der graphischen Darstellung wieder finden. Weiterhin geben wir in eine Modifikation des left-right-numbering an, mit der planare Verbände merkmaladditiv und eben gezeichnet werden können. Schließlich werden wir Links-Relationen auf Kontexten betrachten. Diese stellen sich als sehr ähnlich zu Ferrers-Graphen heraus. Planare Verbände lassen sich durch eine Eigenschaft dieser Graphen, nämlich die Bipartitheit, charakterisieren. Wir werden dieses Ergebnis konstruktiv beweisen und darauf aufbauend einen effizienten Algorithmus angeben, mit dem alle nicht-ähnlichen ebenen Diagramme eines Verbandes bestimmt werden können.

Context and lattice orbifolds have been discussed by M. Zickwolff, B. Ganter and D. Borchmann. Preordering the folding automorphisms by set inclusion of their orbits gives rise to further development. The minimal elements of this preorder have a prime group order and any group element can be dissolved into the product of group elements whose group order is a prime power. This contribution describes a way to compress an orbifold annotation to sets of such minimal automorphisms. This way a hierarchical annotation is described together with an interpretation of the annotation. Based on this annotation an example is given that illustrates the construction of an automaton for certain pattern matching problems in music processing.

In this thesis, we present a lattice theoretical approach to the field of approximations. Given a pair consisting of a kernel system and a closure system on an underlying lattice, one receives a lattice of approximations. We describe the theory of these lattices of approximations. Furthermore, we put a special focus on the case of concept lattices. As it turns out, approximation of formal concepts can be interpreted as traces, which are preconcepts in a subcontext. / In der vorliegenden Arbeit beschreiben wir einen verbandstheoretischen Zugang zum Thema Approximieren. Ausgehend von einem Kern- und einem Hüllensystem auf einem vollständigen Verband erhält man einen Approximationsverband. Wir beschreiben die Theorie dieser Approximationsverbände. Des Weiteren liegt dabei ein Hauptaugenmerk auf dem Fall zugrundeliegender Begriffsverbände. Wie sich nämlich herausstellt, lassen sich Approximationen formaler Begriffe als Spuren auffassen, welche diese in einem vorgegebenen Teilkontext hinterlassen.

In this thesis, we present a lattice theoretical approach to the field of approximations. Given a pair consisting of a kernel system and a closure system on an underlying lattice, one receives a lattice of approximations. We describe the theory of these lattices of approximations. Furthermore, we put a special focus on the case of concept lattices. As it turns out, approximation of formal concepts can be interpreted as traces, which are preconcepts in a subcontext.:Preface 1. Preliminaries 2. Approximations in Complete Lattices 3. Concept Approximations 4. Rough Sets List of Symbols Index Bibliography / In der vorliegenden Arbeit beschreiben wir einen verbandstheoretischen Zugang zum Thema Approximieren. Ausgehend von einem Kern- und einem Hüllensystem auf einem vollständigen Verband erhält man einen Approximationsverband. Wir beschreiben die Theorie dieser Approximationsverbände. Des Weiteren liegt dabei ein Hauptaugenmerk auf dem Fall zugrundeliegender Begriffsverbände. Wie sich nämlich herausstellt, lassen sich Approximationen formaler Begriffe als Spuren auffassen, welche diese in einem vorgegebenen Teilkontext hinterlassen.:Preface 1. Preliminaries 2. Approximations in Complete Lattices 3. Concept Approximations 4. Rough Sets List of Symbols Index Bibliography

Context and lattice orbifolds have been discussed by M. Zickwolff, B. Ganter and D. Borchmann. Preordering the folding automorphisms by set inclusion of their orbits gives rise to further development. The minimal elements of this preorder have a prime group order and any group element can be dissolved into the product of group elements whose group order is a prime power. This contribution describes a way to compress an orbifold annotation to sets of such minimal automorphisms. This way a hierarchical annotation is described together with an interpretation of the annotation. Based on this annotation an example is given that illustrates the construction of an automaton for certain pattern matching problems in music processing.

Formal concept analysis (FCA) is a mathematical formalism based on order and lattice theory for data analysis. It has found applications in a broad range of neighboring fields including Semantic Web, data mining, knowledge representation, data visualization and software engineering. ICFCA is a series of annual international conferences that started in 2003 in Darmstadt and has been held in several continents: Europe, Australia, America and Africa. ICFCA has evolved to be the main forum for researchers working on theoretical or applied aspects of formal concept analysis worldwide. In 2013 the conference returned to Dresden where it was previously held in 2006. This year the selection of contributions was especially competitive. This volume is one of two volumes containing the papers presented at ICFCA 2013. The other volume is published by Springer Verlag as LNAI 7880 in its LNCS series. In addition to the regular contributions, we have included an extended abstract: Jean-Paul Doignon reviews recent results connecting formal concept analysis and knowledge space theory in his contribution “Identifiability in Knowledge Space Theory: a Survey of Recent Results”. The high-quality of the program of the conference was ensured by the much-appreciated work of the authors, the Program Committee members, and the Editorial Board members. Finally, we wish to thank the local organization team. They provided support to make ICFCA 2013 proceed smoothly in a pleasant atmosphere.

Formal concept analysis (FCA) is a mathematical formalism based on order and lattice theory for data analysis. It has found applications in a broad range of neighboring fields including Semantic Web, data mining, knowledge representation, data visualization and software engineering. ICFCA is a series of annual international conferences that started in 2003 in Darmstadt and has been held in several continents: Europe, Australia, America and Africa. ICFCA has evolved to be the main forum for researchers working on theoretical or applied aspects of formal concept analysis worldwide. In 2013 the conference returned to Dresden where it was previously held in 2006. This year the selection of contributions was especially competitive. This volume is one of two volumes containing the papers presented at ICFCA 2013. The other volume is published by Springer Verlag as LNAI 7880 in its LNCS series. In addition to the regular contributions, we have included an extended abstract: Jean-Paul Doignon reviews recent results connecting formal concept analysis and knowledge space theory in his contribution “Identifiability in Knowledge Space Theory: a Survey of Recent Results”. The high-quality of the program of the conference was ensured by the much-appreciated work of the authors, the Program Committee members, and the Editorial Board members. Finally, we wish to thank the local organization team. They provided support to make ICFCA 2013 proceed smoothly in a pleasant atmosphere.:EXTENDED ABSTRACT Jean-Paul Doignon: Identifiability in Knowledge Space Theory: a survey of recent results S. 1 REGULAR CONTRIBUTIONS Ľubomír Antoni, Stanislav Krajči, Ondrej Krídlo and Lenka Pisková: Heterogeneous environment on examples S. 5 Robert Jäschke and Sebastian Rudolph: Attribute Exploration on the Web S. 19 Adam Krasuski and Piotr Wasilewski: The Detection of Outlying Fire Service’s Reports. The FCA Driven Analytics S. 35 Xenia Naidenova and Vladimir Parkhomenko: An Approach to Incremental Learning Based on Good Classification Tests S. 51 Alexey A. Neznanov, Dmitry A. Ilvovsky and Sergei O. Kuznetsov: FCART: A New FCA-based System for Data Analysis and Knowledge Discovery S. 65

Die sogenannten wunderbaren Modelle für Teilraumanordnungen, eingeführt von DeConcini und Procesi, basierend auf den Techniken der Fulton und MacPherson''schen Kompaktifzierung von Konfigurationsräumen, ermöglichen es, eine Fortsetzung von Feynmandistributionen auf die ihnen zugeordneten divergenten Teilräume in kanonischer Weise zu definieren. Dies wurde in der Dissertation von Christoph Bergbauer ausgearbeitet und diese Arbeit führt die dort präsentierten Ideen weiter aus. Im Unterschied formulieren wir die zentralen Begriffe nicht in geometrischer Sprache, sondern mit Hilfe der partiell geordneten Menge der divergenten Subgraphen eines Feynmangraphen. Dieser Ansatz ist inspiriert durch Feichtners Formulierung der wunderbaren Modellkonstruktion aus kombinatorischer Sicht. Diese Betrachtungsweise vereinfacht die Darstellung deutlich und führt zu einem besseren Verständnis der Fortsetzungs- bzw. Renormierungsoperatoren. Darüber hinaus erlaubt sie das Studium der Renormierungsgruppe, d.h. zu untersuchen, wie sich die renormierten Distributionen unter einem Wechsel des Renormierungspunktes verhalten. Wir zeigen, dass eine sogenannte endliche Renormierung sich darstellen läßt als eine Summe von durch die divergenten Subgraphen bestimmten Distributionen. Dies alles unterstreicht den wohlbekannten Fakt, dass perturbative Renormierung zum größten Teil durch die Kombinatorik von Feynmangraphen bestimmt ist und die analytischen Aspekte nur eine untergeordnete Rolle spielen. / The so-called wonderful models of subspace arrangements, developed in by DeConcini and Procesi, based on Fulton and MacPherson''s seminal paper on a compactification of configuration space, serve as a systematic way to resolve the singularities of Feynman distributions and define in this way canonical renormalization operators. In this thesis we continue the work of Bergbauer where wonderful models were introduced to solve the renormalization problem in position space. In contrast to the exposition there, instead of the subspaces in the arrangement of divergent loci we use the poset of divergent subgraphs of a given Feynman graph as the main tool to describe the wonderful construction and the renormalization operators. This is based on a review article by Feichtner where wonderful models were studied from a purely combinatorial viewpoint. The main motivation for this approach is the fact that both, the renormalization process and the model construction, are governed by the combinatorics of this poset. Not only simplifies this the exposition considerably, but it also allows to study the renormalization operators in more detail. Moreover, we explore the renormalization group in this setting, i.e. we study how the renormalized distributions change if one varies the renormalization points. We show that a so-called finite renormalization is expressed as a sum of distributions determined by divergent subgraphs. The bottom line is that - as is well known, at the latest since the discovery of a Hopf algebra structure underlying renormalization - the whole process of perturbative renormalization is governed by the combinatorics of Feynman graphs while the calculus involved plays only a supporting role.