2009 | OriginalPaper | Buchkapitel
Algorithm Design Using Traversals of the Covering Relation
verfasst von : Andrew Burrow
Erschienen in: Conceptual Structures: Leveraging Semantic Technologies
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Where posets are used to represent taxonomies, concept lattices, or information ordered databases there is a need to engineer algorithms that search, update, and transform posets. This paper demonstrates an approach to designing such algorithms. It presents a picture of covering relation traversals that characterises these in terms of up-set and down-set expressions involving union, intersection, and difference. It then provides a detailed analysis of three types of covering relation traversal. The approach is demonstrated by describing a suite of derived algorithms. The intention is to express a manner of decomposing mathematical problems into poset traversals, and to provide context to the selection a particular traversal algorithm. This line of work has previously been pursued by [1]. However, the success and influence of Formal Concept Analysis [2] has shifted the emphasis from posets to lattices, and from algorithms that operate on the graph of the partial order to the formal context. This paper contributes a methodology for the renewed investigation of poset algorithms, with the potential to lead to improvements in algorithms such as the online completion to a lattice.