|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc030201,
author = {Ferenc G\'{e}cseg and Bal\'{a}zs Imreh and
Andr\'{a}s Pluh\'{a}r},
title = {On the Existence of Finite Isomorphically Complete Systems
of Automata},
journal = jalc,
year = 1998,
volume = 3,
number = 2,
pages = {77--84},
keywords = {automata, compositions, completeness},
abstract = {In the theory of compositions of finite automata it is a
central problem to study systems from which every automaton
can be built under a given composition and representation.
Such systems are called complete with respect to the
considered composition and representation. From practical
and theoretical points of view, those compositions and
representations have great importance for which there are
finite complete systems. Under the isomorphic embedding as
representation, a graph theoretical necessary condition of
the existence of finite complete systems is presented by
F. G\'{e}cseg, B. Imreh in 1992. In this paper, we give a
sufficient condition for a composition to admit a finite
complete system under the isomorphic representation, which
reduces the question to a graph coloring problem.}
}