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 150 for “"Decidability"”.
-
Significance and decidability
According to the empiricist criterion of meaning, a sentence makes a meaningful assertion, and thus can be said to be true or false, only if either it is analytic or it is capable, at least in principle, of experiential test. Sentences of this kind are significant sentences. Although many …
-
Decidability in Algebraic Geometry
… theme of our investigation is the concept of Decidability in Algebra/Algebraic Geometry. To the best of our knowledge this seems to be novel in the sense that there is no work known to isolate or to focus on the concept of Decidability in the context of Commutative Algebra. Decidability is …
-
Decidability boundaries in linear dynamical systems
<p>The object of this thesis is the study of the decidability properties of linear dynamical systems, which have fundamental ties to theoretical computer science, software verification, linear hybrid systems, and control theory. <p>In particular, we describe a method for deciding the termination of …
-
Decidability in extensions of Fp((t))
… the existence of an algebraically prime model) decidability of the first-order theory of F_p((t)). However, this technical condition is still largely mysterious. We sketch an (unsuccessful) attempt at an unconditional proof and highlight where difficulties arise.</p> <p>In Chapter 1 we introduce …
-
GUARDED NETKAT: SOUNDNESS, PARTIAL-COMPLETENESS, DECIDABILITY
The equational theory of Kleene Algebra with Tests (KAT) provides an algebraic framework to manipulate uninterpreted programs along with a PSPACE-complete procedure for deciding program equivalence. One of the most successful applications of the KAT theory is found in NetKAT, which instantiates the …
-
Decidability for Residuated Lattices and Substructural Logics
We present a number of results related to the decidability and undecidability of various varieties of residuated lattices and their corresponding substructural logics. The context of this analysis is the extension of residuated lattices by various simple equations, dually, the extension of …
-
Turing Decidability and Computational Complexity of MorseHomology
… is computable in the classical sense of Turing decidability, bound the complexity of finding the Morse homology of a given simplicial complex, and provide a measure for when this is more efficient than simplicial homology.
-
Decidability bounds for extensions of Presburger arithmetic
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms
-
Decidability and Algorithmic Analysis of Dependent Object Types (DOT)
… This thesis presents a detailed investigation of decidability and algorithmic properties of the family of DOT calculi. In decidability analysis, the undecidability of subtyping of several calculi is formally established, including the D <: and D ∧ calculi. Prior to this investigation, the …
-
Decidability for Non-Standard Conversions in Typed Lambda-Calculi
This thesis studies the decidability of conversions in typed lambda-calculi, along with the algorithms allowing for this decidability. Our study takes in consideration conversions going beyond the traditional beta, eta, or permutative conversions (also called commutative conversions). To decide …
-
On the decidability of finite extensions of decidable fields
<p>This paper is primarily concerned with the following question which first appeared in Koenigsmann’s On a Question of Abraham Robinson’s:</p> <p><em>Is a finite field extension of a decidable field always decidable?</em></p> <p>This offers a “twist” to a question that was originally posed by …
-
Expressiveness and Decidability of Weighted Automata and Weighted Logics
… structure. In the second part, we lift four decidability results from max-plus word automata to max-plus tree automata. Max-plus word and tree automata are weighted automata over the max-plus semiring and assign real numbers to words or trees, respectively. We show that, like for max-plus …
-
Decidability in the Hyperdegrees and a Theorem of Hyperarithmetic Analysis
In this thesis we explore two different topics: the complexity of the theory of the hyperdegrees, and the reverse mathematics of a result in graph theory. For the first, we show the $\Sigma_{2}$ theory of the hyperdegrees as an upper-semilattice is decidable, as is the $\Sigma_{2}$ theory of the …
-
Contributions to Recognizability: Self-generating Sets, Decidability, Automaticity and Multidimensional Sets
… alternative decision procedure for a well-known decidability problem. Next, we give bounds on the automaticity of three different languages: the language of primitive words over a finite alphabet, the language of unbordered words over a finite alphabet and the language of representations of monic …
-
Closure, Decidability, and Complexity Results for Restricted Variants of Two-Dimensional Automata
… that can be applied to an automaton's language), decidability properties (questions about languages and automata that can be answered by an algorithm), and complexity properties (computational resources needed to decide problems or recognize languages). We first consider decision problems for …
-
Abstract Numeration Systems : Recognizability, Decidability, Multidimensional S-Automatic Words, and Real Numbers
… on polynomial regular languages. The second is a decidability problem, which has been already studied notably by J. Honkala and A. Muchnik and which is studied here for two new cases: the linear positional numeration systems and the abstract numeration systems. Next, we focus on the extension to …
-
On the decidability of the field of maximal abelian extension of p-adic numbers
<p>In this project we investigate some approaches attacking the question of whether the theory of the maximal abelian extension of the p-adic numbers is decidable. A list of axioms is presented whose completeness we aim to show via quantifier elimination. We separated the quantifier elimination …
Page 1 of 8