Polyregular equivalence is undecidable in higher-order types

Mikołaj Bojańczyk, Grzegorz Fabiański, Rafał Stefański

It is open whether equivalence ( f = g ) is decidable for string-to-string polyregular functions. We consider their higher-order extension based on the λ-calculus definition of pol…