| 1. A. V. FIGALLO, G. RAMON and S. SAAD, iH-Propositional Calculus | 157 [Abstract] [PDF] |
| 2. Tarek Sayed AHMED and Basim SAMIR, Neat Embeddings and Amalgamation | 163 [Abstract] [PDF] |
| 3. David Gracia GARCIA, An Example of a New Kind of Algebraizability | 173 [Abstract] [PDF] |
| 4. Norihiro KAMIDE, An Equivalence Between Sequent Calculi for Linear-Time Temporal Logic | 187 [Abstract] [PDF] |
| 5. Haroldo G. BENATTI and Ruy J.G.B. de QUEIROZ, On the Descriptive Complexity of the Two Disjoint Paths Problem Over Undirected Graphs | 195 [Abstract] [PDF] |
1. A. V. FIGALLO, G. RAMON and S. SAAD, iH-Propositional Calculus
Several authors have pointed out that the class of Nemitz's implicative semilattices are not the same as the
class of Hilbert algebras with the property that for each pair of elements there exists its infimum, which we
called Hilbert algebras with infimum. To the best of our knowledge, the first who realized this fact was Marsden
in 1972. In a previous paper we have shown that the class of Hilbert algebras with infimum is equational and
that the class of implicative semilattices is strictly contained in this variety. In this article, bearing in
mind the relationship between the implicative semilattices and the {->,&}-fragment of the intuitionistic
propositional calculus, we describe a Hilbert style {->,&}-propositional calculus weaker than the intuitionistic
fragment and we show that the algebraic models of this new calculus are Hilbert algebras with infimum.
2. Tarek Sayed AHMED and Basim SAMIR, Neat Embeddings and Amalgamation
We present a property of neat reducts commuting with forming subalgebras as a definability condition.
3. David Gracia GARCIA, An Example of a New Kind of Algebraizability
We study the algebraization of a
non-protoalgebraic logic defined by Dosen. This logic,
despite of being
non-protoalgebraic, has a theory which is
algebraizable in a similar sense than a logic is, according to
Blok
and Pigozzi's notion.
4. Norihiro KAMIDE, An Equivalence Between Sequent Calculi for Linear-Time Temporal Logic
The equivalence between Kawai's sequent calculus LTω and Baratella-Masini's 2-sequent calculus
2Sω is shown for the until-free linear-time temporal logic. By using this equivalence, an alternative proof of
the cut-elimination theorems for LTω and 2Sω is obtained.
5. Haroldo G. BENATTI and Ruy J.G.B. de QUEIROZ, On the Descriptive Complexity of the
Two Disjoint Paths Problem Over Undirected Graphs
We are concerned with the problem
of determining whether an undirected graph (V,E) with
distinguished vertices
s1, s2, t1, t2 has node-disjoint paths
from s1 to t1 and s2 to t2. We show that
it is
definable in least fixed point logic, meaning that it can be
answered in polynomial time the question whether
(G,s1,s2,t1,t2) is a yes instance of the problem by
iteratively evaluating a first-order formula on the graph
until a
fixed-point is reached.