License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.81
URN: urn:nbn:de:0030-drops-186152
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18615/
Go to the corresponding LIPIcs Volume Portal

Schmidt, Jonas ; Schwentick, Thomas ; Todtenhoefer, Jennifer

On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages

pdf-format:
LIPIcs-MFCS-2023-81.pdf (0.9 MB)

Abstract

Previous work on Dynamic Complexity has established that there exist dynamic constant-time parallel algorithms for regular tree languages and context-free languages under label or symbol changes. However, these algorithms were not developed with the goal to minimise work (or, equivalently, the number of processors). In fact, their inspection yields the work bounds ?(n²) and ?(n⁷) per change operation, respectively.
In this paper, dynamic algorithms for regular tree languages are proposed that generalise the previous algorithms in that they allow unbounded node rank and leaf insertions, while improving the work bound from ?(n²) to ?(n^ε), for arbitrary ε > 0.
For context-free languages, algorithms with better work bounds (compared with ?(n⁷)) for restricted classes are proposed: for every ε > 0 there are such algorithms for deterministic context-free languages with work bound ?(n^{3+ε}) and for visibly pushdown languages with work bound ?(n^{2+ε}).

BibTeX - Entry

@InProceedings{schmidt_et_al:LIPIcs.MFCS.2023.81,
  author =	{Schmidt, Jonas and Schwentick, Thomas and Todtenhoefer, Jennifer},
  title =	{{On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{81:1--81:15},
  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/opus/volltexte/2023/18615},
  URN =		{urn:nbn:de:0030-drops-186152},
  doi =		{10.4230/LIPIcs.MFCS.2023.81},
  annote =	{Keywords: Dynamic complexity, work, parallel constant time}
}

Keywords: Dynamic complexity, work, parallel constant time
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI