The growth ratio of synchronous rational relations is unique

by Olivier Carton

Résumé

Nous introduisons des relations α-synchrones pour un nombre rationnel α. Nous montrons que si une relation est α et α' synchrones pour deux nombres différents α et α', alors elles est reconnaissable. Nous donnons un algorithme de synchronisation pour les transducers α-synchrones. Nous prouvons également la clôture par les opérations booléennes et la composition des relations α-synchrones.

Abstract

We introduce α-synchronous relations for a rational number α. We show that if a rational relation is both α- and α'-synchronous for two different numbers α and α', then it is recognizable. We give a synchronization algorithm for α-synchronous transducers. We also prove the closure under boolean operations and composition of α-synchronous relations.


Pdf