Rohit Parikh

TARK Conference 2005 Invited Paper

Logical omniscience and common knowledge: WHAT do we know and what do WE know?

• Rohit Parikh

Two difficult issues for the logic of knowledge have been logical omniscience and common knowledge. Our existing logics of knowledge based on Kripke structures seem to justify logical omniscience, but we know that in real life it does not exist. Also, common knowledge appears to be needed for certain real life procedures to work. But it seems quite implausible that it actually exists in real people. We suggest two procedure based semantics for knowledge which seem to take care of both these issues in a relatively realistic way. What this suggests is that if we really want to understand knowledge, then existing customs and plans must play a greater role than we are used to assigning them.

JELIA Conference 2004 Conference Paper

Knowledge-Theoretic Properties of Strategic Voting

• Samir Chopra
• Eric Pacuit
• Rohit Parikh

Abstract Results in social choice theory such as the Arrow and Gibbard-Satterthwaite theorems constrain the existence of rational collective decision making procedures in groups of agents. The Gibbard-Satterthwaite theorem says that no voting procedure is strategy-proof. That is, there will always be situations in which it is in a voter’s interest to misrepresent its true preferences i. e. , vote strategically. We present some properties of strategic voting and then examine – via a bimodal logic utilizing epistemic and strategizing modalities – the knowledge-theoretic properties of voting situations and note that unless the voter knows that it should vote strategically, and how, i. e. , knows what the other voters’ preferences are and which alternate preference P ′ it should use, the voter will not strategize. Our results suggest that opinion polls in election situations effectively serve as the first n –1 stages in an n stage election.

IJCAI Conference 1999 Conference Paper

An Inconsistency Tolerant Model for Belief Representation and Belief Revision

• Samir Chopra
• Rohit Parikh

TARK Conference 1992 Conference Paper

Topological Reasoning and The Logic of Knowledge

• Lawrence S. Moss
• Rohit Parikh

TARK Conference 1990 Conference Paper

Recent Issues in Reasoning about Knowledge

• Rohit Parikh

FOCS Conference 1983 Conference Paper

Propositional Game Logic

• Rohit Parikh

We define a propositional logic of games which lies in expressive power between the Propositional Dynamic Logic of Fischer and Ladner [FL] and the µ-calculus of Kozen [K]. We show that the logic is decidable and give a very simple, complete set of axioms, one of the rules being Brouwer's bar induction. Even though decidable, this logic is powerful enough to define well orderings. We state some other results, open questions and indicate directions for further research.

TCS Journal 1981 Journal Article

An elementary proof of the completeness of PDL

• Dexter Kozen
• Rohit Parikh

STOC Conference 1981 Conference Paper

Equations between Regular Terms and an Application to Process Logic

• Ashok K. Chandra
• Joseph Y. Halpern
• Albert R. Meyer
• Rohit Parikh

STOC Conference 1980 Conference Paper

Definability in Dynamic Logic

• Albert R. Meyer
• Rohit Parikh

FOCS Conference 1980 Conference Paper

Process Logic: Expressiveness, Decidability, Completeness

• David Harel
• Dexter Kozen
• Rohit Parikh

We define a process logic PL that subsumes Pratt's process logic, Parikh's SOAPL, Nishimura's process logic, and Pnueli's Temporal Logic in expressiveness. The language of PL is an extension of the language of Propositional Dynamic Logic (PDL). We give a deductive system for PL which includes the Segerberg axioms for PDL and prove that it is complete. We also show that PL is decidable.

FOCS Conference 1978 Conference Paper

A Decidability Result for a Second Order Process Logic

• Rohit Parikh

We prove the decidability of the validity problem for a rather general language for talking about computations. As corollaries of our result, we obtain some decidability results of Pratt, Constable, Fischer-Ladner, and Pnueli and also a new decidability result for deterministic propositional dynamic logic.

MFCS Conference 1978 Conference Paper

The Completeness of Propositional Dynamic Logic

• Rohit Parikh

Abstract Propositional modal logic of programs has been introduced by Fischer and Ladner [1], following ideas of Pratt [4]. We shall call it propositional dynamic logic (PDL) following the terminology of Harel, Meyer and Pratt. In the following we prove the completeness of a rather natural set of axioms for this logic and for an extension of it obtained by allowing the inverse operation which converts a program into its inverse. The following is a brief sketch of the plan of the proof. We introduce two auxiliary notions, that of pseudomodel and that of nonstandard model. Pseudomodels are highly syntactic objects and merely represent partial attempts to spell out a model. Thus an inconsistent formula may have a pseudomodel but every attempt to spell out the complete details of a model corresponding to the pseudomodel will, for an inconsistent formula, run into obstacles. A nonstandard model is like a model but we do not insist that R α* =(R α ). R α* is some reflexive transitive relation containing R α, but not necessarily the smallest. We shall show that if a formula A is not disprovable from the axioms then it has a series of consistent pseudomodels whose union is a nonstandard model satisfying certain special induction axioms. It is then shown how such a nonstandard model can be converted into a model in the usual sense.