On Shuffling and Splitting Automata
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913415839088640 |
|---|---|
| author | Cunningham, Ignacio Mollo |
| author_facet | Cunningham, Ignacio Mollo |
| contents | We consider a class of finite state three-tape transducers which models the operation of shuffling and splitting words. We present them as automata over the so-called Shuffling Monoid. These automata can be seen as either shufflers or splitters interchangeably. We prove that functionality is decidable for splitters, and we also show that the equivalence between functional splitters is decidable. Moreover, in the deterministic case, the algorithm for equivalence is polynomial on the number of states of the splitter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_02660 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Shuffling and Splitting Automata Cunningham, Ignacio Mollo Formal Languages and Automata Theory We consider a class of finite state three-tape transducers which models the operation of shuffling and splitting words. We present them as automata over the so-called Shuffling Monoid. These automata can be seen as either shufflers or splitters interchangeably. We prove that functionality is decidable for splitters, and we also show that the equivalence between functional splitters is decidable. Moreover, in the deterministic case, the algorithm for equivalence is polynomial on the number of states of the splitter. |
| title | On Shuffling and Splitting Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2407.02660 |