Skip to content

A paper on the topic of automata theory I wrote for a research intership at the University of Antwerp.

Notifications You must be signed in to change notification settings

kasperengelen/Grammars-and-Transducers

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 

Repository files navigation

Some attribute grammars are register transducers

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.

Abstract

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.

Paper contents

  • Section 1: Introduction
  • Section 2: Preliminaries
  • Section 3: Correspondence of register transducers and L-attributed regular grammars
  • Section 4: Future work
  • Section 5: Conclusions

About

A paper on the topic of automata theory I wrote for a research intership at the University of Antwerp.

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published