BULLETIN OF THE SECTION OF LOGIC

34/2, 2005

TABLE OF CONTENTS


1. Haroldo G. BENATTI and Ruy J. G. B. de QUEIROZ, Descriptive Complexity of Modularity Problems on Graphs 61-76   [Abstract]   [PDF]
2. Juliana BUENO-SOLER and Walter CARNIELLI, Possible-translations Algebraization for Paraconsistent Logics 77-92   [Abstract]   [PDF]
3. V. V. RIMATSKI and V. V. RYBAKOV, A Note on Globally Admissible Inference Rules for Modal and Superintuitionistic Logics 93-100   [Abstract]   [PDF]
4. Gemma ROBLES and Jose M. MENDEZ, Relational Ternary Semantics for a Logic Equivalent to Involutive Mondial t-norm Based Logic IMTL 101-116   [Abstract]   [PDF]

ABSTRACTS

1. Haroldo G. BENATTI and Ruy J. G. B. de QUEIROZ, Descriptive Complexity of Modularity Problems on Graphs The infinitary logic Lω extends first order logic by allowing infinitary conjunctions and disjunctions and requiring that the formulas must have only a finite number of variables. Here we study the expressive power of !Lω which is the existential negation-free fragment of Lω. One of the important features of Lω and !Lω is that their expressive power can be characterized by semantic games. We use pebble games for Lω to prove some problems about the modularity of the length of paths and circuits in directed graphs and in bipartite directed graphs are not definable in this logic. For that we show that those problems over bipartite directed graphs are NP-complete.
Rather than seeking to classify classes of problems by the syntactical complexity of their description in some logical formalism, here we have worked in the other direction: we have shown lower bounds for the descriptive complexity of specific problems. This hints at a research programme which might be called ``concrete'' descriptive complexity, which may be useful in case studies of expressiveness of specific query languages, given that it may suggest a reverse process.

2. Juliana BUENO-SOLER and Walter CARNIELLI, Possible-translations Algebraization for Paraconsistent Logics This note proposes a new notion of algebraizability, which we call possible-translations algebraic semantics, based upon the newly developed possible-translations semantics. This semantics is naturally adequate to obtain an algebraic interpretation for paraconsistent logics, and generalizes the well-known method of algebraization by W. Blok and D. Pigozzi. This generalization obtains algebraic semantics up to translations, applicable to several non-classical logics and particularly apt for paraconsistent logics, a philosophically relevant class of logics with growing importance for applications.

3. V. V. RIMATSKI and V. V. RYBAKOV, A Note on Globally Admissible Inference Rules for Modal and Superintuitionistic Logics In this shot note we consider globally admissible inference rules. A rule r is globally admissible in a logic L if r is admissible in all logics with the finite model property which extend L. Here we prove a reduction theorem: we show that, for any modal logic L extending K4, a rule r is globally admissible in L iff r is admissible in all tabular logics extending L. The similar result holds for superintuitionistic logics.

4. Gemma ROBLES and Jose M. MENDEZ, Relational Ternary Semantics for a Logic Equivalent to Involutive Mondial t-norm Based Logic IMTL We define the logic ICI complete with respect to certain ternary relational structures. ICI is a particular negation extension of Urquhart's many-valued logic C. The logic ICI is deductively equivalent to Esteva and Godo's Involutive Monoidal t-norm based logic IMTL.

BULLETIN OF THE SECTION OF LOGIC