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 - Dagstuhl Publishing

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

Y2 - 28 August 2023 through 1 September 2023

ER -