Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Uniformisation Gives the Full Strength of Regular Languages

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:05:12Z
dc.abstract.enGiven 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryNiemcy
dc.conference.datefinish2019-08-30
dc.conference.datestart2019-08-26
dc.conference.placeAachen
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesshortcutMFCS
dc.conference.shortcutMFCS 2019
dc.conference.weblinkhttps://tcs.rwth-aachen.de/mfcs2019/
dc.contributor.authorMichielini, Vincent
dc.contributor.authorLhote, Nathan
dc.contributor.authorSkrzypczak, Michał
dc.date.accessioned2024-01-26T11:19:27Z
dc.date.available2024-01-26T11:19:27Z
dc.date.copyright2019-08-20
dc.date.issued2019
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.versionFINAL_PUBLISHED
dc.description.volume138
dc.identifier.doi10.4230/LIPICS.MFCS.2019.61
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/124203
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2019/11005/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages61:1--61:13
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleUniformisation Gives the Full Strength of Regular Languages
dc.typeJournalArticle
dspace.entity.typePublication