Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 75 for “"partial orders"”.
-
Diamond-free partial orders
… the class of ‘diamond-free’ 3-cs-transitive partial orders. The notion of diamond-freeness, proposed by Gray, says that for any a ≤ b, the set of points between a and b is linearly ordered. A weak transitivity condition called ‘3-cs-transitivity’ is taken from the corresponding notion for …
-
Ramsey classes and partial orders
We consider the classes of finite coloured partial orders, i.e., partial orders together with unary relations determining the colour of their points. These classes are the ages of the countable homogeneous coloured partial orders, classified by Torrezão de Souza and Truss in 2008. We prove that …
-
A Polynomial Invariant of Partial Orders
… structure on the linearized vector speciesPO of partial orders. In the third chapter, we present a cancellation-free antipode formula for PO, which we generalize in chapter 4 to the setting of A-species, where A is any simplicial hyperplane arrangement. In chapter 5, we study a polynomial …
-
Automated concurrency bug finding using partial-orders
… have renewed interest in symbolic encodings of partial-order semantics of concurrency using propositional logic or decidable fragments of first-order logic. The impetus behind these partial-order encodings is the efficiency of evermore highly optimized decision procedures, such as <em>Boolean …
-
Point processes: Distributions, partial orders and compensators.
… distributions with respect to three known partial orders on a certain space of point process realizations, and (iii) determines the association of a point process under any one of the same three partial orders. For the purposes of points (ii) and (iii), we develop a tool called a …
-
Graph Relations and Constrained Homomorphism Partial Orders
… it we consider analogous notions defined for orders induced by constrained homomorphisms. We identify corresponding cores, prove or disprove universality, characterize gaps and dualities. We give a new and significantly easier proof of the universality of the homomorphism order by showing that …
-
Inference for partial orders from random linear extensions
<p>The study of random orders and of rankings models has attracted much work in the combinatorics and statistics literature. However, there has been little focus on random partial order models for statistical modelling. A partial order on a set P corresponds to a transitively closed, directed …
-
Games on partial orders and other relational structures
… and Truss, for ordinals [25], some scattered orders, and finite coloured linear orders [24]. Here we extend the known results on linear orders by classifying them all up to 3-equivalence (which had previously been done for 2-equivalence), of which there are 281, using the method of characters. …
-
Some Extremal Problems on Graphs and Partial Orders
… and West conjectured that for every product of partial orders, the maximum size of a semiantichain equals the minimum number of unichains needed to cover the product. We prove the case where both factors have width 2. We also use the characterization of product graphs that are perfect to prove …
-
Defining Partial Orders on Graphical Models of Concurrent Systems
Our interest is in models of concurrency, and their theoretical axiomatisation and analysis. We build on a rich thread of research [BSZ14, FSR16, BSZ17a] interpreting models such as Petri nets as so-called string diagrams, a notation for morphisms of symmetric monoidal categories. From there, we …
-
Online Trace Reordering for Efficient Representation of Event Partial Orders
… yet one may have occurred before the other. A partial order of events, therefore, serves as the fundamental data structure for ordering events in distributed and parallel applications. Traditionally, Fidge/Mattern timestamps have been used for representing event partial orders. The size of the …
-
Bayesian inference on partial orders from random rank-order data
… existing models focus on reconstructing total orders rather than partial orders. Models parameterised by partial orders make weaker assumptions about the unknown underlying order relations. This thesis proposes a new class of generic ranking models parameterised by partial orders. We study …
-
ENUMERATION OF PARTIAL ORDERS AND CONVEX GEOMETRIES VIA HOPF MONOIDS
… Hopf monoid of convex geometries, which admits partial orders as a Hopf submonoid, and investigate combinatorial invariants constructed from characters on them. Each invariant consists of a pair: a polynomial and a more general quasisymmetric function. For partial orders, we obtain the order …
-
Necessary and sufficient conditions on partial orders for modeling concurrent computations
Concurrent computations have been modeled using partial orders in both event based and state based domains. We give necessary and sufficient conditions on partial orders for them to be valid state based or event based models of concurrent computations. In particular, we define notions of …
-
Efficient Data Structures for Partial Orders, Range Modes, and Graph Cuts
… Topics discussed fall in three main categories: partial order representation, range modes, and graph cuts. We consider two problems in partial order representation. The first is a data structure to represent a lattice. A lattice is a partial order where the set of elements larger than any two …
-
The reconstruction of cycle-free partial orders from their automorphism groups
Is a cycle-free partial order recognisable from its abstract automorphism group? This thesis resolves that question for two disjoint families: those cycle-free partial orders which share an automorphism group with a tree; and those which satisfy certain transitivity conditions, before giving a …
-
Extremal Problems in Coloring and Labeling of Graphs and Partial Orders
Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs
-
Connecting the two worlds: well-partial-orders and ordinal notation systems
… in his now-classical 1972 paper [47] that well-partial-orders are among the most frequently rediscovered mathematical objects. Well partial-orders have applications in many fields outside the theory of orders: computer science, proof theory, reverse mathematics, algebra, combinatorics, etc. The …
-
Minimizing setups in precedence constrained scheduling
… is equivalent to finding a linear extension of a partial order with minimum number of jumps. This problem is well known as the jump number problem. For general partial orders, the jump number problem was shown to be NP-hard by Pulleyblank in 1981. We show that the problem is polynomial for two …
Page 1 of 4