Polyregular Functions

The polyregular functions are string-to-string functions that have polynomial size outputs, and which can be computed by finite-state devices. This class of functions can be described using many different models that pop up in different areas, and its seems to be a plausible (unique?) candidate for the notion of regularity for functions that have polynomial outputs size. I will report on some recent progress on this topic, regarding questions about the expressive power, as well as some algorithmic problems.

Authors

• Mikołaj Bojańczyk

Keywords

No keywords are indexed for this paper.