No Cover Image

Conference Paper/Proceeding/Abstract 727 views 65 downloads

Comparison-Free Polyregular Functions.

Lê Thành Dũng (Tito) Nguyễn, Camille Noûs, Cécilia Pradic Orcid Logo

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Volume: 198, Pages: 139:1 - 139:20

Swansea University Author: Cécilia Pradic Orcid Logo

  • 57932.pdf

    PDF | Version of Record

    © Lê Thành Dũng (Tito) Nguyễn, Camille Noûs, and Pierre Pradic; licensed under Creative Commons License CC-BY 4.0

    Download (933.79KB)

Check full text

DOI (Published version): 10.4230/LIPIcs.ICALP.2021.139

Abstract

This paper introduces a new automata-theoretic class of string-to-string functions with polynomialgrowth. Several equivalent definitions are provided: a machine model which is a restricted variant ofpebble transducers, and a few inductive definitions that close the class of regular functions underce...

Full description

Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
ISBN: 978-3-95977-195-5
ISSN: 1868-8969
Published: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik 2021
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa57932
first_indexed 2021-09-21T08:55:57Z
last_indexed 2021-11-25T04:16:43Z
id cronfa57932
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2021-11-24T16:35:28.1954152</datestamp><bib-version>v2</bib-version><id>57932</id><entry>2021-09-16</entry><title>Comparison-Free Polyregular Functions.</title><swanseaauthors><author><sid>3b6e9ebd791c875dac266b3b0b358a58</sid><ORCID>0000-0002-1600-8846</ORCID><firstname>C&#xE9;cilia</firstname><surname>Pradic</surname><name>C&#xE9;cilia Pradic</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2021-09-16</date><deptcode>MACS</deptcode><abstract>This paper introduces a new automata-theoretic class of string-to-string functions with polynomialgrowth. Several equivalent definitions are provided: a machine model which is a restricted variant ofpebble transducers, and a few inductive definitions that close the class of regular functions undercertain operations. Our motivation for studying this class comes from another characterization,which we merely mention here but prove elsewhere, based on a &#x3BB;-calculus with a linear type system.As their name suggests, these comparison-free polyregular functions form a subclass of polyregularfunctions; we prove that the inclusion is strict. We also show that they are incomparable withHDT0L transductions, closed under usual function composition &#x2013; but not under a certain &#x201C;map&#x201D;combinator &#x2013; and satisfy a comparison-free version of the pebble minimization theorem.On the broader topic of polynomial growth transductions, we also consider the recently introducedlayered streaming string transducers (SSTs), or equivalently k-marble transducers. We prove that afunction can be obtained by composing such transducers together if and only if it is polyregular,and that k-layered SSTs (or k-marble transducers) are closed under &#x201C;map&#x201D; and equivalent to acorresponding notion of (k + 1)-layered HDT0L systems.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)</journal><volume>198</volume><journalNumber/><paginationStart>139:1</paginationStart><paginationEnd>139:20</paginationEnd><publisher>Schloss Dagstuhl -- Leibniz-Zentrum f&#xFC;r Informatik</publisher><placeOfPublication/><isbnPrint/><isbnElectronic>978-3-95977-195-5</isbnElectronic><issnPrint/><issnElectronic>1868-8969</issnElectronic><keywords>pebble transducers, HDT0L systems, polyregular functions</keywords><publishedDay>2</publishedDay><publishedMonth>7</publishedMonth><publishedYear>2021</publishedYear><publishedDate>2021-07-02</publishedDate><doi>10.4230/LIPIcs.ICALP.2021.139</doi><url>https://drops.dagstuhl.de/opus/volltexte/2021/14208/</url><notes>https://drops.dagstuhl.de/opus/volltexte/2021/14208/</notes><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm>Other</apcterm><funders>French ANR project CoGITARe (ANR-18-CE25-0001)</funders><lastEdited>2021-11-24T16:35:28.1954152</lastEdited><Created>2021-09-16T17:43:25.1372989</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>L&#xEA; Th&#xE0;nh D&#x169;ng (Tito)</firstname><surname>Nguy&#x1EC5;n</surname><order>1</order></author><author><firstname>Camille</firstname><surname>No&#xFB;s</surname><order>2</order></author><author><firstname>C&#xE9;cilia</firstname><surname>Pradic</surname><orcid>0000-0002-1600-8846</orcid><order>3</order></author></authors><documents><document><filename>57932__21034__808a843d4e2547c280bdea653bcdbfb3.pdf</filename><originalFilename>57932.pdf</originalFilename><uploaded>2021-09-28T15:09:01.8464884</uploaded><type>Output</type><contentLength>956199</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>&#xA9; L&#xEA; Th&#xE0;nh D&#x169;ng (Tito) Nguy&#x1EC5;n, Camille No&#xFB;s, and Pierre Pradic; licensed under Creative Commons License CC-BY 4.0</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2021-11-24T16:35:28.1954152 v2 57932 2021-09-16 Comparison-Free Polyregular Functions. 3b6e9ebd791c875dac266b3b0b358a58 0000-0002-1600-8846 Cécilia Pradic Cécilia Pradic true false 2021-09-16 MACS This paper introduces a new automata-theoretic class of string-to-string functions with polynomialgrowth. Several equivalent definitions are provided: a machine model which is a restricted variant ofpebble transducers, and a few inductive definitions that close the class of regular functions undercertain operations. Our motivation for studying this class comes from another characterization,which we merely mention here but prove elsewhere, based on a λ-calculus with a linear type system.As their name suggests, these comparison-free polyregular functions form a subclass of polyregularfunctions; we prove that the inclusion is strict. We also show that they are incomparable withHDT0L transductions, closed under usual function composition – but not under a certain “map”combinator – and satisfy a comparison-free version of the pebble minimization theorem.On the broader topic of polynomial growth transductions, we also consider the recently introducedlayered streaming string transducers (SSTs), or equivalently k-marble transducers. We prove that afunction can be obtained by composing such transducers together if and only if it is polyregular,and that k-layered SSTs (or k-marble transducers) are closed under “map” and equivalent to acorresponding notion of (k + 1)-layered HDT0L systems. Conference Paper/Proceeding/Abstract 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 198 139:1 139:20 Schloss Dagstuhl -- Leibniz-Zentrum für Informatik 978-3-95977-195-5 1868-8969 pebble transducers, HDT0L systems, polyregular functions 2 7 2021 2021-07-02 10.4230/LIPIcs.ICALP.2021.139 https://drops.dagstuhl.de/opus/volltexte/2021/14208/ https://drops.dagstuhl.de/opus/volltexte/2021/14208/ COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University Other French ANR project CoGITARe (ANR-18-CE25-0001) 2021-11-24T16:35:28.1954152 2021-09-16T17:43:25.1372989 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Lê Thành Dũng (Tito) Nguyễn 1 Camille Noûs 2 Cécilia Pradic 0000-0002-1600-8846 3 57932__21034__808a843d4e2547c280bdea653bcdbfb3.pdf 57932.pdf 2021-09-28T15:09:01.8464884 Output 956199 application/pdf Version of Record true © Lê Thành Dũng (Tito) Nguyễn, Camille Noûs, and Pierre Pradic; licensed under Creative Commons License CC-BY 4.0 true eng https://creativecommons.org/licenses/by/4.0/
title Comparison-Free Polyregular Functions.
spellingShingle Comparison-Free Polyregular Functions.
Cécilia Pradic
title_short Comparison-Free Polyregular Functions.
title_full Comparison-Free Polyregular Functions.
title_fullStr Comparison-Free Polyregular Functions.
title_full_unstemmed Comparison-Free Polyregular Functions.
title_sort Comparison-Free Polyregular Functions.
author_id_str_mv 3b6e9ebd791c875dac266b3b0b358a58
author_id_fullname_str_mv 3b6e9ebd791c875dac266b3b0b358a58_***_Cécilia Pradic
author Cécilia Pradic
author2 Lê Thành Dũng (Tito) Nguyễn
Camille Noûs
Cécilia Pradic
format Conference Paper/Proceeding/Abstract
container_title 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
container_volume 198
container_start_page 139:1
publishDate 2021
institution Swansea University
isbn 978-3-95977-195-5
issn 1868-8969
doi_str_mv 10.4230/LIPIcs.ICALP.2021.139
publisher Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url https://drops.dagstuhl.de/opus/volltexte/2021/14208/
document_store_str 1
active_str 0
description This paper introduces a new automata-theoretic class of string-to-string functions with polynomialgrowth. Several equivalent definitions are provided: a machine model which is a restricted variant ofpebble transducers, and a few inductive definitions that close the class of regular functions undercertain operations. Our motivation for studying this class comes from another characterization,which we merely mention here but prove elsewhere, based on a λ-calculus with a linear type system.As their name suggests, these comparison-free polyregular functions form a subclass of polyregularfunctions; we prove that the inclusion is strict. We also show that they are incomparable withHDT0L transductions, closed under usual function composition – but not under a certain “map”combinator – and satisfy a comparison-free version of the pebble minimization theorem.On the broader topic of polynomial growth transductions, we also consider the recently introducedlayered streaming string transducers (SSTs), or equivalently k-marble transducers. We prove that afunction can be obtained by composing such transducers together if and only if it is polyregular,and that k-layered SSTs (or k-marble transducers) are closed under “map” and equivalent to acorresponding notion of (k + 1)-layered HDT0L systems.
published_date 2021-07-02T14:13:15Z
_version_ 1821415094707290112
score 11.543985

Similar Items