The single-use restriction for register automata and transducers over infinite alphabets
<|reference_start|>The single-use restriction for register automata and transducers over infinite alphabets: 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.<|reference_end|>
@article{stefański2024the,
    title={The single-use restriction for register automata and transducers over
  infinite alphabets},
    author={Rafa{l} Stefa'nski},
    journal={arXiv preprint arXiv:2406.18934},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.18934},
    primaryClass={cs.FL cs.CL}
}