Regular Languages in the Sliding Window Model
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929751945379840 |
|---|---|
| author | Ganardi, Moses Hucke, Danny Lohrey, Markus Mamouras, Konstantinos Starikovskaya, Tatiana |
| author_facet | Ganardi, Moses Hucke, Danny Lohrey, Markus Mamouras, Konstantinos Starikovskaya, Tatiana |
| contents | We study the space complexity of the following problem: For a fixed regular language $L$, we receive a stream of symbols and want to test membership of a sliding window of size $n$ in $L$. For deterministic streaming algorithms we prove a trichotomy theorem, namely that the (optimal) space complexity is either constant, logarithmic or linear, measured in the window size $n$. Additionally, we provide natural language-theoretic characterizations of the space classes. We then extend the results to randomized streaming algorithms and we show that in this setting, the space complexity of any regular language is either constant, doubly logarithmic, logarithmic or linear. Finally, we introduce sliding window testers, which can distinguish whether a sliding window of size $n$ belongs to the language $L$ or has Hamming distance $> εn$ to $L$. We prove that every regular language has a deterministic (resp., randomized) sliding window tester that requires only logarithmic (resp., constant) space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_13385 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Regular Languages in the Sliding Window Model Ganardi, Moses Hucke, Danny Lohrey, Markus Mamouras, Konstantinos Starikovskaya, Tatiana Formal Languages and Automata Theory We study the space complexity of the following problem: For a fixed regular language $L$, we receive a stream of symbols and want to test membership of a sliding window of size $n$ in $L$. For deterministic streaming algorithms we prove a trichotomy theorem, namely that the (optimal) space complexity is either constant, logarithmic or linear, measured in the window size $n$. Additionally, we provide natural language-theoretic characterizations of the space classes. We then extend the results to randomized streaming algorithms and we show that in this setting, the space complexity of any regular language is either constant, doubly logarithmic, logarithmic or linear. Finally, we introduce sliding window testers, which can distinguish whether a sliding window of size $n$ belongs to the language $L$ or has Hamming distance $> εn$ to $L$. We prove that every regular language has a deterministic (resp., randomized) sliding window tester that requires only logarithmic (resp., constant) space. |
| title | Regular Languages in the Sliding Window Model |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2402.13385 |