Affordable Access

Publisher Website

On the Complexity of RSRL

Authors
Publisher
Elsevier B.V.
Publication Date
Volume
53
Identifiers
DOI: 10.1016/s1571-0661(05)82580-0
Disciplines
  • Design
  • Linguistics
  • Mathematics

Abstract

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.

Statistics

Seen <100 times
0 Comments

More articles like this

Complexity.

on Ground Water 2006

Complexity.

on Science Jan 24, 1986
More articles like this..