1,721,086 research outputs found
Phase Semantics for Higher Order Completeness, Cut-Elimination and Normalization Proofs (Extended Abstract)
No full text) Mitsuhiro Okada Department of Philosophy Keio University, Tokyo Abstract We give a natural extension of Girard's phase semantics of the linear logic [1] to the classical and intuitionistic higher order linear logics and give a uniform phase-semantic proof of the higher order cut-elimination theorem as well as the completeness theorem. Although our proof in this paper is mainly concentrated on the framework of linear logic, the proof technique works for various different logical systems uniformly, too. We also extend our phase semantics for provability to phase semantics for proofs, by modifying the phase space of monoid domain to that of proofs domain, in a natural way. The resulting phase semantics for proofs provides various versions of proof-normalization theorem. The details of this extension will appear in the full-version of this paper. 1 Introduction Phase space semantics was introduced by Girard[1] for a completeness proof (with respect to provability) of linear logic. Alt..
An application of automated equational reasoning to many-valued logic
No full textIn this paper we present the theorem prover SBR3 for equational logic and itsapplication in the many-valued logic of Lukasiewicz. We give a new equational axiomatization of many-valued logic and we prove by SBR3 that it is equivalent to the classical equational presentation of such logic given by Wajsberg. We feel that our equational axiomatization of Wajsberg algebras is better suited for automated reasoning than the classical one. Indeed, it has allowed us to obtain a fast mechanical proof of the so called "fifth Lukasiewicz conjecture'', which is regarded as a challenge problem for theorem provers
Completion procedures as semidecision procedures
Full text linkIn this paper we give a new abstract framework for the study of Knuth-Bendix type completion procedures, which are regarded as semidecision procedures for theorem proving. First, we extend the classical proof ordering approach started by Bachmair-Dershowitz-Hsiang in such a way that proofs of different theorems can also be compared. This is necessary for the application of proof orderings to theorem proving derivations. We use proof orderings to uniformly define all the fundamental concepts in terms of proof reduction. A completion procedure is given by a set of inference rules and a search plan. The inference rules determine what can be derived from given data. The search plan chooses at each step of the derivation which inference rule to apply to which data. Each inference step either reduces the proof of a theorem or deletes a redundant sentence. Our definition of redundancy is based on the assumed proof ordering. We have shown in a related paper that our definition subsumes those given by Kounalis-Rusinowitch and Bachmair-Ganzinger. We prove that if the inference rules are refutationally complete and the search plan is fair, a completion procedure is a semidecision procedure for theorem proving. The key part of this result is the notion of fairness. Our definition of fairness is the first definition of fairness for completion procedures which addresses the theorem proving problem. It is new in three ways: it is target-oriented, that is it keeps the theorem to be proved into consideration, it is explicitly stated as a property of the search plan and it is defined in terms of proof reduction, so that expansion inferences and contraction inferences are treated uniformly. According to this definition of fairness, it is not necessary to consider all critical pairs in a derivation for the derivation to be fair. This is because not all critical pairs are necessary to prove a given theorem. Considering all critical pairs is an unnecessary source of inefficiency in a theorem proving derivation. We also show that the process of disproving inductive theorems by the so called inductionless induction method is a semidecision process. Finally, we present according to our framework, some equational completion procedures based on Unfailing Knuth-Bendix completion
Husserl and Hilbert on Completeness and Husserl's Term Rewrite-based Theory of Multiplicity (Invited Talk)
Full text linkHilbert and Husserl presented axiomatic arithmetic theories in different ways and proposed two different notions of 'completeness' for arithmetic, at the turning of the 20th Century (1900-1901). The former led to the completion axiom, the latter completion of rewriting. We look into the latter in comparison with the former. The key notion to understand the latter is the notion of definite multiplicity or manifold (Mannigfaltigkeit). We show that his notion of multiplicity is understood by means of term rewrite theory in a very coherent manner, and that his notion of 'definite' multiplicity is understood as the relational web (or tissue) structure, the core part of which is a 'convergent' term rewrite proof structure. We examine how Husserl introduced his term rewrite theory in 1901 in the context of a controversy with Hilbert on the notion of completeness, and in the context of solving the justification problem of the use of imaginaries in mathematics, which was an important issue in the foundations of mathematics in the period
Membership Equational Logic, Calculus of Inductive Constructions, and Rewrite Logic (Extended Abstract)
No full textAbstractMany of the above ideas arose when discussing with people of the afore mentionned groups (Coq, Demons, Maude, PROTHEO), and especially with Gilles Dowek and Christine Paulin. Mitsuhiro Okada also deserves special thanks for introducing me to the Curry-Howard world, while I was introducing him to its Hurry-Coward counterpart
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Semantics for "Enough-Certainty" and Fitting's Embedding of Classical Logic in S4
Full text linkIn this work we look at how Fitting's embedding of first-order classical logic into first-order S4 can help in reasoning when we are interested in satisfaction "in most cases", when first-order properties are allowed to fail in cases that are considered insignificant. We extend classical semantics by combining a Kripke-style model construction of "significant" events as possible worlds with the forcing-Fitting-style semantics construction by embedding classical logic into S4. We provide various examples. Our main running example is an application to symbolic security protocol verification with complexity-theoretic guarantees. In particular, we show how Fitting's embedding emerges entirely naturally when verifying trace properties in computer security
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
