A Tableau Based Decision Procedure for an Expressive Fragment of Hybrid Logic with Binders, Converse and Global Modalities

Autor: Serenella Cerrito, Marta Cialdea Mayer
Přispěvatelé: Informatique, Biologie Intégrative et Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE), Dipartimento di Informatica e Automazione, Università degli Studi Roma Tre, Cerrito, S, Cialdea, Marta, Università degli Studi Roma Tre = Roma Tre University (ROMA TRE)
Rok vydání: 2012
Předmět:
Zdroj: Journal of Automated Reasoning
Journal of Automated Reasoning, Springer Verlag, 2013, 51 (2), pp.197--239. ⟨10.1007/s10817-012-9257-2⟩
Journal of Automated Reasoning, 2013, 51 (2), pp.197--239. ⟨10.1007/s10817-012-9257-2⟩
ISSN: 1573-0670
0168-7433
DOI: 10.1007/s10817-012-9257-2
Popis: International audience; In this paper we provide the first (as far as we know) direct calculus deciding satisfiability of formulae in negation normal form in the fragment of FHL (full hybrid logic with the binder, including the global and converse modalities), where no occurrence of a universal operator is in the scope of a binder. By means of a satisfiability preserving translation of formulae, the calculus can be turned into a satisfiability decision procedure for the fragment \textsf{FHL}\setminus\Box \mathord\downarrow\Box, i.e. formulae in negation normal form where no occurrence of the binder is both in the scope of and contains in its scope a universal operator. The calculus is based on tableaux and termination is achieved by means of a form of anywhere blocking with indirect blocking. Direct blocking is a relation between nodes in a tableau branch, holding whenever the respective labels (formulae) are equal up to (a proper form of) nominal renaming. Indirect blocking is based on a partial order on the nodes of a tableau branch, which arranges them into a tree-like structure.
Databáze: OpenAIRE