Geodesic
Decidability of the interpolation problem and of related properties in tabular logics
Algebra i logika, Tome 48 (2009) no. 6, pp. 754-792.

Voir la notice de l'article provenant de la source Math-Net.Ru

Propositional modal and positive logics are considered as well as extensions of Johansson's minimal logic. It is proved that basic versions of the interpolation property and of the Beth definability property, and also the Hallden property, are decidable on the class of tabular logics, i.e., logics given by finitely many finite algebras. Algorithms are described for constructing counterexamples to each of the properties mentioned in handling cases where the logic under consideration does not possess the required property.
Keywords: decidability, tabular logics, interpolation property, Beth definability property, Hallden property. 
@article{AL_2009_48_6_a3,
     author = {L. L. Maksimova},
     title = {Decidability of the interpolation problem and of related properties in tabular logics},
     journal = {Algebra i logika},
     pages = {754--792},
     publisher = {mathdoc},
     volume = {48},
     number = {6},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2009_48_6_a3/}
}
TY  - JOUR
AU  - L. L. Maksimova
TI  - Decidability of the interpolation problem and of related properties in tabular logics
JO  - Algebra i logika
PY  - 2009
SP  - 754
EP  - 792
VL  - 48
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2009_48_6_a3/
LA  - ru
ID  - AL_2009_48_6_a3
ER  - 
%0 Journal Article
%A L. L. Maksimova
%T Decidability of the interpolation problem and of related properties in tabular logics
%J Algebra i logika
%D 2009
%P 754-792
%V 48
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2009_48_6_a3/
%G ru
%F AL_2009_48_6_a3
L. L. Maksimova. Decidability of the interpolation problem and of related properties in tabular logics. Algebra i logika, Tome 48 (2009) no. 6, pp. 754-792. http://geodesic.mathdoc.fr/item/AL_2009_48_6_a3/

[1] E. W. Beth, “On Padoa's method in the theory of definitions”, Indag. Math., 15:4 (1953), 330–339 | MR

[2] W. Craig, “Three uses of Herbrand–Gentzen theorem in relating model theory and proof theory”, J. Symb. Log., 22:3 (1957), 269–285 | DOI | MR | Zbl

[3] B. Jonsson, “Extensions of relational structures”, Theory of models, Proc. 1963 int. symp. Berkeley, North-Holland, Amsterdam, 1965, 146–157 | MR

[4] J. Barwise, S. Feferman (eds.), Model-theoretic logics, Perspect. Math. Log., Springer-Verlag, New York etc., 1985 | MR | Zbl

[5] D. M. Gabbay, L. Maksimova, Interpolation and definability. Modal and intuitionistic logics, Oxford Logic Guides, 46; Oxford Sci. Publ., Clarendon Press, Oxford, 2005 | MR | Zbl

[6] L. Maksimova, “Decidable properties of logical calculi and of varieties of algebras”, Logic Colloquium' 03, Lect. Notes Logic, 24, eds. V. Stoltenberg-Hansen, J. Vaananen, Assoc. Symb. Log., 2006, 146–166 | MR | Zbl

[7] L. L. Maksimova, “Teorema Kreiga v superintuitsionistskikh logikakh i amalgamiruemye mnogoobraziya psevdobulevykh algebr”, Algebra i logika, 16:6 (1977), 643–681 | MR | Zbl

[8] L. L. Maksimova, “Neyavnaya opredelimost i pozitivnye logiki”, Algebra i logika, 42:1 (2003), 65–93 | MR | Zbl

[9] L. L. Maksimova, “Definability and interpolation in non-classical logics”, Stud. Log., 82:2 (2006), 271–291 | DOI | MR | Zbl

[10] A. V. Chagrov, “Nerazreshimye svoistva rasshirenii logiki dokazuemosti”, Algebra i logika, 29:5 (1990), 350–367 | MR | Zbl

[11] A. Chagrov, M. Zakharyaschev, Modal logics, Oxford Logic Guides, 35, Clarendon Press, Oxford, 1997 | MR | Zbl

[12] A. I. Maltsev, Algebraicheskie sistemy, Nauka, M., 1970 | MR

[13] L. Maksimova, “Restricted interpolation in modal logics”, Advances in modal logic, 4, eds. Ph. Balbiani et al., King's College Publ., London, 2003, 297–311 | MR | Zbl

[14] S. Hallden, “On the semantic non-completeness of certain Lewis calculi”, J. Symb. Log., 16 (1951), 127–129 | DOI | MR | Zbl

[15] Y. Komori, “Logics without Craig's interpolation property”, Proc. Japan Acad. Ser. A, 54 (1978), 46–48 | DOI | MR | Zbl

[16] G. Kreisel, “Explicit definability in intuitionistic logic”, J. Symb. Log., 25 (1960), 389–390 | DOI

