Work-sensitive Dynamic Complexity of Formal Languages

Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering membership and range queries for formal languages in parallel constant time with polynomially many processors. As a prerequisi...

Descripción completa

Detalles Bibliográficos
Autores principales: Schmidt, Jonas, Schwentick, Thomas, Tantau, Till, Vortmeier, Nils, Zeume, Thomas
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2021
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7984110/
http://dx.doi.org/10.1007/978-3-030-71995-1_25
_version_ 1783668007714684928
author Schmidt, Jonas
Schwentick, Thomas
Tantau, Till
Vortmeier, Nils
Zeume, Thomas
author_facet Schmidt, Jonas
Schwentick, Thomas
Tantau, Till
Vortmeier, Nils
Zeume, Thomas
author_sort Schmidt, Jonas
collection PubMed
description Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering membership and range queries for formal languages in parallel constant time with polynomially many processors. As a prerequisite, we propose a framework for specifying dynamic, parallel, constant-time programs that require small amounts of work. This framework is based on the dynamic descriptive complexity framework by Patnaik and Immerman.
format Online
Article
Text
id pubmed-7984110
institution National Center for Biotechnology Information
language English
publishDate 2021
record_format MEDLINE/PubMed
spelling pubmed-79841102021-03-23 Work-sensitive Dynamic Complexity of Formal Languages Schmidt, Jonas Schwentick, Thomas Tantau, Till Vortmeier, Nils Zeume, Thomas Foundations of Software Science and Computation Structures Article Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering membership and range queries for formal languages in parallel constant time with polynomially many processors. As a prerequisite, we propose a framework for specifying dynamic, parallel, constant-time programs that require small amounts of work. This framework is based on the dynamic descriptive complexity framework by Patnaik and Immerman. 2021-03-23 /pmc/articles/PMC7984110/ http://dx.doi.org/10.1007/978-3-030-71995-1_25 Text en © The Author(s) 2021 Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
spellingShingle Article
Schmidt, Jonas
Schwentick, Thomas
Tantau, Till
Vortmeier, Nils
Zeume, Thomas
Work-sensitive Dynamic Complexity of Formal Languages
title Work-sensitive Dynamic Complexity of Formal Languages
title_full Work-sensitive Dynamic Complexity of Formal Languages
title_fullStr Work-sensitive Dynamic Complexity of Formal Languages
title_full_unstemmed Work-sensitive Dynamic Complexity of Formal Languages
title_short Work-sensitive Dynamic Complexity of Formal Languages
title_sort work-sensitive dynamic complexity of formal languages
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7984110/
http://dx.doi.org/10.1007/978-3-030-71995-1_25
work_keys_str_mv AT schmidtjonas worksensitivedynamiccomplexityofformallanguages
AT schwentickthomas worksensitivedynamiccomplexityofformallanguages
AT tantautill worksensitivedynamiccomplexityofformallanguages
AT vortmeiernils worksensitivedynamiccomplexityofformallanguages
AT zeumethomas worksensitivedynamiccomplexityofformallanguages

Ejemplares similares