6533b82cfe1ef96bd128fde4

RESEARCH PRODUCT

The Many Faces of a Translation

Heribert VollmerThomas SchwentickPierre MckenzieDenis Thérien

subject

MonoidGroup (mathematics)0102 computer and information sciences02 engineering and technologyCharacterization (mathematics)Translation (geometry)01 natural sciencesCombinatoricsNondeterministic algorithmRegular language010201 computation theory & mathematicsAperiodic graph0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingVariety (universal algebra)Mathematics

description

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. More strikingly, 2-way V-machines 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 2-way V-transducers.

yearjournalcountryeditionlanguage
2000-01-01
https://doi.org/10.1007/3-540-45022-x_75