Skip to Main content Skip to Navigation
Conference papers

Embeddings of local automata

Abstract : --A local automaton is by definition such that a bounded information about the past and the future is enough to determine the present state. Due to this synchronization property, these automata play an important role for coding purposes. We prove that any irreducible local automaton is contained in a complete one. The proof uses a result from symbolic dynamics due to M. Nasu called the masking lemma. A consequence of this result in the theory of variable length codes is that any locally parsable regular code is included in a maximal one with the same synchronisation delay.
Document type :
Conference papers
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Sylvain Lombardy Connect in order to contact the contributor
Submitted on : Monday, October 3, 2011 - 2:08:31 PM
Last modification on : Saturday, January 15, 2022 - 3:56:54 AM
Long-term archiving on: : Wednesday, January 4, 2012 - 2:26:51 AM


Files produced by the author(s)


  • HAL Id : hal-00620271, version 1


Marie-Pierre Béal, Sylvain Lombardy, Dominique Perrin. Embeddings of local automata. IEEE International Symposium on Information Theory (ISIT'08), Jul 2008, United States. pp.2351-2355. ⟨hal-00620271⟩



Record views


Files downloads