Switch to: References
Citations of:
Add citations
You mustlogin to add citations.
| |
We construct logical languages which allow one to represent a variety of possible types of changes affecting the information states of agents in a multi-agent setting. We formalize these changes by defining a notion of epistemic program. The languages are two-sorted sets that contain not only sentences but also actions or programs. This is as in dynamic logic, and indeed our languages are not significantly more complicated than dynamic logics. But the semantics is more complicated. In general, the semantics of (...) an epistemic program is what we call aprogram model. This is a Kripke model of ‘actions’,representing the agents' uncertainty about the current action in a similar way that Kripke models of ‘states’ are commonly used in epistemic logic to represent the agents' uncertainty about the current state of the system. Program models induce changes affecting agents' information, which we represent as changes of the state model, called epistemic updates. Formally, an update consists of two operations: the first is called the update map, and it takes every state model to another state model, called the updated model; the second gives, for each input state model, a transition relation between the states of that model and the states of the updated model. Each variety of epistemic actions, such as public announcements or completely private announcements to groups, gives what we call an action signature, and then each family of action signatures gives a logical language. The construction of these languages is the main topic of this paper. We also mention the systems that capture the valid sentences of our logics. But we defer to a separate paper the completeness proof. (shrink) | |
In this paper we introduce Dynamic Epistemic Logic, which is alogic for reasoning about information change in a multi-agent system. Theinformation structures we use are based on non-well-founded sets, and canbe conceived as bisimulation classes of Kripke models. On these structures,we define a notion of information change that is inspired by UpdateSemantics (Veltman, 1996). We give a sound and complete axiomatization ofthe resulting logic, and we discuss applications to the puzzle of the dirtychildren, and to knowledge programs. | |
A history of the logic of action is outlined, beginning with St Anselm. Five modern authors are discussed in some detail: von Wright, Fitch, Kanger, Chellas and Pratt. | |
It has been an open question whether or not we can define a belief revision operation that is distinct from simple belief expansion using paraconsistent logic. In this paper, we investigate the possibility of meeting the challenge of defining a belief revision operation using the resources made available by the study of dynamic epistemic logic in the presence of paraconsistent logic. We will show that it is possible to define dynamic operations of belief revision in a paraconsistent setting. | |
No existing conditional semantics captures the dual role of 'if' in embedded interrogatives — 'X wonders if p' — and conditionals. This paper presses the importance and extent of this challenge, linking it to cross-linguistic patterns and other phenomena involving conditionals. Among these other phenomena are conditionals with multiple 'if'-clauses in the antecedent — 'if p and if q, then r' — and relevance conditionals — 'if you are hungry, there is food in the cupboard'. Both phenomena are shown to (...) be problematic for existing analyses. Surprisingly, the decomposition of conditionals needed to capture the link with interrogatives provides a new analysis that captures all three phenomena. The model-theoretic semantics offered here relies on a dynamic conception of meaning and compositionality, a feature discussed throughout. (shrink) | |
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 BASIC MODAL LOGIC . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. | |
We identify the computational complexity of the satisfiability problem for FO 2 , the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO 2 has the finite-model property, which means that if an FO 2 -sentence is satisfiable, then it has a finite (...) model. Moreover, Mortimer showed that every satisfiable FO 2 -sentence has a model whose size is at most doubly exponential in the size of the sentence. In this paper, we improve Mortimer's bound by one exponential and show that every satisfiable FO 2 -sentence has a model whose size is at most exponential in the size of the sentence. As a consequence, we establish that the satisfiability problem for FO 2 is NEXPTIME-complete. (shrink) | |
No categories | |
This work explores the hypothesis that natural language is a tool for changing a language user's state of mind and, more specifically, the hypothesis that a sentence's meaning is constituted by its characteristic role in fulfilling this purpose. This view contrasts with the dominant approach to semantics due to Frege, Tarski and others' work on artificial languages: language is first and foremost a tool for representing the world. Adapted to natural language by Davidson, Lewis, Montague, et. al. this dominant approach (...) has crystalized as truth-conditional semantics: to know the meaning of a sentence is to know the conditions under which that sentence is true. Chapter 1 details the animating ideas of my alternative approach and shows that the representational function of language can be understood in terms of the more general function of changing representational mental states. Chapters 2-4 argue that the additional resources of this more general conception of meaning allow us to explain certain phenomena involving conditionals and grammatical mood that truth-conditional semantics does not. In the analysis of these specific phenomena and the articulation of the general approach on offer, it emerges that this approach combines insights and benefits from both use-theoretic and truth-theoretic work on meaning. (shrink) | |
Logic has pride of place in mathematics and its 20th century offshoot, computer science. Modern symbolic logic was developed, in part, as a way to provide a formal framework for mathematics: Frege, Peano, Whitehead and Russell, as well as Hilbert developed systems of logic to formalize mathematics. These systems were meant to serve either as themselves foundational, or at least as formal analogs of mathematical reasoning amenable to mathematical study, e.g., in Hilbert’s consistency program. Similar efforts continue, but have been (...) expanded by the development of sophisticated methods to study the properties of such systems using proof and model theory. In parallel with this evolution of logical formalisms as tools for articulating mathematical theories (broadly speaking), much progress has been made in the quest for a mechanization of logical inference and the investigation of its theoretical limits, culminating recently in the development of new foundational frameworks for mathematics with sophisticated computer-assisted proof systems. In addition, logical formalisms developed by logicians in mathematical and philosophical contexts have proved immensely useful in describing theories and systems of interest to computer scientists, and to some degree, vice versa. Three examples of the influence of logic in computer science are automated reasoning, computer verification, and type systems for programming languages. (shrink) | |
This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. David Elohim examines the nature of epistemic modality, when the modal operator is interpreted as concerning both apriority and conceivability, as well as states of knowledge and belief. The book demonstrates how epistemic modality and hyperintensionality relate to the computational theory of mind; metaphysical modality and hyperintensionality; the types of mathematical modality and hyperintensionality; to the epistemic status of large cardinal axioms, undecidable (...) propositions, and abstraction principles in the philosophy of mathematics; to the modal and hyperintensional profiles of the logic of rational intuition; and to the types of intention, when the latter is interpreted as a hyperintensional mental state. Chapter \textbf{2} argues for a novel type of expressivism based on the duality between the categories of coalgebras and algebras, and argues that the duality permits of the reconciliation between modal and hyperintensional cognitivism and modal and hyperintensional expressivism. Elohim develops a novel, topic-sensitive truthmaker semantics for dynamic epistemic logic, and develops a novel, dynamic two-dimensional semantics grounded in two-dimensional hyperintensional Turing machines. Chapter \textbf{3} provides an abstraction principle for two-dimensional (hyper-)intensions. Chapter \textbf{4} advances a topic-sensitive two-dimensional truthmaker semantics, and provides three novel interpretations of the framework along with the epistemic and metasemantic. Chapter \textbf{5} applies the fixed points of the modal $\mu$-calculus in order to account for the iteration of epistemic states in a single agent, by contrast to availing of modal axiom 4 (i.e. the KK principle). The fixed point operators in the modal $\mu$-calculus are rendered hyperintensional, which yields the first hyperintensional construal of the modal $\mu$-calculus in the literature and the first application of the calculus to the iteration of epistemic states in a single agent instead of the common knowledge of a group of agents. Chapter \textbf{6} advances a solution to the Julius Caesar problem based on Fine's `criterial' identity conditions which incorporate conditions on essentiality and grounding. Chapter \textbf{7} provides a ground-theoretic regimentation of the proposals in the metaphysics of consciousness and examines its bearing on the two-dimensional conceivability argument against physicalism. The topic-sensitive epistemic two-dimensional truthmaker semantics developed in chapters \textbf{2} and \textbf{4} is availed of in order for epistemic states to be a guide to metaphysical states in the hyperintensional setting. -/- Chapters \textbf{8-12} provide cases demonstrating how the two-dimensional hyperintensions of hyperintensional, i.e. topic-sensitive epistemic two-dimensional truthmaker, semantics, solve the access problem in the epistemology of mathematics. Chapter \textbf{8} examines the interaction between Elohim's hyperintensional semantics and the axioms of epistemic set theory, large cardinal axioms, the Epistemic Church-Turing Thesis, the modal axioms governing the modal profile of $\Omega$-logic, Orey sentences such as the Generalized Continuum Hypothesis, and absolute decidability. These results yield inter alia the first hyperintensional Epistemic Church-Turing Thesis and hyperintensional epistemic set theories in the literature. Chapter \textbf{9} examines the modal and hyperintensional commitments of abstractionism, in particular necessitism, and epistemic hyperintensionality, epistemic utility theory, and the epistemology of abstraction. Elohim countenances a hyperintensional semantics for novel epistemic abstractionist modalities. Elohim suggests, too, that higher observational type theory can be applied to first-order abstraction principles in order to make first-order abstraction principles recursively enumerable, i.e. Turing machine computable, and that the truth of the first-order abstraction principle for two-dimensional hyperintensions is grounded in its being possibly recursively enumerable and the machine being physically implementable. Chapter \textbf{10} examines the philosophical significance of hyperintensional $\Omega$-logic in set theory and discusses the hyperintensionality of metamathematics. Chapter \textbf{11} provides a modal logic for rational intuition and provides a hyperintensional semantics. Chapter \textbf{12} avails of modal coalgebras to interpret the defining properties of indefinite extensibility, and avails of hyperintensional epistemic two-dimensional semantics in order to account for the interaction between interpretational and objective modalities and the truthmakers thereof. This yields the first hyperintensional category theory in the literature. Elohim invents a new mathematical trick in which first-order structures are treated as categories, and Vopenka's principle can be satisfied because of the elementary embeddings between the categories and generate Vopenka cardinals in the category of Set in category theory. Chapter \textbf{13} examines modal responses to the alethic paradoxes. Elohim provides a counter-example to epistemic closure for logical deduction. Chapter \textbf{14} examines, finally, the modal and hyperintensional semantics for the different types of intention and the relation of the latter to evidential decision theory. (shrink) | |
This paper studies intentional action in stit logic. The formal logic study of intentional action appears to be new, since most logical studies of intention concern intention as a static mental state. In the formalization we distinguish three modes of acting: the objective level concerning the choices an agent objectively exercises, the subjective level concerning the choices an agent knows or believes to be exercising, and finally, the intentional level concerning the choices an agent intentionally exercises. Several axioms constraining the (...) relations between these different modes of acting will be considered and discussed. The side effect problem will be analyzed as an interaction between knowingly doing and intentionally doing. Non-successful action will be analyzed as a weakening of the epistemic attitude towards action. Finally, the notion of ‘attempt’ will be briefly considered as a further weakening in this direction. (shrink) | |
The complexity of any logical modeling reflects both the intrinsic structure of a topic described and the weight of the formal tools. Some of this weight seems inherent in even the most basic logical systems. Notably, standard predicate logic is undecidable. In this paper, we investigate ‘lighter’ versions of this general purpose tool, by modally ‘deconstructing’ the usual semantics, and locating implicit choice points in its set up. The first part sets out the interest of this program and the modal (...) techniques employed, while the second part provides technical elaborations demonstrating its viability. (shrink) | |
Many powerful logics exist today for reasoning about multi-agent systems, but in most of these it is hard to reason about an infinite or indeterminate number of agents. Also the naming schemes used in the logics often lack expressiveness to name agents in an intuitive way.To obtain a more expressive language for multi-agent reasoning and a better naming scheme for agents, we introduce a family of logics called term-modal logics. A main feature of our logics is the use of modal (...) operators indexed by the terms of the logics. Thus, one can quantify over variables occurring in modal operators. In term-modal logics agents can be represented by terms, and knowledge of agents is expressed with formulas within the scope of modal operators. (shrink) | |
This paper shows how the dynamic interpretation of natural language introduced in work by Hans Kamp and Irene Heim can be modeled in classical type logic. This provides a synthesis between Richard Montague's theory of natural language semantics and the work by Kamp and Heim. | |
Situational aspects of action are discussed. The presented approach emphasizes the role of situational contexts in which actions are performed. These contexts influence the course of an action; they are determined not only by the current state of the system but also shaped by other factors as time, the previously undertaken actions and their succession, the agents of actions and so on. The distinction between states and situations is explored from the perspective of action systems. The notion of a situational (...) action system is introduced and its theory is expounded. Numerous examples illustrate the reach of the theory. (shrink) | |
This paper combines propositional dynamic logic ) with propositional inquisitive logic ). The result of this combination is a logical system \ that conservatively extends both \ and \, and, moreover, allows for an interaction of the question-forming operator from \ with the structured modalities from \. We study this system from a semantic as well as a syntactic point of view. These two perspectives are linked via a completeness proof, which also shows that \ is decidable. | |
Dynamic Epistemic Logic (DEL) deals with the representation and the study in a multi-agent setting of knowledge and belief change. It can express in a uniform way epistemic statements about: 1. what is true about an initial situation 2. what is true about an event occurring in this situation 3. what is true about the resulting situation after the event has occurred. We axiomatize within the DEL framework what we can infer about (iii) given (i) and (ii). Given three formulas (...) φ,φ' and φ" describing respectively (i), (ii) and (iii), we also show how to build a formula φ ? φ' which captures all the information which can be inferred about (iii) from φ and φ'. We show how our results extend to other modal logics than K. In our proofs and definitions, we resort to a large extent to the normal form formulas for modal logic originally introduced by Kit Fine. In a companion paper (Aucher, 2012), we axiomatize what we can infer about (ii) given (i) and (iii), and what we can infer about (i) given (ii) and (iii), and show how to build two formulas φ ? φ" and φ' ? φ" which capture respectively all the information which can be inferred about (ii) from φ and φ", and all the information which can be inferred about (i) from φ' and φ". (shrink) | |
We provide a complete binary implicational axiomatization of the positive fragment of propositional dynamic logic. The intended application of this result are completeness proofs for non-classical extensions of positive PDL. Two examples are discussed in this article, namely, a paraconsistent extension with modal De Morgan negation and a substructural extension with the residuated operators of the non-associative Lambek calculus. Informal interpretations of these two extensions are outlined. | |
is used to give a formalization of Artemov’s knowledge based reasoning approach to game theory, (KBR), [ 4 , 5 ]. Epistemic states of players are represented explicitly and reasoned about formally. We give a detailed analysis of the Centipede game using both proof theoretic and semantic machinery. This helps make the case that PDL + E can be a useful basis for the logical investigation of game theory. | |
We often have to draw conclusions about states of machines in computer science and about states of knowledge and belief in artificial intelligence based on partial information. Nerode suggested using constructive logic as the language to express such deductions and also suggested designing appropriate intuitionistic Kripke frames to express the partial information. Following this program, Nerode and Wijesekera developed syntax, semantics and completeness for a system of intuitionistic dynamic logic for proving properties of concurrent programs. Like all dynamics logics, this (...) was a logic of many modalities, each expressing a program, but in intuitionistic rather than in classical logic. In that logic, both box and diamond are needed, but these two are not intuitionistically interdefinable and, worse, diamond does not distribute over ‘or’, except for sequential programs. This also happens in other contemplated computer science and AI applications, and leads outside the class of constructive logics investigated in the literature. The present paper fills this gap. We provide intuitionistic logics with independent box and diamond without assuming distribution of diamond over ‘or’. The completeness theorem is based on intuitionistic Kripke frames , but equipped with an additional, quite separate accessibility relation between worlds. In the interpretation of Nerode and Wijesekera , worlds under the partial order represent states of partial knowledge, the accessibility represents change in state of partial knowledge resulting from executing a specific program. But there are many other computer science interpretations. This formalism covers all computer science applications of which we are aware. We also give a cut elimination theorem and algebraic and topological formulations, since these present some new difficulties. Finally, these results were obtained prior to those in Nerode and Wijesekera. (shrink) | |
This is an exploratory paper about combining logics, combining theories and combining structures. Typically when one applies logic to such areas as computer science, artificial intelligence or linguistics, one encounters hybrid ontologies. The aim of this paper is to identify plausible strategies for coping with ontological richness. | |
Propositional dynamic logic is complete but not compact. As a consequence, strong completeness requires an infinitary proof system. In this paper, we present a short proof for strong completeness of $$\mathsf{PDL}$$ relative to an infinitary proof system containing the rule from [α; β n ]φ for all $$n \in {\mathbb{N}}$$, conclude $$[\alpha;\beta^*] \varphi$$. The proof uses a universal canonical model, and it is generalized to other modal logics with infinitary proof rules, such as epistemic knowledge with common knowledge. Also, we (...) show that the universal canonical model of $$\mathsf{PDL}$$ lacks the property of modal harmony, the analogue of the Truth lemma for modal operators. (shrink) | |
Reasoning about change is a central issue in research on human and robot planning. We study an approach to reasoning about action and change in a dynamic logic setting and provide a solution to problems which are related to the Frame problem. Unlike most work on the frame problem the logic described in this paper is monotonic. It (implicitly) allows for the occurrence of actions of multiple agents by introducing non-stationary notions of waiting and test. The need to state a (...) large number of frame axioms is alleviated by introducing a concept of chronological preservation to dynamic logic. As a side effect, this concept permits the encoding of temporal properties in a natural way. We compare the relative merits of our approach and non-monotonic approaches as regards different aspects of the frame problem. Technically, we show that the resulting extended systems of propositional dynamic logic preserve (weak) completeness, finite model property and decidability. (shrink) | |
Providing a compositional interpretation procedure for discourses in which descriptions of complex dependencies between interrelated objects are incrementally built is a key challenge for formal theories of natural language interpretation. This paper examines several quantificational phenomena and argues that to account for these phenomena, we need richly structured contexts of interpretation that are passed on between different parts of the same sentence and also across sentential boundaries. The main contribution of the paper is showing how we can add structure to (...) contexts in an incremental way, starting with the basic notion of context in classical first-order logic, i.e., interpretation contexts formalized as single total variable assignments. (shrink) | |
Machine awareness is a disputed research topic, in some circles considered a crucial step in realising Artificial General Intelligence. Understanding what that is, under which conditions such feature could arise and how it can be controlled is still a matter of speculation. A more concrete object of theoretical analysis is algorithmic iteration for computational intelligence, intended as the theoretical and practical ability of algorithms to design other algorithms for actions aimed at solving well-specified tasks. We know this ability is already (...) shown by current AIs, and understanding its limits is an essential step in qualifying claims about machine awareness and Super-AI. We propose a formal translation of algorithmic iteration in a fragment of modal logic, formulate principles of transparency and faithfulness across human and machine intelligence, and consider the relevance to theoretical research on -AI as well as the practical import of our results. (shrink) | |
This chapter presents a new semantics for inductive empirical knowledge. The epistemic agent is represented concretely as a learner who processes new inputs through time and who forms new beliefs from those inputs by means of a concrete, computable learning program. The agent’s belief state is represented hyper-intensionally as a set of time-indexed sentences. Knowledge is interpreted as avoidance of error in the limit and as having converged to true belief from the present time onward. Familiar topics are re-examined within (...) the semantics, such as inductive skepticism, the logic of discovery, Duhem’s problem, the articulation of theories by auxiliary hypotheses, the role of serendipity in scientific knowledge, Fitch’s paradox, deductive closure of knowability, whether one can know inductively that one knows inductively, whether one can know inductively that one does not know inductively, and whether expert instruction can spread common inductive knowledge—as opposed to mere, true belief—through a community of gullible pupils. (shrink) No categories | |
This is the first paper on constructive concurrent dynamic logic . For the first time, either for concurrent or sequential dynamic logic, we give a satisfactory treatment of what statements are forced to be true by partial information about the underlying computer. Dynamic logic was developed by Pratt [V. Pratt, Semantical considerations on Floyd–Hoare logic, in: 17th Annual IEEE Symp. on Found. Comp. Sci., New York, 1976, pp. 109–121, V. Pratt, Applications of modal logic to programming, Studia Logica 39 257–274] (...) for nondeterministic sequential programs, and by Peleg [D. Peleg, Concurrent dynamic logic, Journal of the Association for Computing Machinery 34 , D. Peleg, Communication in concurrent dynamic logic, Journal of Computer and System Sciences 35 ] for concurrent programs, for the purpose of proving properties of programs such as correctness. Here we define what it means for a dynamic logic formula to be forced to be true knowing only partial information about the results of assignments and tests. This informal CCDL semantics is formalized by intuitionistic Kripke frames modeling this partial information, and each such frame is interpreted as an idealized concurrent machine . In CCDL, proofs and deductions are ω-height, ω-branching, well-founded labeled subtrees of ωω. These are a generalization of the signed tableaux of Nerode [A. Nerode, Some lectures in modal logic, Technical Report, M.S.I. Cornell University, 1989, CIME Logic and Computer Science Montecatini Volume, Springer-Verlag Lecture Notes, 1990, A. Nerode, Some lectures in intuitionistic logic, Technical Report, M.S.I. Cornell University, 1988, Marktoberdorf Logic and Computation NATO Summer School Volume, NATO Science Series, 1990 ] stemming from the prefix tableaux of Fitting [M.C. Fitting, Proof Methods for Modal and Intuitionistic Logic, Reidel, 1983]. We demonstrate the correctness of our tableau proofs, define consistency properties, prove that consistency properties yield models, construct systematic tableaux, prove that systematic tableaux yield a consistency property, and conclude that CCDL is complete. This infinitary semantics and proof procedure will be the primary guide for defining, in a sequel, the correct finitary CCDL based on induction principles. FCCDL is suitable for implementation in constructive logic software systems such as Constable’s NUPRL or Huet-Coquand’s CONSTRUCTIONS. Our goal is to develop a constructive logic programming tool for specification and modular verification of programs in any imperative concurrent language, and for the extraction of concurrent programs from constructive proofs. Subsequent papers will introduce analogous logics for declarative and functional concurrent languages. (shrink) | |
Belief revision from the point of view of doxastic logic. Logic Journal of the IGPL, 3(4), 535–553. Segerberg, K. (1995). Conditional action. In G. Crocco, L. Fariñas, & A. Herzig (Eds.), Conditionals: From philosophy to computer science, Studies ... | |
We present a direct reduction of dynamic epistemic logic in the spirit of [4] to propositional dynamic logic (PDL) [17, 18] by program transformation. The program transformation approach associates with every update action a transformation on PDL programs. These transformations are then employed in reduction axioms for the update actions. It follows that the logic of public announcement, the logic of group announcements, the logic of secret message passing, and so on, can all be viewed as subsystems of PDL. Moreover, (...) the program transformation approach can be used to generate the appropriate reduction axioms for these logics. Our direct reduction of dynamic epistemic logic to PDL was inspired by the reduction of dynamic epistemic logic to automata PDL of [13]. Our approach shows how the detour through automata can be avoided. (shrink) | |
There are three questions associated with Simpson’s paradox (SP): (i) Why is SP paradoxical? (ii) What conditions generate SP? and (iii) How to proceed when confronted with SP? An adequate analysis of the paradox starts by distinguishing these three questions. Then, by developing a formal account of SP, and substantiating it with a counterexample to causal accounts, we argue that there are no causal factors at play in answering questions (i) and (ii). Causality enters only in connection with action. | |
This essay aims to provide a modal logic for rational intuition. Similarly to treatments of the property of knowledge in epistemic logic, I argue that rational intuition can be codified by a modal operator governed by the modal $\mu$-calculus. Via correspondence results between fixed point modal propositional logic and the bisimulation-invariant fragment of monadic second-order logic, a precise translation can then be provided between the notion of 'intuition-of', i.e., the cognitive phenomenal properties of thoughts, and the modal operators regimenting the (...) notion of 'intuition-that'. I argue that intuition-that can further be shown to entrain conceptual elucidation, by way of figuring as a dynamic-interpretational modality which induces the reinterpretation of both domains of quantification and the intensions and hyperintensions of mathematical concepts that are formalizable in monadic first- and second-order formal languages. Hyperintensionality is countenanced via a topic-sensitive epistemic two-dimensional truthmaker semantics. (shrink) | |
Propositional logics in general, considered as a set of sentences, can be undecidable even if they have “nice” representations, e.g., are given by a calculus. Even decidable propositional logics can be computationally complex (e.g., already intuitionistic logic is PSPACE-complete). On the other hand, finite-valued logics are computationally relatively simple—at worst NP. Moreover, finite-valued semantics are simple, and general methods for theorem proving exist. This raises the question to what extent and under what circumstances propositional logics represented in various ways can (...) be approximated by finite-valued logics. It is shown that the minimal m-valued logic for which a given calculus is strongly sound can be calculated. It is also investigated under which conditions propositional logics can be characterized as the intersection of (effectively given) sequences of finite-valued logics. (shrink) | |
We propose a framework for modelling situated resource-bounded agents. The framework is based on an objective ascription of intentional modalities and can be easily tailored to the system we want to model and the properties we wish to specify. As an elaboration of the framework, we introduce a logic, OBA, for describing the observations, beliefs, goals and actions of simple agents, and show that OBA is complete, decidable and has an efficient model checking procedure, allowing properties of agents specified in (...) OBA to be verified using standard theorem proving or model checking techniques. (shrink) | |
Kniha, jako je tato, nemůže být tak docela dílem jediného člověka. Dovést ji do podoby koherentního celku bych nedokázal bez pomoci svých kolegů, kteří po mně text četli a upozornili mě na spoustu chyb a nedůsledností, které se v něm vyskytovaly. Můj dík v tomto směru patří zejména Vojtěchu Kolmanovi, Liboru Běhounkovi a Martě Bílkové. Za připomínky k různým částem rukopisu jsem vděčen i Pavlu Maternovi, Milanu Matouškovi, Prokopu Sousedíkovi, Vladimíru Svobodovi, Petru Hájkovi a Grahamu Priestovi. Kniha vznikla v rámci (...) projektu podpořeného grantem AV ČR číslo A0009001/00. (shrink) | |
 | |
