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. Том 272 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. стр. 67:1-67:14 67 (Leibniz International Proceedings in Informatics, LIPIcs; Том 272).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Harvard
Михельсон, МН & Охотин, АС 2023,
Parallel Enumeration of Parse Trees. в
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France. Том. 272, 67, Leibniz International Proceedings in Informatics, LIPIcs, Том. 272, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, стр. 67:1-67:14, 48th International Symposium on Mathematical Foundations of Computer Science, Bordeaux, Франция,
28/08/23.
https://doi.org/10.4230/LIPIcs.MFCS.2023.67
APA
Михельсон, М. Н., & Охотин, А. С. (2023).
Parallel Enumeration of Parse Trees. в
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France (Том 272, стр. 67:1-67:14). [67] (Leibniz International Proceedings in Informatics, LIPIcs; Том 272). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
https://doi.org/10.4230/LIPIcs.MFCS.2023.67
Vancouver
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. Том 272 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. стр. 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 -
