Decomposition of Automata recognizing Ideals
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910174270193664 |
|---|---|
| author | Berry, Mathias Héam, Pierre-Cyrille Jecker, Ismaël |
| author_facet | Berry, Mathias Héam, Pierre-Cyrille Jecker, Ismaël |
| contents | Minimizing the size of finite automata is a fundamental problem in theoretical computer science. Beyond standard minimization, further reductions can be achieved by decomposing an automaton into smaller components whose languages combine via intersection or union to recover the original language. However, in general, no polynomial-time algorithm is known for computing such decompositions.
In this paper, we focus on automata that recognize ideals, that is, languages at level 1/2 in the Straubing-Thérien hierarchy. Equivalently, these languages are expressible as a finite union of languages of the form $Σ^*a_1Σ^*\dotsΣ^*a_nΣ^*$ where $Σ$ is an alphabet and $a_i$ are letters of $Σ$. We show that the two problems of deciding whether such a language can be decomposed into an intersection or a union of smaller automata are decidable in NL. Moreover, we provide a polynomial-time algorithm that computes a decomposition into an intersection, if one exists, while ensuring that the resulting components also recognize ideal languages. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_25619 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Decomposition of Automata recognizing Ideals Berry, Mathias Héam, Pierre-Cyrille Jecker, Ismaël Formal Languages and Automata Theory 68Q45 F.4.3 Minimizing the size of finite automata is a fundamental problem in theoretical computer science. Beyond standard minimization, further reductions can be achieved by decomposing an automaton into smaller components whose languages combine via intersection or union to recover the original language. However, in general, no polynomial-time algorithm is known for computing such decompositions. In this paper, we focus on automata that recognize ideals, that is, languages at level 1/2 in the Straubing-Thérien hierarchy. Equivalently, these languages are expressible as a finite union of languages of the form $Σ^*a_1Σ^*\dotsΣ^*a_nΣ^*$ where $Σ$ is an alphabet and $a_i$ are letters of $Σ$. We show that the two problems of deciding whether such a language can be decomposed into an intersection or a union of smaller automata are decidable in NL. Moreover, we provide a polynomial-time algorithm that computes a decomposition into an intersection, if one exists, while ensuring that the resulting components also recognize ideal languages. |
| title | Decomposition of Automata recognizing Ideals |
| topic | Formal Languages and Automata Theory 68Q45 F.4.3 |
| url | https://arxiv.org/abs/2604.25619 |