The expressive power of one variable used once: The chomsky hierarchy and first-order monadic constructor rewriting
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- The Expressive Power of One Variable Used Once
Forlagets udgivne version, 694 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021 |
Redaktører | Naoki Kobayashi |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2021 |
Artikelnummer | 5 |
ISBN (Elektronisk) | 9783959771917 |
DOI | |
Status | Udgivet - 2021 |
Begivenhed | 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021 - Virtual, Buenos Aires, Argentina Varighed: 17 jul. 2021 → 24 jul. 2021 |
Konference
Konference | 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 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 195 |
ISSN | 1868-8969 |
Bibliografisk note
Publisher Copyright:
© 2021 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
Ingen data tilgængelig
ID: 281991639