Nominal Topology for Data Languages
This work addresses foundational issues in theoretical computer science for researchers studying automata and formal languages, but it appears incremental as it extends existing topological and algebraic frameworks to the nominal setting.
The paper tackles the problem of characterizing recognizable data languages by proposing a topological perspective using pro-orbit-finite nominal topological spaces, showing they coincide with nominal Stone spaces under certain conditions and establishing dual equivalences and a nominal version of Reiterman's theorem.
We propose a novel topological perspective on data languages recognizable by orbit-finite nominal monoids. For this purpose, we introduce pro-orbit-finite nominal topological spaces. Assuming globally bounded support sizes, they coincide with nominal Stone spaces and are shown to be dually equivalent to a subcategory of nominal boolean algebras. Recognizable data languages are characterized as topologically clopen sets of pro-orbit-finite words. In addition, we explore the expressive power of pro-orbit-finite equations by establishing a nominal version of Reiterman's pseudovariety theorem.