Dot-depth three, return of the J-class
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929227077517312 |
|---|---|
| author | Place, Thomas Zeitoun, Marc |
| author_facet | Place, Thomas Zeitoun, Marc |
| contents | We look at concatenation hierarchies of classes of regular languages. Each such hierarchy is determined by a single class, its basis: level $n$ is built by applying the Boolean polynomial closure operator (BPol), $n$ times to the basis. A prominent and difficult open question in automata theory is to decide membership of a regular language in a given level. For instance, for the historical dot-depth hierarchy, the decidability of membership is only known at levels one and two.
We give a generic algebraic characterization of the operator BPol. This characterization implies that for any concatenation hierarchy, if $n$ is at least two, membership at level $n$ reduces to a more complex problem, called covering, for the previous level, $n-1$. Combined with earlier results on covering, this implies that membership is decidable for dot-depth three and for level two in most of the prominent hierarchies in the literature. For instance, we obtain that the levels two in both the modulo hierarchy and the group hierarchy have decidable membership. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_16195 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dot-depth three, return of the J-class Place, Thomas Zeitoun, Marc Formal Languages and Automata Theory We look at concatenation hierarchies of classes of regular languages. Each such hierarchy is determined by a single class, its basis: level $n$ is built by applying the Boolean polynomial closure operator (BPol), $n$ times to the basis. A prominent and difficult open question in automata theory is to decide membership of a regular language in a given level. For instance, for the historical dot-depth hierarchy, the decidability of membership is only known at levels one and two. We give a generic algebraic characterization of the operator BPol. This characterization implies that for any concatenation hierarchy, if $n$ is at least two, membership at level $n$ reduces to a more complex problem, called covering, for the previous level, $n-1$. Combined with earlier results on covering, this implies that membership is decidable for dot-depth three and for level two in most of the prominent hierarchies in the literature. For instance, we obtain that the levels two in both the modulo hierarchy and the group hierarchy have decidable membership. |
| title | Dot-depth three, return of the J-class |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2401.16195 |