ISSN:
1572-9583
Keywords:
complexity theory
;
constraint logics
;
HPSG formalisms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Linguistics and Literary Studies
,
Computer Science
Notes:
Abstract The SRL (speciate re-entrant logic) of King (1989) is a sound, complete and decidable logic designed specifically to support formalisms for the HPSG (head-driven phrase structure grammar) of Pollard and Sag (1994). The SRL notion of modellability in a signature is particularly important for HPSG, and the present paper modifies an elegant method due to Blackburn and Spaan (1993) in order to prove that modellability in each computable signature is Π 1 0 modellability in some finite signature is Π 1 0 -hard (hence not decidable), and modellability in some finite signature is decidable. Since each finite signature is a computable signature, we conclude that Π01-completeness is the least upper bound on the complexity of modellability both in finite signatures and in computable signatures, though not a lower bound in either.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1008247127922
Permalink
