The expressive power of one variable used once: The chomsky hierarchy and first-order monadic constructor rewriting
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- The Expressive Power of One Variable Used Once
Final published version, 694 KB, PDF document
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.
| Original language | English |
|---|---|
| Title of host publication | 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021 |
| Editors | Naoki Kobayashi |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Publication date | 2021 |
| Article number | 5 |
| ISBN (Electronic) | 9783959771917 |
| DOIs | |
| Publication status | Published - 2021 |
| Event | 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021 - Virtual, Buenos Aires, Argentina Duration: 17 Jul 2021 → 24 Jul 2021 |
Conference
| Conference | 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021 |
|---|---|
| Land | Argentina |
| By | Virtual, Buenos Aires |
| Periode | 17/07/2021 → 24/07/2021 |
| Series | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 195 |
| ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© 2021 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
- Chomsky Hierarchy, Constructor term rewriting, Implicit Complexity
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
No data available
ID: 281991639