Efficient best-first search algorithms have been developed for deterministic two-player games with two-outcome.We present a formal framework to represent such best-first search algorithms.The framework is general enough to express popular algorithms such as Proof Number Search, Monte Carlo Tree Search, and the Product Propagation algorithm.We then show how a similar framework can be devised for two more general settings: two-player games with multiple outcomes, and the model checking problem in modal logic K.This gives rise to new Proof Number and Monte Carlo inspired search algorithms for these settings.Similarly, the alpha-beta pruning technique is known to be very important in games with sequential actions.We propose an extension of this technique for stacked-matrix games, a generalization of zero-sum perfect information two-player games that allows simultaneous moves.

This thesis presents TransLucid, a low-level, purely declarative, intensional programming language. Built on a simple algebra and with just a small number of primitives, TransLucid programs define arbitrary dimensional infinite data structures, which are then queried to produce results. The formal foundations of TransLucid come from the work in intensional logic by Montague and Scott. The background chapters give a history of intensional logic and its predecessors in the Western world, as well as a history of intensional programming and Lucid, the first intensional programming language. The semantics of TransLucid are fully specified in the form of operational semantics. Three levels of semantics are given, in increasing order of efficiency, with the sequential warehouse semantics, the most efficient, being presented together with a proof that any expression will be evaluated by only examining relevant dimensions in the current context. The language is then extended in three important ways, by adding versioned identifiers, (declarative) side-effects and timestamped equations and demands. Adding versioned identifiers to TransLucid enriches the expressiveness of the language and allows the encoding of a variety of programming paradigms, ranging from manipulating large data-cubes to pattern-matching. Adding side-effects supports one of the main reasons for TransLucid: namely, to provide a target language, together with a methodology, for translating the main programming paradigms, thus creating a uniform end platform that can be the focus for optimisation and program verification. A translation of imperative programs into TransLucid is given. Timestamped equations and demands enable TransLucid to become a language for synchronous programming in real-time systems, as well as allowing runtime updates to a program's equations. The language TransLucid represents a decisive advance in declarative programming. It has applications in many fields of computer science and opens up exciting new avenues of research.

Two main questions are addressed in this dissertation, namely: 1. What is the correct higher-order modal theory; 2. What does it take for theories to be equivalent. The whole dissertation consists of an extended argument in defence of the joint truth of two higher-order modal theories, namely, Plantingan Moderate Contingentism, a higher-order necessitist theory advocated by Plantinga (1974) and committed to the contingent being of some individuals, and Williamsonian Thorough Necessitism, a higher-order necessitist theory advocated by Williamson (2013) and committed to the necessary being of every possible individual. The case for the truth of these two theories relies on defences of the following metaphysical theses: i) Thorough Serious Actualism, according to which no things could have been related and yet be nothing, ii) Higher-Order Necessitism, according to which necessarily, every higher-order entity is necessarily something. It is shown that Thorough Serious Actualism and Higher-Order Necessitism are both implicit commitments of very weak logical theories. Prima facie, Plantingan Moderate Contingentism and Williamsonian Thorough Necessitism are jointly inconsistent. The argument for their joint truth thus relies also on showing i) their equivalence, and ii) that the dispute between Plantingans and Williamsonians is merely verbal. The case for i) and ii) relies on the Synonymy Account, an account of theory equivalence developed and defended in the dissertation. According to the account, theories are equivalent just in case they have the same structure of entailments and commitments, and the occupiers of the places in that structure are the same propositions. An immediate consequence of the Synonymy Account is that proponents of synonymous theories are engaged in merely verbal disputes. The Synonymy Account is also applied to the debate between noneists and Quineans, revealing that what is in question in that debate is what are the expressive resources available to describe the world.

