On Graph-theoretic Fibring of Logics

July 7, 2009 in publications

A new paper from ConsRel members has been published:

On Graph-theoretic Fibring of Logics

Amilcar Sernadas, Cristina Sernadas and Joao Rasga

Department of Mathematics, Instituto Superior Técnico, TU Lisbon and SQIG, Instituto de Telecomunicações, Lisbon, Portugal.

Marcelo Coniglio

Department of Philosophy and CLE, State University of Campinas, Brazil.
E-mail: coniglio@cle.unicamp.br

Received 29 July 2008.

Abstract

A graph-theoretic account of fibring of logics is developed, capitalizing on the interleaving characteristics of fibring at the linguistic, semantic and proof levels. Fibring of two signatures is seen as a multi-graph (m-graph) where the nodes and the m-edges include the sorts and the constructors of the signatures at hand. Fibring of two models is a multi-graph (m-graph) where the nodes and the m-edges are the values and the operations in the models, respectively. Fibring of two deductive systems is an m-graph whose nodes are language expressions and the m-edges represent the inference rules of the two original systems. The sobriety of the approach is confirmed by proving that all the fibring notions are universal constructions. This graph-theoretic view is general enough to accommodate very different fibrings of propositional based logics encompassing logics with non-deterministic semantics, logics with an algebraic semantics, logics with partial semantics and substructural logics, among others. Soundness and weak completeness are proved to be preserved under very general conditions. Strong completeness is also shown to be preserved under tighter conditions. In this setting, the collapsing problem appearing in several combinations of logic systems can be avoided.

Keywords: Fibring; graph-theoretic techniques; preservation results; combination of logics; collapsing problem

Link: http://logcom.oxfordjournals.org/cgi/content/abstract/exp024v1?etoc

The bibtex entry for this publication is:

@article{Consrel_2009_Coniglio_b,
abstract = {A graph-theoretic account of fibring of logics is developed, capitalizing on the interleaving characteristics of fibring at the linguistic, semantic and proof levels. Fibring of two signatures is seen as a multi-graph (m-graph) where the nodes and the m-edges include the sorts and the constructors of the signatures at hand. Fibring of two models is a multi-graph (m-graph) where the nodes and the m-edges are the values and the operations in the models, respectively. Fibring of two deductive systems is an m-graph whose nodes are language expressions and the m-edges represent the inference rules of the two original systems. The sobriety of the approach is confirmed by proving that all the fibring notions are universal constructions. This graph-theoretic view is general enough to accommodate very different fibrings of propositional based logics encompassing logics with non-deterministic semantics, logics with an algebraic semantics, logics with partial semantics and substructural logics, among others. Soundness and weak completeness are proved to be preserved under very general conditions. Strong completeness is also shown to be preserved under tighter conditions. In this setting, the collapsing problem appearing in several combinations of logic systems can be avoided. 10.1093/logcom/exp024},
author = {Sernadas, Amilcar and Sernadas, Cristina and Rasga, Joao and Coniglio, Marcelo},
citeulike-article-id = {5086624},
citeulike-linkout-0 = {http://dx.doi.org/10.1093/logcom/exp024},
doi = {10.1093/logcom/exp024},
journal = {J Logic Computation},
month = {July},
pages = {exp024+},
posted-at = {2009-07-07 14:47:57},
priority = {2},
title = {On Graph-theoretic Fibring of Logics},
url = {http://dx.doi.org/10.1093/logcom/exp024},
year = {2009}
}