19TH INTERNATIONAL CONFERENCE ON LOGIC FOR PROGRAMMING, ARTIFICIAL INTELLIGENCE AND REASONING

ALCS ON SATURDAY, DECEMBER 14TH, 2013

08:30-09:30 Session 1
08:30
On the Algebraization of Non-finitary Logics
SPEAKER: James Raftery
ABSTRACT.

In this talk, we exhibit a non-finitary sentential logic that is algebraized by a quasivariety---in fact by a finitely based variety of finite type. The algebraization process requires infinitely many defining equations. The existence of such a logic settles questions posed by J. Czelakowski and by B. Herrmann.

09:00
On Deductive Systems Associated with Equationally Orderable Quasivarieties
SPEAKER: Ramon Jansana
ABSTRACT.

We discuss in general the logics of the order associated with quasivarieties of algebras with an equationally definable partial order and will present some examples related to BCK-alggebras and to Hilbert algebras.

09:30-10:00Coffee Break
10:00-12:00 Session 2B
10:00
The Quest for the Basic Fuzzy Logic
SPEAKER: Petr Cintula
ABSTRACT.

The quest for basic fuzzy logic was initiated by Petr Hajek when he proposed his basic fuzzy logic BL, complete with respect to the semantics given by all continuous t-norms. Later weaker systems, such as MTL, UL or psMTL^r, complete with respect to broader (but still meaningful for fuzzy logics) semantics, have been introduced and disputed the throne of the basic fuzzy logic. We contribute to the quest with our own proposal of a basic fuzzy logic. Indeed, we put forth a very weak logic called SLL, introduced and studied in earlier papers of the authors, and propose it as a base of a new framework which allows to work in a uniform way with both propositional and first-order fuzzy logics.

10:30
Short Communication: Complete MV-Algebra Valued Pavelka Logic
SPEAKER: Esko Turunen
ABSTRACT.

We prove that a Pavelka style fuzzy logic is semantically complete if, and only if the set of values of truth constitutes a complete MV-algebra. This is done by adding a new rule of inference and two axiom schema to Pavelka's original approach.

11:00
Co-Rotation, Co-Rotation-Annihilation, and Involutive Ordinal Sum Constructions of Residuated Semigroups
SPEAKER: Sándor Jenei
ABSTRACT.

Two co-rotation constructions and two co-rotation-annihilation constructions (in both cases a disjoint one and a connected one) will be introduced. In some sense these can be considered ’skew dual’ to the (disjoint and connected) rotation constructions. Just as the rotation(-annihilation) of FLe-algebras results in positive rank involutive FLe-algebras, the co-rotation(-annihilation) of FLe-algebras results in non-positive (zero or negative) rank involutive FLe-algebras; thus providing a wide spectrum of examples for the latter algebra. The fact that co-rotation and co-rotation-annihilation constructions are not simply dual of their rotation and rotation-annihilation counterparts is also reflected by the fact that the class of algebras which can be used in them are quite different. Also, a construction, called involutive ordinal sums will be introduced, and its use will be demonstrated in the structural description of a certain class of involutive FLe-algebras. This construction generalizes the generalized ordinal sums of [N. Galatos, Generalized Ordinals Sums and Translations, Logic Journal of the IGPL, 19 (3), (2011)] in the group-like case.

11:30
Discrete Dualities for n-potent MTL and BL-Algebras
ABSTRACT.

Discrete dualities are known for MTL-algebras; the corresponding relational systems consist of partially ordered sets with an additional ternary relation satisfying certain frame conditions. We extend this discrete duality to n-potent MTL-algebras. That is, we give the additional frame conditions needed to characterise the frames of such algebras. We also show how this approach may applied in the case of 2-potent BL-algebras.

12:00-14:00Lunch
14:00-15:30 Session 3D
14:00
Representations for Ramsey Relation Algebras
ABSTRACT.

A Ramsey Relation Algebra (RaRA), also called a Monk algebra or a Maddux algebra, is a certain finite relation algebra with n+1 atoms. Such an algebra is representable, if there exists an edge-colouring of a complete graph, satisfying the following two conditions. (1) There are no monochromatic triangles, (2) Every non-monochromatic triangle occurs everywhere it can.

