<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="yamai-etal-1989-effective">
    <titleInfo>
        <title>An Effective Enumeration Algorithm of Parses for Ambiguous CFL</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Nariyoshi</namePart>
        <namePart type="family">Yamai</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Tadashi</namePart>
        <namePart type="family">Seko</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Noboru</namePart>
        <namePart type="family">Kubo</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Toru</namePart>
        <namePart type="family">Kawata</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>1989-08</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the First International Workshop on Parsing Technologies</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Masaru</namePart>
            <namePart type="family">Tomita</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Carnegy Mellon University</publisher>
            <place>
                <placeTerm type="text">Pittsburgh, Pennsylvania, USA</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>An efficient algorithm that enumerates parses of ambiguous context-free languages is described, and its time and space complexities are discussed. When context-free parsers are used for natural language parsing, pattern recognition, and so forth, there may be a great number of parses for a sentence. One common strategy for efficient enumeration of parses is to assign an appropriate weight to each production, and to enumerate parses in the order of the total weight of all applied production. However, the existing algorithms taking this strategy can be applied only to the problems of limited areas such as regular languages; in the other areas only inefficient exhaustive searches are known. In this paper, we first introduce a hierarchical graph suitable for enumeration. Using this graph, enumeration of parses in the order of acceptablity is equivalent to finding paths of this graph in the order of length. Then, we present an efficient enumeration algorithm with this graph, which can be applied to arbitrary context-free grammars. For enumeration of k parses in the order of the total weight of all applied productions, the time and space complexities of our algorithm are 0(n³ + kn²) and 0(n³ + kn), respectively.</abstract>
    <identifier type="citekey">yamai-etal-1989-effective</identifier>
    <location>
        <url>https://aclanthology.org/W89-0230</url>
    </location>
    <part>
        <date>1989-08</date>
        <extent unit="page">
            <start>286</start>
            <end>296</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T An Effective Enumeration Algorithm of Parses for Ambiguous CFL
%A Yamai, Nariyoshi
%A Seko, Tadashi
%A Kubo, Noboru
%A Kawata, Toru
%Y Tomita, Masaru
%S Proceedings of the First International Workshop on Parsing Technologies
%D 1989
%8 August
%I Carnegy Mellon University
%C Pittsburgh, Pennsylvania, USA
%F yamai-etal-1989-effective
%X An efficient algorithm that enumerates parses of ambiguous context-free languages is described, and its time and space complexities are discussed. When context-free parsers are used for natural language parsing, pattern recognition, and so forth, there may be a great number of parses for a sentence. One common strategy for efficient enumeration of parses is to assign an appropriate weight to each production, and to enumerate parses in the order of the total weight of all applied production. However, the existing algorithms taking this strategy can be applied only to the problems of limited areas such as regular languages; in the other areas only inefficient exhaustive searches are known. In this paper, we first introduce a hierarchical graph suitable for enumeration. Using this graph, enumeration of parses in the order of acceptablity is equivalent to finding paths of this graph in the order of length. Then, we present an efficient enumeration algorithm with this graph, which can be applied to arbitrary context-free grammars. For enumeration of k parses in the order of the total weight of all applied productions, the time and space complexities of our algorithm are 0(n³ + kn²) and 0(n³ + kn), respectively.
%U https://aclanthology.org/W89-0230
%P 286-296

Markdown (Informal)

[An Effective Enumeration Algorithm of Parses for Ambiguous CFL](https://aclanthology.org/W89-0230) (Yamai et al., IWPT 1989)

• An Effective Enumeration Algorithm of Parses for Ambiguous CFL (Yamai et al., IWPT 1989)

ACL

• Nariyoshi Yamai, Tadashi Seko, Noboru Kubo, and Toru Kawata. 1989. An Effective Enumeration Algorithm of Parses for Ambiguous CFL. In Proceedings of the First International Workshop on Parsing Technologies, pages 286–296, Pittsburgh, Pennsylvania, USA. Carnegy Mellon University.