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

String-to-String Interpretations With Polynomial-Size Output

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:34:39Z
dc.abstract.enString-to-string MSO interpretations are like Courcelle's MSO transductions, except that a single output position can be represented using a tuple of input positions instead of just a single input position. In particular, the output length is polynomial in the input length, as opposed to MSO transductions, which have output of linear length. We show that string-to-string MSO interpretations are exactly the polyregular functions. The latter class has various characterisations, one of which is that it consists of the string-to-string functions recognised by pebble transducers. Our main result implies the surprising fact that string-to-string MSO interpretations are closed under composition.
dc.affiliationUniwersytet Warszawski
dc.conference.countryGrecja
dc.conference.datefinish2019-07-12
dc.conference.datestart2019-07-08
dc.conference.placePatras
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2019
dc.conference.weblinkhttps://icalp2019.upatras.gr/
dc.contributor.authorLhote, Nathan
dc.contributor.authorBojańczyk, Mikołaj
dc.contributor.authorKiefer, Sandra
dc.date.accessioned2024-01-26T08:20:37Z
dc.date.available2024-01-26T08:20:37Z
dc.date.copyright2019-07-04
dc.date.issued2019
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.ICALP.2019.106
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/120838
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2019/10682/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages106:1--106:14
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleString-to-String Interpretations With Polynomial-Size Output
dc.typeJournalArticle
dspace.entity.typePublication