1. "Communication, Consensus and Knowledge," (with P. Krasucki), J.
Economic Theory 52 (1990), pp. 178-189.
A connection between knowledge as studied in mathematical
economics and in distributed computing.
2. "Levels of knowledge in distributed computing," (with P. Krasucki),
Sadhana - Proc. Ind. Acad. Sci. 17 (1992), pp. 167-191.
We show a correspondence between levels of knowledge,
with common knowledge being the highest level, and certain regular languages.
3. "Probabilistic Knowledge and Probabilistic Common Knowledge," (with
Paul Krasucki and Gilbert Ndjatou), ISMIS 90, North Holland (1990),
pp. 1-8.
We show how to answer questions like "How much
does A know about B's knowledge of C?", in a manner which naturally generalises
Shannon's definition. In particular we show how there can be probabilistic
common knowledge in a group even when there is no common knowledge in
the usual sense.
4. "Finite and Infinite Dialogues", in the Proceedings of a Workshop
on Logic from Computer Science, Ed. Moschovakis, MSRI publications,
Springer 1991, pp. 481-498.
There are various puzzles current in the literature,
the muddy children puzzle for instance, which nicely bring out the structure
of common knowledge and the role it plays in communication. We consider
variants and extensions of this puzzle including some where a conversation
may go on through the transfinite ordinals before terminating and a game
theoretic version where one may speak even when one is not sure but can
be penalized for an incorrect answer.
5. "Monotonic and Non-monotonic Logics of Knowledge", in Fundamenta
Informatica special issue, Logics for Artificial Intelligence vol XV
(1991), pp. 255-274.
Shows how to interpret a non-monotonic rule of
McCarthy and obtains completeness and decidability results. The intuition
is that if some A is all that someone knows, then we can reason non-monotonically
about that person's state of knowledge. The Mr. Sum and Mr. Product puzzle
can be understood in such a framework. An earlier version of this paper
appeared in FST-TCS, (1984)
6. "A Test for Fuzzy Logic", SIGACT NEWS, 22, 3, Summer 1991,
pp. 49-50.
Examines the question of whether Fuzzy logic can
provide an adequate semantics for our linguistic practices. It is argued
that Zadeh's fuzzy values do not have a basis on reality, even though
they do seem to capture some intuition. Some experimental results are
reported.
7. "A Logical Study of Distributed Transition Systems," with Lodaya,
Ramanujam and Thiagarajan. Information and Computation 119, May
1995, pp. 91-119.
A study of a variety of logics for reasoning about
concurrency.
8. "Notes of Rohit Parikh's lectures on Reasoning about Knowledge,"
by Anna Maria Zanaboni. (The lectures were given in Acireale at an International
School for Computer Scientists) published in Italy, summer 1993. (Cassa
di Risparmio di Padova e Rovigo)
9. "Vagueness and Utility: the Semantics of Common Nouns," in Linguistics
and Philosophy 17 (1994), pp. 521-35.
We point out that to date there do not exist satisfactory
logics or semantics for vague predicates. We show that these predicates
are person dependent, i.e. the way they are applied varies from person
to person and also from occasion to occasion. Hence a theory is needed
of why they are useful in communication and do not lead to difficulties.
We show how there are settings where despite some differences in application
by the various individuals involved, communication is useful. These are
the (robust) settings in which we do in fact use these predicates, avoiding
them in other areas where such sturdiness does not obtain.
10. "Logical omniscience," in Logic and Computational Complexity,
Ed. Leivant, Springer Lecture Notes in Computer Science no. 960,
(1995) 22-29.
PDF format
Current logics of knowledge have the property
that under their definition of what it means for $i$ to know some formula
A, $i$ knows all valid formulas and also the consequences of anything
that $i$ knows. This is implausible and to find more plausible definitions
of knowledge is the problem of logical omniscience. We make some algorithim
based suggestions. An earlier version of this paper appeared in ISMIS
1987, ed. Z. Ras, pp. 432-439.
12. "Language as social software" (abstract) International Congress
on Logic, Methodology and Philosophy of Science (1995), page 417.
Full version to appear in Future Pasts, Ed. Floyd and Shieh, Oxford
U. Press, 2000.
PDF format
One can view language as playing the role of a
system of signals to facilitate social behaviour. It turns out that this
view is very flexible and can explain various philosophical puzzles like
Searle's Chinese room puzzle or Quine's indetermincy of translation thesis.
13. "Knowledge based computation" (Extended abstract), in Proceedings
of AMAST-95, Montreal, July 1995, Edited by Alagar and Nivat, LNCS
no. 936, pp. 127-42.
A short survey of work in this area done to date.
14. "Topological Reasoning and The Logic of Knowledge" (with Dabrowski
and Moss), Annals of Pure and Applied Logic 78 (1996), pp. 73-110.
It was noticed long ago by Goedel and Tarski that
topological spaces can be used to analyse modal notions. We carry the
ball in the opposite direction and show that many topological notions
have a strong modal-theoretical and knowledge-theoretic character and
that a modal intuition underlies some of our reasoning about topology.
While it is true that one's knowledge depends on one's evidence, traditional
definitions of knowledge leave out the fact that one can gather or improve
one's knowledge. E.g. a measurement of some quantity can be made more
accurate by using better instruments. This observation allows us to develop
a logic with two modalities, one for knowledge and the other for effort.
Some topological notions like closed or {\em perfect can be defined in
this logic. We provide axiomatizations and prove completeness results.
15. "How far can we formalize language games?" in The Foundational
Debate, edited by DePauli-Scimanovich, Koehler and Stadler, Kluwer
Academic (1995) pp. 89-100.
Wittgenstein's views in the Philosophy of Mathematics
are examined and shown to be very modern in spirit. We raise the question
how far one can provide formal versions of language games as a way of
making certain problems more explicit.
16. "Vague predicates and language games," Theoria Spain, vol XI,
no. 27, Sep 1996, pp. 97-107. Further research along the lines of
#9, above.
17. "Belief revision and language splitting" in Proc. Logic, Language
and Computation, Ed. Moss, Ginzburg and de Rijke, CSLI 1999, pp. 266-278
(earlier version appeared in 1996 in the preliminary proceedings).
The celebrated AGM axioms for belief revision
allow the trivial revision under which all old information is lost. We
show how we can incorporate a formal notion of relevance which allows
one's information to be split uniquely into a number of disjoint subject
areas. Revising information only in those areas where new information
is received blocks the trivial revision.
18. "Length and structure of proofs," in Synthese 114, (1998),
special issue edited by J. Hintikka.
A survey of work in the theory of proofs, beginning
with our own work in the late sixties and early seventies and giving an
account of subsequent results to date.
19. "Frege's puzzle and belief revision," typescript, November 1997.
Presented at the World Congress of Philosophy, Boston 1998.
Ever since Frege there have been, largely unsuccessful,
attempts to work out a notion of sense or meaning which will allow us
to explain the cognitive contribution made by a sentence and also explain
how its truth value is determined. Various puzzles, Frege's Hesperus-Phosphorus
puzzle, Kripke's Pierre puzzle, Burge's arthritis puzzle, etc show up
the difficulty of the problem. We show how an approach based on the notion
of belief revision can address these various issues.
20. "Propositions, propositional attitudes and belief revision" to appear
in Advances in Modal Logic, Volume 2, K. Segerberg, M. Zakharyaschev,
M. de Rijke, H. Wansing, editors, CSLI Publications, 2000.
PDF format
This is a revised and expanded version of #19
above
21. "The Santa Fe bar problem revisited" (with Amy Greenwald and Bud
Mishra), presented at the Stony Brook workshop on Game Theory, summer
1998.
The Santa Fe bar problem is a problem about a
bar in Santa Fe New Mexico. The capacity of the bar is less than the number
of people who want to go there but even people who do want to go, would
not like to if it is crowded. This creates a game theoretic problem where
it is impossible for the prospective customers to have a uniform strategy
which can succeed. If everyone thinks that the bar will be crowded, then
they will not go and the bar will be empty. If everyone thinks that the
bar will be uncrowded, then they will go and the bar will in fact be crowded.
Thus a uniform learning algorithm is not possible. We point out a similarity
to the Russell paradox and investigate what kind of learning is possible.
22. "Sock Sorting," (with
Laxmi Parida and Vaughan Pratt), appeared in a volume dedicated
to Johan van Benthem electronically published by the University of Amsterdam.
If a person puts n pairs of socks in the washing
machine and then the dryer, then when the wash is completed, what he has
is 2*n individual socks. Socks which are near enough in color will seem
to match, but this matching relation is not transitive. This results in
the situation that naive matching can leave socks un-matched. So how can
one match socks? One way is to try all possible matchings, and the problem
looks on the face of it as if it can be NP-complete. But we show that
there is a quadratic algorithm.
23. "An Inconsistency Tolerant Model for Belief Representation
and Belief Revision," (with Samir Chopra), appeared in Proc. IJCAI
99.
We define the notion of a B-structure which consists
of a number of theories with overlapping languages glued together. Such
a structure allows us to localize an agent's beliefs as well as represent
a situation where an agent's beliefs are globally incosistent but locally
consistent. This model provides for both query answering and belief revision.
Axioms analogous to those of AGM are satisfied.
24. "Non-Monotonic Inference on Sequenced Belief Bases", (with
Samir Chopra and Konstantinos Georgatos), Proceedings of the Delphi
Conference in Logic, July 1999.
We consider the approach to belief representation
and belief revision where revision is taken to be the trivial operation
of concatenation of new information. The logical sophistication will then
be in the operation for answering queries. This is done using a maxi-consistent
subset of previously received information, which gives priority to more
recently received information as well as to more relevant information.
25."Two place probabilities, beliefs and belief revision: on the foundations
of iterative belief kinematics", (with Horacio Arlo Costa), in Amsterdam
Colloquium '99.
We extend some results of van Fraassen on two
dimensional probabilities, sometimes called Popper functions. The idea
is that $P(X,Y)$ gives the probability of $X$ relative to $Y$ and this
notion can make sense even if the probability of $Y$ itself is 0. Van
Fraassen defined a family of cores which represent various {\em Maginot
lines for beliefs. I.e. they represent positions to which we fall back
when some very surprising information is received. We give a complete
characterization of the notion of cores for the case where the whole space
is countable.
|