Standard

A parallel algorithm for counting parse trees. / Михельсон, Маргарита Николаевна; Охотин, Александр Сергеевич.

In: Information and Computation, Vol. 303, 105237, 01.03.2025.

Research output: Contribution to journal › Article › peer-review

Harvard

Михельсон, МН & Охотин, АС 2025, 'A parallel algorithm for counting parse trees', Information and Computation, vol. 303, 105237. https://doi.org/10.1016/j.ic.2024.105237

APA

Михельсон, М. Н., & Охотин, А. С. (2025). A parallel algorithm for counting parse trees. Information and Computation, 303, [105237]. https://doi.org/10.1016/j.ic.2024.105237

Vancouver

Михельсон МН, Охотин АС. A parallel algorithm for counting parse trees. Information and Computation. 2025 Mar 1;303. 105237. https://doi.org/10.1016/j.ic.2024.105237

Author

Михельсон, Маргарита Николаевна ; Охотин, Александр Сергеевич. / A parallel algorithm for counting parse trees. In: Information and Computation. 2025 ; Vol. 303.

BibTeX

@article{13125b0d0ac940558eee76b0ae005388,
title = "A parallel algorithm for counting parse trees",
abstract = "A parallel algorithm for computing the number of parse trees of a given string according to a fixed context-free grammar is defined. More generally, the algorithm applies to computing the weight of a string in a weighted grammar over any semiring. The algorithm is first implemented on an arithmetic circuit of depth at most 6(log2⁡n)2+O(log⁡n) and with O(n6) elements, where the constant factors in the big-O notation depend on the grammar. Then, the circuit is improved using fast matrix multiplication to use only O(n5.38) elements, while preserving depth O((log⁡n)2).",
keywords = "Context-free grammars, Matrix multiplication, Parallel algorithms, Parsing, Weighted grammars",
author = "Михельсон, {Маргарита Николаевна} and Охотин, {Александр Сергеевич}",
year = "2025",
month = mar,
day = "1",
doi = "10.1016/j.ic.2024.105237",
language = "English",
volume = "303",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - A parallel algorithm for counting parse trees

AU - Михельсон, Маргарита Николаевна

AU - Охотин, Александр Сергеевич

PY - 2025/3/1

Y1 - 2025/3/1

N2 - A parallel algorithm for computing the number of parse trees of a given string according to a fixed context-free grammar is defined. More generally, the algorithm applies to computing the weight of a string in a weighted grammar over any semiring. The algorithm is first implemented on an arithmetic circuit of depth at most 6(log2⁡n)2+O(log⁡n) and with O(n6) elements, where the constant factors in the big-O notation depend on the grammar. Then, the circuit is improved using fast matrix multiplication to use only O(n5.38) elements, while preserving depth O((log⁡n)2).

AB - A parallel algorithm for computing the number of parse trees of a given string according to a fixed context-free grammar is defined. More generally, the algorithm applies to computing the weight of a string in a weighted grammar over any semiring. The algorithm is first implemented on an arithmetic circuit of depth at most 6(log2⁡n)2+O(log⁡n) and with O(n6) elements, where the constant factors in the big-O notation depend on the grammar. Then, the circuit is improved using fast matrix multiplication to use only O(n5.38) elements, while preserving depth O((log⁡n)2).

KW - Context-free grammars

KW - Matrix multiplication

KW - Parallel algorithms

KW - Parsing

KW - Weighted grammars

UR - https://www.mendeley.com/catalogue/5e7d04f6-3b4c-3c92-8af6-c7c358ad7c8d/

U2 - 10.1016/j.ic.2024.105237

DO - 10.1016/j.ic.2024.105237

M3 - Article

VL - 303

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 105237

ER -

ID: 131232926