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
_version_ 1783530447840477184
author Bhaskar, Siddharth
Chandlee, Jane
Jardine, Adam
Oakden, Christopher
author_facet Bhaskar, Siddharth
Chandlee, Jane
Jardine, Adam
Oakden, Christopher
author_sort Bhaskar, Siddharth
collection PubMed
description 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.
format Online
Article
Text
id pubmed-7206634
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72066342020-05-08 Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions Bhaskar, Siddharth Chandlee, Jane Jardine, Adam Oakden, Christopher Language and Automata Theory and Applications Article 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. 2020-01-07 /pmc/articles/PMC7206634/ http://dx.doi.org/10.1007/978-3-030-40608-0_10 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Bhaskar, Siddharth
Chandlee, Jane
Jardine, Adam
Oakden, Christopher
Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions
title Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions
title_full Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions
title_fullStr Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions
title_full_unstemmed Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions
title_short Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions
title_sort boolean monadic recursive schemes as a logical characterization of the subsequential functions
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206634/
http://dx.doi.org/10.1007/978-3-030-40608-0_10
work_keys_str_mv AT bhaskarsiddharth booleanmonadicrecursiveschemesasalogicalcharacterizationofthesubsequentialfunctions
AT chandleejane booleanmonadicrecursiveschemesasalogicalcharacterizationofthesubsequentialfunctions
AT jardineadam booleanmonadicrecursiveschemesasalogicalcharacterizationofthesubsequentialfunctions
AT oakdenchristopher booleanmonadicrecursiveschemesasalogicalcharacterizationofthesubsequentialfunctions

Ejemplares similares