Book contents
- Frontmatter
- Contents
- Preface
- Part I Formal Background
- 1 Formal Preliminaries
- 2 Monoidal Finite-State Automata
- 3 Classical Finite-State Automata and Regular Languages
- 4 Monoidal Multi-Tape Automata and Finite-State Transducers
- 5 Deterministic Transducers
- 6 Bimachines
- Part II From Theory to Practice
- References
- Index
4 - Monoidal Multi-Tape Automata and Finite-State Transducers
from Part I - Formal Background
Published online by Cambridge University Press: 29 July 2019
- Frontmatter
- Contents
- Preface
- Part I Formal Background
- 1 Formal Preliminaries
- 2 Monoidal Finite-State Automata
- 3 Classical Finite-State Automata and Regular Languages
- 4 Monoidal Multi-Tape Automata and Finite-State Transducers
- 5 Deterministic Transducers
- 6 Bimachines
- Part II From Theory to Practice
- References
- Index
Summary
An important generalization of classical finite-state automata are multi-tape automata, which are used for recognizing relations of a particular type. The so-called regular relations (also refered to as ‘rational relations’) offer a natural way to formalize all kinds of translations and transformations, which makes multi-tape automata interesting for many practical applications and explains the general interest in this kind of device. A natural subclass are monoidal finite-state transducers, which can be defined as two-tape automata where the first tape reads strings. In this chapter we present the most important properties of monoidal multi-tape automata in general and monoidal finite-state transducers in particular. We show that the class of relations recognized by n-tape automata is closed under a number of useful relational operations like composition, Cartesian product, projection, inverse etc. We further present a procedure for deciding the functionality of classical finite-state transducers.
Keywords
- Type
- Chapter
- Information
- Finite-State TechniquesAutomata, Transducers and Bimachines, pp. 72 - 93Publisher: Cambridge University PressPrint publication year: 2019