On the Complexity of Prefix Formulas in Modal Logic of Subset Spaces

Heinemann, Bernhard GND

Most logics used in Computer Science have an intractable satisfiability (model-checking, derivability) problem. This restricts their general applicability severely. Only confining to smaller classes of admissible formulas can probably bring down the complexity bounds. In the present paper we follow this strategy for the subset space logic recently proposed by Moss and PARIKH [MP, DMP]. Forming nSAT as in sentential logic, but with prefix formulas instead of literals, we obtain nice generalizations of the following results well-known from the propositional case: nSAT ϵ P if n ≤ 2, and nSAT is NP-complete if n 2 ≥ 3.

Vorschau

Zitieren

Zitierform:

Heinemann, Bernhard: On the Complexity of Prefix Formulas in Modal Logic of Subset Spaces. Hagen 1996. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe