Let C be a countable partial order. A C-colored linear order (X,f) is a countable linear order X with a map f:X → C. If (X,f) and (X',f') are two such C-colored linear orders, an embedding is an order-preserving φ:X → X' such that f(x) ≤C f'(φ(x)) for all x in X. The quasi-order of C-colored linear orders under embeddability is analytic. Its complexity in the reduction hierarchy depends on the combinatorial properties of C. We will present some results and some open problems.
The complexity of colored linear orders
28.05.2009 15:00 - 16:30
Organiser:
KGRC
Location:
SR 101, 2. St., Währinger Str. 25