-
This thesis’s main objects of study are natural language predicates that can embed clauses. These verbs or verb-like expressions usually represent some relation between the subject of a sentence and a proposition. Clause-embedding predicates differ in the types of clauses they can embed. The chal...
-
The Query-by-Example problem (QBE) is about the existence of a fitting query for a given database instance and positive/negative labelled data examples. The question is: given an input database instance and sets of user examples, does there exist an explanatory query whose answers to it include t...
-
Classically, many problems can be shown to have computational lower bounds in their time complexity conditioned on the hardness of three popular problems; k-SAT, 3SUM and APSP. This is done through fine-grained reductions and research in this classical field has recently exploded, as can be seen ...
-
This thesis contributes to the study of degrees of the finite model property (FMP), initiated by G. Bezhanishvili, N. Bezhanishvili and T. Moraschini (2022). We investigate degrees of FMP in extensions of bi-intuitionistic logic through the lens of universal algebra. Motivated by the characterisa...
-
Cost automata, introduced under the name ‘distance parity automata’, are in fact automata with something extra: counters. In the most simple case, the automaton has one counter which, during a transition, we can increase, check, reset or perform a combination of these actions. This machinery is v...
-
This thesis presents a study of translations, special “hybrid” logical systems developed on the basis of these translations, and general Blok-Esakia theory. This is done on two levels: the development of a theoretical framework for analysing such questions, as well as an analysis of the special c...
-
This thesis introduces and develops the notion of a relative weak factorization system. Motivated by research directions in type theory, we combine ideas from algebraic weak factorization systems with the concept of relative monads and comonads, to define a generalized, more flexible analogue of ...
-
Weihrauch degree theory is a field of study which attempts to classify mathematical theorems based on their computational content. Brattka and Gherardi obtained a picture of the Weihrauch degrees of theorems of mathematical analysis which is stratified by the so-called choice and boundedness prin...
-
In the literature on relative consistency results, one often encounters the claim that all natural axiomatic theories are linearly ordered in terms of consistency strength. Without a precise definition of a natural theory, it is not clear how to assess the truth of this claim or how to judge whet...
-
This thesis is an investigation into how to define the notion of bisimulation over parity formulas. We provide and argue for a list of criteria against which we could judge how good such a definition is. In general, a notion of bisimulation should be sound, closed under union and composition, eas...
-
The present thesis studies formal properties of a family of so-called modal information logics (MILs)—modal logics first proposed in van Benthem (1996) as a way of using possible-worlds semantics to model a theory of information. They do so by extending the language of propositional logic with a ...