# The single-use restriction for register automata and transducers over infinite alphabets

arXiv: https://arxiv.org/abs/2406.18934 · HTML: https://mlsanity.com/paper/2406.18934/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 53 references that are in the map.
- First posted on arXiv 27 Jun 2024.

## Builds on (most cited first, 2 of 2)

- [Folding interpretations](https://mlsanity.com/paper/2301.05101/) (2023)
- [Nominal Topology for Data Languages](https://mlsanity.com/paper/2304.13337/) (2023)

## Abstract (arXiv)

This thesis studies the single-use restriction for register automata and transducers over infinite alphabets. The restriction requires that a read-access to a register should have the side effect of destroying its contents. This constraint results in robust classes of languages and transductions. For automata models, we show that one-way register automata, two-way register automata, and orbit-finite monoids have the same expressive power. For transducer models, we show that single-use Mealy machines and single-use two-way transducers admit versions of the Krohn-Rhodes decomposition theorem. Moreover, single-use Mealy machines are equivalent to an algebraic model called local algebraic semigroup transductions. Additionally, we show that single-use two-way transducers are equivalent to single-use streaming string transducers (SSTs) over infinite alphabets and to regular list functions with atoms. Compared with the previous work arXiv:1907.10504, this thesis offers a coherent narrative on the single-use restriction. We introduce an abstract notion of single-use functions and use them to define all the discussed single-use models. We also introduce and study the algebraic models of local semigroup transduction and local rational semigroup transduction.