On the Influence of Confluence in Modal Logics

• Autorzy: Gasquet O.
• Języki publikacji: EN

Abstrakty

EN

In this paper we prove that adding a confluence axiom to a modal logic which behaves rather well from the viewpoint of complexity of the satisfaction problem, drastically increases its complexity and blows it up from PSPACE-completeness to NEXPTIME-completeness. More precisely, we investigate here both monomodal K + confluence and bimodal K with confluence between the two modalities.

Słowa kluczowe

EN

modal logic; tableaux; confluence; complexity; satisfaction problem; tiling problem; NEXPTIME-completeness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 70, nr 3
• Strony: 227--250
• Opis fizyczny: bibliogr. 8 poz.

Twórcy

autor

Gasquet O.

• Institut de Recherche en Informatique de Toulouse, Université Paul Sabatier, 118 Route de Narbonne, 31062 Toulouse CEDEX 4, France fr,

Bibliografia

• [Fariñas del Cerro and Gasquet 2002] L. Fariñas del Cerro, and O. Gasquet. A general framework for patterndriven modal tableaux Logic Journal of the IGPL, 10(1):51-84, 2002.
• [Fariñas del Cerro and Gasquet 1999] L. Fari"nas Del Cerro, O. Gasquet. Tableaux Based Decision Procedures for Modal Logics of Confluence and Density. Fundamenta Informaticae, 40(4):317-333, 1999.
• [Fariñas del Cerro Penttonen 1988] Luis Fariñas del Cerro, Martti Penttonen. Grammar Logics, Synth`ese et analyse, vol. 121-122, pp. 123-134, 1988.
• [Ladner 1977] R. Ladner. The computational complexity of provability in systems of modal logic. SIAM Journal on Computing, 6:467-480, 1977.
• [Marx 1999] M. Marx Complexity of Products of Modal Logics Journal of Logic and Computation,9(2), 221-238, 1999.
• [Marx, Mikulas 2001] M. Marx,S. Mikulas Products, or How to Create Modal Logics of High Complexity Logic Journal of the IGPL,9(1), 2001.
• [Sahlqvist 1975] H. Sahlqvist. Completeness and correspondence in the first and second order semantics for modal logics. In S.Kanger editor, Proc. 3rd Scandinavian Logic Symposium 1973, Studies in Logic 82 (1975), North-Holland, 1973
• [van Emde Boas 1997] P. van Emde Boas The convenience of tilings. In A. Sorbi (ed.), Complexity, Logic and Recursion Theory, volume 187 of Lecture Notes in Pure and Applied Mathematics, 331-363. Marcel Dekker Inc., 1997.