DFKI-LT - An Efficient Typed Feature Structure Index: Theory and Implementation

Bernd Kiefer, Hans-Ulrich Krieger
An Efficient Typed Feature Structure Index: Theory and Implementation
2 Proceedings of the 13th International Conference on Parsing Technologies, Nara, Japan, ACL, SIGPARSE, the Special Interest Group on Parsing of the Association for Computational Linguistics (ACL), 11/2013
Many applications (not necessarily only from computational linguistics), involving record- or graph-like structures, would benefit from a framework which would allow to efficiently test a single structure T under various operations o against a compact representation I of a set of similar structures: T o I. Besides a Boolean answer, we would also like to see those structures stored in I which are entailed by operation o. In our case, we are especially interested in os that implement feature structure subsumption and unifiability. The urgent need for such a kind of framework is related to our work on the approximation of (P)CFGs from unification-based grammars. We not only define the mathematical apparatus for this in terms of finite-state automata, but also come up with an efficient implementation mostly along the theoretical basis, together with measurements in which we compare our implementation of I against a discrimination tree index.
Files: BibTeX