|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc050310,
author = {Mitrana, Victor},
title = {On the Degree of Communication in Parallel Communicating
Finite Automata Systems},
journal = jalc,
year = 2000,
volume = 5,
number = 3,
pages = {301--314},
keywords = {parallel communicating finite automata, degree of
communication, communication step},
abstract = {A parallel communicating finite automata system consists
of several finite automata working independently but
communicating states with each other by request. We introduce
a dynamical descriptional complexity measure for all variants
of parallel communicating finite automata systems and discuss
some computational aspects with respect to this measure. The
degree of communication of a given automata system for a
given word expresses the minimal number of communications
necessary to recognize the word. The degree of communication
of an automata system is taken as the maximal degree of
communication for all words recognized by the system, if the
degree of communication for every word is bounded by a
constant, or infinite otherwise. We discuss here the
possibility of algorithmically computing the degree of
communication for a word, of an automata system or for a
language.}
}