Polyregular functions

I will describe a class of string-to-string functions, called the polyregular functions. These functions admit numerous equivalent descriptions: (a) automata with pebbles; (b) a fragment of lambda calculus; (c) a fragment of for-programs; (d) compositions of certain atomic functions, such as reverse or a form of string squaring; and (e) string-to-string interpretations definable in monadic second-order logic.

Authors

• Mikolaj Bojanczyk.

Keywords

No keywords are indexed for this paper.