A Sharper Upper Bound for the Separating Words Problem
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912305208360960 |
|---|---|
| author | Dumitru, Bogdan C. |
| author_facet | Dumitru, Bogdan C. |
| contents | We show that for any two distinct words $ s_1, s_2 $ over an arbitrary alphabets, there exists a deterministic finite automaton with $ O(\log^2 n) $ states that accepts $ s_1 $ and rejects $ s_2 $. This improves the previous upper bound of $O(n^{1/3}\log^7 n)$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23184 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Sharper Upper Bound for the Separating Words Problem Dumitru, Bogdan C. Formal Languages and Automata Theory Number Theory We show that for any two distinct words $ s_1, s_2 $ over an arbitrary alphabets, there exists a deterministic finite automaton with $ O(\log^2 n) $ states that accepts $ s_1 $ and rejects $ s_2 $. This improves the previous upper bound of $O(n^{1/3}\log^7 n)$ |
| title | A Sharper Upper Bound for the Separating Words Problem |
| topic | Formal Languages and Automata Theory Number Theory |
| url | https://arxiv.org/abs/2503.23184 |