The first condition is clearly a Ramsey type constraint; the second is a loose expression intended to mean the following: (a) each vertex has an outgoing edge of every colour, and (b) each edge is a base for every consistent (that is, non-monochromatic) triangle. The first requirement gives an upper bound for the size of the graph. The second gives a lower bound. It is not known whether the lower bound is smaller than the upper bound in general, that is, for an arbitrary number of colours. For two colours, there is precisely one colouring satisfying the requirements. For three colours, there are precisely three such colourings. It has been known for some time that appropriate colourings exist for 4 and 5 colours.

Using a construction based on finite fields, and some easy computations in GAP, we can show that appropriate colourings exist for up to 120 colours. Curiously, the construction does not work for 8 colours, has to be slightly tweaked to produce a colouring with 9 colours, and for 13 colours it is not known whether it works.

Unfortunately, we have no general theorem stating that for every n > 13 the construction will work, but it seems to be a reasonable conjecture.

14:30
An Isomorphism Criterion for Colimits of Sequences of Finitely Presented Objects
SPEAKER: Luca Spada
ABSTRACT.

We prove a general criterion reducing isomorphisms between colimits of sequences of finitely presented objects in a category to the notion of a confluence between their diagrams.

15:00
A Completeness Theorem for Two-Layer Modal Logics
ABSTRACT.

In this talk we provide a new general framework for two-layer modal fuzzy logics that encompasses known examples by Petr Hájek and others and paves the way for future development. We go far beyond the landscape of fuzzy logics by showing how one can construct a modal logic (for an arbitrary modality, not necessarily read as a probability) over an arbitrary non-classical logic (under certain technical requirements). Therefore, we need not assume that the starting logic is fuzzy, and we can develop a general theory of two-layer modal logics, showing how the methods used in the fuzzy literature can lead to completeness results using very few properties of the underlying logics. As a semantics, we propose particular kinds of measured Kripke Frames and prove corresponding completeness theorems.

15:30-16:00Coffee Break
16:00-17:00 Session 4B
16:00
Algorithmic-Algebraic Canonicity for Mu-Calculi
ABSTRACT.

The modal mu-calculus was defined by Kozen and is obtained by adding to the basic modal logic the least and greatest fixed point operators. The correspondence and completeness of logics with fixed point operators has been the subject of recent studies by Bezhanishvili and Hodkinson, and by Conradie et al. Both of these works aim to develop a Sahlqvist-like theory for their respective fixed point settings.

Sahlqvist theory consists of two parts: canonicity and correspondence. The Sahlqvist formulas are a recursively defined class of modal formulas with a particular syntactic shape. Any modal logic axiomatized by Sahlqvist formulas is strongly complete (via canonicity) with respect to its class of Kripke frames, and the latter is moreover guaranteed to be an elementary class. The work of Bezhanishvili and Hodkinson looks at both of these aspects, obtaining a syntactic class which allows for limited use of fixed point operators and for which a modified version of canonicity is proved. By contrast, Conradie et. al. look at only correspondence, and using an algorithmic approach obtains results for a much broader class of formulas. This algorithmic approach builds on work by Conradie and Palmigiano on canonicity and correspondence for distributive modal logic.

In the current work we prove that the members of a certain class of intuitionistic mu-formulas are canonical, in the sense of Bezhanishvili and Hodkinson; that is, they are preserved under certain modified canonical extensions. Our methods use a variation of the ALBA algorithm (Ackermann Lemma Based Algorithm). We show that all mu-inequalities that can be successfully processed by our algorithm, $\mu^*$-ALBA, are canonical.

16:30
Cut-free Calculi for Challenge Logics in a Lazy Way
ABSTRACT.

The development of cut-free calculi for expressive logics, e.g. quantified non-classical logics, is usually a non-trivial task. However, for a wide range of challenge logics there exists an elegant and uniform solution: By modeling and studying these logics as fragments of classical higher-order logic (HOL) --- a research direction I have recently proposed --- existing results for HOL can often be reused. We illustrate the idea with quantified conditional logics.