Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Bhaskar, Siddharth, Chandlee, Jane, Jardine, Adam, Oakden, Christopher
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206634/
http://dx.doi.org/10.1007/978-3-030-40608-0_10
Descripción
Sumario: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.

Ejemplares similares