No Cover Image

Conference Paper/Proceeding/Abstract 82 views

Implicit automata in λ-calculi III: affine planar string-to-string functions

Cécilia Pradic Orcid Logo, Ian Price

Mathematical Foundations of Programming Semantics 2024

Swansea University Authors: Cécilia Pradic Orcid Logo, Ian Price

Abstract

We prove a characterization of first-order string-to-string transduction via λ-terms typed in non-commutative affine logic that compute with Church encoding, extending the analogous known characterization of star-free languages. We show that every first-order transduction can be computed by a λ-term...

Full description

Published in: Mathematical Foundations of Programming Semantics 2024
Published: Oxford 2024
URI: https://cronfa.swan.ac.uk/Record/cronfa68303
first_indexed 2024-11-25T14:21:49Z
last_indexed 2024-12-11T14:17:03Z
id cronfa68303
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2024-12-11T10:19:07.8919127</datestamp><bib-version>v2</bib-version><id>68303</id><entry>2024-11-19</entry><title>Implicit automata in &#x3BB;-calculi III: affine planar string-to-string 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><author><sid>bdc2b56a25bb7272cbbfdb189e5402d6</sid><firstname>Ian</firstname><surname>Price</surname><name>Ian Price</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2024-11-19</date><deptcode>MACS</deptcode><abstract>We prove a characterization of first-order string-to-string transduction via &#x3BB;-terms typed in non-commutative affine logic that compute with Church encoding, extending the analogous known characterization of star-free languages. We show that every first-order transduction can be computed by a &#x3BB;-term using a known Krohn-Rhodes-style decomposition lemma. The converse direction is given by compiling &#x3BB;-terms into two-way reversible planar transducers. The soundness of this translation involves showing that the transition functions of those transducers live in a monoidal closed category of diagrams in which we can interpret purely affine &#x3BB;-terms. One challenge is that the unit of the tensor of the category in question is not a terminal object. As a result, our interpretation does not identify &#x3B2;-equivalent terms, but it does turn &#x3B2;-reductions into inequalities in a poset-enrichment of the category of diagrams.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>Mathematical Foundations of Programming Semantics 2024</journal><volume/><journalNumber/><paginationStart/><paginationEnd/><publisher/><placeOfPublication>Oxford</placeOfPublication><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords/><publishedDay>7</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2024</publishedYear><publishedDate>2024-12-07</publishedDate><doi/><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2024-12-11T10:19:07.8919127</lastEdited><Created>2024-11-19T15:11:48.1332301</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>C&#xE9;cilia</firstname><surname>Pradic</surname><orcid>0000-0002-1600-8846</orcid><order>1</order></author><author><firstname>Ian</firstname><surname>Price</surname><order>2</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2024-12-11T10:19:07.8919127 v2 68303 2024-11-19 Implicit automata in λ-calculi III: affine planar string-to-string functions 3b6e9ebd791c875dac266b3b0b358a58 0000-0002-1600-8846 Cécilia Pradic Cécilia Pradic true false bdc2b56a25bb7272cbbfdb189e5402d6 Ian Price Ian Price true false 2024-11-19 MACS We prove a characterization of first-order string-to-string transduction via λ-terms typed in non-commutative affine logic that compute with Church encoding, extending the analogous known characterization of star-free languages. We show that every first-order transduction can be computed by a λ-term using a known Krohn-Rhodes-style decomposition lemma. The converse direction is given by compiling λ-terms into two-way reversible planar transducers. The soundness of this translation involves showing that the transition functions of those transducers live in a monoidal closed category of diagrams in which we can interpret purely affine λ-terms. One challenge is that the unit of the tensor of the category in question is not a terminal object. As a result, our interpretation does not identify β-equivalent terms, but it does turn β-reductions into inequalities in a poset-enrichment of the category of diagrams. Conference Paper/Proceeding/Abstract Mathematical Foundations of Programming Semantics 2024 Oxford 7 12 2024 2024-12-07 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2024-12-11T10:19:07.8919127 2024-11-19T15:11:48.1332301 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Cécilia Pradic 0000-0002-1600-8846 1 Ian Price 2
title Implicit automata in λ-calculi III: affine planar string-to-string functions
spellingShingle Implicit automata in λ-calculi III: affine planar string-to-string functions
Cécilia Pradic
Ian Price
title_short Implicit automata in λ-calculi III: affine planar string-to-string functions
title_full Implicit automata in λ-calculi III: affine planar string-to-string functions
title_fullStr Implicit automata in λ-calculi III: affine planar string-to-string functions
title_full_unstemmed Implicit automata in λ-calculi III: affine planar string-to-string functions
title_sort Implicit automata in λ-calculi III: affine planar string-to-string functions
author_id_str_mv 3b6e9ebd791c875dac266b3b0b358a58
bdc2b56a25bb7272cbbfdb189e5402d6
author_id_fullname_str_mv 3b6e9ebd791c875dac266b3b0b358a58_***_Cécilia Pradic
bdc2b56a25bb7272cbbfdb189e5402d6_***_Ian Price
author Cécilia Pradic
Ian Price
author2 Cécilia Pradic
Ian Price
format Conference Paper/Proceeding/Abstract
container_title Mathematical Foundations of Programming Semantics 2024
publishDate 2024
institution Swansea University
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
document_store_str 0
active_str 0
description We prove a characterization of first-order string-to-string transduction via λ-terms typed in non-commutative affine logic that compute with Church encoding, extending the analogous known characterization of star-free languages. We show that every first-order transduction can be computed by a λ-term using a known Krohn-Rhodes-style decomposition lemma. The converse direction is given by compiling λ-terms into two-way reversible planar transducers. The soundness of this translation involves showing that the transition functions of those transducers live in a monoidal closed category of diagrams in which we can interpret purely affine λ-terms. One challenge is that the unit of the tensor of the category in question is not a terminal object. As a result, our interpretation does not identify β-equivalent terms, but it does turn β-reductions into inequalities in a poset-enrichment of the category of diagrams.
published_date 2024-12-07T20:49:26Z
_version_ 1821440020608712704
score 11.047609

Similar Items