From Compactifying Lambda-Letrec Terms to Recognizing Regular-Expression Processes
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913525223391232 |
|---|---|
| author | Grabmayer, Clemens |
| author_facet | Grabmayer, Clemens |
| contents | As a supplement to my talk at the workshop, this extended abstract motivates and summarizes my work with co-authors on problems in two separate areas: first, in the lambda-calculus with letrec, a universal model of computation, and second, on Milner's process interpretation of regular expressions, a proper subclass of the finite-state processes. The aim of my talk was to motivate a transferal of ideas for workable concepts of structure-constrained graphs: from the problem of finding compact graph representations for terms in the lambda-calculus with letrec to the problem of recognizing finite process graphs that can be expressed by regular expressions. In both cases the construction of structure-constrained graphs was expedient in order to enable to go back and forth easily between, in the first case, lambda-terms and term graphs, and in the second case, regular expressions and process graphs.
The main focus here is on providing pointers to my work with co-authors, in both areas separately. A secondary focus is on explaining directions of my present projects, and describing research questions of possibly general interest that have developed out of my work in these two areas. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_00538 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | From Compactifying Lambda-Letrec Terms to Recognizing Regular-Expression Processes Grabmayer, Clemens Logic in Computer Science Formal Languages and Automata Theory F.4.1; F1.1; I.2.2 As a supplement to my talk at the workshop, this extended abstract motivates and summarizes my work with co-authors on problems in two separate areas: first, in the lambda-calculus with letrec, a universal model of computation, and second, on Milner's process interpretation of regular expressions, a proper subclass of the finite-state processes. The aim of my talk was to motivate a transferal of ideas for workable concepts of structure-constrained graphs: from the problem of finding compact graph representations for terms in the lambda-calculus with letrec to the problem of recognizing finite process graphs that can be expressed by regular expressions. In both cases the construction of structure-constrained graphs was expedient in order to enable to go back and forth easily between, in the first case, lambda-terms and term graphs, and in the second case, regular expressions and process graphs. The main focus here is on providing pointers to my work with co-authors, in both areas separately. A secondary focus is on explaining directions of my present projects, and describing research questions of possibly general interest that have developed out of my work in these two areas. |
| title | From Compactifying Lambda-Letrec Terms to Recognizing Regular-Expression Processes |
| topic | Logic in Computer Science Formal Languages and Automata Theory F.4.1; F1.1; I.2.2 |
| url | https://arxiv.org/abs/2410.00538 |