Back to Search
Start Over
From Two-Way Transducers to Regular Function Expressions.
- Source :
-
International Journal of Foundations of Computer Science . Sep2020, Vol. 31 Issue 6, p843-873. 31p. - Publication Year :
- 2020
-
Abstract
- Transducers constitute a fundamental extension of automata. The class of regular word functions has recently emerged as an important class of word-to-word functions, characterized by means of (functional, or unambiguous, or deterministic) two-way transducers, copyless streaming string transducers, and MSO-definable graph transformations. A fundamental result in language theory is Kleene's Theorem, relating finite state automata and regular expressions. Recently, a set of regular function expressions has been introduced and used to prove a similar result for regular word functions, by showing its equivalence with copyless streaming string transducers. In this paper, we propose a direct, simplified and effective translation from unambiguous two-way transducers to regular function expressions extending the Brzozowski and McCluskey algorithm. In addition, our approach allows us to derive a subset of regular function expressions characterizing the (strict) subclass of functional sweeping transducers. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 31
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 146967885
- Full Text :
- https://doi.org/10.1142/S0129054120410087