works on
automata theory 1communication complexity 1functions over arbitrary domains 1nerode theorem 1nominal sets 1regular languages 1

From the 1 of 3 linked papers with an AI index.

collaborators
Showing cs.PLShow all

1 paper · 1 filter

cs.PL2026

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 po…