Two or three things I know about tree transducers
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929495830691840 |
|---|---|
| author | Nguyên, Lê Thành Dũng |
| author_facet | Nguyên, Lê Thành Dũng |
| contents | You might know that the name "tree transducers" refers to various kinds of automata that compute functions on ranked trees, i.e. terms over a first-order signature.
But have you ever wondered about how to remember what a macro tree transducer does? Or what are the connections between top-down tree(-to-string) transducers, multi bottom-up tree(-to-string) transducers, tree-walking transducers, (invisible) pebble tree transducers, monadic second-order transductions, unfoldings of rooted directed acyclic graphs (i.e. term graphs) -- and what happens when the functions that they compute are composed?
The answers may be found in old papers (mostly coauthored by Engelfriet), but maybe you can save some time by first looking at this short note. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03169 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Two or three things I know about tree transducers Nguyên, Lê Thành Dũng Formal Languages and Automata Theory You might know that the name "tree transducers" refers to various kinds of automata that compute functions on ranked trees, i.e. terms over a first-order signature. But have you ever wondered about how to remember what a macro tree transducer does? Or what are the connections between top-down tree(-to-string) transducers, multi bottom-up tree(-to-string) transducers, tree-walking transducers, (invisible) pebble tree transducers, monadic second-order transductions, unfoldings of rooted directed acyclic graphs (i.e. term graphs) -- and what happens when the functions that they compute are composed? The answers may be found in old papers (mostly coauthored by Engelfriet), but maybe you can save some time by first looking at this short note. |
| title | Two or three things I know about tree transducers |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2409.03169 |