Creating and sharing knowledge for telecommunications

Decidability and complexity of fibred logics without shared connectives

Marcelino, S. ; Caleiro, C.

Logic Journal of the IGPL Vol. 24, Nº 5, pp. 673 - 707, June, 2016.

ISSN (print): 1368-9894
ISSN (online): 1367-0751

Scimago Journal Ranking: 0,43 (in 2016)

Digital Object Identifier: 10.1093/jigpal/jzw033

Fibring is a powerful mechanism for combining logics, and an essential tool for designing and understanding complex logical systems. Abstract results about the semantics and proof-theory of fibred logics have been extensively developed, including general preservation results for metalogical properties like soundness and (sufficient conditions for) completeness. Decidability, however, a key ingredient for the automated support of the fibred logic, has not deserved similar attention. In this article, we extend the preliminary results obtained in [ 29 ] regarding theoremhood, and address the problem of deciding the consequence relation of fibred logics, assuming that the logics do not share connectives. Namely, under this assumption, we provide a thorough characterization of the mixed patterns of reasoning that can occur in the fibred logic, and use it to obtain the first general decidability preservation result for fibring. The complexity of the decision procedure we obtain is also analysed.