Browsing by study line "Matematiikka"

Several extensions of first-order logic are studied in descriptive complexity theory. These extensions include transitive closure logic and deterministic transitive closure logic, which extend first-order logic with transitive closure operators. It is known that deterministic transitive closure logic captures the complexity class of the languages that are decidable by some deterministic Turing machine using a logarithmic amount of memory space. An analogous result holds for transitive closure logic and nondeterministic Turing machines. This thesis concerns the k-ary fragments of these two logics. In each k-ary fragment, the arities of transitive closure operators appearing in formulas are restricted to a nonzero natural number k. The expressivity of these fragments can be studied in terms of multihead finite automata. The type of automaton that we consider in this thesis is a two-way multihead automaton with nested pebbles. We look at the expressive power of multihead automata and the k-ary fragments of transitive closure logics in the class of finite structures called word models. We show that deterministic twoway k-head automata with nested pebbles have the same expressive power as first-order logic with k-ary deterministic transitive closure. For a corresponding result in the case of nondeterministic automata, we restrict to the positive fragment of k-ary transitive closure logic. The two theorems and their proofs are based on the article ’Automata with nested pebbles capture first-order logic with transitive closure’ by Joost Engelfriet and Hendrik Jan Hoogeboom. In the article, the results are proved in the case of trees. Since word models can be viewed as a special type of trees, the theorems considered in this thesis are a special case of a more general result.

The goal of the thesis is to prove the Dold-Kan Correspondence, which is a theorem stating that the category of simplicial abelian groups sAb and the category of positively graded chain complexes Ch+ are equivalent. The thesis also goes through these concepts mentioned in the theorem, starting with categories and functors in the first section. In this section, the aim is to give enough information about category theory, so that the equivalence of categories can be understood. The second section uses these category theoretical concepts to define the simplex category, where the objects are ordered sets n = { 0 -> 1 -> ... -> n }, where n is a natural number, and the morphisms are order preserving maps between these sets. The idea is to define simplicial objects, which are contravariant functors from the simplex category to some other category. Here is also given the definition of coface and codegeneracy maps, which are special kind of morphisms in the simplex category. With these, the cosimplicial (and later simplicial) identities are defined. These identities are central in the calculations done later in the thesis. In fact, one can think of them as the basic tools for working with simplicial objects. In the third section, the thesis introduces chain complexes and chain maps, which together form the category of chain complexes. This lays the foundation for the fourth section, where the goal is to form three different chain complexes out of any given simplicial abelian group A. These chain complexes are the Moore complex A*, the chain complex generated by degeneracies DA* and the normalized chain complex NA*. The latter two of these are both subcomplexes of the Moore complex. In fact, it is later on shown that there exists an isomorphism An = NAn +DAn between the abelian groups forming these chain complexes. This connection between these chain complexes is an important one, and it is proved and used later on in the seventh section. At this point in the thesis, all the knowledge for understanding the Dold-Kan Correspondence has been presented. Thus begins the forming of the functors needed for the equivalence, which the theorem claims to exist. The functor from sAb to Ch+ maps a simplicial abelian group A to its normalized chain complex NA*, the definition of which was given earlier. This direction does not require that much additional work, since most of it was done in the sections dealing with chain complexes. However, defining the functor in the opposite direction does require some more thought. The idea is to map a chain complex K* to a simplicial abelian group, which is formed using direct sums and factorization. Forming it also requires the definition of another functor from a subcategory of the simplex category, where the objects are those of the simplex category but the morphisms are only the injections, to the category of abelian groups Ab. After these functors have been defined, the rest of the thesis is about showing that they truly do form an equivalence between the categories sAb and Ch+.

The thesis consists of presenting and analysing the original proof for the Embedding Theorem that Hassler Whitney gave in his 1936 article Differentiable Manifolds. The embedding theorem states that given an m-dimensional Cr-differentiable (r ≥ 1) manifold M, it is possible to embed it in Euclidean space Rn, if n ≥ 2m + 1. Embedding is defined as a mapping f : M → Rn which is Cr-smooth, bijective immersion that is homeomorphism to its image f[M]. Whitney’s proof rests on few important novel concepts and a series of lemmas in relation to them. These concepts include the concept of the k-extent of a set, a sort of a k-dimensional measure in an n-dimensional space; the concept of Cr-function g : M → N approximating (f, M, r, η), where f is a Cr-function f : M → N, η an error function; and the concept of (f, r, η)-properties defined for such g. Outstanding lemmas of general nature are Lemma 7: If f : M → N is a Cr-map and A ⊂ M is of finite (zero) k-extent, then f[A] is of finite (zero) k-extent. Lemma 8: For open sets R and R′ of Rm and Rh, if {Tα} is a h-parameter family of C1-maps of R ⊂ Rm into Rn, and A ⊂ R and B ⊂ Rn closed subsets, such that A is of finite k-extent and B of zero (h − k)-extent, then for some α ∈ R′, Tα[A] does not intersect B. Lemma 9: If f : M → N is a Cr-map, η positive continuous function in M, Ω1, Ω2, . . . are (f, r, η)- properties, then there is a Cr-map F : M → N which approximates (f, M, r, η) and has properties Ω1, Ω2, . . . . Lemmas 11 and 12 then show that bijectivity and immersion property are the logical sum of countable number of (f, r, η)-properties. These facts are used in finding an embedding F : M → Rn by perturbing a given smooth function f : M → Rn. Detailed treatment of all proofs is provided. Adjustments to the proofs are made where deemed necessary; auxiliary assumptions are made where they seem to be required. Clarifications and proofs are given to facts noted but not proven in the article