Orientador: Prof. Dr. Vinícius Cifú Lopes / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2015. / Iniciamos esse trabalho com uma breve introdução histórica para que o leitor tenha uma noção de quando e por que houve interesse em sistematizar os raciocínios lógicos desde Aristóteles até nossos dias. A seguir, apresentamos noções de linguagens, com seus símbolos e regras de formação, sintaxe dos cálculos proposicional e de predicados, funções e operações envolvendo o cálculo de predicados e aplicações (fórmulas matemáticas bem conhecidas). No terceiro capítulo introduzimos o conceito de semântica e apresentamos alguns procedimentos de prova como as tabelas-verdade, tableaux e dedução natural envolvidos nesses sistemas. No quarto capítulo apresentamos a Lógica Modal Alética, demonstrações de teoremas do sistema S5, semântica relacionada com mundos possíveis. Em seguida, apresentamos noções de lógicas modais não aléticas e no sexto capítulo, finalizamos esse trabalho com uma atividade que pode ser aplicada para alunos no Ensino Médio. / We begin this work with a brief historical introduction to when and why there was interest in systematizing logical reasoning since Aristotle until our days. Next, we introduce notions of languages, with its symbols and forming rules, the syntax of propositional and predicate calculi, functions and operations involving the predicate calculus and applications (well known mathematical formulas). In the third chapter we introduce the concept of semantics and present some proof procedures as truth tables, tableaux and natural deduction involved in these systems. In the fourth chapter we present alethic Modal logic, proofs of theorems of the S5 system, and the semantics related to possible worlds. Then, we present notions of non-alethic modal logics. In the sixth chapter, we conclude with an activity that can be applied to high school students.

Cette thèse étudie la théorie de la correspondance et la théorie des preuves pour la logique modale monotone et les logiques qui en sont proches.La première partie de la thèse établit une connexion formelle entre la théorie de la correspondance algorithmique et des résultats de caractérisation duale pour les treillis finis, similaire à la caractérisation par Nation d'une hiérarchie de variétés de treillis qui généralise les treillis distributifs. Cette connexion formelle est établie en utilisant la logique modale monotone. Nous adaptons l'algorithme ALBA pour la correspondance à l'environnement de la logique modale monotone, et nous utilisons un encodage, induit par une dualité, des treillis finis sous forme de 'neighbourhood frames' pour traduire les termes de la théorie des treillis en formules de la logic modal monotone.La deuxième partie de la thèse étend la théorie des 'display calculi' à la logique Baltag-Moss-Solecki pour les actions épistémiques et la connaissance (Epistemic Actions and Knowledge), à la logique modale monotone et à la logique propositionnelle dynamique (PDL). Nos résultats incluent plusieurs méta-théorèmes d'élimination de la coupure qui généralisent le théorème original de Belnap dans des dimensions différentes et indépendantes. Les deux principales généralisations des 'display calculi' traitées dans la thèse sont : la généralisation d'une théorie pour les langages ne contenant qu'un seul type à une théorie pour les langages contenant plusieurs types, et la généralisation d'une théorie pour les calculs satisfaisant la propriété de 'display' aux calculs ne la satisfaisant pas. / The present thesis focuses on Monotone Modal Logic and closely related logics from the point of view of Correspondence Theory and Proof Theory.The first part of the thesis establishes a formal connection between algorithmic corre- spondence theory and certain dual characterization results for finite lattices, similar to Nation's characterization of a hierarchy of pseudovarieties of finite lattices progressively generalizing finite distributive lattices. This formal connection is established through monotone modal logic. Specifically, we adapt the correspondence algorithm ALBA to the setting of monotone modal logic, and we use a certain duality-induced encoding of finite lattices as monotone neighbourhood frames to translate lattice terms into formulas in monotone modal logic.The second part of the thesis extends the theory of display calculi to Baltag-Moss- Solecki's logic of Epistemic Actions and Knowledge (EAK), Monotone Modal Logic (MML), and Propositional Dynamic Logic (PDL). Our results include several cut-elimination metatheorems, which generalize the original metatheorem of Belnap in different and mutually independent dimensions. The two main generalizations of display calculi treated in the thesis are: the generalization from single type to multi-type languages, and from the full or relativized display property to no display property.

