Amílcar Sernadas (IT y Instituto Superior Técnico)

Parallel Composition of Logics

The practical significance of the problem of combining logics is widely recognized, namely in knowledge representation (within artificial intelligence) and in formal specification and verification of algorithms and protocols (within software engineering and information security). In these fields, the need for working with several calculi at the same time is the rule rather than the exception. The topic is also of interest on purely theoretical grounds. For instance, one might be tempted to look at predicate temporal logic as resulting from the combination of first-order logic and propositional temporal logic. However, the approach will be significant only if general preservation results are available about the combination mechanism at hand, namely preservation of completeness. For these reasons, different forms of combining logics have been studied and several such transference results have been reported in the literature. To name just a few, fusion (of modal logics), temporalization and fibring are now well understood, although some interesting open problems remain, namely concerning transference results. Fibring [1] is the most general form of combination and its recent graphic-theoretic account makes it applicable to a wide class of logics, including substructural and non truth-functional logics. Capitalizing on these latest developments in the theory of fibring [2] and inspired by parallel composition of processes, a novel form of combination of logics, subsuming fibring as a special case, is proposed together with conservativeness results [3,4]. Special attention is given to the parallel composition of calculi via a generalization of the notion of 2-category.

[1] D. Gabbay. Fibred semantics and the weaving of logics: part 1. Journal of Symbolic Logic, 61(4):1057–1120, 1996.

[2] A. Sernadas, C. Sernadas, J. Rasga, and M. Coniglio. On graph-theoretic fibring of logics. Journal of Logic and Computation, 19:1321--1357, 2009.

[3] A. Sernadas, C. Sernadas and J. Rasga. Parallel composition of logics - semantics. Submitted for publication.

[4] A. Sernadas, C. Sernadas and J. Rasga. Parallel composition of logic calculi. Submitted for publication.