Network Topologies for Parallel Communicating Finite Automata: Token-Ring and Token-Bus

In this paper, parallel communicating finite automata (abbreviated as PCFA) that communicate by states will be investigated. We define new topologies for them, the Token-Ring and Token-Bus topology. The new topologies have two working modes and will be illustrated with an example. We study the computational power of deterministic Token-Ring and Token-Bus PCFA and prove that they are equal to deterministic one-way multi-head finite automata. The same is proven for their non-deterministic versions. We compare the topologies to each other in their different working modes. It will be derived that non-deterministic versions of Token-Ring and Token-Bus PCFA are strictly more powerful than deterministic ones. In addition it is shown that the language classes of Token-Ring and Token-Bus PCFA are strictly included in the complexity class NL and that all language classes accepted by them are incomparable to the class of (deterministic) (linear) context-free languages and the class of Church-Rosser languages. (The material published in this paper is based on the results presented in the Bachelor’s thesis under the same name by Philomena Moek. The thesis was submitted in June of 2023.)