Boolean monadic recursive schemes as a logical characterization of the subsequential functions
Document Type
Conference Proceeding
Role
Contributor
Published In
Proceedings of the 14th International Conference on Language and Automata Theory and Applications (LATA 2020)
Publisher
Springer
First Page
157
Last Page
169
Publication Date
2-2020
Abstract
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.
Keywords
Algebraic Logic, Computability and Recursion Theory, Formal Languages and, Automata Theory, Formal Logic, Linear Logic, Symbolic and Algebraic Manipulation, Automata Theory and Formal Languages
Suggested Citation
Bhaskar, S., et al. (2020). "Boolean monadic recursive schemes as a logical characterization of the subsequential functions." In Proceedings of the 14th International Conference on Language and Automata Theory and Applications (LATA 2020), edited by A. Leporati, C. Martin-Vide, D. Shapira, and C. Zandron (Springer). https://doi.org/10.1007/978-3-030-40608-0_10
