{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:43:45Z","timestamp":1760244225842,"version":"build-2065373602"},"reference-count":35,"publisher":"MDPI AG","issue":"19","license":[{"start":{"date-parts":[[2022,9,23]],"date-time":"2022-09-23T00:00:00Z","timestamp":1663891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"FCT\/MCTES","award":["UIDB\/50008\/2020"],"award-info":[{"award-number":["UIDB\/50008\/2020"]}]},{"name":"EU","award":["UIDB\/50008\/2020"],"award-info":[{"award-number":["UIDB\/50008\/2020"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics"],"abstract":"<jats:p>Transfer theorems for combined logics provide essential tools and insight for reasoning about complex logical systems. In this paper, we present the first sufficient criterion (contextual extensibility) for decidability to be preserved through combination of propositional logics, and we study the complexity upper bounds induced by the method. In order to assess the scope and usability of our criterion, we illustrate its use in re-obtaining two standard important (though partial) results of the area: the preservation of decidability for disjoint combinations of logics, and the preservation of decidability for fusions of modal logics. Due to the very abstract nature and generality of the idea underlying contextual extensibility, we further explore its applicability beyond propositional logics. Namely, we explore the particular case of 2-deductive systems, and as a byproduct, we obtain the preservation of decidability for disjoint combinations of equational logics and discuss the relationship of this result and of our criterion with several related results with meaningful applications in satisfiability modulo theories.<\/jats:p>","DOI":"10.3390\/math10193481","type":"journal-article","created":{"date-parts":[[2022,9,26]],"date-time":"2022-09-26T01:41:58Z","timestamp":1664156518000},"page":"3481","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Decidability Preservation and Complexity Bounds for Combined Logics"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5587-6585","authenticated-orcid":false,"given":"Carlos","family":"Caleiro","sequence":"first","affiliation":[{"name":"Security and Quantum Information Group\u2014Instituto de Telecomunica\u00e7\u00f5es, Department Matem\u00e1tica\u2014Instituto Superior T\u00e9cnico, Universidade de Lisboa, 1049-001 Lisbon, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6941-7555","authenticated-orcid":false,"given":"S\u00e9rgio","family":"Marcelino","sequence":"additional","affiliation":[{"name":"Security and Quantum Information Group\u2014Instituto de Telecomunica\u00e7\u00f5es, Department Matem\u00e1tica\u2014Instituto Superior T\u00e9cnico, Universidade de Lisboa, 1049-001 Lisbon, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2022,9,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1057","DOI":"10.2307\/2275807","article-title":"Fibred Semantics and the Weaving of Logics Part 1: Modal and Intuitionistic Logics","volume":"61","author":"Gabbay","year":"1996","journal-title":"J. Symb. Log."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Gabbay, D. (1999). Fibring Logics. Oxford Logic Guides, Clarendon Press.","DOI":"10.1093\/oso\/9780198503811.001.0001"},{"key":"ref_3","unstructured":"Childers, T., and Majers, O. (1994, January 7\u201310). Universal logic. Proceedings of the VIII International Symposium, LOGICA\u201994, Liblice, Czechia."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1093\/jigpal\/jzp095","article-title":"The challenge of combining logics","volume":"19","year":"2011","journal-title":"Log. J. IGPL"},{"key":"ref_5","unstructured":"FroCoS (2022, May 31). The International Symposium on Frontiers of Combining Systems. Available online: http:\/\/frocos.cs.uiowa.edu."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/3-540-69778-0_15","article-title":"Fibring Semantic Tableaux","volume":"Volume 1397","year":"1998","journal-title":"Automated Reasoning with Analytic Tableaux and Related Methods"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/1-4020-3521-7_2","article-title":"Fibring of logics as a universal construction","volume":"Volume 13","author":"Gabbay","year":"2005","journal-title":"Handbook of Philosophical Logic"},{"key":"ref_8","unstructured":"Carnielli, W., Coniglio, M., Gabbay, D., Gouveia, P., and Sernadas, C. (2008). Analysis and Synthesis of Logics: How to Cut and Paste Reasoning Systems, Springer. Applied Logic."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1093\/logcom\/12.3.443","article-title":"Fibring Labelled Deduction Systems","volume":"12","author":"Rasga","year":"2002","journal-title":"J. Log. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1093\/logcom\/9.2.149","article-title":"Fibring of Logics as a Categorial Construction","volume":"9","author":"Sernadas","year":"1999","journal-title":"J. Log. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"414","DOI":"10.2307\/2694931","article-title":"Fibring: Completeness preservation","volume":"66","author":"Zanardo","year":"2001","journal-title":"J. Symb. Log."},{"key":"ref_12","unstructured":"Caleiro, C., and Marcelino, S. (2021). Modular semantics for combined many-valued logics, submitted."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Koslow, A., and Buchsbaum, A. (2015). Deciding theoremhood in fibred logics without shared connectives. The Road to Universal Logic\u2014Volume 2, Springer. Studies in Universal Logic.","DOI":"10.1007\/978-3-319-10193-4"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1093\/jigpal\/jzw033","article-title":"Decidability and complexity of fibred logics without shared connectives","volume":"24","author":"Marcelino","year":"2016","journal-title":"Log. J. IGPL"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1093\/logcom\/exq022","article-title":"Preservation by fibring of the finite model property","volume":"21","author":"Coniglio","year":"2011","journal-title":"J. Log. Comput."},{"key":"ref_16","first-page":"361","article-title":"Fusions of modal logics revisited","volume":"Volume 1","author":"Kracht","year":"1998","journal-title":"Advances in Modal Logic"},{"key":"ref_17","unstructured":"Gabbay, D., Kurucz, A., Wolter, F., and Zakharyaschev, M. (2003). Many-Dimensional Modal Logics: Theory and Applications, Elsevier. Studies in Logic and the Foundations of Mathematics."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"15","DOI":"10.4064\/cm-30-1-15-25","article-title":"The join of equational theories","volume":"30","author":"Pigozzi","year":"1974","journal-title":"Colloq. Math."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/357073.357079","article-title":"Simplification by Cooperating Decision Procedures","volume":"1","author":"Nelson","year":"1979","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2422.322411","article-title":"Deciding Combinations of Theories","volume":"31","author":"Shostak","year":"1984","journal-title":"J. ACM"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1413","DOI":"10.1016\/j.ic.2005.05.009","article-title":"A New Combination Procedure for the Word Problem That Generalizes Fusion Decidability Results in Modal Logics","volume":"204","author":"Baader","year":"2006","journal-title":"Inf. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/S0304-3975(01)00332-2","article-title":"Unions of Non-disjoint Theories and Combinations of Satisfiability Procedures","volume":"290","author":"Tinelli","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/11559306_3","article-title":"Combining Data Structures with Nonstably Infinite Theories Using Many-sorted Logic","volume":"Volume 3717","author":"Gramlich","year":"2005","journal-title":"Frontiers of Combining Systems"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10817-004-6241-5","article-title":"Model-Theoretic Methods in Combined Constraint Satisfiability","volume":"33","author":"Ghilardi","year":"2004","journal-title":"J. Autom. Reason."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10817-017-9411-y","article-title":"Many-sorted equivalence of shiny and strongly polite theories","volume":"60","author":"Casal","year":"2018","journal-title":"J. Autom. Reason."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10817-019-09512-4","article-title":"Politeness and Combination Methods for Theories with Bridging Functions","volume":"64","author":"Chocron","year":"2020","journal-title":"J. Autom. Reason."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Rasga, J., and Sernadas, C. (2020). Decidability of Logical Theories and Their Combination, Birkh\u00e4user.","DOI":"10.1007\/978-3-030-56554-1"},{"key":"ref_28","first-page":"2063","article-title":"On the characterization of fibred logics, with applications to conservativity and finite-valuedness","volume":"27","author":"Marcelino","year":"2016","journal-title":"J. Log. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"W\u00f3jcicki, R. (1988). Theory of Logical Calculi, Kluwer.","DOI":"10.1007\/978-94-015-6942-2"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF00370317","article-title":"Independent propositional modal logics","volume":"39","author":"Thomason","year":"1980","journal-title":"Stud. Log."},{"key":"ref_31","first-page":"111","article-title":"Algebraic semantics for universal Horn logic without equality","volume":"19","author":"Blok","year":"1992","journal-title":"Univers. Algebra Quasigroup Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/BF01195727","article-title":"On the structure of varieties with equationally definable principal congruences III","volume":"32","author":"Blok","year":"1994","journal-title":"Algebra Universalis"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Dixon, C., and Finger, M. (2017). Interpolation, Amalgamation and Combination (The Non-disjoint Signatures Case). Frontiers of Combining Systems (FroCoS 2017), Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-319-66167-4"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1016\/j.apal.2018.04.001","article-title":"Modularity results for interpolation, amalgamation and superamalgamation","volume":"169","author":"Ghilardi","year":"2018","journal-title":"Ann. Pure Appl. Log."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Ghilardi, S., and Gianola, A. (2022). Interpolation and Uniform Interpolation in Quantifier-Free Fragments of Combined First-Order Theories. Mathematics, 3.","DOI":"10.3390\/math10030461"}],"container-title":["Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2227-7390\/10\/19\/3481\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:38:21Z","timestamp":1760143101000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2227-7390\/10\/19\/3481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,23]]},"references-count":35,"journal-issue":{"issue":"19","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["math10193481"],"URL":"https:\/\/doi.org\/10.3390\/math10193481","relation":{},"ISSN":["2227-7390"],"issn-type":[{"type":"electronic","value":"2227-7390"}],"subject":[],"published":{"date-parts":[[2022,9,23]]}}}