2026-07-21T14:18:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12738 2024-03-06T10:50:42Z ddc:004 open_access

Regular Choice Functions and Uniformisations For countable Domains Michielini, Vincent Skrzypczak, Michał Uniformisation Monadic Second-order logic Countable words We view languages of words over a product alphabet A x B as relations between words over A and words over B. This leads to the notion of regular relations - relations given by a regular language. We ask when it is possible to find regular uniformisations of regular relations. The answer depends on the structure or shape of the underlying model: it is true e.g. for ω-words, while false for words over ℤ or for infinite trees. In this paper we focus on countable orders. Our main result characterises, which countable linear orders D have the property that every regular relation between words over D has a regular uniformisation. As it turns out, the only obstacle for uniformisability is the one displayed in the case of ℤ - non-trivial automorphisms of the given structure. Thus, we show that either all regular relations over D have regular uniformisations, or there is a non-trivial automorphism of D and even the simple relation of choice cannot be uniformised. Moreover, this dichotomy is effective. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vincent Michielini and Michał Skrzypczak 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.69 urn:nbn:de:0030-drops-127386 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.69 eng https://creativecommons.org/licenses/by/3.0/legalcode