Why should moral philosophers, moral psychologists, and machine ethicists care about computational complexity? Debates on whether artificial intelligence (AI) can or should be used to solve problems in ethical domains have mainly been driven by what AI can or cannot do in terms of human capacities. In this paper, we tackle the problem from the other end by exploring what kind of moral machines are possible based on what computational systems can or cannot do. To do so, we analyze normative (...) ethics through the lens of computational complexity. First, we introduce computational complexity for the uninitiated reader and discuss how the complexity of ethical problems can be framed within Marr’s three levels of analysis. We then study a range of ethical problems based on consequentialism, deontology, and virtue ethics, with the aim of elucidating the complexity associated with the problems themselves (e.g., due to combinatorics, uncertainty, strategic dynamics), the computational methods employed (e.g., probability, logic, learning), and the available resources (e.g., time, knowledge, learning). The results indicate that most problems the normative frameworks pose lead to tractability issues in every category analyzed. Our investigation also provides several insights about the computational nature of normative ethics, including the differences between rule- and outcome-based moral strategies, and the implementation-variance with regard to moral resources. We then discuss the consequences complexity results have for the prospect of moral machines in virtue of the trade-off between optimality and efficiency. Finally, we elucidate how computational complexity can be used to inform both philosophical and cognitive-psychological research on human morality by advancing the moral tractability thesis. (shrink) | |
1. Reasoning about action and change, or more generally reasoning about dynamic systems, is not only central to knowledge representation and reasoning but at the heart of computer science (Fisher e... | |
This book illustrates the program of Logical-Informational Dynamics. Rational agents exploit the information available in the world in delicate ways, adopt a wide range of epistemic attitudes, and in that process, constantly change the world itself. Logical-Informational Dynamics is about logical systems putting such activities at center stage, focusing on the events by which we acquire information and change attitudes. Its contributions show many current logics of information and change at work, often in multi-agent settings where social behavior is essential, (...) and often stressing Johan van Benthem's pioneering work in establishing this program. However, this is not a Festschrift, but a rich tapestry for a field with a wealth of strands of its own. The reader will see the state of the art in such topics as information update, belief change, preference, learning over time, and strategic interaction in games. Moreover, no tight boundary has been enforced, and some chapters add more general mathematical or philosophical foundations or links to current trends in computer science. The theme of this book lies at the interface of many disciplines. Logic is the main methodology, but the various chapters cross easily between mathematics, computer science, philosophy, linguistics, cognitive and social sciences, while also ranging from pure theory to empirical work. Accordingly, the authors of this book represent a wide variety of original thinkers from different research communities. And their interconnected themes challenge at the same time how we think of logic, philosophy and computation. Thus, very much in line with van Benthem's work over many decades, the volume shows how all these disciplines form a natural unity in the perspective of dynamic logicians (broadly conceived) exploring their new themes today. And at the same time, in doing so, it offers a broader conception of logic with a certain grandeur, moving its horizons beyond the traditional study of consequence relations. (shrink) | |
This paper describes an approach for reasoning in a dynamic domain with nondeterministic actions in which an agent’s beliefs correspond to the simplest, or most plausible, course of events consistent with the agent’s observations and beliefs. The account is based on an epistemic extension of the situation calculus, a first-order theory of reasoning about action that accommodates sensing actions. In particular, the account is based on a qualitative theory of nondeterminism. Our position is that for commonsense reasoning, the world is (...) most usefully regarded as deterministic, and that nondeterminism is an epistemic phenomenon, arising from an agent’s limited awareness and perception. The account offers several advantages: an agent has a set of categorical beliefs, yet can deal with equally-likely outcomes or with outcomes of differing plausibility. The agent maintains as its set of contingent beliefs the most plausible, or simplest, picture of the world, consistent with its beliefs and actions it believes it executed; yet it may modify these in light of later information. (shrink) | |
A first-order dynamic non-commutative logic, which has no structural rules and has some program operators, is introduced as a Gentzen-type sequent calculus. Decidability, cut-elimination and completeness theorems are shown for DN or its fragments. DN is intended to represent not only program-based, resource-sensitive, ordered, sequence-based, but also hierarchical reasoning. | |
Reasoning about concurrent programs involves representing the information that concurrent processes manipulate disjoint portions of memory. In sophisticated applications, the division of memory between processes is not static. Through operations, processes can exchange the implied ownership of memory cells. In addition, processes can also share ownership of cells in a controlled fashion as long as they perform operations that do not interfere, e.g., they can concurrently read shared cells. Thus the traditional paradigm of distributed computing based on locations is replaced (...) by a paradigm of concurrent computing which is more tightly based on program structure. Concurrent Separation Logic with Permissions, developed by O’Hearn, Bornat et al., is able to represent sophisticated transfer of ownership and permissions between processes. We demonstrate how these ideas can be used to reason about fine-grained concurrent programs which do not employ explicit synchronization operations to control interference but cooperatively manipulate memory cells so that interference is avoided. Reasoning about such programs is challenging and appropriate logical tools are necessary to carry out the reasoning in a reliable fashion. We argue that Concurrent Separation Logic with Permissions provides such tools. We illustrate the logical techniques by presenting the proof of a concurrent garbage collector originally studied by Dijkstra et al., and extended by Lamport to handle multiple user processes. (shrink) | |
We describe BDD-based decision procedures for the modal logic K. Our approach is inspired by the automata-theoretic approach, but we avoid explicit automata construction. Instead, we compute certain fixpoints of a set of types — which can be viewed as an on-the-fly emptiness of the automaton. We use BDDs to represent and manipulate such type sets, and investigate different kinds of representations as well as a “level-based” representation scheme. The latter turns out to speed up construction and reduce memory consumption (...) considerably. We also study the effect of formula simplification on our decision procedures. To prove the viability of our approach, we compare our approach with a representative selection of other approaches, including a translation of K to QBF. Our results indicate that the BDD-based approach dominates for modally heavy formulae, while search-based approaches dominate for propositionally heavy formulae. (shrink) | |
This book concerns the foundations of epistemic modality and hyperintensionality and their applications to the philosophy of mathematics. David Elohim examines the nature of epistemic modality, when the modal operator is interpreted as concerning both apriority and conceivability, as well as states of knowledge and belief. The book demonstrates how epistemic modality and hyperintensionality relate to the computational theory of mind; metaphysical modality and hyperintensionality; the types of mathematical modality and hyperintensionality; to the epistemic status of large cardinal axioms, undecidable (...) propositions, and abstraction principles in the philosophy of mathematics; to the modal and hyperintensional profiles of the logic of rational intuition; and to the types of intention, when the latter is interpreted as a hyperintensional mental state. Chapter \textbf{2} argues for a novel type of expressivism based on the duality between the categories of coalgebras and algebras, and argues that the duality permits of the reconciliation between modal and hyperintensional cognitivism and modal and hyperintensional expressivism. Elohim develops a novel, topic-sensitive truthmaker semantics for dynamic epistemic logic, and develops a novel, dynamic two-dimensional semantics grounded in two-dimensional hyperintensional Turing machines. Chapter \textbf{3} provides an abstraction principle for two-dimensional (hyper-)intensions. Chapter \textbf{4} advances a topic-sensitive two-dimensional truthmaker semantics, and provides three novel interpretations of the framework along with the epistemic and metasemantic. Chapter \textbf{5} applies the fixed points of the modal $\mu$-calculus in order to account for the iteration of epistemic states in a single agent, by contrast to availing of modal axiom 4 (i.e. the KK principle). The fixed point operators in the modal $\mu$-calculus are rendered hyperintensional, which yields the first hyperintensional construal of the modal $\mu$-calculus in the literature and the first application of the calculus to the iteration of epistemic states in a single agent instead of the common knowledge of a group of agents. Chapter \textbf{6} advances a solution to the Julius Caesar problem based on Fine's `criterial' identity conditions which incorporate conditions on essentiality and grounding. Chapter \textbf{7} provides a ground-theoretic regimentation of the proposals in the metaphysics of consciousness and examines its bearing on the two-dimensional conceivability argument against physicalism. The topic-sensitive epistemic two-dimensional truthmaker semantics developed in chapters \textbf{2} and \textbf{4} is availed of in order for epistemic states to be a guide to metaphysical states in the hyperintensional setting. -/- Chapters \textbf{8-12} provide cases demonstrating how the two-dimensional hyperintensions of hyperintensional, i.e. topic-sensitive epistemic two-dimensional truthmaker, semantics, solve the access problem in the epistemology of mathematics. Chapter \textbf{8} examines the interaction between Elohim's hyperintensional semantics and the axioms of epistemic set theory, large cardinal axioms, the Epistemic Church-Turing Thesis, the modal axioms governing the modal profile of $\Omega$-logic, Orey sentences such as the Generalized Continuum Hypothesis, and absolute decidability. These results yield inter alia the first hyperintensional Epistemic Church-Turing Thesis and hyperintensional epistemic set theories in the literature. Chapter \textbf{9} examines the modal and hyperintensional commitments of abstractionism, in particular necessitism, and epistemic hyperintensionality, epistemic utility theory, and the epistemology of abstraction. Elohim countenances a hyperintensional semantics for novel epistemic abstractionist modalities. Elohim suggests, too, that higher observational type theory can be applied to first-order abstraction principles in order to make first-order abstraction principles recursively enumerable, i.e. Turing machine computable, and that the truth of the first-order abstraction principle for two-dimensional hyperintensions is grounded in its being possibly recursively enumerable and the machine being physically implementable. Chapter \textbf{10} examines the philosophical significance of hyperintensional $\Omega$-logic in set theory and discusses the hyperintensionality of metamathematics. Chapter \textbf{11} provides a modal logic for rational intuition and provides a hyperintensional semantics. Chapter \textbf{12} avails of modal coalgebras to interpret the defining properties of indefinite extensibility, and avails of hyperintensional epistemic two-dimensional semantics in order to account for the interaction between interpretational and objective modalities and the truthmakers thereof. This yields the first hyperintensional category theory in the literature. Elohim invents a new mathematical trick in which first-order structures are treated as categories, and Vopenka's principle can be satisfied because of the elementary embeddings between the categories and generate Vopenka cardinals in the category of Set in category theory. Chapter \textbf{13} examines modal responses to the alethic paradoxes. Elohim provides a counter-example to epistemic closure for logical deduction. Chapter \textbf{14} examines, finally, the modal and hyperintensional semantics for the different types of intention and the relation of the latter to evidential decision theory. (shrink) |
Home |New books and articles |Bibliographies |Philosophy journals |About PhilPapers |API |Contact us |Code of conduct
PhilPapers logo byAndrea Andrews andMeghan Driscoll.
This site uses cookies and Google Analytics (see ourterms & conditions for details regarding the privacy implications).Use of this site is subject toterms & conditions.
All rights reserved byThe PhilPapers Foundation
Server: philpapers-web-54b44b69b7-vb4rf uwo