<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="kipps-1989-analysis">
    <titleInfo>
        <title>Analysis of Tomita’s Algorithm for General Context-Free Parsing</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">James</namePart>
        <namePart type="given">R</namePart>
        <namePart type="family">Kipps</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>A variation on Tomita’s algorithm is analyzed in regards to its time and space complexity. It is shown to have a general time bound of 0(n^\tildeρ+1), where n is the length of the input string and ρ is the length of the longest production. A modified algorithm is presented in which the time bound is reduced to 0(n³). The space complexity of Tomita’s algorithm is shown to be proportional to n² in the worst case and is changed by at most a constant factor with the modification. Empirical results are used to illustrate the trade off between time and space on a simple example. A discussion of two subclasses of context-free grammars that can be recognized in 0(n²) and O(n) is also included.</abstract>
    <identifier type="citekey">kipps-1989-analysis</identifier>
    <location>
        <url>https://aclanthology.org/W89-0220</url>
    </location>
    <part>
        <date>1989-08</date>
        <extent unit="page">
            <start>193</start>
            <end>202</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T Analysis of Tomita’s Algorithm for General Context-Free Parsing
%A Kipps, James R.
%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 kipps-1989-analysis
%X A variation on Tomita’s algorithm is analyzed in regards to its time and space complexity. It is shown to have a general time bound of 0(n^\tildeρ+1), where n is the length of the input string and ρ is the length of the longest production. A modified algorithm is presented in which the time bound is reduced to 0(n³). The space complexity of Tomita’s algorithm is shown to be proportional to n² in the worst case and is changed by at most a constant factor with the modification. Empirical results are used to illustrate the trade off between time and space on a simple example. A discussion of two subclasses of context-free grammars that can be recognized in 0(n²) and O(n) is also included.
%U https://aclanthology.org/W89-0220
%P 193-202

Markdown (Informal)

[Analysis of Tomita’s Algorithm for General Context-Free Parsing](https://aclanthology.org/W89-0220) (Kipps, IWPT 1989)

• Analysis of Tomita’s Algorithm for General Context-Free Parsing (Kipps, IWPT 1989)

ACL

• James R. Kipps. 1989. Analysis of Tomita’s Algorithm for General Context-Free Parsing. In Proceedings of the First International Workshop on Parsing Technologies, pages 193–202, Pittsburgh, Pennsylvania, USA. Carnegy Mellon University.