On the degree of communication in parallel communicating finite automata systems

摘要

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.