Induced permutation automata and coverings of strongly connected automata

Induced permutation automata and coverings of strongly connected automata

0.00 Avg rating0 Votes
Article ID: iaor20001647
Country: Netherlands
Volume: 91
Issue: 1/3
Start Page Number: 243
End Page Number: 249
Publication Date: Jan 1999
Journal: Discrete Applied Mathematics
Authors: , ,
Abstract:

Let A = (S, Σ, N) be a strongly connected automaton and e be a minimal idempotent of characteristic semigroup 𝒞(A). The unique (up to isomorphism) subgroup e𝒞(A)e is a very important group in automaton automorphism theory. For example, the automorphism group 𝒜(A) of A is a homomorphic image of a subgroup of e𝒞(A)e. If H is a subgroup of 𝒜(A), then the automorphism group of the factor automaton A/H is also homomorphic to a subgroup of e𝒞(A)e. In this paper we show another property of e𝒞(A)e. First, we introduce the induced permutation automaton whose characteristic semigroup is isomorphic to e𝒞(A)e, and the generalized factor automaton. Using these two automata, we construct a cascade product covering of A, if e𝒞(A)e is not {id} (identity permutation group). This is an example of an effective admissible subset system covering, as well as a generalization of the result of Krohn et al. which gave a decomposition of A, if the automorphism group of A is not {id}.

Reviews

Required fields are marked *. Your email address will not be published.