Boolean monadic recursive schemes as a logical characterization of the subsequential functions
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
This paper defines boolean monadic recursive schemes (BMRSs), a restriction on recursive programs, and shows that when interpreted as transductions on strings they describe exactly the subsequential functions. We discuss how this new result furthers the study of the connections between logic, formal languages and functions, and automata.
Original language | English |
---|---|
Title of host publication | Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings |
Editors | Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron |
Number of pages | 13 |
Publisher | Springer VS |
Publication date | 2020 |
Pages | 157-169 |
ISBN (Print) | 9783030406073 |
DOIs | |
Publication status | Published - 2020 |
Event | 14th International Conference on Language and Automata Theory and Applications, LATA 2020 - Milan, Italy Duration: 4 Mar 2020 → 6 Mar 2020 |
Conference
Conference | 14th International Conference on Language and Automata Theory and Applications, LATA 2020 |
---|---|
Land | Italy |
By | Milan |
Periode | 04/03/2020 → 06/03/2020 |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12038 LNCS |
ISSN | 0302-9743 |
- Finite automata, Logic, Recursive program schemes, Subsequential functions
Research areas
ID: 258666397