The polyregular functions are a class of string-to-string functions that have polynomial size
outputs, and which can be defined using finite state models. There are many equivalent …

String-to-string MSO interpretations are like Courcelle's MSO transductions, except that a
single output position can be represented using a tuple of input positions instead of just a …

Regular word transductions extend the robust notion of regular languages from a qualitative
to a quantitative reasoning. They were already considered in early papers of formal …

Our starting point are register automata for data words, in the style of Kaminski and Francez.
We study the effects of the single-use restriction, which says that a register is emptied …

We consider polyregular functions, which are certain string-to-string functions that have
polynomial output size. We prove that a polyregular function has output size O(n^k) if and …

In real-time decision making and runtime monitoring applications, declarative languages are
commonly used as they facilitate modular high-level specifications with the compiler …

We show that a polyregular word-to-word function is regular if and only its output size is at
most linear in its input size. Moreover a polyregular function can be realized by: a transducer …

We prove a characterization of first-order string-to-string transduction via $\lambda $-terms
typed in non-commutative affine logic that compute with Church encoding, extending the …

We study the polyregular string-to-string functions, which are certain functions of polynomial
output size that can be described using automata and logic. We describe a system of …

This paper introduces a new automata-theoretic class of string-to-string functions with
polynomial growth. Several equivalent definitions are provided: a machine model which is a …