Les arguments de concevabilité sont des arguments philosophiques reposant sur le principe selon lequel tout ce qui est concevable est possible. Cette thèse se propose d'évaluer à un niveau général cette forme d'argumentation en s'appuyant sur des exemples historiques et contemporains. les arguments de concevabilité, quelle que soit la position philosophique qu'ils visent à défendre, soulèvent en effet des difficultés qui leur sont communes et ont trait principalement (i) à la définition de la notion de possibilitée, (ii) à la définition de la notion de concevabilité, et (iii) à la légitimité de l'inférence allant de l'une à l'autre. Le travail consiste d'abord (chapitres 1-3) à construire la catégorie que constituent les arguments de concevabilité en spécifiant notamment le genre de thèses philosophiques qu'ils peuvent chercher à établir. Une fois précisés les objectifs que les arguments de concevabilité peuvent viser, il s'engage (chapitres 4-8) dans l'examen de savoir si les ressources fournies par Ia concevabilité et l'inférence menant du concevable vers le possible suffisent à les atteindre. Pour ce faire, le travail propose une analyse détaillée des différentes formes de possibilité (chapitres 4-5) et de concevabilité (chapitres 6-8) impliquées dans ces arguments. II aboutit à une position dite sceptique modérée au sujet de la validité de cette forme d'argumentation, sur la base de la démonstration que, pour les thèses philosophiques qui nécessitent l'etablissement d'une possibilité métaphysique, la concevabilitée s'avère être un guide insuffisamment fiable, quelle que soit la manière dont on comprend la concevabilité. Mais il défend aussi l'idée que le fait que les arguments de concevabilité ne soient pas toujours concluants n'implique pas qu'ils sont depourvus d'utilité argumentative: car ils nous obligent à clarifier les implications modales de nos conceptions philosophiques et la manière dont nous pouvons raisonner au sujet de ces implications. Cette conception des arguments de concevabilité est appliquée pour finir à la clarification d'un chapitre essentiel de la philosophie de la cognition contemporaine relatif à la possibilité de fournir une explication naturaliste (physicaliste) de la conscience phénoménale, et ou un argument de concevabilité qui a fait couler beaucoup d'encre, dit argument des zombis, joue un rôle essentiel. / Conceivability arguments are philosophical arguments which rely crucially on the principle according to which conceivability entails possibility. This dissertation provides an analysis and a critical assessment of this kind of argumentative strategy, on the basis of contemporary and historical examples. Various possible explanations of the notion of conceivability are considered and it is argued that the inference from conceivability to possibility does not enable conceivability arguments to reach all their intended conclusions, especially those pertaining to substantial metaphysical issues.

The eight topological RCC8(or Egenhofer-Franzosa)- relations between spatial regions play a fundamental role in spatial reasoning, spatial and constraint databases, and geographical information systems. In analogy with Halpern and Shoham’s modal logic of time intervals based on the Allen relations, we introduce a family of modal logics equipped with eight modal operators that are interpreted by the RCC8-relations. The semantics is based on region spaces induced by standard topological spaces, in particular the real plane. We investigate the expressive power and computational complexity of the logics obtained in this way. It turns our that, similar to Halpern and Shoham’s logic, the expressive power is rather natural, but the computational behavior is problematic: topological modal logics are usually undecidable and often not even recursively enumerable. This even holds if we restrict ourselves to classes of finite region spaces or to substructures of region spaces induced by topological spaces. We also analyze modal logics based on the set of RCC5relations, with similar results.

In classical propositional logic (CPL) logical reasoning is formalised as logical entailment and can be computed by means of tableau and resolution proof procedures. Unfortunately CPL is not expressive enough and using first order logic (FOL) does not solve the problem either since proof procedures for these logics are not decidable. Modal propositional logics (MPL) on the other hand are both decidable and more expressive than CPL. It therefore seems reasonable to apply tableau and resolution proof systems to MPL in order to compute logical entailment in MPL. Although some of the principles in CPL are present in MPL, there are complexities in MPL that are not present in CPL. Tableau and resolution proof systems which address these issues and others will be surveyed here. In particular the work of Abadi & Manna (1986), Chan (1987), del Cerro & Herzig (1988), Fitting (1983, 1990) and Gore (1995) will be reviewed. / Computing / M. Sc. (Computer Science)

