Affordable Access

Publisher Website

On the Complexity of RSRL

Elsevier B.V.
Publication Date
DOI: 10.1016/s1571-0661(05)82580-0
  • Design
  • Linguistics
  • Mathematics


Abstract In this paper we present a computability and a complexity result on Relational Speciate Reentrant Logic (RSRL). RSRL is a description logic designed to formalise the linguistic framework and theory Head-Driven Phrase Structure Grammar. We show here that given an RSRL-formula and a finite RSRL-interpretation it is in general not decidable if the formula is true in the given interpretation by reduction to Post Correspondence Problems. For so-called chainless RSRL, a semantically weaker version in which the expressive power of RSRL is significantly reduced, we show that if a class of finite structures is definable in chainless RSRL it is decidable by a Turing machine polynomially time bounded in the size of the input structures.

There are no comments yet on this publication. Be the first to share your thoughts.