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.CSL.2023.35
URN: urn:nbn:de:0030-drops-174963
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17496/
Tschirbs, Felix ;
Vortmeier, Nils ;
Zeume, Thomas
Dynamic Complexity of Regular Languages: Big Changes, Small Work
Abstract
Whether a changing string is member of a certain regular language can be maintained in the DynFO framework of Patnaik and Immerman: after changing the symbol at one position of the string, a first-order update formula can express - using additionally stored information - whether the resulting string is in the regular language.
We extend this and further known results by considering changes of many positions at once. We also investigate to which degree the obtained update formulas imply work-efficient parallel dynamic algorithms.
BibTeX - Entry
@InProceedings{tschirbs_et_al:LIPIcs.CSL.2023.35,
author = {Tschirbs, Felix and Vortmeier, Nils and Zeume, Thomas},
title = {{Dynamic Complexity of Regular Languages: Big Changes, Small Work}},
booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
pages = {35:1--35:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-264-8},
ISSN = {1868-8969},
year = {2023},
volume = {252},
editor = {Klin, Bartek and Pimentel, Elaine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17496},
URN = {urn:nbn:de:0030-drops-174963},
doi = {10.4230/LIPIcs.CSL.2023.35},
annote = {Keywords: dynamic descriptive complexity, regular languages, batch changes, work}
}
|
Keywords: |
|
dynamic descriptive complexity, regular languages, batch changes, work |
|
Collection: |
|
31st EACSL Annual Conference on Computer Science Logic (CSL 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
