Zur Hauptnavigation Zum Inhaltsbereich Zur Suche Zum Seitenfu├č

Mark-Oliver Stehr

Zyklische Ordnungen - Axiome und einfache Eigenschaften

Cyclic Orders - Axioms and Simple Properties

Mark-Oliver Stehr

Diplomarbeit at the Department of Computer Science, University of Hamburg, June 1996


The aim of this work is to find an axiomization of (partial) cyclic orders in a systematic way starting from axioms for acyclic (partial) orders. The intention is to develop a general, mathematical theory comparable to the well known theory of acyclic (partial) orders.

The starting point for the formalization is a quite general representation based on sets of words. These sets are called generalized relations in this context as they generalize both formal langugages and relations of fixed arity.

The major classes of simple (no repetitions of elements in words), subword-closed, rotation-closed, consistent, complete, total and transitive, generalized relations are introduced independently of each other and their connections are explored. Acyclic as well as cyclic orders can be defined and characterized as generalized relations combining some of these notions in different ways. The words can be conceived as finite, total suborders, which in combination constitute the whole, (partial or total) acyclic or cyclic order. Cyclicity is formalized by rotation-closed, generalized relations. In analogy to the transitivity for acyclic orders as binary relations we require a form of cyclic transitivity for cyclic orders.

In parallel to the axiomatization we prove several simple and intuitive properties of cyclic orders. In particular we analyze the directed relation of immediate neigborhood and show the it can only represent an abstraction of cyclic orders in general. That is, there are different cyclic orders with identical relations of immediate neighborhood.

The main result of this work ist the representability of cyclic orders by generalized relations containing only words restricted to maximum length three. This implies that all cyclic orders of practical relevance can be described by a set for triples.

Finally we define the globally oriented, cyclic orders which are cyclic orders, that can be extended (by adding further words) to total, cyclic orders. Surprisingly there is a simple example showing that not all cyclic orders are globally oriented. But we can prove, that the class of globally oriented, cyclic orders is identical to the class of cyclic orders which can be related to acyclic order by means of a cut, which has to be defined appropriately.

Postscript version of this work in gzip-Format (907 kByte)
Attention! The first page contains a picture of a cyclic order which requires some processing time on a conventional printer !

Last Change: 17:40 05/19/2011