In this repository you will find a paper, titled "Some attribute grammars are register transducers". This paper was written as part of the course "Research Project 2" in the first semester of the 2021-2022 academic year at the University of Antwerp.
There exist many formalisms that are suited for computing regular string functions, among which are the register transducers. In this paper we propose that attribute grammars are also capable of computing these functions, and we exactly define the class of attribute grammars that are as expressive as the class of register transducers. Additionally, we propose a method to translate register transducers into attribute grammars and a method to perform the reverse translation. Finally, we argue that our findings make regular functions more accessible and that attribute grammars are very expressive and under-studied.
- Section 1: Introduction
- Section 2: Preliminaries
- Section 3: Correspondence of register transducers and L-attributed regular grammars
- Section 4: Future work
- Section 5: Conclusions