Standard

Parallel Enumeration of Parse Trees. / Михельсон, Маргарита Николаевна; Охотин, Александр Сергеевич.

48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. Vol. 272 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. p. 67:1-67:14 67 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Harvard

Михельсон, МН & Охотин, АС 2023, Parallel Enumeration of Parse Trees. in 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. vol. 272, 67, Leibniz International Proceedings in Informatics, LIPIcs, vol. 272, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 67:1-67:14, 48th International Symposium on Mathematical Foundations of Computer Science, Bordeaux, France, 28/08/23. https://doi.org/10.4230/LIPIcs.MFCS.2023.67

APA

Михельсон, М. Н., & Охотин, А. С. (2023). Parallel Enumeration of Parse Trees. In 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France (Vol. 272, pp. 67:1-67:14). [67] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 272). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2023.67

Vancouver

Михельсон МН, Охотин АС. Parallel Enumeration of Parse Trees. In 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. Vol. 272. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. p. 67:1-67:14. 67. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.MFCS.2023.67

Author

Михельсон, Маргарита Николаевна ; Охотин, Александр Сергеевич. / Parallel Enumeration of Parse Trees. 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. Vol. 272 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. pp. 67:1-67:14 (Leibniz International Proceedings in Informatics, LIPIcs).

BibTeX

@inproceedings{0e6b4b7e169b432d800b3d41e11595f3,
title = "Parallel Enumeration of Parse Trees",
abstract = "A parallel algorithm for enumerating parse trees of a given string according to a fixed context-free grammar is defined. The algorithm computes the number of parse trees of an input string; more generally, it applies to computing the weight of a string in a weighted grammar. The algorithm is first implemented on an arithmetic circuit of depth O((log n)2) with O(n6) elements. Then, it 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 = "2023",
month = aug,
doi = "10.4230/LIPIcs.MFCS.2023.67",
language = "English",
isbn = "9783959772921",
volume = "272",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "67:1--67:14",
booktitle = "48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France",
address = "Germany",
note = "48th International Symposium on Mathematical Foundations of Computer Science ; Conference date: 28-08-2023 Through 01-09-2023",
url = "https://mfcs2023.labri.fr",

}

RIS

TY - GEN

T1 - Parallel Enumeration of Parse Trees

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

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

N1 - Conference code: 48

PY - 2023/8

Y1 - 2023/8

N2 - A parallel algorithm for enumerating parse trees of a given string according to a fixed context-free grammar is defined. The algorithm computes the number of parse trees of an input string; more generally, it applies to computing the weight of a string in a weighted grammar. The algorithm is first implemented on an arithmetic circuit of depth O((log n)2) with O(n6) elements. Then, it 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 enumerating parse trees of a given string according to a fixed context-free grammar is defined. The algorithm computes the number of parse trees of an input string; more generally, it applies to computing the weight of a string in a weighted grammar. The algorithm is first implemented on an arithmetic circuit of depth O((log n)2) with O(n6) elements. Then, it 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/d60bb0ca-281e-3e35-9362-97519bcf00b7/

U2 - 10.4230/LIPIcs.MFCS.2023.67

DO - 10.4230/LIPIcs.MFCS.2023.67

M3 - Conference contribution

SN - 9783959772921

VL - 272

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 67:1-67:14

BT - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 48th International Symposium on Mathematical Foundations of Computer Science

Y2 - 28 August 2023 through 1 September 2023

ER -

ID: 108696082