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 21 for “"Linear Orders"”.
-
Maximal Saturated Linear Orders
… in 1907 regarding pantachies, which are maximal linearly ordered subsets of the space of real-valued sequences partially ordered by eventual domination. Hausdorff's question was as follows: is there a pantachie containing no gaps of order type the first uncountable cardinal? In Chapter 1, some …
-
GENERALIZED OPTIMAL LINEAR ORDERS
… foundation as the basis for exploring new word orders with an undercurrent of psycholinguistic optimality. In particular, we focus on notions of dependency length minimization given the difficulties in human and computational language processing in handling long-distance dependencies. We then …
-
Computable Linear Orders and Turing Reductions
This thesis explores computable linear orders through Turing Reductions and codes zero jump and zero double jump into linear orders using discrete, dense, and block linear relations.
-
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. …
-
A Canonical Countryman Line
… is to give a novel proof that the uncountable linear order C(ρ0) is a Countryman line using an innovative presentation of the full lower trace from Todorcevic's method of minimal walks. In order to motivate the subject we will explicate the basis problem for the class of uncountable linear …
-
Ramsey theory and its application
… with a partial order and a fixed number of linear orders extending the partial order. Third, we study the relations between Ramsey theorems which have points in common with the classical Ramsey theorem and the dual Ramsey theorem by the concept of interpretation.
-
The Universality Problem
… is a faithful functor F from the category L of linear orders to the category G of graphs that preserves model theoretic-related universality results (classes of objects having universal models in exactly the same cardinals, and also having the same universality spectrum). Trees constitute …
-
A Journey from Finite to Automatic Structures and Beyond
… the isomorphismproblemfor unary automatic linear orders, equivalence structures and trees. We also extend the notion of state complexity from regular languages to structures and study this in the context of unary automatic structures. For automatic structures in general, the isomorphism …
-
A generalized Koszul theory and its applications in representation theory.
… standardly (resp., properly) stratified for all linear orders.
-
ON THE MINIMALITY OF NON-$\sigma$-SCATTERED ORDERS
… study the minimality of non-$\sigma$-scattered orders. While there are insightful theorems, due to Laver, about $\sigma$-scattered orders, we will show the class of non-$\sigma$-scattered orders tend to be more chaotic by a number of consistency results. For instance, we show if there is a …
-
The Borel Complexity of Isomorphism for Some First Order Theories
… for all lambda. Second, we consider colored linear orders, which are (complete theories of) a linear order expanded by countably many unary predicates. We discover the same characterization as with o-minimal theories, taking the same values, with the exception that all finite values are …
-
Applications of Transferring the Ramsey Property Between Categories
… in [25], with the Self-Dual Ramsey Theorem of Linear Orders as proven in [23]. It turns out when working with trees there is no Ramsey Theorem for a nice subcategory of pairs of maps. However we obtain a subcategory with finite Ramsey degrees.
-
Computability Theoretic Aspects of Profinite Groups and Models of Presburger Arithmetic
… key to these results is the connection between linear orders, divisible ordered abelian groups and Presburger groups. We show how given a linear order $L$, one can construct a divisible ordered abelian group $V_L$ and a Presburger group $P_L=V_L\times \Z$ such that the degree spectra and Scott …
-
Combinatorics of Condorcet Domains
Condorcet domains are sets of linear orders in which the majority relation of any profile with an odd number of voters is always transitive. One of the major research questions in the literature focuses on characterising maximal Condorcet domains. The class of peak-pit maximal Condorcet domains has …
-
Better-Quasi-Orders: Extensions and Abstractions
… generalise the notion of �-scattered to partial orders and prove that some large classes of �-scattered partial orders are better-quasi-ordered under embeddability. This generalises theorems of Laver, Corominas and Thomass�e regarding �-scattered linear orders, �-scattered trees, countable …
-
Degree Spectra of Unary relations on ω and ζ
Let X be a unary relation on the domain of (ω,<). The degree spectrum of X on (ω,<) is the set of Turing degrees of the image of X in all computable presentations of (ω,<). Many results are known about the types of degree spectra that are possible for relations forming infinite and coinfinite c.e. …
-
On the Satisfiability of Temporal Logics with Concrete Domains
… results regarding the satisfiability of LTL (linear temporal logic) with constraints over the integers have been established in the past years, while the corresponding results for branching time logics were only partial. In this work we prove that satisfiability of CTL* (computation tree …
-
The computational complexity of prefix classes of logical theories
… for the prefix classes of the theory of finite linear orders with added unary predicates. By a direct coding of Turing machines we get that for $m\geq2$ the formulas in $\Pi\sb{m}$ have an $NSPACE$(exp$\sb{m}(d\sb{m}n$/log $n$)) lower bound. A careful analysis of a finite automata decision …
-
Notions of Complexity Within Computable Structure Theory
… construction. We restrict our attention to linear orders, and ask if, given a computable linear order $\A$ with degree of categoricity $\boldsymbol{d}$, it is possible to construct a computable isomorphic copy of $\A$ such that the isomorphism achieves the degree of categoricity and …
-
Subalgebras of small Souslin Algebras and maximal chains in Souslin Algebras
… its maximal chains are pairwise isomorphic as linear orders. The basic question which motivated this thesis was, whether there is under appropriate set theoretical assumptions an atomless and chain homogeneous, atomless and complete Boolean algebra B, such that the maximal chains of B are not …
Page 1 of 2