@inproceedings{de-vreught-honig-1991-slow,
title = "Slow and Fast Parallel Recognition",
author = "de Vreught, Hans and
Honig, Job",
editor = "Tomita, Masaru and
Kay, Martin and
Berwick, Robert and
Hajicova, Eva and
Joshi, Aravind and
Kaplan, Ronald and
Nagao, Makoto and
Wilks, Yorick",
booktitle = "Proceedings of the Second International Workshop on Parsing Technologies",
month = feb # " 13-25",
year = "1991",
address = "Cancun, Mexico",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/1991.iwpt-1.15",
pages = "127--135",
abstract = "In the first part of this paper a slow parallel recognizer is described for general CFG{'}s. The recognizer runs in $\Theta(n^3/p(n))$ time with $p(n) = O(n^2)$ processors. It generalizes the items of the Earley algorithm to double dotted items, which are more suited to parallel parsing. In the second part a fast parallel recognizer is given for general CFG{'}s. The recognizer runs in $O(log n)$ time using $O(n^6)$ processors. It is a generalisation of the Gibbons and Rytter algorithm for grammars in CNF.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="de-vreught-honig-1991-slow">
<titleInfo>
<title>Slow and Fast Parallel Recognition</title>
</titleInfo>
<name type="personal">
<namePart type="given">Hans</namePart>
<namePart type="family">de Vreught</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Job</namePart>
<namePart type="family">Honig</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>1991-feb 13-25</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the Second 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>
<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">Robert</namePart>
<namePart type="family">Berwick</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">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">Makoto</namePart>
<namePart type="family">Nagao</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>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Cancun, Mexico</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<abstract>In the first part of this paper a slow parallel recognizer is described for general CFG’s. The recognizer runs in Θ(n³/p(n)) time with p(n) = O(n²) processors. It generalizes the items of the Earley algorithm to double dotted items, which are more suited to parallel parsing. In the second part a fast parallel recognizer is given for general CFG’s. The recognizer runs in O(log n) time using O(n⁶) processors. It is a generalisation of the Gibbons and Rytter algorithm for grammars in CNF.</abstract>
<identifier type="citekey">de-vreught-honig-1991-slow</identifier>
<location>
<url>https://aclanthology.org/1991.iwpt-1.15</url>
</location>
<part>
<date>1991-feb 13-25</date>
<extent unit="page">
<start>127</start>
<end>135</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Slow and Fast Parallel Recognition
%A de Vreught, Hans
%A Honig, Job
%Y Tomita, Masaru
%Y Kay, Martin
%Y Berwick, Robert
%Y Hajicova, Eva
%Y Joshi, Aravind
%Y Kaplan, Ronald
%Y Nagao, Makoto
%Y Wilks, Yorick
%S Proceedings of the Second International Workshop on Parsing Technologies
%D 1991
%8 feb 13 25
%I Association for Computational Linguistics
%C Cancun, Mexico
%F de-vreught-honig-1991-slow
%X In the first part of this paper a slow parallel recognizer is described for general CFG’s. The recognizer runs in Θ(n³/p(n)) time with p(n) = O(n²) processors. It generalizes the items of the Earley algorithm to double dotted items, which are more suited to parallel parsing. In the second part a fast parallel recognizer is given for general CFG’s. The recognizer runs in O(log n) time using O(n⁶) processors. It is a generalisation of the Gibbons and Rytter algorithm for grammars in CNF.
%U https://aclanthology.org/1991.iwpt-1.15
%P 127-135
Markdown (Informal)
[Slow and Fast Parallel Recognition](https://aclanthology.org/1991.iwpt-1.15) (de Vreught & Honig, IWPT 1991)
ACL
- Hans de Vreught and Job Honig. 1991. Slow and Fast Parallel Recognition. In Proceedings of the Second International Workshop on Parsing Technologies, pages 127–135, Cancun, Mexico. Association for Computational Linguistics.