The Nondeterministic Information Logic NIL is PSPACE-complete

Article type: Research Article

Authors: Demri, Stéphane

Affiliations: Laboratoire LEIBNIZ-C.N.R.S., 46 Avenue Félix Viallet, 38031 Grenoble, France. email: [email protected]

Note: [] Address for correspondence: Laboratoire LEIBNIZ-C.N.R.S., 46 Avenue Félix Viallet, 38031 Grenoble, France

Abstract: The nondeterministic information logic NIL has been introduced by Orłowska and Pawlak in 1984 as a logic for reasoning about total information systems with the similarity, the forward inclusion and the backward inclusion relations. In 1987, Vakarelov provides the first first-order characterization of structures derived from information systems and this has been done with the semantical structures of NIL. Since then, various extensions of NIL have been introduced and many issues for information logics about decidability and Hilbert-style proof systems have been solved. However, computational complexity issues have been seldom attacked in the literature mainly because the information logics are propositional polymodal logics with interdependent modal connectives. We show that NIL satisfiability is a PSPACE-complete problem. PSPACE-hardness is shown to be an easy consequence of PSPACE-hardness of the well-known modal logic S4. The main difficulty is to show that NIL satisfiability is in PSPACE. To do so we present an original construction that extends various previous works by Ladner (1977), Halpern and Moses (1992) and Spaan (1993).

Keywords: information system, multimodal logic, computational complexity, Ladner-like algorithm

DOI: 10.3233/FI-2000-423401

Journal: Fundamenta Informaticae, vol. 42, no. 3-4, pp. 211-234, 2000