Search

Theorem proving is one of the most widely used approaches to the verification of computer systems, and its theoretical basis is generally a proof system for formal derivation of logic formulas. In this paper, we propose a sound and complete proof system for Propositional Projection Temporal Logic (PPTL) with indexed expressions, which is a unified temporal logic that subsumes the well used Linear Temporal Logic (LTL). First, the syntax, semantics and logic laws of PPTL that allows indexed expressions are introduced, and the representation of LTL constructs by PPTL formulas is illustrated. Then, the proof system for the logic is presented which consists of axioms and inference rules for the derivation of both basic constructs and indexed expressions. To show the capability of the proof system, several examples of formal proofs are provided. Finally, the soundness and completeness of the proof system are demonstrated. [ABSTRACT FROM AUTHOR]

To specify and verify the concurrent and reactive systems with the theorem proving approach, a complete axiomatization is formalized for first order projection temporal logic (PTL) with both finite and infinite time. To this end, PTL is restricted to a finite domain, and the syntax, semantics as well as the axiomatization of PTL are presented. Further, the techniques of labeled normal form and labeled normal form graph of PTL formulas are introduced respectively, with which a decision procedure for quantifier free PTL (QFPTL) formulas is given. Moreover, a generalized labeled normal form graph is defined and employed to transform a quantified PTL formula into its equivalent QFPTL formula. Finally, a decision procedure for PTL is formalized and the completeness of the axiomatic system is proved based on the decidability of PTL formulas. [ABSTRACT FROM AUTHOR]

Abstract: The aim of this paper is to obtain a theoretical foundation of inconsistency-tolerant (or paraconsistent) reasoning by presenting a comprehensive study of the structural proof-theory of David Nelson’s paraconsistent logic. Inconsistency handling has a growing importance in Computer Science since inconsistencies may frequently occur in knowledge-based and intelligent information systems. Paraconsistent, inconsistency-tolerant logics have been studied to cope with such inconsistencies. In this paper, proof systems for Nelson’s paraconsistent logic N4 are comprehensively studied. The logic N4 is a fundamental system and known to be a common basis for various extended and useful paraconsistent logics. Some basic theorems including cut-elimination, normalization and completeness are uniformly proved using various embedding theorems. A variety of sequent calculi and natural deduction systems for N4 and some closely related systems are presented and compared. [Copyright &y& Elsevier]

Abstract: We solve the Angel Problem, by describing a strategy that guarantees the win of an Angel of power 2 or greater. Basically, the Angel should move north as quickly as possible. However, he should detour around eaten squares, as long as the extra distance does not exceed twice the number of eaten squares evaded. We show that an Angel following this strategy will always spot a trap early enough to avoid it. [Copyright &y& Elsevier]

Abstract: For a propositional proof system we introduce the complexity class of all disjoint -pairs for which the disjointness of the pair is efficiently provable in the proof system . We exhibit structural properties of proof systems which make canonical -pairs associated with these proof systems hard or complete for . Moreover, we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for and the reductions between the canonical pairs exist. [Copyright &y& Elsevier]

Abstract: Context-aware computing refers to a paradigm in which applications sense aspects of the environment and use this information to adjust their behavior in response to changing circumstances. In this paper, we present a formal model and notation (Context UNITY) for expressing quintessential aspects of context-aware computations; existential quantification, for instance, proves to be highly effective in capturing the notion of discovery in open systems. Furthermore, Context UNITY treats context in a manner that is relative to the specific needs of an individual application and promotes an approach to context maintenance that is transparent to the application. In this paper, we construct the model from first principles, introduce its proof logic, and demonstrate how the model can be used as an effective abstraction tool for context-aware applications and middleware. [Copyright &y& Elsevier]

Abstract: An infinitary proof theory is developed for modal logics whose models are coalgebras of polynomial functors on the category of sets. The canonical model method from modal logic is adapted to construct a final coalgebra for any polynomial functor. The states of this final coalgebra are certain “maximal” sets of formulas that have natural syntactic closure properties. The syntax of these logics extends that of previously developed modal languages for polynomial coalgebras by adding formulas that express the “termination” of certain functions induced by transition paths. A completeness theorem is proven for the logic of functors which have the Lindenbaum property that every consistent set of formulas has a maximal extension. This property is shown to hold if the deducibility relation is generated by countably many inference rules. A counter-example to completeness is also given. This is a polynomial functor that is not Lindenbaum: it has an uncountable set of formulas that is deductively consistent but has no maximal extension and is unsatisfiable, even though all of its countable subsets are satisfiable. [Copyright &y& Elsevier]

An arithmetical system is presented with the property that from every proof a realizing term can be extracted that is definable in a certain affine linear typed variant of Gödel''s T and therefore defines a non-size-increasing polynomial time computable function. [Copyright &y& Elsevier]

It is well known that one can build models of full higher-order dependent-type theory (also called the calculus of constructions) using partial equivalence relations (PERs) and assemblies over a partial combinatory algebra. But the idea of categories of PERs and ERs (total equivalence relations) can be applied to other structures as well. In particular, we can easily define the category of ERs and equivalence-preserving continuous mappings over the standard category Top0 of topological T0-spaces; we call these spaces (a topological space together with an ER) equilogical spaces and the resulting category Equ. We show that this category—in contradistinction to Top0—is a cartesian closed category. The direct proof outlined here uses the equivalence of the category Equ to the category PEqu of PERs over algebraic lattices (a full subcategory of Top0 that is well known to be cartesian closed from domain theory). In another paper with Carboni and Rosolini (cited herein), a more abstract categorical generalization shows why many such categories are cartesian closed. The category Equ obviously contains Top0 as a full subcategory, and it naturally contains many other well known subcategories. In particular, we show why, as a consequence of work of Ershov, Berger, and others, the Kleene–Kreisel hierarchy of countable functionals of finite types can be naturally constructed in Equ from the natural numbers object N by repeated use in Equ of exponentiation and binary products. We also develop for Equ notions of modest sets (a category equivalent to Equ) and assemblies to explain why a model of dependent type theory is obtained. We make some comparisons of this model to other, known models. [Copyright &y& Elsevier]