|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
28 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Dynamic Membership for Regular Languages | | Antoine Amarilli
; Louis Jachiet
; Charles Paperman
; | | Date: |
15 Feb 2021 | | Abstract: | We study the dynamic membership problem for regular languages: fix a language
L, read a word w, build in time O(|w|) a data structure indicating if w is in
L, and maintain this structure efficiently under substitution edits on w. We
consider this problem on the unit cost RAM model with logarithmic world length,
where the problem always has a solution in O(log |w| / log log |w|).
We show that the problem is in O(log log |w|) for languages in an
algebraically-defined class QSG, and that it is in O(1) for another class QLZG.
We show that languages not in QSG admit a reduction from the prefix problem for
a cyclic group, so that they require Omega(log n/ log log n) operations in the
worst case; and that QSG languages not in QLZG admit a reduction from the
prefix problem for the monoid U_1, which we conjecture cannot be maintained in
O(1). This yields a conditional trichotomy. We also investigate intermediate
cases between O(1) and O(log log n).
Our results are shown via the dynamic word problem for monoids and
semigroups, for which we also give a classification. We thus solve open
problems of the paper of Skovbjerg Frandsen, Miltersen, and Skyum on the
dynamic word problem, and additionally cover regular languages. | | Source: | arXiv, 2102.07728 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER