@inproceedings{de-vreught-honig-1991-slow,
title = "Slow and Fast Parallel Recognition",
author = "de Vreught, Hans and
Honig, Job",
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>
<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^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.</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
%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^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.
%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.