Iteration of rational transductions
| Autor: | David Simplot, Alain Terlutte |
|---|---|
| Rok vydání: | 2000 |
| Předmět: |
Finite-state machine
Semigroup Quantitative Biology::Molecular Networks General Mathematics Linear space Quantitative Biology::Cell Behavior Computer Science Applications Quantitative Biology::Subcellular Processes Combinatorics Philosophy of language Iterated function Context-sensitive language Software Mathematics |
| Zdroj: | RAIRO - Theoretical Informatics and Applications. 34:99-129 |
| ISSN: | 1290-385X 0988-3754 |
| DOI: | 10.1051/ita:2000109 |
| Popis: | The purpose of this paper is to show connections between iterated length-preserving rational transductions and linear space computations. Hence, we study the smallest family of transductions containing length-preserving rational transductions and closed under union, composition and iteration. We give several characterizations of this class using restricted classes of length-preserving rational transductions, by showing the connections with "context-sensitive transductions" and transductions associated with recognizable picture languages. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|