Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.61
URN: urn:nbn:de:0030-drops-110053
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11005/
Lhote, Nathan ; Michielini, Vincent ; Skrzypczak, Michal
Uniformisation Gives the Full Strength of Regular Languages
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{lhote_et_al:LIPIcs:2019:11005,
author = {Nathan Lhote and Vincent Michielini and Michal Skrzypczak},
title = {{Uniformisation Gives the Full Strength of Regular Languages}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {61:1--61:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-117-7},
ISSN = {1868-8969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11005},
URN = {urn:nbn:de:0030-drops-110053},
doi = {10.4230/LIPIcs.MFCS.2019.61},
annote = {Keywords: pseudo-variety, finite word, semigroup, uniformisation, regular language}
}
| Keywords: | pseudo-variety, finite word, semigroup, uniformisation, regular language | |
| Seminar: | 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 20.08.2019 |
