Lawrence Moss

This paper presents a logical system in which various group-level epistemic actions are incorporated into the object language. That is, we consider the standard modeling of knowledge among a set of agents by multi-modal Kripke structures. One might want to consider actions that take place, such as announcements to groups privately, announcements with suspicious outsiders, etc. In our system, such actions correspond to additional modalities in the object language. That is, we do not add machinery on top of models (as in Fagin et al., Reasoning about knowledge. MIT, Cambridge, 1995), but we reify aspects of the machinery in the logical language. Special cases of our logic have been considered in Plaza (Logics of public communications. In: Proceedings of the 4th international symposium on methodologies for intelligent systems, Charlotte, 1989), Gerbrandy (Dynamic epistemic logic. In: Moss LS, et al …

We construct logical languages which allow one to represent a variety of possible types of changes affecting the information states of agents in a multi-agent setting. We formalize these changes by defining a notion of epistemic program. The languages are two-sorted sets that contain not only sentences but also actions or programs. This is as in dynamic logic, and indeed our languages are not significantly more complicated than dynamic logics. But the semantics is more complicated. In general, the semantics of an epistemic program is what we call aprogram model. This is a Kripke model of ‘actions’,representing the agents' uncertainty about the current action in a similar way that Kripke models of ‘states’ are commonly used in epistemic logic to represent the agents' uncertainty about the current state of the system. Program models induce changes affecting agents' information, which we represent as …

We present a generalization of modal logic to logics which are interpreted on coalgebras of functors on sets. The leading idea is that infinitary modal logic contains characterizing formulas. That is, every model-world pair is characterized up to bisimulation by an infinitary formula. The point of our generalization is to understand this on a deeper level. We do this by studying a fragment of infinitary modal logic which contains the characterizing formulas and is closed under infinitary conjunction and an operation called Δ. This fragment generalizes to a wide range of coalgebraic logics. Each coalgebraic logic is determined by a functor on sets satisfying a few properties, and the formulas of each logic are interpreted on coalgebras of that functor. Among the logics obtained are the fragment of infinitary modal logic mentioned above as well as versions of natural logics associated with various classes of transition systems …

I was hooked; I spent several periods on hall monitor duty making up continued fractions and" solving" them. Eventually I stumbled on some problematic ones, which should have led me to the concept of limit, I suppose. But they at least led me to appreciate the notion when I learned of it a couple years later.And eventually, it led me to appreciate the construction of the reals as Cauchy sequences of rationals. But that was far down the road. I had a similar experience a few years ago, in reading a manuscript 2 by Peter Aczel on non-wellfounded 3 sets.

We present a bimodal logic suitable for formalizing reasoning about points and sets, and also states of the world and views about them. The most natural interpretation of the logic is in subset spaces, and we obtain complete axiomatizations for the sentences which hold in these interpretations. In addition, we axiomatize the validities of the smaller class of topological spaces in a system we call topologic. We also prove decidability for these two systems. Our results on topologic relate early work of McKinsey on topological interpretations of S4 with recent work of Georgatos on topologic.Some of the results of this paper were presented (Moss and Parikh, 1992) at the 1992 conference on Theoretical Aspects of Reasoning about Knowledge.

This paper pursues the model theoretic semantics of natural language determiners (quantifiers) exemplified in Barwise & Cooper (1981), van Benthem (1982, 1983a, 1983b), Keenan (1981), Keenan & Moss (1984), Keenan & Stavi (1981), Thijsse (1982, 1983), Westerståhl (1982), and Zwarts (1983). Like many of these works, ours owes a certain debt to the earlier work of Mostowski (1957) and Lindström (1966). Following most closely the notation of Keenan & Stavi (henceforth K&S) we treat one place determiner (det1’s) as expressions, such as every, John's, which combine with one common noun phrase (CNP), such as house, white house, to form a full noun phrase (NP): every house, John's white house. The purpose of this paper is twofold: First, we explore the semantic properties of k> 1 place determiners (detk's)–expressions which combine with k CNP's to form an NP. Second, we investigate the contribution to the expressive power of English of the various classes of dett's we distin-guish. The paper is organized in four sections: The first provides the linguistic motivation for studying k-place dets. The second presents several subclasses of such dets, concentrating on those we call “cardinal” and “logical”. It is these classes, together with the full class of “non-logical” dets, whose expressive power is investigated in sections 3 and 4. The latter notes several unsolved problems.

What are fields of mathematics, such as probability theory, point-set topology, and combinatorics,about? When asked this, a mathematician is likely to answer that the field is about various mathematical concepts, or about the consequences of some axioms or other. Although this answer would be adequate for many purposes, it misses a deeper answer that areas of mathematics can be seen as repositories for our intuitions about several aspects of ordinary life. For example, combinatories can be seen as just the mathematical home for intuitions about activities likecounting andarranging. General topology can be seen as the home for intuitions aboutcloseness.

<h3 class="gsh_h3">Publisher Summary</h3>This chapter focuses on the main themes and technical contributions of situation theory. Linguists were encouraged to provide semantic analyses that used whatever entities they needed, without worrying too much about the technical matter of the way such entities should be modeled. The linguistic project became to be known as “situation semantics” and the logical project was called “situation theory.” Situation theory was intended to stand to situation semantics as type. Situation theory stands to Montague grammar. In any foundational study, one has to decide whether to build models or theories. The strategies are distinct if not divergent, and the ideal of a canonical theory is rarely achieved. The chapter introduces the class of simple information structures. Structures in this class are intended to provide a naive model of the structure of information, as captured by the relational structures of first …

In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 Σ¹₁–complete. Two of these fragments do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 Σ⁰₁–complete. These results go via reduction to problems concerning domino systems.

This volume contains the Proceedings of the First Workshop on Coalgebraic Methods in Computer Science (CMCS '98). The Workshop was held in Lisbon, Portugal on March 28 and 29, 1998, as a satellite event to ETAPS '98.During the last decade, it has become increasingly clear that many state-based dynamical systems, such as transition systems, automata, and object-based systems, can be captured uniformly as coalgebras. Coalgebra is beginning to develop into a field of its own, with its own model theory and proof methods (involving bisimulations and invariants).The aim of this workshop is to bring together researchers with a common interest in the theory of coalgebra and its applications. We are very happy with both the number and the quality of the papers that were submitted, as well as with the fact that the Workshop has attracted many participants.The papers in this volume were reviewed by the …

This paper gives a treatment of substitution for “parametric” objects in final coalgebras, and also presents principles of definition by corecursion for such objects. The substitution results are coalgebraic versions of well-known consequences of initiality, and the work on corecursion is a general formulation which allows one to specify elements of final coalgebras using systems of equations. One source of our results is the theory of hypersets, and at the end of this paper we sketch a development of that theory which calls upon the general work of this paper to a very large extent and particular facts of elementary set theory to a much smaller extent.

The Aristotelian syllogistic cannot account for the validity of certain inferences involving relational facts. In this paper, we investigate the prospects for providing a relational syllogistic. We identify several fragments based on (a) whether negation is permitted on all nouns, including those in the subject of a sentence; and (b) whether the subject noun phrase may contain a relative clause. The logics we present are extensions of the classical syllogistic, and we pay special attention to the question of whether reductio ad absurdum is needed. Thus our main goal is to derive results on the existence (or nonexistence) of syllogistic proof systems for relational fragments. We also determine the computational complexity of all our fragments.

Epistemic logic investigates what agents know or believe about certain factual descriptions of the world, and about each other. It builds on a model of what information is (statically) available in a given system, and isolates general principles concerning knowledge and belief. The information in a system may well change as a result of various changes: events from the outside, observations by the agents, communication between the agents, etc. This requires information updates. These have been investigated in computer science via interpreted systems; in philosophy and in artificial intelligence their study leads to the area of belief revision. A more recent development is called dynamic epistemic logic. Dynamic epistemic logic is an extension of epistemic logic with dynamic modal operators for belief change (ie, information update). It is the focus of our contribution, but its relation to other ways to model dynamics will also be discussed in some detail.Situating the chapter This chapter works under the assumption that knowledge is a variety of true justifiable belief. The suggestion that knowledge is nothing but true justified belief is very old in philosophy, going back to Plato if not further. The picture is that we are faced with alternative “worlds”, including perhaps our own world but in addition other worlds. To know something is to observe that it is true of the worlds considered possible. Reasoners adjust their stock of possible worlds to respond to changes internal or external to them, to their reasoning or to facts coming from outside them. The identity of knowledge with true justified (or justifiable) belief has been known to be problematic in light of the …