A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Universal gates with wires in a row
Tekijät: Salo Ville
Kustantaja: Springer
Julkaisuvuosi: 2022
Journal: Journal of Algebraic Combinatorics
Lehden akronyymi: J ALGEBR COMB
Vuosikerta: 55
Numero: 2
Aloitussivu: 335
Lopetussivu: 353
Sivujen määrä: 19
ISSN: 0925-9899
eISSN: 1572-9192
DOI: https://doi.org/10.1007/s10801-021-01053-7
Verkko-osoite: https://link.springer.com/article/10.1007%2Fs10801-021-01053-7
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/67531805
Tiivistelmä
We give some optimal size generating sets for the group generated by shifts and local permutations on the binary full shift. We show that a single generator, namely the fully asynchronous application of the elementary cellular automaton 57 (or, by symmetry, ECA 99), suffices in addition to the shift. In the terminology of logical gates, we have a single reversible gate whose shifts generate all (finitary) reversible gates on infinitely many binary-valued wires that lie in a row and cannot (a priori) be rearranged. We classify pairs of words u, v such that the gate swapping these two words, together with the shift and the bit flip, generates all local permutations. As a corollary, we obtain analogous results in the case where the wires are arranged on a cycle, confirming a conjecture of Macauley-McCammond-Mortveit and Vielhaber.
We give some optimal size generating sets for the group generated by shifts and local permutations on the binary full shift. We show that a single generator, namely the fully asynchronous application of the elementary cellular automaton 57 (or, by symmetry, ECA 99), suffices in addition to the shift. In the terminology of logical gates, we have a single reversible gate whose shifts generate all (finitary) reversible gates on infinitely many binary-valued wires that lie in a row and cannot (a priori) be rearranged. We classify pairs of words u, v such that the gate swapping these two words, together with the shift and the bit flip, generates all local permutations. As a corollary, we obtain analogous results in the case where the wires are arranged on a cycle, confirming a conjecture of Macauley-McCammond-Mortveit and Vielhaber.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali