Publication
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.
Abstract
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.