Automata for the commutative closure of regular sets
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915243664343040 |
|---|---|
| author | Becher, Verónica Deveali, Simon Lew Cunningham, Ignacio Mollo |
| author_facet | Becher, Verónica Deveali, Simon Lew Cunningham, Ignacio Mollo |
| contents | Consider $ A^* $, the free monoid generated by the finite alphabet $A$ with the concatenation operation. Two words have the same commutative image when one is a permutation of the symbols of the other. The commutative closure of a set $ L \subseteq A^* $ is the set $ {C}(L) \subseteq A^* $ of words whose commutative image coincides with that of some word in $ L $. We provide an algorithm that, given a regular set $ L $, produces a finite state automaton that accepts the commutative closure $ {C}(L) $, provided that this closure set is regular. The problem of deciding whether $ {C}(L) $ is regular was solved by Ginsburg and Spanier in 1966 using the decidability of Presburger sentences, and by Gohon in 1985 via formal power series. The problem of constructing an automaton that accepts $ {C}(L) $ has already been studied in the literature. We give a simpler algorithm using an algebraic approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_10864 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Automata for the commutative closure of regular sets Becher, Verónica Deveali, Simon Lew Cunningham, Ignacio Mollo Formal Languages and Automata Theory Consider $ A^* $, the free monoid generated by the finite alphabet $A$ with the concatenation operation. Two words have the same commutative image when one is a permutation of the symbols of the other. The commutative closure of a set $ L \subseteq A^* $ is the set $ {C}(L) \subseteq A^* $ of words whose commutative image coincides with that of some word in $ L $. We provide an algorithm that, given a regular set $ L $, produces a finite state automaton that accepts the commutative closure $ {C}(L) $, provided that this closure set is regular. The problem of deciding whether $ {C}(L) $ is regular was solved by Ginsburg and Spanier in 1966 using the decidability of Presburger sentences, and by Gohon in 1985 via formal power series. The problem of constructing an automaton that accepts $ {C}(L) $ has already been studied in the literature. We give a simpler algorithm using an algebraic approach. |
| title | Automata for the commutative closure of regular sets |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2504.10864 |