[17] L. Maksimova, “Interpolation and joint consistency”, We will show them! Essays in honour of Dov Gabbay, Vol. 2, eds. S. Artemov et al., King's College Publ., London, 2005, 293–305

[18] L. L. Maksimova, “Modalnye logiki i mnogoobraziya modalnykh algebr: svoistvo Beta, interpolyatsiya i amalgamiruemost”, Algebra i logika, 31:2 (1992), 145–166 | MR | Zbl

[19] L. L. Maksimova, “Analog teoremy Beta v normalnykh rasshireniyakh modalnoi logiki K4”, Sib. matem. zh., 33:6 (1992), 118–130 | MR | Zbl

[20] J. Czelakowski, “Logical matrices and the amalgamation property”, Stud. Log., 41:4 (1982), 329–341 | DOI | MR | Zbl

[21] L. Maksimova, “Intuitionistic logic and implicit definability”, Ann. Pure Appl. Logic, 105:1–3 (2000), 83–102 | DOI | MR | Zbl

[22] L. L. Maksimova, “Ogranichennaya interpolyatsiya i proektivnoe svoistvo Beta v ekvatsionalnoi logike”, Algebra i logika, 42:6 (2003), 712–726 | MR

[23] L. Henkin, J. D. Monk, A. Tarski, Cylindric Algebras, Part II, North-Holland, Amsterdam, 1985 | MR | Zbl

[24] L. L. Maksimova, “Proektivnye svoistva Beta v modalnykh i superintuitsionistskikh logikakh”, Algebra i logika, 38:3 (1999), 316–333 | MR | Zbl

[25] H. Ono, “Interpolation and the Robinson property for logics not closed under the Boolean operations”, Algebra Univers., 23:2 (1986), 111–122 | DOI | MR | Zbl

[26] J. Czelakowski, D. Pigozzi, “Amalgamation and interpolation in abstract algebraic logic”, Models, algebras and proofs, Sel. papers X Latin Am. symp. math. logic (Bogota, Colombia, June 24–29, 1995), Lect. Notes Pure Appl. Math., 203, eds. X. Caicedo et al., Marcel Dekker, New York, 1999, 187–265 | MR | Zbl

[27] I. Sain, “Beth's and Craig's properties via epimorphisms and amalgamation in algebraic logic”, Algebraic logic and universal algebra in computer science, Conf. (Ames, Iowa, USA, June 1–4, 1988), Lect. Notes Comput. Sci., 425, eds. C. H. Bergman et al., Springer-Verlag, Berlin, 1990, 209–226 | MR

[28] E. Hoogland, Definability and interpolation. Model-theoretic investigations, ILLC Diss. Ser., DS-2001-05, Amsterdam, 2001

[29] L. L. Maksimova, “Slabaya forma interpolyatsii v ekvatsionalnoi logike”, Algebra i logika, 47:1 (2008), 94–107 | MR | Zbl

[30] L. Maksimova, “On variable separation in modal and superintuitionistic logics”, Stud. Log., 55:1 (1995), 99–112 | DOI | MR | Zbl

[31] A. Wronski, “Remarks on Hallden-completeness of modal and intermediate logics”, Bull. Sect. Logic, 5:4 (1976), 126–129 | MR

[32] W. Rautenberg, Klassische und nichtklassische Aussagenlogik, Logik Grundlagen Mathematik, 22, Friedr. Vieweg Sohn, Braunschweig–Wiesbaden, 1979 | MR | Zbl

[33] W. Rautenberg, “Splitting lattices of logics”, Arch. Math. Logik Grundlagenforsch., 20 (1980), 155–159 | DOI | MR | Zbl

[34] B. Jonsson, “Algebras whose congruence lattices are distributive”, Mathem. Scand., 21 (1967), 110–121 | MR | Zbl

[35] L. L. Maksimova, “Interpolyatsiya i opredelimost v rasshireniyakh minimalnoi logiki”, Algebra i logika, 44:6 (2005), 726–750 | MR | Zbl

[36] V. A. Yankov, “O svyazi mezhdu vyvodimostyu v intuitsionistskom ischislenii vyskazyvanii i konechnymi implikativnymi strukturami”, Dokl. AN SSSR, 151:6 (1963), 1293–1294 | Zbl

[37] H. Ono, “Substructural logics and residuated lattices – an introduction”, Trends in logic. 50 years of Studia Logica, Trends Log. Stud. Log. Libr., 21, eds. V. F. Hendricks et al., Kluwer Academic Publ., Dordrecht, 2003, 193–228 | MR | Zbl

[38] L. Maksimova, “Interrelation of algebraic, semantical and logical properties for superintuitionistic and modal logics”, Logic, algebra, and computer science, Helena Rasiowa in memoriam, Banach Cent. Publ., 46, eds. D. Niwinski et al., Polish Acad. Sci., Inst. Math., Warszawa, 1999, 159–168 | MR | Zbl