1 Search Results for "Mikhelson, Margarita"

Document

DOI: 10.4230/LIPIcs.MFCS.2023.67

Parallel Enumeration of Parse Trees

Authors: Margarita Mikhelson and Alexander Okhotin

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

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)²) with O(n⁶) elements. Then, it is improved using fast matrix multiplication to use only O(n^5.38) elements, while preserving depth O((log n)²).

Cite as

Margarita Mikhelson and Alexander Okhotin. Parallel Enumeration of Parse Trees. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mikhelson_et_al:LIPIcs.MFCS.2023.67,
  author =	{Mikhelson, Margarita and Okhotin, Alexander},
  title =	{{Parallel Enumeration of Parse Trees}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.67},
  URN =		{urn:nbn:de:0030-drops-186016},
  doi =		{10.4230/LIPIcs.MFCS.2023.67},
  annote =	{Keywords: Context-free grammars, weighted grammars, parsing, parallel algorithms, matrix multiplication}
}

Refine by Type
1 Document/PDF

Refine by Publication Year
1 2023

Refine by Author
1 Mikhelson, Margarita
1 Okhotin, Alexander

Refine by Series/Journal
1 LIPIcs

Refine by Classification
1 Theory of computation → Grammars and context-free languages
1 Theory of computation → Parallel algorithms

Refine by Keyword
1 Context-free grammars
1 matrix multiplication
1 parallel algorithms
1 parsing
1 weighted grammars

1 Search Results for "Mikhelson, Margarita"

Parallel Enumeration of Parse Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message