Mirna Džamonja: WQOs, FACs and their width
11/04/15 09:52
Tuesday, April 21, 2015 17:15
Room: D1-215
Speaker: Mirna Džamonja
Title: WQOs, FACs and their width
Abstract. A quasi-order is WQO if it has no infinite antichains or infinite decreasing sequences. A partial order is FAC if it has no infinite antichains. These restrictions on the orders mean that there are several naturally defined ordinal valued ranks that can be used to study them, for example, the rank of the tree of antichains, called the width. These ranks have been studied from the point of view of order theory, Ramsey theory, and also the theory of algorithms, since it turns out that a large class of « well structured systems « of algorithms can be modeled using the wqo. We shall present certain structural results connecting FAC and WQO orders and then some calculations of the ranks. The new results presented in the talk come from a collaborative work with Schnoebelen and Schmitz.
Room: D1-215
Speaker: Mirna Džamonja
Title: WQOs, FACs and their width
Abstract. A quasi-order is WQO if it has no infinite antichains or infinite decreasing sequences. A partial order is FAC if it has no infinite antichains. These restrictions on the orders mean that there are several naturally defined ordinal valued ranks that can be used to study them, for example, the rank of the tree of antichains, called the width. These ranks have been studied from the point of view of order theory, Ramsey theory, and also the theory of algorithms, since it turns out that a large class of « well structured systems « of algorithms can be modeled using the wqo. We shall present certain structural results connecting FAC and WQO orders and then some calculations of the ranks. The new results presented in the talk come from a collaborative work with Schnoebelen and Schmitz.