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 8 of 8 for “"Definability"”.
-
Definability and decidability for expansions of arithmetic by sets definable from positional numeration systems
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-12-04 without embargo terms
-
On Weak Number Theories
Decidability and definability are two separate but quite related topics in logic. Many undecidability results are proved by positive definability results. In Chapter 1 we reformulate Schinzel's theorem about diophantine equations with parameters to get some number theoretic results. In later …
-
Descriptive complexity of constraint problems
… CSPs over the Boolean domain can be framed as a definability result: Either a CSP is definable in fixed-point logic with rank (FPR), or it is NP-hard. Furthermore, we show that a dichotomy exists also in the general case. For VCSPs over arbitrary domains, we show that a VCSP is either definable …
-
Algebraically closed fields with characters; differential-henselian monotone valued differential fields
… valued differential fields. We also consider definability in differential-henselian monotone fields with c-map and angular component map.
-
Effective Versions of Ramsey's Theorem
… the degrees of unsolvability and arithmetical definability properties of sets in H(P) for recursive and recursively enumerable partitions P.
-
Probabilistic concurrent game semantics
… terms of strategies. For the latter, we show a definability result in the spirit of the game semantics tradition. This solves an open problem, as it is notoriously difficult to model Probabilistic PCF with sequential game semantics. Finally, we introduce a model for measurable game semantics, in …
-
Logic and games on automatic structures
… characterization of such quantifiers in terms of definability using cardinality and modulo counting quantifiers. We show that these quantifiers indeed preserve regularity on all automatic structures, including the non-injective omega-automatic ones. As a corollary we answer a question of …