Algorithm Design Using Traversals of the Covering Relation
Date and time: 11.30am - 12.30pm, Friday 25th September, 2009
Venue: 10.08.03 (Building 10, Level 8, Room 3)
Abstract:
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. However, the success and influence of Formal Concept Analysis 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.
About the speaker:
Andrew Burrow is an ARC Postdoctoral Fellow at SIAL working on the ARC Discovery Grants Acts of Electronic Communications, and acting as executive director of the Spatial Information Architecture laboratory.
Seminar Organisation
Seminars are free and open to the general public. No booking is necessary. If you are interested in giving a presentation in this seminar series, or to make suggestions for speakers, please contact Xiaodong Li, the seminar co-ordinator.