License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.177
URN: urn:nbn:de:0030-drops-26521
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2652/
Go to the corresponding LIPIcs Volume Portal

Koller, Alexander ; Thater, Stefan

Underspecified computation of normal forms

pdf-format:
10002.KollerAlexander.2652.pdf (0.2 MB)

Abstract

We show how to compute readings of ambiguous natural language sentences that are minimal in some way. Formally, we consider the problem of computing, out of a set C of trees and a rewrite system R, those trees in C that cannot be rewritten into a tree in C. We solve the problem for sets of trees that are described by semantic representations typically used in computational linguistics, and a certain class of rewrite systems that we use to approximate entailment, and show how to compute the irreducible trees efficiently by intersecting tree automata. Our algorithm solves the problem of computing weakest readings that has been open for 25 years in computational linguistics.

BibTeX - Entry

@InProceedings{koller_et_al:LIPIcs:2010:2652,
  author =	{Alexander Koller and Stefan Thater},
  title =	{{Underspecified computation of normal forms}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{177--192},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Christopher Lynch},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2652},
  URN =		{urn:nbn:de:0030-drops-26521},
  doi =		{10.4230/LIPIcs.RTA.2010.177},
  annote =	{Keywords: Rewrite systems tree automata normal forms computational linguistics}
}

Keywords: Rewrite systems tree automata normal forms computational linguistics
Collection: Proceedings of the 21st International Conference on Rewriting Techniques and Applications
Issue Date: 2010
Date of publication: 06.07.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI