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 131 for “"computability"”.
-
Computability and Structure
This dissertation contains results in the area of constructive mathematics with emphasis to computable algebra and computable analysis. Mal'cev [66] and Rabin [86] initiated the study of computable groups, and Turing [96, 95] started the investigation of effective procedures in analysis. The thesis …
-
Computability over abstract structures
Not available
-
Computability and Tiling Problems
… problems and mathematical logic, specifically computability theory. We focus on Wang prototiles, as defined in [32]. We begin by studying Domino Problems, and do not restrict ourselves to the usual problems concerning finite sets of prototiles. We first consider two domino problems: whether a …
-
Weighted computability with discounting
Στην παρούσα διατριβή εισάγουμε τις έννοιες της Γραμμικής Χρονικής Λογικής (Linear TimeLogic, εν συντομία LTL) με βάρη και discounting από τον ημιδακτύλιο max-plus, της πρώτηςτάξης λογικής (First-Order Logic, εν συντομία FO logic) με βάρη και discounting από τον maxplus,των ω-star-free σειρών και …
-
Computability, probability and logic
Contains fulltext : 139785.pdf (Publisher’s version ) (Open Access)
-
Computability Theory and Some Applications
We explore various areas of computability theory, ranging from applications in computable structure theory primarily focused on problems about computing isomorphisms, to a number of new results regarding the degree-theoretic notion of the bounded Turing hierarchy. In Chapter 2 (joint with Csima, …
-
Partition Theorems and Computability Theory
"We also study Ramsey degrees, i.e. those Turing degrees which are able to compute homogeneous sets for every computable 2-coloring of pairs of natural numbers, in an attempt to further understand the effective content of Ramsey's Theorem for exponent 2. We establish some new results about these …
-
Analog Computability with Differential Equations
… model of computation to the notion of tracking computability as studied by Tucker and Zucker.
-
Rethinking Resource Allocation: Fairness and Computability
In the field of multiagent systems, one important problem is fairly allocating items among a set of agents. The gold standard fairness property is envy-freeness whereby each agent prefers the bundle allocated to them over any other bundle. For indivisible goods, envy-freeness cannot be guaranteed: …
-
Formalizing Abstract Computability: Turing Categories in Coq
… extensively studied using traditional tools of computability theory. However, with the development of category-theoretic methods it has become possible to study recursion in a more general (abstract) sense. The particular model this thesis is structured around is known as a Turing category. The …
-
Chemical reaction networks: Computability, complexity, and randomness
<p>In this dissertation we study the computational power of chemical reaction networks (CRNs), under both the deterministic and stochastic semantics of the model. We explore the class of real numbers that are computed in real time by deterministic CRNs. We develop the elements of the theory of …
-
Computability of Function Spaces from Harmonic Analysis
… its values in finite time. We explore notions of computability for function spaces such as the Hardy space H^1(R) and the Besov space B^p(T) from harmonic analysis. After a comprehensive introduction to computable analysis and studying several function spaces, we establish some original results. …
-
Computability and complexity of two-way finite automata
Υπολογισιμότητα πεπερασμένων αυτοματων μιας κεφαλής και ισοδυναμία αυτών. Κλάσεις πολυπλοκότητας αυτομάτων, πληρότητα, αναγωγές, σχέσεις με πολυπλοκότητα μηχανών τιούρινγκ. Αναζήτηση αναγωγής για την πληρότητα προβλημάτων με σταθερή είσοδο.
-
On the Computability of the Frechet Distance Between Triangulated Surfaces
… is computable. In this thesis, we study the computability of the Frechet distance between triangulated surfaces. We give three partial answers to the question whether it is computable. For triangulated surfaces, we show that the Frechet distance is semi-computable, a weaker notion of …
-
Computability and Complexity Properties of Automatic Structures and their Applications
… algorithms. Continuing a tradition of studying computability in mathematics, we examine automatic structures, mathematical objects which can be represented by automata, and apply resulting observations to computer science. We measure the complexity of automatic structures via well-established …
-
Computability Theoretic Aspects of Profinite Groups and Models of Presburger Arithmetic
Profinite groups, which are exactly the Galois groups, are all either finite or uncountable. However, all second countable profinite groups can be presented as the set of paths through a countable tree. We use these tree presentations to find upper bounds on the complexity of the existential …
Page 1 of 7