Cet ouvrage a été rédigé en LaTeX, ce qui permet d'atteindre directement certaines sections, notes ou références bibliographiques par le biais des hyperliens. / Ce mémoire se veut une synthèse critique de la littérature portant sur la logique déontique. Le premier objectif est d'y présenter un aperçu historique de son origine et de son évolution. Cet objectif sera principalement atteint par le biais du chapitre 2 portant sur les paradoxes, lequel nous permettra non seulement de voir en réaction à quoi les principales approches se sont développées, mais nous donnera aussi une vue d'ensemble quant aux différents courants que l'on retrouve en logique déontique. En second lieu, cet ouvrage vise à fournir une synthèse de la littérature portant sur l'analyse formelle du discours normatif. Les chapitres 3, 4 et 5 offrent une synthèse des principaux courants qui cherchent à répondre à cet objectif, ce que l'on peut regrouper sous trois banières, à savoir les logiques monadiques, les logiques dyadiques et les logiques temporelles. Finalement, nous proposons une lecture critique de cette littérature. Cette critique, qui repose notamment sur la prémisse à savoir que la logique déontique se doit non pas de rendre compte de l'utilisation du discours normatif mais plutôt de sa structure, vise à montrer que les systèmes actuels ne parviennent pas à rendre compte adéquatement de certaines caractéristiques fondamentales au discours juridique. / In this essay we aim to provide a critical analysis of the literature regarding deontic logic. First of all, we wish to give a historical account of deontic logic's evolution, which will be done mainly by chapter 2. This chapter concerns the paradoxes of deontic logic and gives an overview of the usual systems and their origin. Our second objective is to provide a synthesis of the literature regarding the formal analysis of the normative discourse. The chapters 3, 4 and 5 give an account of the three principal ways which deal with deontic operators, that is the monadic deontic logic, the dyadic deontic logic and the temporal deontic logic. Finally, we propose a critical analysis of that literature and we show that these systems do not represent adequately some of the normative discourse's fundamental characteristics. We will accomplish this by providing an analysis of the legal discourse and show that the concept of obligation has some properties and behaves in a way that cannot be represented by the actual systems.

Em Complexidade Descritiva investigamos o uso de logicas para caracterizar classes problemas pelo vies da complexidade. Desde 1974, quando Fagin provou que NP e capturado pela logica existencial de segunda-ordem, considerado o primeiro resultado da area, outras relac~oes entre logicas e classes de complexidade foram estabelecidas. Os resultados mais conhecidos normalmemte envolvem logica de primeira-ordem e suas extens~oes, e classes de complexidade polinomiais em tempo ou espaco. Alguns exemplos sÃo que a logica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse P e que a logica de segunda-ordem estendida com o operador de fecho transitivo captura a classe PSPACE. Nesta dissertaÃÃo, analisaremos inicialmente a expressividade de algumas logicas modais com relacÃo ao problema de decisÃo REACH e veremos que e possvel expressa-lo com as logicas temporais CTL e CTL. Analisaremos tambem o uso combinado de logicas de ordem superior com o operador de menor ponto xo e obteremos como resultado que cada nvel dessa hierarquia captura cada nvel da hierarquia determinstica em tempo exponencial. Como corolario, provamos que a hierarquia de HOi(LFP) nÃo colapsa, ou seja, HOi(LFP) HOi+1(LFP) / In Descriptive Complexity, we investigate the use of logics to characterize computational classes os problems through complexity. Since 1974, when Fagin proved that the class NP is captured by existential second-order logic, considered the rst result in this area, other relations between logics and complexity classes have been established. Wellknown results usually involve rst-order logic and its extensions, and complexity classes in polynomial time or space. Some examples are that the rst-order logic extended by the least xed-point operator captures the class P and the second-order logic extended by the transitive closure operator captures the class PSPACE. In this dissertation, we will initially analyze the expressive power of some modal logics with respect to the decision problem REACH and see that is possible to express it with temporal logics CTL and CTL. We will also analyze the combined use of higher-order logics extended by the least xed-point operator and obtain as result that each level of this hierarchy captures each level of the deterministic exponential time hierarchy. As a corollary, we will prove that the hierarchy of HOi(LFP), for i 2, does not collapse, that is, HOi(LFP) HOi+1(LFP)