PhilPapers is currently in read-only mode while we are performing some maintenance. You can use the site normally except that you cannot sign in. This shouldn't last long.
The effects of public announcements, private communications, deceptive messages to groups, and so on, can all be captured by a general mechanism of updating multi-agent models with update action models, now in widespread use. There is a natural extension of the definition of a bisimulation to action models. Surely enough, updating with bisimilar action models gives the same result (modulo bisimulation). But the converse turns out to be false: update models may have the same update effects without being bisimilar. We (...) propose action emulation as a notion of equivalence more appropriate for action models, and generalizing standard bisimulation. It is proved that action emulation provides a full characterization of update effect. We first concentrate on the general case, and next focus on the important case of action models with propositional preconditions. Our notion of action emulation yields a simplification procedure for action models, and it gives designers of multi-agent systems a useful tool for comparing different ways of representing a particular communicative action. (shrink)
In this paper we present a dynamic assignment language which extends the dynamic predicate logic of Groenendijk and Stokhof [1991: 39–100] with assignment and with generalized quantifiers. The use of this dynamic assignment language for natural language analysis, along the lines of o.c. and [Barwise, 1987: 1–29], is demonstrated by examples. We show that our representation language permits us to treat a wide variety of donkey sentences: conditionals with a donkey pronoun in their consequent and quantified sentences with donkey pronouns (...) anywhere in the scope of the quantifier. It is also demonstrated that our account does not suffer from the so-called proportion problem.Discussions about the correctness or incorrectness of proposals for dynamic interpretation of language have been hampered in the past by the difficulty of seeing through the ramifications of the dynamic semantic clauses (phrased in terms of input-output behaviour) in non-trivial cases. To remedy this, we supplement the dynamic semantics of our representation language with an axiom system in the style of Hoare. While the representation languages of barwise and Groenendijk and Stokhof were not axiomatized, the rules we propose form a deduction system for the dynamic assignment language which is proved correct and complete with respect to the semantics. (shrink)
We explore some logics of change, focusing on commands to change the world in such a way that certain elementary propositions become true or false. This investigation starts out from the following two simplifying assumptions: (1) the world is a collection of facts (Wittgenstein), and (2), the world can be changed by changing elementary facts (Marx). These assumptions allow us to study the logic of imperatives in the simplest possible setting.
Logical frameworks for analysing the dynamics ofinformation processing abound [4, 5, 8, 10, 12, 14, 20, 22]. Some of these frameworks focus on the dynamics of the interpretation process, some on the dynamics of the process of drawing inferences, and some do both of these. Formalisms galore, so it is felt that some conceptual streamlining would pay off. This paper is part of a larger scale enterprise to pursue the obvious parallel between information processing and imperative programming. We demonstrate that (...) logical tools from theoretical computer science are relevant for the logic of information flow. More specifically, we show that the perspective of bare logic [13, 18] can fruitfully be applied to the conceptual simplification of information flow logics. Part one of this program consisted of the analysis of 'dynamic interpretation' in this way, using the example of dynamic predicate logic [10]; the results were published in [7]. The present paper constitutes the second part of the program, the analysis of 'dynamic inference'. Here we focus on Veltman’s update logic [22]. Update logic is an example of a logical framework which takes the dynamics of drawing inferences into account by modelling information growth as discarding of possibilities. This paper shows how information logics like update logic can fruitfully be studied by linking their dynamic principles to static 'correctness descriptions'. Our theme is exemplified by providing a sound and complete HoarelPratt style deduction system for update logic. The Hoare/Pratt correctness statements use modal propositional dynamic logic as assertion language and connect update logic to the modal propositional logic S5. The connection with S5 provides a clear link between the dynamic and the static semantics of update logic. The fact that update logic is decidable was noted already in [2]; the connection with S5 provides an alternative proof. The S5 connection can also be used for rephrasing the validity notions of update logic and for performing consistency checks. In conclusion, it is argued that interpreting the dynamic statements of information logics as dynamic modal operators has much wider applicability. In fact, the method can be used to axiomatize quite a wide range of information logics. (shrink)
Eric: “We were wondering if you could give a talk on DEL and Process Algebra (in the sense that both are languages to describe how the model changes).” Jan: “I will give it a try.”.
This paper describes the work of the Polish logician Jan Kalicki (1922?1953). After a biographical introduction, his work on logical matrices and equational logic is appraised. A bibliography of his papers and reviews is also included.
Mijn wetenschappelijke bijdrage sluit aan bij het stuk van Jan Willem Klop in deze zelfde afscheidsbundel, dat ik van Jan Willem onder embargo te lezen heb gekregen. Je zult je herinneren dat Jan Willem in de CWI lezing ter gelegenheid van zijn eredoctoraat kort refereerde aan de Thue Morse reeks. Noem deze reeks M . Jan Willem gaf de versie die start met 1. Noem het resultaat van omwisselen van nullen en enen in de Thue Morse reeks M . De (...) reeks M is wat je krijgt als je het Thue Morse proces start met 0. (shrink)
We will present relational tools for analysing (large) software systems, based on the Haskell datatype for relations defined in Chapter 5 of Doets and Van Eijck, The Haskell Road to Logic, Maths and Programming, King’s College Publications, London 2004 [DvE04]. The main purpose is to demonstrate some very concrete applications of abstract relations, and to make the point that functional programming is highly relevant to software engineering.
Susan Okin read Robert Nozick as taking it to be fundamental to his Libertarianism that people own themselves, and that they can acquire entitlement to other things by making them. But she thinks that, since mothers make people, all people must then be owned by their mothers, a consequence Okin finds absurd. She sees no way for Nozick to make a principled exception to the idea that people own what they make when what they make is people, concluding that Nozick’s (...) theory of entitlement must be false, and that entitlement must instead be rooted in people’s needs. I say Okin misreads Nozick’s Libertarianism. In fact, its fundamental principle is that, simply by being persons, people are entitled to the maximum negative liberty compatible with a like liberty for all persons. Further, Nozick, and Jan Narveson, who has taken on the advocacy of Libertarian ideas, analyze liberty as freedom to interact with things, and analyze being entitled to or having property in something, as freedom to interact with it, to determine what may be done with it. People therefore have such freedom to do what they want with themselves, and such freedom to do what they want with other things, as is compatible with all persons having similar freedom. The former is what self-ownership amounts to, the latter, ownership of other things. Libertarianism’s fundamental principle therefore both grounds and delimits entitlements in ways entailing that mothers don’t own persons by dint of making them. Otherwise, since it would then be the prerogative of mothers to determine what shall be done with the persons they made, the persons made would lack equal liberty, this violating the fundamental principle. (shrink)
To ascertain that a formalization of the intuitive notion of a ‘concept’ is linguistically interesting, one has to check whether it allows to get a grip on distinctions and notions from lexical semantics. Prime candidates are notions like ‘prototype’, ‘stereotypical attribute’, ‘essential attribute versus accidental attribute’, ‘intension versus extension’. We will argue that although the current paradigm of formal concept analysis as an application of lattice theory is not rich enough for an analysis of these notions, a lattice theoretical approach (...) to concepts is a suitable starting point for formalizing them. (shrink)
We look at lying as an act of communication, where (i) the proposition that is communicated is not true, (ii) the utterer of the lie knows that what she communicates is not true, and (iii) the utterer of the lie intends the lie to be taken as truth. Rather than dwell on the moral issues, we provide a sketch of what goes on logically when a lie is communicated. We present a complete logic of manipulative updating, to analyse the effects (...) of lying in public discourse. Next, we turn to the study of lying in games. First, a game-theoretical analysis is used to explain how the possibility of lying makes such games interesting, and how lying is put to use in optimal strategies for playing the game. Finally, we give a matching logical analysis. Our running example of lying in games in liar’s dice. (shrink)
• Relational logic = First Order Logic plus Relational Operators. • Most relational operations are expressible in first order logic, but not all of them.
Thinking about Martin Stokhof as a philosopher and colleague, his formal analysis (together with Jeroen Groenendijk) of questions and question answering is the first thing that comes to mind. This work is part of a fruitful tradition that has recently spawned inquisitive semantics, and the focus on question answering in dynamic epistemic logic. The theme is still very much alive at ILLC today. Next, I am reminded of the dynamic turn in natural language semantics, of the way he and Jeroen (...) Groenendijk criticized Hans Kamp’s ideas about discourse representation, and how this led to the invention of dynamic predicate logic. Later it became clear that dynamic predicate logic can be viewed as the action part of quantified dynamic logic, invented much earlier by David Harel. This led to a connection, a semantic parallel, between the analysis of programming and the analysis of natural language. Thinking about Martin as a philosopher still longer, it is impossible to further postpone the thought of Ludwig Wittgenstein. This is the connection that I am least familiar with, so this is what I will write about, in the hope that developing my thought in writing will create a somewhat better understanding. (shrink)
Discourse Representation Theory is a specific name for the work of Hans Kamp in the area of dynamic interpretation of natural language. Also, it has gradually become a generic term for proposals for dynamic interpretation of natural language in the same spirit. These proposals have in common that each new sentence is interpreted in terms of the contribution it makes to an existing piece of interpreted discourse. The interpretation conditions for sentences are given as instructions for updating the representation of (...) the discourse. (shrink)
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)
Individual rational action consists of (i) knowing what you want, (ii) taking proper steps to approach what you want as closely as possible, within the confines of the law. This one can learn, although some people are more skilled in it than others. Modern democracies are set up in such a way that they leave as much room as possible for individual rational action. Education for citizenship is sometimes taken to be: getting young citizens acquainted with the legal possibilities for (...) maximizing their individual interests. How about collective rational action? Game theory shows that if people engage in individual rational action, the common good suffers. This is known as ‘the tragedy of the commons’. It was also known in Antiquity: ”What is common to the greatest number has the least care bestowed upon it” (Aristotle). To understand the issues involved we will analyse the notions of ”common knowledge”, ”individual commitment” and ”collective intention”. (shrink)
Presuppositions of utterances are the pieces of information you convey with an utterance no matter whether your utterance is true or not We rst study presupposition in a very simple framework of updating propo sitional information with examples of how presuppositions of complex propositional updates can be calculated Next we move on to presupposi tions and quanti cation in the context of a dynamic version of predicate logic suitably modi ed to allow for presupposition failure In both the propositional and (...) the quanti cational case presupposition failure can be viewed as error abortion of procedures Thus a dynamic assertion logic which describes the preconditions for error abortion is the suitable tool for analysing presupposition.. (shrink)
An emerging standard for polymorphically typed, lazy, purely functional programming is Haskell, a language named after Haskell Curry. Haskell is based on (polymorphically typed) lambda calculus, which makes it an excellent tool for computational semantics.
Notice: This PDF version was distributed by request to members of the Friends of the SEP Society and by courtesy to SEP content contributors. It is solely for their fair use. Unauthorized distribution is prohibited. To learn how to join the Friends of the..
We carry out (formalize) the Karttunen-Stalnaker pragmatic account of presupposition projection within a state-of-the art version of dynamic epistemic logic. It turns out that the basic projection facts can all be derived from a Gricean maxim ‘be informative’. This sheds light on a recent controversy on the appropriateness of dynamic semantics as a tool for analysing presupposition.
Time discounting is the phenomenon that a desired result in the future is perceived as less valuable than the same result now. Economic theories can take this psychological fact into account in several ways. In the economic literature the most widely used type of additive time discounting is exponential discounting. In exponential discounting, the fall of valuation depends by a constant factor on the length of the delay period. It is well known, however, that exponential time discounting often does not (...) describe well how people actually behave. Most people are averse to short delays in gratification now, while their future selves may not mind a bit of extra waiting. This behaviour can be described well by non-exponential discounting functions such as hyperbolic discounting. In hyperbolic discounting, valuations fall rapidly for small delay periods, but the fall gets slower for longer delay periods. Hyperbolic discounting captures phenomena such as procrastination, addiction and in general inconsistency over time. This chapter investigates whether forms of non-exponential discounting, in particular close to the so called Quasi-Hyperbolic model, could also be characterized in terms of dynamically consistent choices when individuals discount the welfare of future selves as well as their payoffs. (shrink)
This talk shows how propositional dynamic logic (PDL) can be interpreted as a logic for multi-agent knowledge update and belief revision, or as a logic of preference change, if the basic relations are read as preferences instead of plausibilities. Our point of departure is the logic of communication and change (LCC) of [9]. Like LCC, our logic uses PDL as a base epistemic language. Unlike LCC, we start out from agent plausibilities, add their converses, and build knowledge and belief operators (...) from these with the PDL constructs. We extend the update mechanism of LCC to an update mechanism that handles belief change as relation substitution, and we show that the update part of this logic is more expressive than either that of LCC or that of epistemic/doxastic PDL with a belief change modality. Next, we show that the properties of knowledge and belief are preserved under any update, unlike in LCC. We prove completeness of the logic and give examples of its use. If there is time, we will also look at the preference interpretation of the system, and at preference change scenarios that can be modelled with it. (shrink)
We contrast Bonanno’s ‘Belief Revision in a Temporal Framework’ [15] with preference change and belief revision from the perspective of dynamic epistemic logic (DEL). For that, we extend the logic of communication and change of [11] with relational substitutions [8] for preference change, and show that this does not alter its properties. Next we move to a more constrained context where belief and knowledge can be defined from preferences [29; 14; 5; 7], prove completeness of a very expressive logic of (...) belief revision, and define a mechanism for updating belief revision models using a combination of action priority update [7] and preference substitution [8]. (shrink)
In this paper1, we develop an epistemic logic to specify and reason about the information flow on the underlying communication channels. By combining ideas from Dynamic Epistemic Logic (DEL) and Interpreted Systems (IS), our semantics offers a natural and neat way of modelling multi-agent communication scenarios with different assumptions about the observational power of agents. We relate our logic to the standard DEL and IS..
Almost forty years ago Richard Montague proposed to analyse natural language with the same tools as formal languages. In particular, he gave formal semantic analyses of several interesting fragments of English in terms of typed logic. This led to the development of Montague grammar as a particular style of formal analysis of natural language.
Categorization is probably one of the most central areas in the study of cognition, language and information. However, there is a serious gap running through the semantic treatments of categories and concepts [3]. On one side we find the ’classical’, formal approach, based on logical considerations, that has lent itself well for computational applications. In this approach, concepts are defined in terms of necessary and sufficient conditions. On the other side is an informal approach to categorization that is usually motivated (...) by the results of psychological experiments and that has not found its way into technologies on a large scale. Concepts here are based on prototypes, stereotypical attributes and family resemblances, which have become the hallmark of cognitive semantics. Obviously, it is important to bridge this gap, for theoretical and practical reasons. (shrink)
This paper introduces DEMO, a Dynamic Epistemic Modelling tool. DEMO allows modelling epistemic updates, graphical display of update results, graphical display of action models, formula evaluation in epistemic models, translation of dynamic epistemic formulas to PDL formulas, and so on. The paper implements the reduction of dynamic epistemic logic [16, 2, 3, 1] to PDL given in [12]. The reduction of dynamic epistemic logic to automata PDL from [24] is also discussed and implemented. Epistemic models are minimized under bisimulation, and (...) update action models are minimized under action emulation (the appropriate structural notion for having the same update effect, cf. [13]). The paper is an exemplar of tool building for epistemic update logic. It contains the full code of an implementation in Haskell [22], in ‘literate programming’ style [23], of DEMO. (shrink)
In this tutorial, the meaning of natural language is analysed along the lines proposed by Gottlob Frege and Richard Montague. In building meaning representations, we assume that the meaning of a complex expression derives from the meanings of its components. Typed logic is a convenient tool to make this process of composition explicit. Typed logic allows for the building of semantic representations for formal languages and fragments of natural language in a compositional way. The tutorial ends with the discussion of (...) an example fragment, implemented in the functional programming language Haskell Haskell Team; Jones.. (shrink)
This paper shows how propositional dynamic logic (PDL) can be interpreted as a logic for multi-agent belief revision. For that we revise and extend the logic of communication and change (LCC) of [9]. Like LCC, our logic uses PDL as a base epistemic language. Unlike LCC, we start out from agent plausibilities, add their converses, and build knowledge and belief operators from these with the PDL constructs. We extend the update mechanism of LCC to an update mechanism that handles belief (...) change as relation substitution, and we show that the update part of this logic is more expressive than either that of LCC or that of doxastic/epistemic PDL with a belief change modality. It is shown that the properties of knowledge and belief are preserved under any update, and that the logic is complete. (shrink)
Just as war can be viewed as continuation of diplomacy using other means, computational semantics is continuation of logical analysis of natural language by other means. For a long time, the tool of choice for this used to be Prolog. In our recent textbook we argue (and try to demonstrate by example) that lazy functional programming is a more appropriate tool. In the talk we will lay out a program for computational semantics, by linking computational semantics to the general analysis (...) of procedures for social interaction. The talk will give examples of how Haskell can be used to begin carrying out this program. (shrink)
It is well established by now that computer science has a number of concerns in common with natural language understanding. Common themes show up in particular with algorithmic aspects of text processing. This chapter gives an overview of border crossings from NLP to CS and back. Starting out from syntactic analysis, we trace our route via a philosophical puzzle about meaning, Hoare correctness rules for dynamic semantics, error state analysis of presupposition, equational reasoning about state change, programming with frameworks originally (...) devised for natural language semantics, and the logic of incremental processing. In many cases methods and perspectives developed on one side of the border proved quite useful on the other side, although usually it becomes clear after a while that tools have to be redesigned to fit. The chapter ends with a sketch of the emerging contours of a ‘proper treatment of context in natural language’ that is more than just an application of a logic designed for program analysis. (shrink)
This paper contains the full code of an implementation in Haskell [2], in ‘literate programming’ style [3], of an approach to deductive parsing based on [4]. We focus on the case of the Earley [1] parsing algorithm for CF languages.
‘all A are B’ ; A ⊆ B ‘no A are B’ ; A ⊆ B ‘some A are not B’ ; A ⊆ B ‘some A are B’ ; A ⊆ B (equivalently: A ∩ B = ∅). A knowledge base is a list of triples (Class1, Class2, Boolean) where (A, B, ) expresses that A ⊆ B, and (A, B, ⊥) expresses that A ⊆ B.
Key ingredients in discourse meaning are reference markers: objects in the formal representation that the discourse is about. It is well-known that reference markers are not like first order variables. Indeed, it is the received view that reference markers are like the variables in imperative programming languages. However, in a computational semantics of discourse that treats reference markers as ‘dynamically bound’ variables, every noun phrase will get linked to a dynamic variable, so it will give rise to a marker index. (...) Where do these indices come from? How do we handle them when combining (or ‘merging’) pieces of discourse? We will argue that reference markers are better treated as indices into context, and we will present a theory of context and context extension based on this view. In context semantics, noun phrases do not come with fixed indices, so the merge problem does not arise. This solves a vexing issue with coordination that causes trouble for all current versions of compositional discourse representation theory. (shrink)
Hyper tableau reasoning is a version of clausal form tableau reasoning where all negative literals in a clause are resolved away in a single inference step. Constrained hyper tableaux are a generalization of hyper tableaux, where branch closing substitutions, from the point of view of model generation, give rise to constraints on satisfying assignments for the branch. These variable constraints eliminate the need for the awkward ‘purifying substitutions’ of hyper tableaux. The paper presents a non-destructive and proof confluent calculus for (...) constrained hyper tableaux, together with a soundness and completeness proof, with completeness based on a new way to generate models from open tableaux. It is pointed out that the variable constraint approach applies to free variable tableau reasoning in general. (shrink)
We sketch recent insights in dynamic epistemic logic and use them to shed new light on old ideas about common knowledge as a prerequisite for linguistic communication.
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)
Computer software is written in languages like C, Java or Haskell. In many cases social software is written in natural language. The talk will explore connections between the areas of natural language analysis and social software.
This is a review of Quantifiers, Logic, and Language, edited by Jaap van der Does and Jan van Eijk, published by CSLI (Center for the Study of Language and Information) Publications in 1996.
We de ne an executable process interpretation for dynamic rst order logic and show that it is a faithful approximation of a dynamic interpre tation procedure for rst order formulas familiar from natural language semantics extended with constructs for bounded choice and bounded it eration This new interpretation of extended dynamic FOL is inspired by an executable interpretation for standard FOL proposed by Apt and Bezem The relation to the Apt Bezem style execution process and the advantages of taking dynamic (...) FOL rather than standard FOL as one s point of reference are discussed at some length Our results relate computational interpretation of FOL to a research tra dition from natural language semantics We discuss some example pro grams in Dynamo a simple language for dynamic logic programming based on the executable process interpretation for dynamic FOL.. (shrink)
Let R be a binary relation on some domain. Use R∗ for the reflexive transitive closure of R, i.e., the smallest binary relation S with R ⊆ S that is reflexive and transitive. Use R+ for the transitive closure of R, i.e., the smallest binary relation S with R ⊆ S that is transitive. Use I for the identity relation on the domain. Let n range over natural numbers. Define Rn as follows, by induction: R0 := I Rn+1 := R (...) ◦ R.. (shrink)
Dynamic epistemic logic is the logic of the effects of epistemic actions like making public announcements, passing private messages, revealing secrets, telling lies. This paper takes its starting point from the version of dynamic epistemic logic of [2], and demonstrates a tool that can be used for showing what goes on during a series of epistemic updates: the dynamic epistemic modelling tool DEMO [7, 9]. DEMO allows modelling epistemic updates, graphical display of update results, graphical display of action models, formula (...) evaluation in epistemic models, and translation of dynamic epistemic formulas to PDL [22] formulas. DEMO is written in Haskell. This paper intends to demonstrate its usefulness for visualizing the model transformations that take place during epistemic updating. (shrink)
Three key ways of updating one’s knowledge are (i) perception of states of affairs, e.g., seeing with one’s own eyes that something is the case, (ii) reception of messages, e.g., being told that something is the case, and (iii) drawing new conclusions from known facts. If one represents knowledge by means of Kripke models, the implicit assumption is that drawing conclusions is immediate. This assumption of logical omniscience is a useful abstraction. It leaves the distinction between (i) and (ii) to (...) be accounted for. In current versions of Update Logic (Dynamic Epistemic Logic, Logic of Communication and Change) perception and message reception are not distinguished. This paper proposes an extension of Update Logic that makes this distinction explicit. The logic deals with three kinds of updates: announcements, changes of the world, and observations about the world in the presence of witnesses. The resulting logic is shown to be complete by means of a reduction to epistemic propositional dynamic logic by a well known method. (shrink)
This is a case-study in knowledge representation and dynamic epistemic protocol verification. We analyze the ‘one hundred prisoners and a lightbulb’ puzzle. In this puzzle it is relevant what the agents (prisoners) know, how their knowledge changes due to observations, and how they affect the state of the world by changing facts, i.e., by their actions. These actions depend on the history of previous actions and observations. Part of its interest is that all actions are local, i.e. not publicly observable, (...) and part of the problem is therefore how to disseminate local results to other agents, and make them global. The various solutions to the puzzle are presented as protocols (iterated functions from agent’s local states, and histories of actions, to actions). The paper consists of three parts. First, we present different versions of the puzzle, and their solutions. This includes a probabilistic version, and a version assuming synchronicity (the interval between prisoners’ interrogations is known). The latter is very informative for the prisoners, and allows different protocols (with faster expected termination). Then, we model the puzzle in an epistemic logic incorporating dynamic operators for the effects of information changing events. Such events include both informative actions, where agents become more informed about the non-changing state of the world, and factual changes, wherein the world and the facts describing it change themselves as well. Finally, we verify the basic protocol to solve the problem. Novel contributions in this paper are: Firstly, Protocol 2 and Protocol 4. Secondly, the modelling in dynamic epistemic logic in its entirety — we do not know of a case study that combines factual and informational dynamics in a setting of non-public events, or of a similar proposal.. (shrink)
A key notion of equivalence for modal and epistemic logic is bisimulation. However, to capture the update effects of action models in epistemic update logic, this notion turns out to be too strong. We propose necessary and sufficient conditions for having the same update effect, in the cases of action models with propositional preconditions and action models with modal precondions. Next, the notion of an action emulation is proposed as a notion of equivalence more appropriate for action models than bisimulation. (...) It is proved that every bisimulation is an action emulation, but not vice versa, and that in the context of action models with propositional or modal preconditions, action emulation provides a full characterisation of update effect. (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.
This paper extends the Earley parsing algorithm for context free languages [3] to the case of sequentially indexed languages. Sequentially indexed languages are related to indexed languages [1, 2]. The difference is that parallel processing of index stacks is replaced by sequential processing [4].
By his critical reflections on the crisis of modern civilization, Jan Patočka, phenomenologist of the Other Europe, incarnates the critical consciousness of the phenomenological movement. He was in fact one of the first European philosophers to have emphasized the necessity of abandoning the hitherto Eurocentric propositions of solution to the crisis when he explicitly raised the problems of a “Post-European humanity”. In advocating an understanding of the history of European humanity different from those of Husserl and Heidegger, Patočka directs his (...) philosophical reflections back to sketch a more profound phenomenology of the natural world insufficiently thematized in Husserl and absent in Heidegger’s Sein und Zeit. By virtue of its emphasis on the structural characteristics of movement, of praxis, and of the disclosure of the abyssal nature of human existence and of the original nothingness as the (non-)foundation of the phenomenal world, Patočka’s phenomenology of the natural world constitutes an opening towards the reception of Others and other cultures, in particular that of Chinese Taoist philosophy. (shrink)
We take a fresh look at voting theory, in particular at the notion of manipulation, by employing the geometry of the Saari triangle. This yields a geometric proof of the Gibbard/Satterthwaite theorem, and new insight into what it means to manipulate the vote. Next, we propose two possible strengthenings of the notion of manipulability (or weakenings of the notion of non-manipulability), and analyze how these affect the impossibility proof for non-manipulable voting rules.
This is indeed a very nice draft that I have read with great pleasure, and that has helped me to better understand the completeness proof for LCC. Modal fixed point logic allows for an illuminating new version (and a further extension) of that proof. But still. My main comment is that I think the perspective on substitutions in the draft paper is flawed. The general drift of the paper is that relativization, (predicate) substitution and product update are general operations on (...) models, and that it is important to check whether given logical languages are closed under these operations. FO logic is closed under relativization, predicate substitution and product constructions (such as those involved in relative interpretation). The minimal modal logic is closed under relativization, which explains the reduction of epistemic logic (withhout common knowledge) + public announcement to epistemic logic simpliciter (as observed in Van Benthem, [2]). The reduction breaks down as soon as one adds common knowledge. The minimal modal logic is also closed under substitution, which explains the reduction of epistemic logic plus (publicly observable) factual change to epistemic logic simpliciter, via the following reduction axioms (I use !p := φ for the operation of publicly changing the truth value of p to φ): [!p := φ]p ↔ φ [!p := φ]q ↔ q (p and q syntactically different ) [!p := φ]¬ψ ↔ ¬[!p := φ]ψ [!p := φ](ψ1 ∧ ψ2) ↔ [!p := φ]ψ1 ∧ [!p := φ]ψ2 [!p := φ][i]ψ ↔ [i][!p := φ]ψ Unlike the case of relativisation, this can be extended to the case of epistemic logic with common knowledge, by means of: [!p := φ]CGψ ↔ CG[!p := φ]ψ We get the following.. (shrink)
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..
In this paper we forge a connection between dynamic epistemic logics of belief revision on one hand and studies of collective judgement and multi-agent preference change on the other. Belief revision in the spirit of dynamic epistemic logic uses updating with relational substitutions to change the beliefs of individual agents. Collective judgement in social choice theory studies the collective outcomes of individual belief changes. We start out from the logic of communication and change (LCC), which is basically epistemic propositional dynamic (...) logic (PDL) extended with update action modalities. We show how epistemic PDL can be made to handle belief operators. Our new version of epistemic/doxastic PDL does not impose any constraints on the basic relations. Because of this it does not suffer from the drawback of LCC that constraints on epistemic relations, such as transitivity and reflexivity, may get lost under updates that are admitted by the system. After introducing the base system without constraints, we study the effects of imposing a single constraint, namely the constraint that the agent’s preference relations are linked. Linkedness is a natural extension of local connectedness to the multi-agent case. It assures that if Alice prefers y to x and Bob prefers z to x, then both Alice and Bob can make up their minds when given a choice between y and z. Since general belief changes may not preserve linkedness, we propose a recipe for belief change that does preserve it. Finally, we show that the resulting framework can be used to model consensus seeking procedures. We focus on the case of plenary Dutch meetings. In Dutch meetings, a belief change (or rather: preference change) is performed for all agents in the meeting if a majority believes (or: is in favour of) the proposition that is under discussion. A special case of these meetings is judgement aggregation, and we apply our framework to the discursive dilemma in.. (shrink)
We model the ‘100 prisoners and a lightbulb’ puzzle in an epistemic logic incorporating dynamic operators for the effects of information changing events. Such events include both informative actions, where agents become more informed about the non-changing state of the world, and factual changes, wherein the world and the facts describing it change themselves as well. We specify the underlying nondeterministic protocol and verify its postconditions in a recent extension of the model checker DEMO with factual change. We also present (...) a synchronized version of the riddle, for which there are also other protocols, and we report on efforts to minimize the expected termination of such protocols when assuming random scheduling. (shrink)
• Causing a jump from nothingness to being. • The description conveys that there is tension. something is not there, and I want it to be there. I struggle to force it into existence.
Logics of communication should provide accounts of changes in the state of information of a group of discourse participants, on the basis of message exchanged within the group. We will give an overview of the way this is done in dynamic epistemic logics, focussing on a number of different types of informative actions with their epistemic effects, and indicating the relevance of this work for semantics and pragmatics of natural language. At the end of the talk we will sketch a (...) recent result on translating logics for generic epistemic updating into PDL (propositional dynamic logic). (shrink)
Dynamic logic, broadly conceived, is the logic that analyses change by decomposing actions into their basic building blocks and by describing the results of performing actions in given states of the world. The actions studied by dynamic logic can be of various kinds: actions on the memory state of a computer, actions of a moving robot in a closed world, interactions between cognitive agents performing given communication protocols, actions that change the common ground between speaker and hearer in a conversation, (...) actions that change the contextually available referents in a conversation, and so on. (shrink)
Many arguments for flexible type assignment to syntactic categories have to do with the need to account for the various scopings resulting from the interaction of quantified DPs with other quantified DPs or with intensional or negated verb contexts. We will define a type for arbitrary arity relations in polymorphic type theory. In terms of this, we develop the Boolean algebra of relations as far as needed for natural language semantics. The type for relations is flexible: it can do duty (...) for the whole family of types t, e → t, e → e → t, and so on. If we use this flexible type for the interpretations of verbs, we can perform a ‘flexible lift’ on DP interpretations, so that DPs get interpreted as operations on verb meanings. This leads to an elegant implementation of Keenan’s proposal for polyadic quantification in natural language (‘Beyond the Frege Boundary’). It turns out that scope reorderings are particularly easy to implement in this framework. (shrink)
It is a sunny autumn day, and our protagonists have taken their meals outside, to enjoy the mild rays of the September sun. The NIAS cook Paul Nolte, as always glowing with pride while serving out his delicious food, has prepared a traditional Dutch meal today with sausage, red cabbage and pieces of apple.
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)
Organized around the central concept of struggle, this paper is an introduction to the later thought of the Czech phenomenologist Jan Patočka (1907–1977), with attention to the circumstances of his life. The first section of the paper presents Patočka’s description of the “three movements” of human existence, with emphasis upon the second, the movement of defense, work, and survival. The second section examines his later conception of philosophy, where he reprised elements of classical Greek thought (the Heraclitean notion of polemos (...) and the Socratic notion of “care of the soul”) for their relevance in the modern world. (shrink)
Non-determined game logic is the logic of two player board games where the game may end in a draw: unlike the case with determined games, a loss of one player does not necessarily constitute of a win of the other player. A calculus for non-determined game logic is given in [4] and shown to be complete. The calculus adds a new rule for the treatment of greatest fixpoints, and a new unfolding axiom for iterations of the universal player. The technique (...) of the completeness proof is inspired by the canonical model construction for propositional dynamic logic (PDL). In this paper, this is extended to the logic of determined games. It is proved that the calculus for nondetermined game logic, together with the axiom of determinacy, is complete for determined game logic. Next, it is shown that the axioms and rules of the new calculus can all be derived from the calculus proposed by Parikh in [5], for which the completeness was still open. This proves Parikh’s conjecture that his calculus is complete for determined games. (shrink)
Light version of DEMO for composing epistemic models, based on the code for the ESSLLI 2008 course on Dynamic Epistemic Logic (see http:// homepages.cwi.nl/~jve/courses/esslli08/) extended with vocabulary information [EWS10]. Factual change is also treated. The piece ends with some examples: the muddy children, and hat puzzles, dealing with the interaction of perception and change [Eijar].
Functions of type n are characteristic functions on n-ary relations. In Beyond the Frege Boundary [6], Keenan established their importance for natural language semantics, by showing that natural language has many examples of irreducible type n functions, where he called a function of type n reducible if it can be represented as a composition of functions of type 1 . We will give a normal form theorem for functions of type n , and use this to show that natural language (...) has many examples of irreducible type n functions in a much stronger sense, where we take a function to be reducible if it can be represented as a composition of functions of lower types. (shrink)
In [11] it is shown how propositional dynamic logic (PDL) can be interpreted as a logic of belief revision that extends the logic of communication and change (LCC) given in [7]. This new version of epistemic/doxastic PDL does not impose any constraints on the basic relations and because of this it does not suffer from the drawback of LCC that these constraints may get lost under updates that are admitted by the system. Here, we will impose one constraint, namely that (...) the agent’s plausibility relations are linked. Linkedness is a natural extension of local connectedness to the multi-agent case and it assures that we know the agent’s preferences between all relevant alternatives. Since the belief updates that are used in [11] may not preserve linkedness, we limit ourselves to a particular kind of belief change that does preserve it. Our framework has obvious connections to coalition logic [17] and social choice theory [19]. We show how we can use it to model consensus seeking in plenary Dutch meetings. In Dutch meetings, a belief update is done for all agents in the meeting if a majority beliefs the proposition that is under discussion. A special case of these meetings is judgement aggregation, and we apply our framework to the discursive dilemma in this field [15]. (shrink)
Epistemic logic is the logic of knowledge, and dynamic epistemic logic is the logic of effects of communicative actions on the knowledge states of a set of agents. Typical communicative actions are making public announcements, passing private messages, revealing secrets, telling lies. This paper takes its starting point from the version of dynamic epistemic logic of [3], and demonstrates a tool that can be used for showing what goes on during a series of epistemic updates: the dynamic epistemic modelling tool (...) DEMO [10]. DEMO allows modelling epistemic updates, graphical display of update results, graphical display of action models, formula evaluation in epistemic models, and translation of dynamic epistemic formulas to PDL [23] formulas. DEMO is written in Haskell. This paper intends to demonstrate its use for calculating and visualizing the model transformations that take place during epistemic updating. (shrink)
This is a case-study in knowledge representation. We analyze the ‘one hundred prisoners and a lightbulb’ puzzle. In this puzzle it is relevant what the agents (prisoners) know, how their knowledge changes due to observations, and how they affect the state of the world by changing facts, i.e., by their actions. These actions depend on the history of previous actions and observations. Part of its interest is that all actions are local, i.e. not publicly observable, and part of the problem (...) is therefore how to disseminate local results to other agents, and make them global. The various solutions to the puzzle are presented as protocols (iterated functions from agent’s local states, and histories of actions, to actions). The computational aspect is about average runtime termination under conditions of random (‘fair’) scheduling. (shrink)
The communicative effect of a collective message from the Dutch former minister of finance Wouter Bos to inform all his contacts about his new email address is completely different from that of a set of individual messages to the same list. The talk will explain how differences of this kind can be modelled in epistemic logic (the logic of knowledge). A central notion here is common knowledge. We will explain the general framework for describing update effects of messages as mappings (...) on epistemic models (“knowledge models”), and we will give a sketch of some recent work in this area. (shrink)
Het communicatieve effect van een collectieve email van Wouter Bos aan al zijn contacten is totaal anders dan van hetzelfde bericht gestuurd aan iedere geadresseerde persoonlijk. In de lezing zal worden ingegaan op de vraag hoe je dit soort verschillen kunt modelleren in epistemische logica. Een centrale notie hierbij is ‘common knowledge’ of ‘collectief weten’. Dit begrip zal worden geillustreerd aan de hand van een aantal logische puzzles, en van protocollen uit het dagelijks leven die bedoeld zijn om collectief weten (...) tot stand te brengen. Er zal worden uitgelegd waarom het in gevallen waar een economische belang in het geding is niet rationeel is ‘to agree to disagree’ (van elkaar te weten dat we de waarde van een economisch goed verschillend beoordelen). Als er tijd is doen we ook een demonstratie epistemisch modelleren. (shrink)
Syllogistics reduces to only two rules of inference: monotonicity and symmetry, plus a third if one wants to take existential import into account. We give an implementation that uses only the monotonicity and symmetry rules, with an addendum for the treatment of existential import. Soundness follows from the monotonicity properties and symmetry properties of the Aristotelean quantifiers, while completeness for syllogistic theory is proved by direct inspection of the valid syllogisms. Next, the valid syllogisms are decomposed in terms of the (...) rules they involve. The implementation uses Haskell [8], and is given in ‘literate programming’ style [9]. (shrink)
• Relational logic = First Order Logic plus Relational Operators. • Most relational operations are expressible in first order logic, but not all of them.
As regular readers of The Pluralist are aware, there appeared in 2008 an issue devoted to Jan Olof Bengtsson's The Worldview of Personalism.1 The issue included five articles, each concerned with a different aspect of the book; and after each article, there was a "Reply" by Bengtsson. In what follows, I shall say something about Bengtsson's reply to my own contribution, "Absolute and Personal Idealism." However, first let me briefly describe that article's argument.In "Absolute and Personal Idealism," I examined the (...) personalist attack on absolutism as formulated by Andrew Seth Pringle-Pattison in two works: Hegelianism and Personality and The Idea of God in the Light of Recent Philosophy. In the first section of .. (shrink)
• Wat wil ik doen/maken/cre¨eren (in het klein, in het groot . . . )? • Welke richting kies ik? • Wat is belangrijk? Wat minder belangrijk? Je kunt helderheid voor jezelf cre¨eren (weer: in het klein, in het groot) door de dingen die je wilt doen te rangschikken in volgorde van belangrijkheid.
Guarded actions are changes with preconditions acting as a guard. Guarded action models are multimodal Kripke models with the valuations replaced by guarded actions. Call guarded action logic the result of adding product updates with guarded action models to PDL (propositional dynamic logic). We show that guarded action logic reduces to PDL.
• Een programma puzzle • Puzzelen met steentjes • Functies en functioneel programmeren • Functies maken met lambda abstractie • Eigenschappen van dingen en karakteristieke functies • De ‘filter’ functie • Oneindige lijsten • Priemgetallen herkennen en genereren • Opdrachten..
How to write a program in Haskell, and how to use the Haskell testing tools . . . QuickCheck is a tool written in the functional programming language Haskell that allows testing of specifications by means of randomly generated tests. QuickCheck is part of the standard Haskell library. Re-implementations of QuickCheck exist for many languages, including Ruby and Scheme. SmallCheck is a similar tool, different from QuickCheck in that it tests properties for all finitely many values of a datatype up (...) to some given depth, with progressive increase of depth. Haskell is a research language: many of the testing tools that were first developed for Haskell later find their way to other languages. These slides discuss QuickCheck (two versions), SmallCheck, and some work in progress. We end with some examples of Alloy specifications. (shrink)
This paper contains the full code of a prototype implementation in Haskell [5], in ‘literate programming’ style [6], of the tableau-based calculus and proof procedure for hybrid logic presented in [4].
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)
We explore some logics of change, focusing on commands to change the world in such a way that certain elementary propositions become true or false. This investigation starts out from the following two simplifying assumptions: (1) the world is a collection of facts (Wittgenstein), and (2), the world can be changed by changing elementary facts (Marx). These assumptions allow us to study the logic of imperatives in the simplest possible setting.
Dislocation phenomena in natural language can be, and often are, thought of as the effects of movement transformations. We propose to handle these phenomena in terms of parser combinators [3, 8] that transform recursive descent parsers for a ‘deep structure language’ into parsers for a ‘surface structure language’. This combinator approach to extraction keeps close to the ‘movement’ intuition and gives a computational account of the well known island constraints on extraction first proposed in [7].
As a start, we give further examples of Alloy specifications. Next we turn to specification of imperative programs. Assertions about programs are specifications of how the program is supposed to behave. Assertions can be used for correctness reasoning and for testing. We illustrate the important notions of preconditions and postconditions. We demonstrate how the state transitions of imperative programming can be modelled as relations in Alloy. Correctness reasoning can be linked to testing and debugging by means of executable assertions, and (...) by means of random generation of test cases based on preconditions and postconditions. (shrink)
• Een voorbeeld van direct inzicht • Puzzelen met steentjes en programma’s • Functies en functioneel programmeren • Functies maken met lambda abstractie • Eigenschappen van dingen en karakteristieke functies • De ‘filter’ functie • Oneindige lijsten • Priemgetallen herkennen en genereren • Opdrachten..
This paper presents a short biography of Jan Patočka, as well as biographical data of the author in connection to the life and work of Jan Patočka. The paper describes Patočka’s academic activity at Charles University between 1968 and 1972, how he continued by giving private underground seminars in the dark years of 1972 to 1976, and how his engagement culminated in the dissident movement Charter 77. The author explains how the unofficial underground Patočka Archive was established on the very (...) day of Patočka’s death, even before the terrible events around his funeral. Before the official Patočka Archive was founded on the 1st of January, 1990, many volumes of his works were edited secretly during the period of 1977 to 1989. This made it possible to continue successfully publishing the series of the Complete Works of Jan Patočka after 1990. (shrink)
The aim of the present study is (1) to show, on the basis of a number of unpublished documents, how Heinrich Scholz supported his Warsaw colleague Jan ?ukasiewicz, the Polish logician, during World War II, and (2) to discuss the efforts he made in order to enable Jan ?ukasiewicz and his wife Regina to move from Warsaw to Münster under life-threatening circumstances. In the first section, we explain how Scholz provided financial help to ?ukasiewicz, and we also adduce evidence of (...) the risks incurred by German scholars who offered assistance to their Polish colleagues. In the second section, we discuss the dramatic circumstances surrounding the ?ukasiewiczes' move to Münster in the summer of 1944. (shrink)
Dynamic predicate logic (DPL), presented in [5] as a formalism for representing anaphoric linking in natural language, can be viewed as a fragment of a well known formalism for reasoning about imperative programming [6]. An interesting difference from other forms of dynamic logic is that the distinction between formulas and programs gets dropped: DPL formulas can be viewed as programs. In this paper we show that DPL is in fact the basis of a hierarchy of formulas-as-programs languages.
to a number of issues related to testing and specification. Brief review of first order logic. Use of first order logic for specification, in the specification tool Alloy.
Overview • Alloy peculiarity • Alloy utilities • Assignments and pre- and postconditions in Alloy • Alloy for automated logical reasoning • Alloy specifications of algorithms • On your to do list: – Look through the example code in these slides, – make sure you understand what is happening. Note: Alloy Peculiarity..
The tableau substitution rule in free variable tableau reasoning is destructive, for in general, T has consequences that T0 lacks. We show how this destructive feature can be eliminated in favour of a set-up that replaces tableau substitution with the generation and incremental merge of variable constraints on tableau branches. The approach diifers from other constraint based techniques in tableau reasoning in that we constrain tableau branches rather than clauses, and use disunification constraints rather than unification constraints. We prove soundness (...) and completeness, with the completeness proof based on a new way to generate models from open tableaux. (shrink)
Logics of communication should provide accounts of changes in the state of information of a group of discourse participants, on the basis of message exchanged within the group. We will give an overview of the way this is done in dynamic epistemic logic, focussing on a number of different types of informative actions with their epistemic effects, and presenting a number of new results. At the end of the talk we will indicate the relevance of this work for semantics and (...) pragmatics of natural language. (shrink)
• Intelligent Tasks: Finding the Next Term of a Sequence • Difference Analysis of Polynomial Sequences • Charles Babbage’s Difference Engine • Finding the Form of the Sequence. • Gaussian Elimination. • Example Application: the Pie Cutting Sequence • What has this to do with Intelligence? • What has it all to do with Consciousness (if anything)?
We implement the extension of the logical consequence relation to a partial order ≤ on arbitary types built from e (entities) and t (Booleans) that was given in [1], and the definition of monotonicity preserving and monotonicity reversing functions in terms of ≤. Next, we present a new algorithm for polarity marking, and implement this for a particular fragment of syntax. Finally, we list the reseach agenda that these definitions and this algorithm suggest. The implementations use Haskell [8], and are (...) given in ‘literate programming’ style [9]. (shrink)
Three key ways of updating one’s knowledge are (i) perception of states of affairs, (ii) reception of messages, (iii) drawing new conclusions from known facts. If one represents knowledge by means of Kripke models, the implicit assumption is that drawing conclusions is immediate. This assumption of logical omniscience is a useful abstraction. It leaves the distinction between (i) and (ii) to be accounted for. In current versions of Update Logic (Dynamic Epistemic Logic, Logic of Communication and Change) perception and message (...) reception are not distinguished. We will look at what is needed to distinguish them. (shrink)
Logical frameworks for analysing the dynamics of information processing abound [4, 5, 8, 10, 12, 14, 20, 22]. Some of these frameworks focus on the dynamics of the interpretation process, some on the dynamics of the process of drawing inferences, and some do both of these. Formalisms galore, so it is felt that some conceptual streamlining would pay off.This paper is part of a larger scale enterprise to pursue the obvious parallel between information processing and imperative programming. We demonstrate that (...) logical tools from theoretical computer science are relevant for the logic of information flow. More specifically, we show that the perspective of Hoare logic [13, 18] can fruitfully be applied to the conceptual simplification of information flow logics. (shrink)
This paper sketches an approach to pronoun reference resolution in context based on a dynamic incremental semantics for NL in polymorphic type theory. Our set-up provides full incrementality of processing, and can handle salience and pronoun resolution in context. An implementation of the system in Haskell, in ‘literate programming’ style, exists. The full literate source code can be found at http://www.cwi.nl/ jve/papers/02/rric.
This paper defines the grammar class of sequentially indexed grammars. Sequentially indexed grammars are the result of a change in the index stack handling mechanism of indexed grammars [Aho68, Aho69]. Sequentially indexed grammars are different from linear indexed grammars [Gaz88]. Like indexed languages, sequentially indexed languages are a fully abstract language class. Unlike indexed languages, sequentially indexed languages allow polynomial parsing algorithms. We give a polynomial algorithm for parsing with sequentially indexed gramamrs that is an extension of the Earley algorithm (...) for parsing with context free grammars. (shrink)
