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 metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620271
Contributor : Sylvain Lombardy <>
Submitted on : Monday, October 3, 2011 - 2:08:31 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Wednesday, January 4, 2012 - 2:26:51 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620271, version 1

Citation

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⟩

Share

Metrics

Record views

303

Files downloads

260