The complexity of certain modal formulas on binary ramified subset trees

• Autorzy: Heinemann, B.
• Języki publikacji: EN

Abstrakty

EN

In the present note we determine the complexity of the satisfiability problem of a certain modal logic of subset spaces which was proposed in [6]. The corresponding semantics is defined w.r.t. binary ramified subset trees consisting of a set X and a distinguished set O of subsets of X such that the relation of reverse set inclusion makes O a binary ramified tree. It turns out that the satisfiability problem of the logic is complete in NP.

Słowa kluczowe

EN

modal logic of subset spaces; binary ramified subset trees; satisfiability problem; complexity

• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 39, Nr 3
• Strony: 259-272
• Opis fizyczny: bibliogr. 11 poz.

Twórcy

autor

Heinemann, B.

• Fachbereich Informatik, FernUniversität Hagen, D-58084 Hagen, Germany,