An Efficient Typed Feature Structure Index: Theory and Implementation

Bernd Kiefer; Hans-Ulrich Krieger

In: Proceedings of the 13th International Conference on Parsing Technologies. International Conference on Parsing Technologies (IWPT-2013), November 27-29, Nara, Japan, 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.


Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence