iterations of REA operators, as well as extensions, generalizations and other applications are given in [6] while those for the ...

This is the first paper on constructive concurrent dynamic logic . For the first time, either for concurrent or sequential dynamic logic, we give a satisfactory treatment of what statements are forced to be true by partial information about the underlying computer. Dynamic logic was developed by Pratt [V. Pratt, Semantical considerations on Floyd–Hoare logic, in: 17th Annual IEEE Symp. on Found. Comp. Sci., New York, 1976, pp. 109–121, V. Pratt, Applications of modal logic to programming, Studia Logica 39 257–274] (...) for nondeterministic sequential programs, and by Peleg [D. Peleg, Concurrent dynamic logic, Journal of the Association for Computing Machinery 34 , D. Peleg, Communication in concurrent dynamic logic, Journal of Computer and System Sciences 35 ] for concurrent programs, for the purpose of proving properties of programs such as correctness. Here we define what it means for a dynamic logic formula to be forced to be true knowing only partial information about the results of assignments and tests. This informal CCDL semantics is formalized by intuitionistic Kripke frames modeling this partial information, and each such frame is interpreted as an idealized concurrent machine . In CCDL, proofs and deductions are ω-height, ω-branching, well-founded labeled subtrees of ωω. These are a generalization of the signed tableaux of Nerode [A. Nerode, Some lectures in modal logic, Technical Report, M.S.I. Cornell University, 1989, CIME Logic and Computer Science Montecatini Volume, Springer-Verlag Lecture Notes, 1990, A. Nerode, Some lectures in intuitionistic logic, Technical Report, M.S.I. Cornell University, 1988, Marktoberdorf Logic and Computation NATO Summer School Volume, NATO Science Series, 1990 ] stemming from the prefix tableaux of Fitting [M.C. Fitting, Proof Methods for Modal and Intuitionistic Logic, Reidel, 1983]. We demonstrate the correctness of our tableau proofs, define consistency properties, prove that consistency properties yield models, construct systematic tableaux, prove that systematic tableaux yield a consistency property, and conclude that CCDL is complete. This infinitary semantics and proof procedure will be the primary guide for defining, in a sequel, the correct finitary CCDL based on induction principles. FCCDL is suitable for implementation in constructive logic software systems such as Constable’s NUPRL or Huet-Coquand’s CONSTRUCTIONS. Our goal is to develop a constructive logic programming tool for specification and modular verification of programs in any imperative concurrent language, and for the extraction of concurrent programs from constructive proofs. Subsequent papers will introduce analogous logics for declarative and functional concurrent languages. (shrink)

In this paper we introduce effectiveness into model theory of intuitionistic logic. The main result shows that any computable theory T of intuitionistic predicate logic has a Kripke model with decidable forcing such that for any sentence φ, φ is forced in the model if and only if φ is intuitionistically deducible from T.

We initiate the study of computable model theory of modal logic, by proving effective completeness theorems for a variety of first-order modal logics. We formulate a natural definition of a decidable Kripke model, and show how to construct such a decidable Kripke model of a given decidable theory. Our construction is inspired by the effective Henkin construction for classical logic. The Henkin construction, however, depends in an essential way on the Deduction Theorem. In its usual form the Deduction Theorem fails (...) for modal logic. In our construction, the Deduction Theorem is replaced by a result about objects called finite Kripke diagrams. We argue that this result can be viewed as an analogue of the Deduction Theorem for modal logic. (shrink)

The content of existence theorems in the calculus of variations has been explored and an effective treatment of semi-continuity has been achieved. An algorithm has been developed which captures the natural algorithmic content of the notion of a semi-continuous function and this is used to obtain an effective version of the “chattering lemma” of control theory and ordinary differential equations. This lemma reveals the main computational content of the theory of relaxed optimal control.

In this paper, we study the lower semilattice of NP-subspaces of both the standard polynomial time representation and the tally polynomial time representation of a countably infinite dimensional vector space V∞ over a finite field F. We show that for both the standard and tally representation of V∞, there exists polynomial time subspaces U and W such that U + V is not recursive. We also study the NP analogues of simple and maximal subspaces. We show that the existence of (...) P-simple and NP-maximal subspaces is oracle dependent in both the tally and standard representations of V∞. This contrasts with the case of sets, where the existence of NP-simple sets is oracle dependent but NP-maximal sets do not exist. We also extend many results of Nerode and Remmel concerning the relationship of P bases and NP-subspaces in the tally representation of V∞ to the standard representation of V∞. (shrink)

