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-WS 1995)
- Copy Citation:
- PDF:
- https://aclanthology.org/1995.iwpt-1.2.pdf
Export citation
@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.",
}
<?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>
%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
Markdown (Informal)
[Acyclic Context-sensitive Grammars](https://aclanthology.org/1995.iwpt-1.2) (Aarts, IWPT-WS 1995)
- Acyclic Context-sensitive Grammars (Aarts, IWPT-WS 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.