Nominal Topology for Data Languages

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, a form of nominal topological spaces generalizing classical profinite spaces. Assuming globally bounded support sizes of the underlying nominal sets, which correspond to bounds on the number of registers of automata, pro-orbit-finite nominal topological spaces coincide with nominal Stone spaces and are shown to be dually equivalent to a suitable 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 and provide a nominal version of Reiterman’s pseudovariety theorem. This talk is based on joint work with Fabian Birkmann and Stefan Milius, presented at ICALP 2023. Contributed talk given by Henning Urbat Coffee Break Thursday 16h00 - 17h00, Special Session | HS 3 | "Open Problems Tools and Experiments" Friday Friday 09h00 - 10h00, Keynote Speaker | HS 3 | chair: Slawek Lasota | Meena Mahajan - Quantified Boolean Formulas and Proof Complexity For several years, both proof complexity and practical solving focussed on propositional proof systems and detecting (un)satisfiability. In the last two decades, several proof systems for the more succinct Quantified Boolean Formulas QBFs have been proposed and studied, and several QBF solvers have been developed. This talk will give an overview of what has been achieved in QBF proof complexity, and how (if at all) it informs QBF solving. Coffee Break Friday 10h30 - 11h42, Contributed Talks Probabilistic and Timed Systems | HS 3 | chair: Michael Cadilhac Games 3 | HS 4 | chair: Maximilian P. Weininger Probabilistic and Timed Systems | HS 3 | chair: Michael Cadilhac Games 3 | HS 4 | chair: Maximilian P. Weininger

Authors

• Henning Urbat

Keywords

No keywords are indexed for this paper.