No Cover Image

Journal article 542 views 45 downloads

Implicit Automata in λ-calculi III: Affine Planar String-to-string Functions

Cécilia Pradic Orcid Logo, Ian Price

Electronic Notes in Theoretical Informatics and Computer Science, Volume: Volume 4 - Proceedings of MFPS XL

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

  • 68303.VoR.pdf

    PDF | Version of Record

    Released under the terms of a Creative Commons Attribution 4.0 International (CC BY 4.0) license.

    Download (427.37KB)

Check full text

DOI (Published version): 10.46298/entics.14804

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: Electronic Notes in Theoretical Informatics and Computer Science
ISSN: 2969-2431
Published: Oxford Centre pour la Communication Scientifique Directe (CCSD) 2024
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa68303
first_indexed 2024-11-25T14:21:49Z
last_indexed 2025-06-28T07:48:52Z
id cronfa68303
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2025-06-27T12:10:27.4892903</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>Journal Article</type><journal>Electronic Notes in Theoretical Informatics and Computer Science</journal><volume>Volume 4 - Proceedings of MFPS XL</volume><journalNumber/><paginationStart/><paginationEnd/><publisher>Centre pour la Communication Scientifique Directe (CCSD)</publisher><placeOfPublication>Oxford</placeOfPublication><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic>2969-2431</issnElectronic><keywords>non-commutative linear logic, transducers, &#x3BB;-calculus, automata theory, Church encodings</keywords><publishedDay>11</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2024</publishedYear><publishedDate>2024-12-11</publishedDate><doi>10.46298/entics.14804</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>2025-06-27T12:10:27.4892903</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><document><filename>68303__34602__6f1d0b8cb9dc4bfb86f9ac7e4fd28959.pdf</filename><originalFilename>68303.VoR.pdf</originalFilename><uploaded>2025-06-26T20:21:44.6338638</uploaded><type>Output</type><contentLength>437628</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>Released under the terms of a Creative Commons Attribution 4.0 International (CC BY 4.0) license.</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2025-06-27T12:10:27.4892903 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. Journal Article Electronic Notes in Theoretical Informatics and Computer Science Volume 4 - Proceedings of MFPS XL Centre pour la Communication Scientifique Directe (CCSD) Oxford 2969-2431 non-commutative linear logic, transducers, λ-calculus, automata theory, Church encodings 11 12 2024 2024-12-11 10.46298/entics.14804 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2025-06-27T12:10:27.4892903 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 68303__34602__6f1d0b8cb9dc4bfb86f9ac7e4fd28959.pdf 68303.VoR.pdf 2025-06-26T20:21:44.6338638 Output 437628 application/pdf Version of Record true Released under the terms of a Creative Commons Attribution 4.0 International (CC BY 4.0) license. true eng https://creativecommons.org/licenses/by/4.0/
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 Journal article
container_title Electronic Notes in Theoretical Informatics and Computer Science
container_volume Volume 4 - Proceedings of MFPS XL
publishDate 2024
institution Swansea University
issn 2969-2431
doi_str_mv 10.46298/entics.14804
publisher Centre pour la Communication Scientifique Directe (CCSD)
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 1
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-11T17:44:17Z
_version_ 1850691192252006400
score 11.08899

Similar Items