Affordable Access

A Nice Labelling for Tree-Like Event Structures of Degree 3 (Extended Version)

Authors
  • Santocanale, Luigi
Type
Preprint
Publication Date
Mar 20, 2009
Submission Date
Mar 20, 2009
Source
arXiv
License
Yellow
External links

Abstract

We address the problem of finding nice labellings for event structures of degree 3. We develop a minimum theory by which we prove that the labelling number of an event structure of degree 3 is bounded by a linear function of the height. The main theorem we present in this paper states that event structures of degree 3 whose causality order is a tree have a nice labelling with 3 colors. Finally, we exemplify how to use this theorem to construct upper bounds for the labelling number of other event structures of degree 3.

Report this publication

Statistics

Seen <100 times