Regular Approximations of CFLs: A Grammatical View

Mark-Jan Nederhof

Regular Approximations of CFLs: A Grammatical View

Correct Metadata for

Use this form to create a GitHub issue with structured data describing the correction. You will need a GitHub account. Once you create that issue, the correction will be reviewed by a staff member.

⚠️ Mobile Users: Submitting this form to create a new issue will only work with github.com, not the GitHub Mobile app.

Important: The Anthology treat PDFs as authoritative. Please use this form only to correct data that is out of line with the PDF. See our corrections guidelines if you need to change the PDF.

Title Adjust the title. Retain tags such as <fixed-case>.

Authors Adjust author names and order to match the PDF.

Abstract Correct abstract if needed. Retain XML formatting tags such as <tex-math>. You may use <b>...</b> for bold, <i>...</i> for italic, and <url>...</url> for URLs.

Verification against PDF Ensure that the new title/authors match the snapshot below. (If there is no snapshot or it is too small, consult the PDF.)

Authors concatenated from the text boxes above:

ALL author names match the snapshot above—including middle initials, hyphens, and accents.

Abstract

We show that for each context-free grammar a new grammar can be constructed that generates a regular language. This construction differs from existing methods of approximation in that use of a pushdown automaton is avoided . This allows better insight into how the generated language is affected. The new method is also more attractive from a computational viewpoint.

Anthology ID:: 1997.iwpt-1.19
Volume:: Proceedings of the Fifth International Workshop on Parsing Technologies
Month:: September 17-20
Year:: 1997
Address:: Boston/Cambridge, Massachusetts, USA
Editors:: Anton Nijholt, Robert C. Berwick, Harry C. Bunt, Bob Carpenter, Eva Hajicova, Mark Johnson, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Alon Lavie, Makoto Nagao, Mark Steedman, Masaru Tomita, K. Vijay-Shanker, David Weir, Kent Wittenburg, Mats Wiren
Venue:: IWPT
SIG:: SIGPARSE
Publisher:: Association for Computational Linguistics
Note:
Pages:: 159–170
Language:
URL:: https://aclanthology.org/1997.iwpt-1.19/
DOI:
Bibkey:
Cite (ACL):: Mark-Jan Nederhof. 1997. Regular Approximations of CFLs: A Grammatical View. In Proceedings of the Fifth International Workshop on Parsing Technologies, pages 159–170, Boston/Cambridge, Massachusetts, USA. Association for Computational Linguistics.
Cite (Informal):: Regular Approximations of CFLs: A Grammatical View (Nederhof, IWPT 1997)
Copy Citation:
PDF:: https://aclanthology.org/1997.iwpt-1.19.pdf

PDF Cite Search Fix data

Export citation

BibTeX
MODS XML
Endnote
Preformatted

@inproceedings{nederhof-1997-regular,
    title = "Regular Approximations of {CFL}s: A Grammatical View",
    author = "Nederhof, Mark-Jan",
    editor = "Nijholt, Anton  and
      Berwick, Robert C.  and
      Bunt, Harry C.  and
      Carpenter, Bob  and
      Hajicova, Eva  and
      Johnson, Mark  and
      Joshi, Aravind  and
      Kaplan, Ronald  and
      Kay, Martin  and
      Lang, Bernard  and
      Lavie, Alon  and
      Nagao, Makoto  and
      Steedman, Mark  and
      Tomita, Masaru  and
      Vijay-Shanker, K.  and
      Weir, David  and
      Wittenburg, Kent  and
      Wiren, Mats",
    booktitle = "Proceedings of the Fifth International Workshop on Parsing Technologies",
    month = sep # " 17-20",
    year = "1997",
    address = "Boston/Cambridge, Massachusetts, USA",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/1997.iwpt-1.19/",
    pages = "159--170",
    abstract = "We show that for each context-free grammar a new grammar can be constructed that generates a regular language. This construction differs from existing methods of approximation in that use of a pushdown automaton is avoided . This allows better insight into how the generated language is affected. The new method is also more attractive from a computational viewpoint."
}

