Conference Paper/Proceeding/Abstract 629 views 47 downloads
Comparison-Free Polyregular Functions.
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Volume: 198, Pages: 139:1 - 139:20
Swansea University Author:
Cécilia Pradic
-
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)
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...
| 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| 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 λ-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. |
|---|---|
| Item Description: |
https://drops.dagstuhl.de/opus/volltexte/2021/14208/ |
| Keywords: |
pebble transducers, HDT0L systems, polyregular functions |
| College: |
Faculty of Science and Engineering |
| Funders: |
French ANR project CoGITARe (ANR-18-CE25-0001) |
| Start Page: |
139:1 |
| End Page: |
139:20 |