# Asynchronous sliding block maps

Marie-Pierre Béal; Olivier Carton

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 2, page 139-156
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBéal, Marie-Pierre, and Carton, Olivier. "Asynchronous sliding block maps." RAIRO - Theoretical Informatics and Applications 34.2 (2010): 139-156. <http://eudml.org/doc/222032>.

@article{Béal2010,

abstract = {
We define a notion of asynchronous sliding block map that can be realized
by transducers labeled in A* × B*. We show that, under some
conditions, it is possible to synchronize this transducer by state
splitting, in order to get a transducer which defines the same sliding
block map and which is labeled in A × Bk, where k is a constant
integer. In the case of a transducer with a strongly connected graph,
the synchronization process can be considered as an implementation of an
algorithm of Frougny and Sakarovitch for synchronization of rational
relations of bounded delay. The algorithm can be applied in the case
where the transducer has a constant integer transmission rate on cycles
and has a strongly connected graph. It keeps the locality of the input
automaton of the transducer. We show that the size of the sliding window
of the synchronous local map grows linearly during the process, but that
the size of the transducer is intrinsically exponential. In the case of
non strongly connected graphs, the algorithm of Frougny and Sakarovitch
does not keep the locality of the input automaton of the transducer. We
give another algorithm to solve this case without losing the good dynamic
properties that guaranty the state splitting process.
},

author = {Béal, Marie-Pierre, Carton, Olivier},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {asynchronous sliding block map; transducer},

language = {eng},

month = {3},

number = {2},

pages = {139-156},

publisher = {EDP Sciences},

title = {Asynchronous sliding block maps},

url = {http://eudml.org/doc/222032},

volume = {34},

year = {2010},

}

TY - JOUR

AU - Béal, Marie-Pierre

AU - Carton, Olivier

TI - Asynchronous sliding block maps

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 34

IS - 2

SP - 139

EP - 156

AB -
We define a notion of asynchronous sliding block map that can be realized
by transducers labeled in A* × B*. We show that, under some
conditions, it is possible to synchronize this transducer by state
splitting, in order to get a transducer which defines the same sliding
block map and which is labeled in A × Bk, where k is a constant
integer. In the case of a transducer with a strongly connected graph,
the synchronization process can be considered as an implementation of an
algorithm of Frougny and Sakarovitch for synchronization of rational
relations of bounded delay. The algorithm can be applied in the case
where the transducer has a constant integer transmission rate on cycles
and has a strongly connected graph. It keeps the locality of the input
automaton of the transducer. We show that the size of the sliding window
of the synchronous local map grows linearly during the process, but that
the size of the transducer is intrinsically exponential. In the case of
non strongly connected graphs, the algorithm of Frougny and Sakarovitch
does not keep the locality of the input automaton of the transducer. We
give another algorithm to solve this case without losing the good dynamic
properties that guaranty the state splitting process.

LA - eng

KW - asynchronous sliding block map; transducer

UR - http://eudml.org/doc/222032

ER -

## References

top- R.L. Adler, D. Coppersmith and M. Hassner, Algorithms for sliding block codes. IEEE Trans. Inform. TheoryIT-29 (1983) 5-22. Zbl0499.94009
- A. Aho, R. Sethi and J. Ullman, Compilers. Addison-Wesley (1986).
- J.J. Ashley, Factors and extensions of full shifts I. IEEE Trans. Inform. Theory34 (1988) 389-399.
- J.J. Ashley, A linear bound for sliding-block decoder window size, II. IEEE Trans. Inform. Theory42 (1996) 1913-1924. Zbl0868.94052
- M.-P. Béal, Codage Symbolique. Masson (1993).
- M.-P. Béal and O. Carton, Asynchronous sliding block maps, in Proc. of DLT'99 (2000) (to appear). Zbl0967.68100
- M.-P. Béal and D. Perrin, Symbolic dynamics and finite automata, in Handbook of Formal Languages, edited by G. Rosenberg and A. Salomaa, Vol. 2. Springer (1997), Chap. 10.
- C. Berge, Graphes. Gauthier-Villar (1983).
- J. Berstel, Transductions and Context-Free Languages. B.G. Teubner (1979).
- J. Berstel and D. Perrin, Theory of Codes. Academic Press (1984). Zbl0587.68066
- S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1972). Zbl0317.94045
- C.C. Elgot and J.E. Mezei, On relations defined by generalized finite automata. IBM J. Res. Develop.9 (1965) 47-68. Zbl0135.00704
- C. Frougny and J. Sakarovitch, Synchronized relations of finite words. Theoret. Comput. Sci.108 (1993) 45-82. Zbl0783.68065
- C. Frougny and J. Sakarovitch, Synchronisation déterministe des automates à délai borné. Theoret. Comput. Sci.191 (1998) 61-77.
- K.A.S. Immink, P.H. Siegel and J.K. Wolf, Codes for digital recorders. IEEE Trans. Inform. Theory44 (1998) 2260-2300. Zbl0933.94007
- D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995). Zbl1106.37301
- B. Marcus, Factors and extensions of full shifts. Monatsh. Math.88 (1979) 239-247. Zbl0432.54036
- B. Marcus, R. Roth and P. Siegel, Handbook of Coding Theory, Vol. 2. Elsevier (1998), chap. Constrained Systems and Coding for Recording Channels.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.