2009 seminar talk: The complexity of colored linear orders

Talk held by Alberto Marcone (Udine) at the KGRC seminar on 2009-05-28.


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.

Bottom menu

Kurt Gödel Research Center for Mathematical Logic. Währinger Straße 25, 1090 Wien, Austria. Phone +43-1-4277-50501. Last updated: 2010-12-16, 04:37.