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

Abstract

top
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.

How to cite

top

Bé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
  1. R.L. Adler, D. Coppersmith and M. Hassner, Algorithms for sliding block codes. IEEE Trans. Inform. TheoryIT-29 (1983) 5-22.  
  2. A. Aho, R. Sethi and J. Ullman, Compilers. Addison-Wesley (1986).  
  3. J.J. Ashley, Factors and extensions of full shifts I. IEEE Trans. Inform. Theory34 (1988) 389-399.  
  4. J.J. Ashley, A linear bound for sliding-block decoder window size, II. IEEE Trans. Inform. Theory42 (1996) 1913-1924.  
  5. M.-P. Béal, Codage Symbolique. Masson (1993).  
  6. M.-P. Béal and O. Carton, Asynchronous sliding block maps, in Proc. of DLT'99 (2000) (to appear).  
  7. 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.  
  8. C. Berge, Graphes. Gauthier-Villar (1983).  
  9. J. Berstel, Transductions and Context-Free Languages. B.G. Teubner (1979).  
  10. J. Berstel and D. Perrin, Theory of Codes. Academic Press (1984).  
  11. S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1972).  
  12. C.C. Elgot and J.E. Mezei, On relations defined by generalized finite automata. IBM J. Res. Develop.9 (1965) 47-68.  
  13. C. Frougny and J. Sakarovitch, Synchronized relations of finite words. Theoret. Comput. Sci.108 (1993) 45-82.  
  14. C. Frougny and J. Sakarovitch, Synchronisation déterministe des automates à délai borné. Theoret. Comput. Sci.191 (1998) 61-77.  
  15. K.A.S. Immink, P.H. Siegel and J.K. Wolf, Codes for digital recorders. IEEE Trans. Inform. Theory44 (1998) 2260-2300.  
  16. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995).  
  17. B. Marcus, Factors and extensions of full shifts. Monatsh. Math.88 (1979) 239-247.  
  18. B. Marcus, R. Roth and P. Siegel, Handbook of Coding Theory, Vol. 2. Elsevier (1998), chap. Constrained Systems and Coding for Recording Channels.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.