This paper is a brief history of natural logic at the interface of logic, linguistics, and nowadays also other disciplines. It merely summarizes some facts that deserve to be common knowledge.
Many cognitive activities are irreducibly social, involving interaction between several different agents. We look at some examples of this in linguistic communication and games, and show how logical methods provide exact models for the relevant information flow and world change. Finally, we discuss possible connections in this arena between logico-computational approaches and experimental cognitive science.
Over the past decades, logicians interested in rational agency and intelligent interaction studied major components of these phenomena, such as knowledge, belief, and preference. In recent years, standard ‘static’ logics describing information states of agents have been generalized to dynamic logics describing actions and events that produce information, revise beliefs, or change preferences, as explicit parts of the logical system. Van Ditmarsch, van der Hoek & Kooi 2007, Baltag, van Ditmarsch & Moss 2008, van Benthem, to appear A, are up-to-date (...) accounts of this dynamic trend (the present paper follows Chapter 9 of the latter book). But in reality, concrete rational agency contains all these dynamic processes entangled. A concrete setting for this entanglement are games – and this paper is a survey of their interfaces with logic, both static and dynamic. Games are intriguing also since their analysis brings together two major streams, or tribal communities: ‘hard’ mathematical logics of computation, and ‘soft’ philosophical logics of propositional attitudes. Of course, this hard/soft distinction is spurious, and there is no natural border line between the two sources: it is their congenial mixture that makes current theories of agency so lively. (shrink)
We show how belief revision can be treated systematically in the format of dynamic- epistemic logic, when operators of conditional belief are added. The core engine consists of definable update rules for changing plausibility relations between worlds, which have been proposed independently in the dynamic-epistemic literature on preference change. Our analysis yields two new types of modal result. First, we obtain complete logics for concrete mechanisms of belief revision, based on compositional reduction axioms. Next, we show how various ab- stract (...) postulates for belief revision can be analyzed by standard modal frame correspondences for model-changing operations. (shrink)
In the last few years, preference logic and in particular, the dynamic logic of preference change, has suddenly become a live topic in my Amsterdam and Stanford environments. At the request of the editors, this article explains how this interest came about, and what is happening. I mainly present a story around some recent dissertations and supporting papers, which are found in the references. There is no pretense at complete coverage of preference logic (for that, see Hanson 2001) or even (...) of preference change (Hanson 1995). (shrink)
We discuss games of both perfect and imperfect information at two levels of structural detail: players’ local actions, and their global powers for determining outcomes of the game. We propose matching logical languages for both. In particular, at the ‘action level’, imperfect information games naturally model a combined ‘dynamic-epistemic language’ – and we find correspondences between special axioms and particular modes of playing games with their information dynamics. At the ‘outcome level’, we present suitable notions of game equivalence, plus some (...) simple representation results. (shrink)
Natural languages are vehicles of information, arguably the most important, certainly the most ubiquitous that humans possess. Our everyday interactions with the world, with each other and with ourselves depend on them. And even where in the specialised contexts of science we use dedicated formalisms to convey information, their use is embedded in natural language. This omnipresence of natural language is due in large part to its flexibility, which is almost always a virtue, sometimes a vice. Natural languages are able (...) to carry information in a wide variety of ways, about a seemingly unlimited range of topics, which makes them both efficient and versatile, and hence useful in almost every circumstance. But sometimes, when pinpoint precision is what counts, this versatility can get in the.. (shrink)
Classical epistemic logic describes implicit knowledge of agents about facts and knowledge of other agents, based on semantic information. The latter is produced by acts of observation or communication, that are described well by dynamic epistemic logics. What these logics do not describe, however, is how significant information is also produced by acts of inference – and key axioms of the system merely postulate “deductive closure”. In this paper, we take the view that all information is produced by acts, and (...) hence we also need a dynamic logic of inference steps showing what effort on the part of the agent makes a conclusion explicit knowledge. Strong omniscience properties of agents should be seen not as static idealizations, but as the result of dynamic processes that agents engage in. This raises two questions: (a) how to define suitable information states of agents and matching notions of explicit knowledge, (b) how to define natural processes over these states that generate new explicit knowledge. To this end, we extend earlier epistemic “awareness models” into a dynamic system that includes acts of public observation, but also adding and dropping formulas from the currently ‘entertained’ set, we give a completeness theorem, and we show how this dynamics updates explicit knowledge. Similar ideas have been proposed before, but they were restricted to update with factual propositions; our new dynamic system applies to arbitrary formulas. We also extend our approach to multi-agent scenarios where awareness changes may happen privately. Finally, we mention further directions and related approaches. (shrink)
This paper is based on tutorials on 'Logic and Games' at the 7th Asian Logic Conference in Hsi-Tou, Taiwan, 1999, and until 2002 in Siena, Stuttgart, Trento, Udine, and Utrecht. We present logic games as a topic per se, giving models for dynamic interaction between agents. First, we survey some basic logic games. Then we show how their common properties raise general issues of game structure and 'game logics'. Next, we review logic games in the light of general game logic. (...) Finally, we discuss more 'realistic' influences from game theory into logic games, including players' preferences, and imperfect information. (shrink)
1 Logic in philosophy The century that was Logic has played an important role in modern philosophy, especially, in alliances with philosophical schools such as the Vienna Circle, neopositivism, or formal language variants of analytical philosophy. The original impact was via the work of Frege, Russell, and other pioneers, backed up by the prestige of research into the foundations of mathematics, which was fast bringing to light those amazing insights that still impress us to-day. The Golden Age of the 1930s (...) deeply affected philosophy, and heartened the minority of philosophers with a formalanalytical bent. As Brand Blanshard writes in Reason and Analysis (1964) – I quote from memory here, to avoid the usual disappointment when re-reading an original text. (shrink)
Rational agents base their actions on information from observation, inference, introspection, or other sources. But this information comes in different kinds, and it is usually handled by different logical mechanisms. We discuss how to integrate external ‘updating information’ and internal ‘elucidating information’ into one system of dynamic epistemic logic, by distinguishing two basic informational actions: ‘bare seeing’ versus ‘conscious realization’.
Logic is not just about single-agent notions like reasoning, or zero-agent notions like truth, but also about communication between two or more people. What we tell and ask each other can be just as 'logical' as what we infer in Olympic solitude. We show how such interactive phenomena can be studied systematically by merging epistemic and dynamic logic.
Dov Gabbay is a prolific logician just by himself. But beyond that, he is quite good at making other people investigate the many further things he cares about. As a result, King's College London has become a powerful attractor in our field worldwide. Thus, it is a great pleasure to be an organizer for one of its flagship events: the Augustus de Morgan Workshop of 2005. Benedikt Loewe and I proposed the topic of 'interactive logic' for this occasion, with an (...) emphasis on social software – the logical analysis and design of social procedures – and on games, arguably the formal interactive setting par excellence. This choice reflects current research interests in our logic community at ILLC Amsterdam and beyond. In this broad area of interfaces between logic, computer science, and game theory, this paper is my own attempt at playing Dov. I am, perhaps not telling, but at least asking other people to find out for me what I myself cannot. (shrink)
Preference is a basic notion in human behaviour, underlying such varied phenomena as individual rationality in the philosophy of action and game theory, obligations in deontic logic (we should aim for the best of all possible worlds), or collective decisions in social choice theory. Also, in a more abstract sense, preference orderings are used in conditional logic or non-monotonic reasoning as a way of arranging worlds into more or less plausible ones. The field of preference logic (cf. Hansson [10]) studies (...) formal systems that can express and analyze notions of preference between various sorts of entities: worlds, actions, or propositions. The art is of course to design a language that combines perspicuity and low complexity with reasonable expressive power. In this paper, we take a particularly simple approach. As preferences are binary relations between worlds, they naturally support standard unary modalities. In particular, our key modality ♦ϕ will just say that is ϕ true in some world which is at least as good as the current one. Of course, this notion can also be indexed to separate agents. The essence of this language is already in [4], but our semantics is more general, and so are our applications and later language extensions. Our modal language can express a variety of preference notions between propositions. Moreover, as already suggested in [9], it can “deconstruct” standard conditionals, providing an embedding of conditional logic into more standard modal logics. Next, we take the language to the analysis of games, where some sort of preference logic is evidently needed ([23] has a binary modal analysis different from ours). We show how a qualitative unary preference modality suffices for defining Nash Equilibrium in strategic games, and also the Backward Induction solution for finite extensive games. Finally, from a technical perspective, our treatment adds a new twist. Each application considered in this paper suggests the need for some additional access to worlds before the preference modality can unfold its true power.. (shrink)
Sitting in the office of a distinguished philosopher of language recently, I watched him lean back (somewhat precariously) in his chair, look at the ceiling, and sigh: “Johan, we both write all this stuff about information, context, and communication – but is not the only time you really feel that you are making progress, when you resolutely close your eyes, and shut out the world and the others?” I appreciated his point, and indeed, in most spheres of life on this (...) planet, “l’Enfer” is most definitely “Les Autres”. (shrink)
Understanding human behaviour involves "why"'s as well as "how"'s. Rational people have good reasons for acting, but it can be hard to find out what these were and how they worked. In this Note, we discuss a few ways in which actions, preferences, and expectations are intermingled. This mixture is especially clear with the well-known solution procedure for extensive games called 'Backward Induction'. In particular, we discuss three scenarios for analyzing behaviour in a game. One can rationalize given moves as (...) revealing agents' preferences, one can also rationalize them as revealing agents' beliefs about others, but one can also change a predicted pattern of behaviour by making promises. All three scenarios transform given games to new ones, and we prove some results about their scope. A more general view of relevant game transformations would involve dynamic and epistemic game logics. Finally, our analysis describes and disentangles matters: but it will not tell you what to do! (shrink)
Game-theoretic solution concepts describe sets of strategy profiles that are optimal for all players in some plausible sense. Such sets are often found by recursive algorithms like iterated removal of strictly dominated strategies in strategic games, or backward induction in extensive games. Standard logical analyses of solution sets use assumptions about players in fixed epistemic models for a given game, such as mutual knowledge of rationality. In this paper, we propose a different perspective, analyzing solution algorithms as processes of learning (...) which change game models. Thus, strategic equilibrium gets linked to fixed-points of operations of repeated announcement of suitable epistemic statements. This dynamic stance provides a new look at the current interface of games, logic, and computation. (shrink)
The notion of preference occurs across many areas, including the philosophy of action, decision theory, optimality theory, and game theory. In these settings, individual preferences between worlds or actions can be used to predict behavior by rational agents. In a more abstract sense, the notion of preference also occurs in conditional logic, non-monotonic logic and belief revision theory, whose semantics involve an ordering of the possible worlds in terms of relative similarity or plausibility, or other preference-like relations.
Information is a notion of wide use and great intuitive appeal, and hence, not surprisingly, different formal paradigms claim part of it, from Shannon channel theory to Kolmogorov complexity. Information is also a widely used term in logic, but a similar diversity repeats itself: there are several competing logical accounts of this notion, ranging from semantic to syntactic. In this chapter, we will discuss three major logical accounts of information.
The combination of logic and game theory provides a fine-grained perspective on information and interaction dynamics, a Theory of Play. In this paper we lay down the main components of such a theory, drawing on recent advances in the logical dynamics of actions, preferences, and information. We then show how this fine-grained perspective has already shed new light on the long-term dynamics of information exchange, as well as on the much-discussed question of extensive game rationality.
The most widely used attractive logical account of knowledge uses standard epistemic models, i.e., graphs whose edges are indistinguishability relations for agents. In this paper, we discuss more general topological models for a multi-agent epistemic language, whose main uses so far have been in reasoning about space. We show that this more geometrical perspective affords greater powers of distinction in the study of common knowledge, defining new collective agents, and merging information for groups of agents.
Meer informatie over de uitgaven van Sdu Uitgevers en Academic Service kunt u verkrijgen bij: Sdu Klantenservice Postbus 20014 2500 EA Den Haag tel.: (070) 378 98 80 www.sdu.nl/service..
Transition systems can be viewed either as process diagrams or as Kripke structures. The rst perspective is that of process theory, the second that of modal logic. This paper shows how various formalisms of modal logic can be brought to bear on processes. Notions of bisimulation can not only be motivated by operations on transition systems, but they can also be suggested by investigations of modal formalisms. To show that the equational view of processes from process algebra is closely related (...) to modal logic, we consider various ways of looking at the relation between the calculus of basic process algebra and propositional dynamic logic. More concretely, the paper contains preservation results for various bisimulation notions, a result on the expressive power of propositional dynamic logic, and a de nition of bisimulation which is the proper notion of invariance for concurrent propositional dynamic logic. (shrink)
Current dynamic epistemic logics often become cumbersome and opaque when common knowledge is added for groups of agents. Still, postconditions regarding common knowledge express the essence of what communication achieves. We present some methods that yield so-called reduction axioms for common knowledge. We investigate the expressive power of public announcement logic with relativized common knowledge, and present reduction axioms that give a detailed account of the dynamics of common knowledge in some major communication types.
SOCREAL 2010: 2nd International Workshop on Philosophy and Ethics of Social Reality. Sapporo, Japan, 2010-03-27/28. Keynote Lecture 1. Joining Information and Evaluation: a dynamic logical perspective.
A variety of logical frameworks have been developed to study rational agents interacting over time. This paper takes a closer look at one particular interface, between two systems that both address the dynamics of knowledge and information flow. The first is Epistemic Temporal Logic (ETL) which uses linear or branching time models with added epistemic structure induced by agents’ different capabilities for observing events. The second framework is Dynamic Epistemic Logic (DEL) that describes interactive processes in terms of epistemic event (...) models which may occur inside modalities of the language. This paper systematically and rigorously relates the DEL framework with the ETL framework. The precise relationship between DEL and ETL is explored via a new representation theorem characterizing the largest class of ETL models corresponding to DEL protocols in terms of notions of Perfect Recall , No Miracles , and Bisimulation Invariance . We then focus on new issues of completeness . One contribution is an axiomatization for the dynamic logic of public announcements constrained by protocols, which has been an open problem for some years, as it does not fit the usual ‘reduction axiom’ format of DEL. Finally, we provide a number of examples that show how DEL suggests an interesting fine-structure inside ETL. (shrink)
Current dynamic-epistemic logics model different types of information change in multi-agent scenarios. We generalize these logics to a probabilistic setting, obtaining a calculus for multi-agent update with three natural slots: prior probability on states, occurrence probabilities in the relevant process taking place, and observation probabilities of events. To match this update mechanism, we present a complete dynamic logic of information change with a probabilistic character. The completeness proof follows a compositional methodology that applies to a much larger class of dynamic-probabilistic (...) logics as well. Finally, we discuss how our basic update rule can be parameterized for different update policies, or learning methods. (shrink)
Information is a recognized fundamental notion across the sciences and humanities, which is crucial to understanding physical computation, communication, and human cognition. The Philosophy of Information brings together the most important perspectives on information. It includes major technical approaches, while also setting out the historical backgrounds of information as well as its contemporary role in many academic fields. Also, special unifying topics are high-lighted that play across many fields, while we also aim at identifying relevant themes for philosophical reflection. There (...) is no established area yet of Philosophy of Information, and this Handbook can help shape one, making sure it is well grounded in scientific expertise. As a side benefit, a book like this can facilitate contacts and collaboration among diverse academic milieus sharing a common interest in information. -/- . First overview of the formal and technical issues involved in the philosophy of information . Integrated presentation of major mathematical approaches to information, form computer science, information theory, and logic . Interdisciplinary themes across the traditional boundaries of natural sciences, social sciences, and humanities. (shrink)
Modern logic is undergoing a cognitive turn, side-stepping Frege’s ‘antipsychologism’. Collaborations between logicians and colleagues in more empirical fields are growing, especially in research on reasoning and information update by intelligent agents. We place this border-crossing research in the context of long-standing contacts between logic and empirical facts, since pure normativity has never been a plausible stance. We also discuss what the fall of Frege’s Wall means for a new agenda of logic as a theory of rational agency, and what (...) might then be a viable understanding of ‘psychologism’ as a friend rather than an enemy of logical theory. (shrink)
We present a number of, somewhat unusual, ways of describing what Craig’s interpolation theorem achieves, and use them to identify some open problems and further directions.
We make a proposal for formalizing simultaneous games at the abstraction level of player’s powers, combining ideas from dynamic logic of sequential games and concurrent dynamic logic. We prove completeness for a new system of ‘concurrent game logic’ CDGL with respect to finite non-determined games. We also show how this system raises new mathematical issues, and throws light on branching quantifiers and independence-friendly evaluation games for first-order logic.
Abduction is a typical theme where logic and philosophy of science meet today: occasionally, with computer science as a go-between. This is just one instance of a broader study of ‘styles of reasoning’, dating back to Bolzano and Peirce. The resulting concern with ‘logical architecture’ moves us closer to cognitive science, and the dynamics of reasoning intertwined with learning and belief revision. The crucial process of self-correction involved here is usually triggered by others, and hence a shared target of logic (...) and philoso-phy of science should be the phenomenon of ‘intelligent interaction’ between rational agents. (shrink)
. We prove new Lindström theorems for the basic modal propositional language, and for some related fragments of first-order logic. We find difficulties with such results for modal languages without a finite-depth property, high-lighting the difference between abstract model theory for fragments and for extensions of first-order logic. In addition we discuss new connections with interpolation properties, and the modal invariance theorem.
Current dynamic epistemic logics often become cumbersome and opaque when common knowledge is added. In this paper we propose new versions that extend the underlying static epistemic language in such a way that dynamic completeness proofs can be obtained by perspicuous reduction axioms.
Current dynamic epistemic logics for analyzing effects of informational events often become cumbersome and opaque when common knowledge is added for groups of agents. Still, postconditions involving common knowledge are essential to successful multi-agent communication. We propose new systems that extend the epistemic base language with a new notion of ‘relativized common knowledge’, in such a way that the resulting full dynamic logic of information flow allows for a compositional analysis of all epistemic postconditions via perspicuous ‘reduction axioms’. We also (...) show how such systems can deal with factual alteration, rather than just information change, making them cover a much wider range of realistic events. After a warm-up stage of analyzing logics for public announcements, our main technical results are expressivity and completeness theorems for a much richer logic that we call LCC. This is a dynamic epistemic logic whose static base is propositional dynamic logic (PDL), interpreted epistemically. This system is capable of expressing all model-shifting operations with finite action models, while providing a compositional analysis for a wide range of informational events. This makes LCC a serious candidate for a standard in dynamic epistemic logic, as we illustrate by analyzing some complex communication scenarios, including sending successive emails with both ‘cc’ and ‘bcc’ lines, and other private announcements to subgroups. Our proofs involve standard modal techniques, combined with a new application of Kleene’s theorem on finite automata, as well as new Ehrenfeucht games of model comparison. (shrink)
Epistemology and epistemic logic At first sight, the modern agenda of epistemology has little to do with logic. Topics include different definitions of knowledge, its basic formal properties, debates between externalist and internalist positions, and above all: perennial encounters with sceptics lurking behind every street corner, especially in the US. The entry 'Epistemology' in the Routledge Encyclopedia of Philosophy (Klein 1993) and the anthology (Kim and Sosa 2000) give an up-to-date impression of the field. Now, epistemic logic started as a (...) contribution to epistemology, or at least a tool in its modus operandi, with the seminal book Knowledge and Belief (Hintikka's 1962, 2005). Formulas like Ki for "the agent i knows that " Bi for "the agent i believes that " provided logical forms for stating and analyzing philosophical propositions and arguments. And more than that, their model-theoretic semantics in terms of ranges of alternatives provided an appealing extensional way of thinking about what agents know or believe in a given situation. In particular, on Hintikka's view, an agent knows those propositions which are true in all situations compatible with what she knows about the actual world; i.e., her current range of uncertainty. (shrink)
Taking Löb's Axiom in modal provability logic as a running thread, we discuss some general methods for extending modal frame correspondences, mainly by adding fixed-point operators to modal languages as well as their correspondence languages. Our suggestions are backed up by some new results – while we also refer to relevant work by earlier authors. But our main aim is advertizing the perspective, showing how modal languages with fixed-point operators are a natural medium to work with.
Modern logic is about information flow and communication far beyond its traditional agenda of inference and meaning. This makes it a player at a central academic interface between many disciplines, where normative and descriptive stances, often thought to be at odds, meet in creating new practices which also affect reality. This same theatre is where philosophy in general would thrive, if it so wished.
Current dynamic epistemic logics for analyzing effects of informational events often become cumbersome and opaque when common knowledge is added for groups of agents. Still, postconditions involving common knowledge are essential to successful multi-agent communication. We propose new systems that extend the epistemic base language with a new notion of ‘relativized common knowledge’, in such a way that the resulting full dynamic logic of information flow allows for a compositional analysis of all epistemic postconditions via perspicuous ‘reduction axioms’. We also (...) show how such systems can deal with factual alteration, rather than just information change, making them cover a much wider range of realistic events. After a warm-up stage of analyzing logics for public announcements, our main technical results are expressivity and completeness theorems for a much richer logic that we call LCC. This is a dynamic epistemic logic whose static base is propositional dynamic logic (PDL), interpreted epistemically. This system is capable of expressing all model-shifting operations with finite action models, while providing a compositional analysis for a wide range of informational events. This makes LCC a serious candidate for a standard in dynamic epistemic logic, as we illustrate by analyzing some complex communication scenarios, including sending successive emails with both ‘cc’ and ‘bcc’ lines, and other private announcements to subgroups. Our proofs involve standard modal techniques, combined with a new application of Kleene’s theorem on finite automata, as well as new Ehrenfeucht games of model comparison. (shrink)
We discuss formats for formal theories, from sets of models to more complex constructs with an epistemic slant, clarifying the issue of what it means to update a theory. Using properties of verisimilitude as a lead, we also provide some connections between formal calculus of theories in the philosophy of science and modal-epistemic logics. Throughout, we use this case study as a platform for discussing more general connections between logic and general methodology.
Some initial motivations for the Guarded Fragment still seem of interest in carrying its program further. First, we stress the equivalence between two perspectives: (a) satisfiability on standard models for guarded first-order formulas, and (b) satisfiability on general assignment models for arbitrary first-order formulas. In particular, we give a new straightforward reduction from the former notion to the latter. We also show how a perspective shift to general assignment models provides a new look at the fixed-point extension LFP(FO) of first-order (...) logic, making it decidable. Next, we relate guarded syntax to earlier quantifier restriction strategies for achieving effective axiomatizability in second-order logic – pointing at analogies with ‘persistent’ formulas, which are essentially in the Bounded Fragment of many-sorted first-order logic. Finally, we look at some further unexplored directions, including the systematic use of ‘quasi-models’ as a semantics by itself. (shrink)
The general verificationist thesis says that What is true can be known or formally: φ → ◊Kφ VT Fitch's argument trivializes this principle. It uses a weak modal epistemic logic to show that VT collapses truth and knowledge, by taking a clever substitution instance for φ: P ∧ ¬KP → ◊ K(P ∧ ¬KP) Then we have the following chain of three conditionals (a) ◊ K(P ∧ ¬KP) → ◊ (KP ∧ K¬KP) in the minimal modal logic for the knowledge (...) operator K, (b) ◊ (KP ∧ K¬KP) → ◊ (KP ∧¬KP) in the modal logic T, and finally (c) ◊ (KP ∧¬KP) → ⊥ in the minimal modal logic for. (shrink)
Current dynamic epistemic logics often become cumbersome and opaque when common knowledge is added. In this paper we propose new versions that extend the underlying static epistemic language in such a way that dynamic completeness proofs can be obtained by perspicuous reduction axioms.
Dynamic update of information states is a new paradigm in logicalsemantics. But such updates are also a traditional hallmark ofprobabilistic reasoning. This note brings the two perspectives togetherin an update mechanism for probabilities which modifies state spaces.
Game logics describe general games through powers of players for forcing outcomes. In particular, they encode an algebra of sequential game operations such as choice, dual and composition. Logic games are special games for specific purposes such as proof or semantical evaluation for first-order or modal languages. We show that the general algebra of game operations coincides with that over just logical evaluation games, whence the latter are quite general after all. The main tool in proving this is a representation (...) of arbitrary games as modal or first-order evaluation games. We probe how far our analysis extends to product operations on games. We also discuss some more general consequences of this new perspective for standard logic. (shrink)
For a Euclidean space , let L n denote the modal logic of chequered subsets of . For every n 1, we characterize L n using the more familiar Kripke semantics, thus implying that each L n is a tabular logic over the well-known modal system Grz of Grzegorczyk. We show that the logics L n form a decreasing chain converging to the logic L of chequered subsets of . As a result, we obtain that L is also a logic (...) over Grz, and that L has the finite model property. We conclude the paper by extending our results to the modal language enriched with the universal modality. (shrink)
We analyze extensive games as interactive process models, using modallanguages plus matching notions of bisimulation as varieties of gameequivalences. Our technical results show how to fit existing modalnotions into this new setting.
Preservation and interpolation results are obtained for L ∞ω and sublogics $\mathscr{L} \subseteq L_{\infty\omega}$ such that equivalence in L can be characterized by suitable back-and-forth conditions on sets of partial isomorphisms.
It has been known since the seventies that the formulas of modal logic are invariant for bisimulations between possible worlds models — while conversely, all bisimulation-invariant first-order formulas are modally definable. In this paper, we extend this semantic style of analysis from modal formulas to dynamic program operations. We show that the usual regular operations are safe for bisimulation, in the sense that the transition relations of their values respect any given bisimulation for their arguments. Our main result is a (...) complete syntactic characterization of all first-order definable program operations that are safe for bisimulation. This is a semantic functional completeness result for programming, which may be contrasted with the more usual analysis in terms of computational power. The 'Safety Theorem' can be modulated in several ways. We conclude with a list of variants, extensions, and further developments. (shrink)
In this paper, we generalize the set-theoretic translation method for poly-modal logic introduced in [11] to extended modal logics. Instead of devising an ad-hoc translation for each logic, we develop a general framework within which a number of extended modal logics can be dealt with. We first extend the basic set-theoretic translation method to weak monadic second-order logic through a suitable change in the underlying set theory that connects up in interesting ways with constructibility; then, we show how to tailor (...) such a translation to work with specific cases of extended modal logics. (shrink)
We give a condensed survey of recent research on generalized quantifiers in logic, linguistics and computer science, under the following headings: Logical definability and expressive power, Polyadic quantifiers and linguistic definability, Weak semantics and axiomatizability, Computational semantics, Quantifiers in dynamic settings, Quantifiers and modal logic, Proof theory of generalized quantifiers.
Labeled transition systems are key structures for modeling computation. In this paper, we show how they lend themselves to ordinary logical analysis (without any special new formalisms), by introducing their standard first-order theory. This perspective enables us to raise several basic model-theoretic questions of definability, axiomatization and preservation for various notions of process equivalence found in the computational literature, and answer them using well-known logical techniques (including the Compactness theorem, Saturation and Ehrenfeucht games). Moreover, we consider what happens to this (...) general theory when one restricts attention to special classes of transition systems (in particular, finite ones), as well as extended logical languages (in particular, infinitary first-order logic). We hope that this puts standard logical formalisms on the map as a serious option for a theory of computational processes. As a side benefit, our approach increases comparability with several other existing formalisms over labeled transition systems (such as Process Algebra or Modal Logic). We provide some pointers to this effect, too. (shrink)
Johan van Benthem (1988). Games in Logic. In Jakob Hoepelman (ed.), Representation and Reasoning: Proceedings of the Stuttgart Conference Workshop on Discourse Representation, Dialogue Tableaux, and Logic Programming. M. Niemeyer Verlag.
Of the various notions of reduction in the logical literature, relative interpretability in the sense of Tarskiet al. [6] appears to be the central one. In the present note, this syntactic notion is characterized semantically, through the existence of a suitable reduction functor on models. The latter mathematical condition itself suggests a natural generalization, whose syntactic equivalent turns out to be a notion of interpretability quite close to that of Ershov [1], Szczerba [5] and Gaifman [2].
REFERENCES Barwise, J. & R. Cooper (1981) — 'Generalized Quantifiers and Natural Language', Linguistics and Philosophy 4:2159-219. Van Benthem, J. (1983a) — ' Five Easy Pieces', in Ter Meulen (ed.), 1-17. Van Benthem, J. (1983b) ...
Exact philosophy consists of various disciplines scattered and separated. Formal semantics and philosophy of science are good examples of two such disciplines. The aim of this paper is to show that there is possible to find some integrating bridge topics between the two fields, and to show how insights from the one are illuminating and suggestive in the other.
