Acyclic Context-sensitive Grammars

Erik Aarts

Acyclic Context-sensitive Grammars

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

A grammar formalism is introduced that generates parse trees with crossing branches. The uniform recognition problem is NP-complete, but for any fixed grammar the recognition problem is polynomial.

Anthology ID:: 1995.iwpt-1.2
Volume:: Proceedings of the Fourth International Workshop on Parsing Technologies
Month:: September 20-24
Year:: 1995
Address:: Prague and Karlovy Vary, Czech Republic
Editors:: Eva Hajicova, Bernard Lang, Robert Berwick, Harry Bunt, Bob Carpenter, Ken Church, Aravind Joshi, Ronald Kaplan, Martin Kay, Makoto Nagao, Anton Nijholt, Mark Steedman, Henry Thompson, Masaru Tomita, K. Vijay-Shanker, Yorick Wilks, Kent Wittenburg
Venues:: IWPT | WS
SIG:: SIGPARSE
Publisher:: Association for Computational Linguistics
Note:
Pages:: 1–9
Language:
URL:: https://aclanthology.org/1995.iwpt-1.2/
DOI:
Bibkey:
Cite (ACL):: Erik Aarts. 1995. Acyclic Context-sensitive Grammars. In Proceedings of the Fourth International Workshop on Parsing Technologies, pages 1–9, Prague and Karlovy Vary, Czech Republic. Association for Computational Linguistics.
Cite (Informal):: Acyclic Context-sensitive Grammars (Aarts, IWPT 1995)
Copy Citation:
PDF:: https://aclanthology.org/1995.iwpt-1.2.pdf

PDF Cite Search Fix data

Export citation

BibTeX
MODS XML
Endnote
Preformatted

@inproceedings{aarts-1995-acyclic,
    title = "Acyclic Context-sensitive Grammars",
    author = "Aarts, Erik",
    editor = "Hajicova, Eva  and
      Lang, Bernard  and
      Berwick, Robert  and
      Bunt, Harry  and
      Carpenter, Bob  and
      Church, Ken  and
      Joshi, Aravind  and
      Kaplan, Ronald  and
      Kay, Martin  and
      Nagao, Makoto  and
      Nijholt, Anton  and
      Steedman, Mark  and
      Thompson, Henry  and
      Tomita, Masaru  and
      Vijay-Shanker, K.  and
      Wilks, Yorick  and
      Wittenburg, Kent",
    booktitle = "Proceedings of the Fourth International Workshop on Parsing Technologies",
    month = sep # " 20-24",
    year = "1995",
    address = "Prague and Karlovy Vary, Czech Republic",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/1995.iwpt-1.2/",
    pages = "1--9",
    abstract = "A grammar formalism is introduced that generates parse trees with crossing branches. The uniform recognition problem is NP-complete, but for any fixed grammar the recognition problem is polynomial."
}

Download as File

<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="aarts-1995-acyclic">
    <titleInfo>
        <title>Acyclic Context-sensitive Grammars</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Erik</namePart>
        <namePart type="family">Aarts</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>1995-sep 20-24</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the Fourth International Workshop on Parsing Technologies</title>
        </titleInfo>
        <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">Bernard</namePart>
            <namePart type="family">Lang</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Robert</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="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">Ken</namePart>
            <namePart type="family">Church</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">Makoto</namePart>
            <namePart type="family">Nagao</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <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">Mark</namePart>
            <namePart type="family">Steedman</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Henry</namePart>
            <namePart type="family">Thompson</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">Yorick</namePart>
            <namePart type="family">Wilks</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>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Prague and Karlovy Vary, Czech Republic</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>A grammar formalism is introduced that generates parse trees with crossing branches. The uniform recognition problem is NP-complete, but for any fixed grammar the recognition problem is polynomial.</abstract>
    <identifier type="citekey">aarts-1995-acyclic</identifier>
    <location>
        <url>https://aclanthology.org/1995.iwpt-1.2/</url>
    </location>
    <part>
        <date>1995-sep 20-24</date>
        <extent unit="page">
            <start>1</start>
            <end>9</end>
        </extent>
    </part>
</mods>
</modsCollection>

Download as File

%0 Conference Proceedings
%T Acyclic Context-sensitive Grammars
%A Aarts, Erik
%Y Hajicova, Eva
%Y Lang, Bernard
%Y Berwick, Robert
%Y Bunt, Harry
%Y Carpenter, Bob
%Y Church, Ken
%Y Joshi, Aravind
%Y Kaplan, Ronald
%Y Kay, Martin
%Y Nagao, Makoto
%Y Nijholt, Anton
%Y Steedman, Mark
%Y Thompson, Henry
%Y Tomita, Masaru
%Y Vijay-Shanker, K.
%Y Wilks, Yorick
%Y Wittenburg, Kent
%S Proceedings of the Fourth International Workshop on Parsing Technologies
%D 1995
%8 sep 20 24
%I Association for Computational Linguistics
%C Prague and Karlovy Vary, Czech Republic
%F aarts-1995-acyclic
%X A grammar formalism is introduced that generates parse trees with crossing branches. The uniform recognition problem is NP-complete, but for any fixed grammar the recognition problem is polynomial.
%U https://aclanthology.org/1995.iwpt-1.2/
%P 1-9

Download as File

Markdown (Informal)

[Acyclic Context-sensitive Grammars](https://aclanthology.org/1995.iwpt-1.2/) (Aarts, IWPT 1995)

Acyclic Context-sensitive Grammars (Aarts, IWPT 1995)

ACL

Erik Aarts. 1995. Acyclic Context-sensitive Grammars. In Proceedings of the Fourth International Workshop on Parsing Technologies, pages 1–9, Prague and Karlovy Vary, Czech Republic. Association for Computational Linguistics.