John Newcombe Crossley is a man of many talents, fortunate to have lived an eventful life. He is a mathematician, a logician, a historian of ancient mathematics.

Query processing in ground definite deductive is known to correspond precisely to a linear programming problem. However, the “groundedness” requirement is a huge drawback to using linear programming techniques for logic program computations because the ground version of a logic program can be very large when compared to the original program. Furthermore, when we move from propositional logic programs to first-order logic programs, this effectively means that functions symbols may not occur in clauses. In this paper, we develop a theory (...) of “instantiate- by-need” that performs instantiations only when needed. We prove that this method is sound and complete when computing answer substitutions for non-ground logic programs including those containing function symbols. More importantly, when taken in conjunction with Colmerauer's result that unification can be viewed as linear programming, this means that resolution with unification can be completely replaced by linear programming as an operational paradigm. Additionally, our tree construction method is not rigidly tied to the linear programming paradigm-we will show that given any method M that can compute the set of atomic logical consequences of a propositional logic program, our method can use M to compute , the set of all atoms that are consequences of a first-order logic program. (shrink)

The First International Workshop brings together researchers from the theoretical ends of the logic programming and artificial intelligence communities to discuss their mutual interests. Logic programming deals with the use of models of mathematical logic as a way of programming computers, where theoretical AI deals with abstract issues in modeling and representing human knowledge and beliefs. One common ground is nonmonotonic reasoning, a family of logics that includes room for the kinds of variations that can be found in human reasoning. (...) Topics covered: Stable Semantics. Default Logic. AutoEpistemic Logic. Truth Maintenance Systems. Implementation Issues. Diagnosis. Applications. Inheritance Reasoning. Logics of Belief. Inconsistency and Non-Monotonicity. (shrink)

This is a review of Logic for Applications, by Anil Nerode and Richard A. Shore, published by Springer-Verlag in 1993.

In this paper I distinguish two ways of raising a sceptical problem of others' minds: via a problem concerning the possibility of error or via a problem concerning sources of knowledge. I give some reason to think that the second problem raises a more interesting problem in accounting for our knowledge of others’ minds and consider proposed solutions to the problem.

Phenomenal particularism is the view that particular external objects are sometimes part of the phenomenal character of perceptual experience. It is a central part of naïve realist or relational views of perception. We consider a series of recent objections to phenomenal particularism and argue that naïve realism has the resources to block them. In particular, we show that these objections rest on assumptions about the nature of phenomenal character that the naïve realist will reject, and that they ignore the full (...) resources that naïve realism has to offer in explaining phenomenal character. (shrink)

Papers presented in three conferences, supported by the Fritz Thyssen Foundation, the Excellence Cluster 16: 'Cultural Foundation of Integration' at the University of Konstanz, and the Institute of German Studies and the Forum Scientairum at the Univesity of Tubingen.

This book deals with the question of understanding religion and its relationship with politics in the context of developing countries. It reviews specific theories, such as modernisation theory, marxism, liberalism, hermeneutics and critical approach to explain questions related to religion and religious traditions. The book focuses on the recent attempts to theorise religion by Jurgen Habermas. It argues modernisation and orthodox Marxian theory are inadequate in understanding the recent spurt of religious phenomenon in politics. It discusses Hans-Georg Gadamer’s view to (...) show a way forward regarding dialectical hermeneutics in facilitating a dialogue between different traditions and religions. The book is of interest to students, scholars, practitioners of development, and all those who concern themselves with the questions of religion, tradition, modernity and secular well-being in developing countries such as India and beyond. (shrink)

What is the status of the claims which make up Kant’s arguments in the Critique of Pure Reason? This question seemed to Kant’s contemporaries to require a metacritique. Strawson’s criticisms of Kant should be understood in this context: as raising a metacritical challenge about Kant’s grounds for the claims which make up his arguments. What about the claims which make up Strawson’s own arguments in The Bounds of Sense? I argue in this chapter, against what I take to be the (...) general consensus, that Strawson did not and should not have understood these claims to be analytic. Rather he is somewhat puzzlingly committed to our possessing non-analytic but still a priori knowledge of his claims. What could such knowledge consist in? I’ll extract from G.E. Moore’s early writings on Kant a model for understanding such knowledge, one which enables us to better appreciate the way in which Strawson’s methodology dovetails with Kant’s own. (shrink)