Standard
The expressive power of one variable used once : The chomsky hierarchy and first-order monadic constructor rewriting. / Simonsen, Jakob Grue.
6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021. red. / Naoki Kobayashi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. 5 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 195).
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
Simonsen, JG 2021,
The expressive power of one variable used once: The chomsky hierarchy and first-order monadic constructor rewriting. i N Kobayashi (red.),
6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021., 5, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, bind 195, 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021, Virtual, Buenos Aires, Argentina,
17/07/2021.
https://doi.org/10.4230/LIPIcs.FSCD.2021.5
APA
Simonsen, J. G. (2021).
The expressive power of one variable used once: The chomsky hierarchy and first-order monadic constructor rewriting. I N. Kobayashi (red.),
6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021 [5] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Bind 195
https://doi.org/10.4230/LIPIcs.FSCD.2021.5
Vancouver
Simonsen JG.
The expressive power of one variable used once: The chomsky hierarchy and first-order monadic constructor rewriting. I Kobayashi N, red., 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2021. 5. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 195).
https://doi.org/10.4230/LIPIcs.FSCD.2021.5
Author
Simonsen, Jakob Grue. / The expressive power of one variable used once : The chomsky hierarchy and first-order monadic constructor rewriting. 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021. red. / Naoki Kobayashi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 195).
Bibtex
@inproceedings{6a0a61ae4d644b26a8e921c12933ab28,
title = "The expressive power of one variable used once: The chomsky hierarchy and first-order monadic constructor rewriting",
abstract = "We study the implicit computational complexity of constructor term rewriting systems where every function and constructor symbol is unary or nullary. Surprisingly, adding simple and natural constraints to rule formation yields classes of systems that accept exactly the four classes of languages in the Chomsky hierarchy.",
keywords = "Chomsky Hierarchy, Constructor term rewriting, Implicit Complexity",
author = "Simonsen, {Jakob Grue}",
note = "Publisher Copyright: {\textcopyright} 2021 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021 ; Conference date: 17-07-2021 Through 24-07-2021",
year = "2021",
doi = "10.4230/LIPIcs.FSCD.2021.5",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Naoki Kobayashi",
booktitle = "6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021",
}
RIS
TY - GEN
T1 - The expressive power of one variable used once
T2 - 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021
AU - Simonsen, Jakob Grue
N1 - Publisher Copyright:
© 2021 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2021
Y1 - 2021
N2 - We study the implicit computational complexity of constructor term rewriting systems where every function and constructor symbol is unary or nullary. Surprisingly, adding simple and natural constraints to rule formation yields classes of systems that accept exactly the four classes of languages in the Chomsky hierarchy.
AB - We study the implicit computational complexity of constructor term rewriting systems where every function and constructor symbol is unary or nullary. Surprisingly, adding simple and natural constraints to rule formation yields classes of systems that accept exactly the four classes of languages in the Chomsky hierarchy.
KW - Chomsky Hierarchy
KW - Constructor term rewriting
KW - Implicit Complexity
UR - http://www.scopus.com/inward/record.url?scp=85115264748&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FSCD.2021.5
DO - 10.4230/LIPIcs.FSCD.2021.5
M3 - Article in proceedings
AN - SCOPUS:85115264748
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021
A2 - Kobayashi, Naoki
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 17 July 2021 through 24 July 2021
ER -
