@inproceedings{10.1145/3531130.3533326,
    Abstract = {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 definitions of this class, with roots in automata theory, programming languages and logic. This paper surveys recent results on polyregular functions. It presents five of the equivalent definitions, and gives self-contained proofs for most of the equivalences. Decision problems as well as restricted subclasses of the polyregular functions are also discussed.},
    Address = {New York, NY, USA},
    Author = {Bojanczyk, Mikolaj},
    BookTitle = {Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science},
    File = {Transducers of polynomial growth - 3531130.3533326.pdf},
    ISBN = {9781450393515},
    Location = {Haifa, Israel},
    Publisher = {Association for Computing Machinery},
    Series = {LICS '22},
    Title = {Transducers of Polynomial Growth},
    URL = {https://doi.org/10.1145/3531130.3533326},
    Year = {2022},
    articleno = {1},
    bdsk-url-1 = {https://doi.org/10.1145/3531130.3533326},
    date-added = {2022-08-09 11:11:36 +0200},
    date-modified = {2022-08-09 11:11:36 +0200},
    numpages = {27},
    doi = {10.1145/3531130.3533326}
}

@inproceedings{10.1145/3531130.3533326, Abstract = {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 definitions of this class, with roots in automata theory, programming languages and logic. This paper surveys recent results on polyregular functions. It presents five of the equivalent definitions, and gives self-contained proofs for most of the equivalences. Decision problems as well as restricted subclasses of the polyregular functions are also discussed.}, Address = {New York, NY, USA}, Author = {Bojanczyk, Mikolaj}, BookTitle = {Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science}, File = {Transducers of polynomial growth - 3531130.3533326.pdf}, ISBN = {9781450393515}, Location = {Haifa, Israel}, Publisher = {Association for Computing Machinery}, Series = {LICS '22}, Title = {Transducers of Polynomial Growth}, URL = {https://doi.org/10.1145/3531130.3533326}, Year = {2022}, articleno = {1}, bdsk-url-1 = {https://doi.org/10.1145/3531130.3533326}, date-added = {2022-08-09 11:11:36 +0200}, date-modified = {2022-08-09 11:11:36 +0200}, numpages = {27}, doi = {10.1145/3531130.3533326} }