Boolean monadic recursive schemes as a logical characterization of the subsequential functions

Siddharth Bhaskar; Jane Chandlee; Adam Jardine; Christopher Oakden

doi:10.1007/978-3-030-40608-0_10

Boolean monadic recursive schemes as a logical characterization of the subsequential functions

Siddharth Bhaskar, Jane Chandlee, Adam Jardine, Christopher Oakden

School of Arts and Sciences, Linguistics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

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.

Original language	English (US)
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
Publisher	Springer
Pages	157-169
Number of pages	13
ISBN (Print)	9783030406073
DOIs	https://doi.org/10.1007/978-3-030-40608-0_10
State	Published - 2020
Event	14th International Conference on Language and Automata Theory and Applications, LATA 2020 - Milan, Italy Duration: Mar 4 2020 → Mar 6 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12038 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Language and Automata Theory and Applications, LATA 2020
Country/Territory	Italy
City	Milan
Period	3/4/20 → 3/6/20

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Keywords

Finite automata
Logic
Recursive program schemes
Subsequential functions

Access to Document

10.1007/978-3-030-40608-0_10

Cite this

Bhaskar, S., Chandlee, J., Jardine, A., & Oakden, C. (2020). Boolean monadic recursive schemes as a logical characterization of the subsequential functions. In A. Leporati, C. Martín-Vide, D. Shapira, & C. Zandron (Eds.), Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings (pp. 157-169). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12038 LNCS). Springer. https://doi.org/10.1007/978-3-030-40608-0_10

Bhaskar, Siddharth ; Chandlee, Jane ; Jardine, Adam et al. / Boolean monadic recursive schemes as a logical characterization of the subsequential functions. Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings. editor / Alberto Leporati ; Carlos Martín-Vide ; Dana Shapira ; Claudio Zandron. Springer, 2020. pp. 157-169 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6fac18a7181a4a168958decc3c3a0ac3,

title = "Boolean monadic recursive schemes as a logical characterization of the subsequential functions",

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 = "Finite automata, Logic, Recursive program schemes, Subsequential functions",

author = "Siddharth Bhaskar and Jane Chandlee and Adam Jardine and Christopher Oakden",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; 14th International Conference on Language and Automata Theory and Applications, LATA 2020 ; Conference date: 04-03-2020 Through 06-03-2020",

year = "2020",

doi = "10.1007/978-3-030-40608-0_10",

language = "English (US)",

isbn = "9783030406073",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "157--169",

editor = "Alberto Leporati and Carlos Mart{\'i}n-Vide and Dana Shapira and Claudio Zandron",

booktitle = "Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings",

}

Bhaskar, S, Chandlee, J, Jardine, A & Oakden, C 2020, Boolean monadic recursive schemes as a logical characterization of the subsequential functions. in A Leporati, C Martín-Vide, D Shapira & C Zandron (eds), Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12038 LNCS, Springer, pp. 157-169, 14th International Conference on Language and Automata Theory and Applications, LATA 2020, Milan, Italy, 3/4/20. https://doi.org/10.1007/978-3-030-40608-0_10

Boolean monadic recursive schemes as a logical characterization of the subsequential functions. / Bhaskar, Siddharth; Chandlee, Jane; Jardine, Adam et al.

Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings. ed. / Alberto Leporati; Carlos Martín-Vide; Dana Shapira; Claudio Zandron. Springer, 2020. p. 157-169 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12038 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Boolean monadic recursive schemes as a logical characterization of the subsequential functions

AU - Bhaskar, Siddharth

AU - Chandlee, Jane

AU - Jardine, Adam

AU - Oakden, Christopher

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

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

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

KW - Finite automata

KW - Logic

KW - Recursive program schemes

KW - Subsequential functions

UR - http://www.scopus.com/inward/record.url?scp=85081553260&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85081553260&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-40608-0_10

DO - 10.1007/978-3-030-40608-0_10

M3 - Conference contribution

AN - SCOPUS:85081553260

SN - 9783030406073

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 157

EP - 169

BT - Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings

A2 - Leporati, Alberto

A2 - Martín-Vide, Carlos

A2 - Shapira, Dana

A2 - Zandron, Claudio

PB - Springer

T2 - 14th International Conference on Language and Automata Theory and Applications, LATA 2020

Y2 - 4 March 2020 through 6 March 2020

ER -

Bhaskar S, Chandlee J, Jardine A, Oakden C. Boolean monadic recursive schemes as a logical characterization of the subsequential functions. In Leporati A, Martín-Vide C, Shapira D, Zandron C, editors, Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings. Springer. 2020. p. 157-169. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-40608-0_10

Boolean monadic recursive schemes as a logical characterization of the subsequential functions

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this