Paper: A Complete And Recursive Feature Theory

ACL ID P93-1026
Title A Complete And Recursive Feature Theory
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1993

Various feature descriptions are being employed in constrained-based grammar formalisms. The com- mon notational primitive of these descriptions are functional attributes called features. The descrip- tions considered in this paper are the possibly quan- tified first-order formulae obtained from a signature of features and sorts. We establish a complete first- order theory FT by means of three axiom schemes and construct three elementarily equivalent models. One of the models consists of so-called feature graphs, a data structure common in computational linguistics. The other two models consist of so-called feature trees, a record-like data structure generaliz- ing the trees corresponding to first-order terms. Our completeness proof exhibits a terminating simplification system deciding val...