The many faces of a translation

First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this characterization lifts to “ V -translations” and “ V -single-valued-NFTs”, where V is an arbitrary monoid pseudovariety tha...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2006-02, Vol.72 (1), p.163-179
Main Authors: McKenzie, Pierre, Schwentick, Thomas, Thérien, Denis, Vollmer, Heribert
Format: Article
Language:English
Subjects:
Automata theory
Descriptive complexity
Finite model theory
Logic in computer science
Monoids
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this characterization lifts to “ V -translations” and “ V -single-valued-NFTs”, where V is an arbitrary monoid pseudovariety that is closed under reversal. More strikingly, two-way V -transducers are introduced, and the following three models are shown exactly equivalent to Eilenberg's classical notion of a bimachine when V is a group variety or when V is the variety of aperiodic monoids: V -translations, V -single-valued-NFTs and two-way V -transducers.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2005.08.003