Download as File

<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="nederhof-1997-regular">
    <titleInfo>
        <title>Regular Approximations of CFLs: A Grammatical View</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Mark-Jan</namePart>
        <namePart type="family">Nederhof</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>1997-sep 17-20</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the Fifth International Workshop on Parsing Technologies</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Anton</namePart>
            <namePart type="family">Nijholt</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Robert</namePart>
            <namePart type="given">C</namePart>
            <namePart type="family">Berwick</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Harry</namePart>
            <namePart type="given">C</namePart>
            <namePart type="family">Bunt</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Bob</namePart>
            <namePart type="family">Carpenter</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Eva</namePart>
            <namePart type="family">Hajicova</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Mark</namePart>
            <namePart type="family">Johnson</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Aravind</namePart>
            <namePart type="family">Joshi</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Ronald</namePart>
            <namePart type="family">Kaplan</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Martin</namePart>
            <namePart type="family">Kay</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Bernard</namePart>
            <namePart type="family">Lang</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Alon</namePart>
            <namePart type="family">Lavie</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Makoto</namePart>
            <namePart type="family">Nagao</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Mark</namePart>
            <namePart type="family">Steedman</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Masaru</namePart>
            <namePart type="family">Tomita</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">K</namePart>
            <namePart type="family">Vijay-Shanker</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">David</namePart>
            <namePart type="family">Weir</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Kent</namePart>
            <namePart type="family">Wittenburg</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Mats</namePart>
            <namePart type="family">Wiren</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Boston/Cambridge, Massachusetts, USA</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>We show that for each context-free grammar a new grammar can be constructed that generates a regular language. This construction differs from existing methods of approximation in that use of a pushdown automaton is avoided . This allows better insight into how the generated language is affected. The new method is also more attractive from a computational viewpoint.</abstract>
    <identifier type="citekey">nederhof-1997-regular</identifier>
    <location>
        <url>https://aclanthology.org/1997.iwpt-1.19/</url>
    </location>
    <part>
        <date>1997-sep 17-20</date>
        <extent unit="page">
            <start>159</start>
            <end>170</end>
        </extent>
    </part>
</mods>
</modsCollection>

Download as File

%0 Conference Proceedings
%T Regular Approximations of CFLs: A Grammatical View
%A Nederhof, Mark-Jan
%Y Nijholt, Anton
%Y Berwick, Robert C.
%Y Bunt, Harry C.
%Y Carpenter, Bob
%Y Hajicova, Eva
%Y Johnson, Mark
%Y Joshi, Aravind
%Y Kaplan, Ronald
%Y Kay, Martin
%Y Lang, Bernard
%Y Lavie, Alon
%Y Nagao, Makoto
%Y Steedman, Mark
%Y Tomita, Masaru
%Y Vijay-Shanker, K.
%Y Weir, David
%Y Wittenburg, Kent
%Y Wiren, Mats
%S Proceedings of the Fifth International Workshop on Parsing Technologies
%D 1997
%8 sep 17 20
%I Association for Computational Linguistics
%C Boston/Cambridge, Massachusetts, USA
%F nederhof-1997-regular
%X We show that for each context-free grammar a new grammar can be constructed that generates a regular language. This construction differs from existing methods of approximation in that use of a pushdown automaton is avoided . This allows better insight into how the generated language is affected. The new method is also more attractive from a computational viewpoint.
%U https://aclanthology.org/1997.iwpt-1.19/
%P 159-170

Download as File

Markdown (Informal)

[Regular Approximations of CFLs: A Grammatical View](https://aclanthology.org/1997.iwpt-1.19/) (Nederhof, IWPT 1997)

Regular Approximations of CFLs: A Grammatical View (Nederhof, IWPT 1997)

ACL

Mark-Jan Nederhof. 1997. Regular Approximations of CFLs: A Grammatical View. In Proceedings of the Fifth International Workshop on Parsing Technologies, pages 159–170, Boston/Cambridge, Massachusetts, USA. Association for Computational Linguistics.