Skip to Main content Skip to Navigation
Journal articles

Embeddings of local automata

Abstract : We prove that any local irreducible automaton is contained in a complete one. The proof uses Nasu's masking lemma. We use the same technique to give a new proof that any weakly deterministic irreducible automaton is contained in a complete one.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619770
Contributor : Sylvain Lombardy <>
Submitted on : Thursday, October 6, 2011 - 1:59:51 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Saturday, January 7, 2012 - 2:21:05 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619770, version 1

Citation

Marie-Pierre Béal, Sylvain Lombardy, Dominique Perrin. Embeddings of local automata. Illinois Journal of Mathematics, 2010, 54 (1), pp.155-174. ⟨hal-00619770⟩

Share

Metrics

Record views

386

Files downloads

269