2026-07-20T05:13:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11005 2024-03-06T10:47:02Z ddc:004 open_access

Uniformisation Gives the Full Strength of Regular Languages Lhote, Nathan Michielini, Vincent Skrzypczak, Michał pseudo-variety finite word semigroup uniformisation regular language Given R a binary relation between words (which we treat as a language over a product alphabet AxB), a uniformisation of it is another relation L included in R which chooses a single word over B, for each word over A whenever there exists one. It is known that MSO, the full class of regular languages, is strong enough to define a uniformisation for each of its relations. The quest of this work is to see which other formalisms, weaker than MSO, also have this property. In this paper, we solve this problem for pseudo-varieties of semigroups: we show that no nonempty pseudo-variety weaker than MSO can provide uniformisations for its relations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathan Lhote and Vincent Michielini and Michał Skrzypczak 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.61 urn:nbn:de:0030-drops-110053 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.61 eng https://creativecommons.org/licenses/by/3.0/legalcode