Parallel Communicating Finite Automata: The Non-Forgetting Model
Jana Schulz · 2026
Read Parallel Communicating Finite Automata: The Non-Forgetting Model by Jana Schulz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26684.txt.
Introduction
Jana Schulz introduces the non-forgetting model of parallel communicating finite automata. Such systems team several small automata together. Each can ask another for its current state. In the classical model, asking makes the asker forget its own state. The new model lets automata keep their state while querying, a more realistic behaviour.
Schulz compares the computing power of many variants. Most non-forgetting variants match multi-head finite automata exactly, in both deterministic and nondeterministic cases, when the counts of automata and heads agree. One special case breaks the pattern: deterministic centralised systems in non-returning mode sit strictly below their counterpart. Proving that exception also completed a proof left open in earlier work. The results answer questions for the new model that remain open for the classical forgetting one.
Catalog record
| CREATOR | Jana Schulz |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.26684
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Parallel Communicating Finite Automata: The Non-Forgetting Model Jana Schulz Abstract Parallel Communicating Finite Automata (PCFA) are systems of several finite automata that can communicate by requesting the state of another automaton. As an attempt to make PCFA as defined in [ 9 ] and [ 3 ] more realistic, the non-forgetting model is introduced where automata retain their own states while querying. As in previous publications, several variants of these automata systems are considered. The computational capacity of the non-forgetting model is investigated and compared to ”forgetting” systems and multi-head finite automata. It is shown that most variants of non-forgetting PCFA are as powerful as multi-head automata in the deterministic and nondeterministic cases where the number of automata equals the number of heads. The only exception is the special case of deterministic centralized systems in non-returning mode. Here, a strict inclusion is proved. In the course of this proving, a proof from [ 3 ] is completed. With that, this paper answers some questions for nfPCFA that are open for the classical ”forgetting” case. 1 Introduction and Motivation Parallel Communicating Finite Automata Systems were first introduced in [ 9 ] and further investigated in [ 3 ] among others. This paper builds on the definition introduced in the latter. A Parallel Communicating Finite Automata System of degree k (denoted by PCFA( k )) is a system of k finite automata that work independently on the same input tape. The automata are not aware of each other’s positions or movements on the input tape but can communicate via their states. In the original model, an automaton can enter a special query state to request the state of another automaton in the system. When doing so, the querying automaton leaves and therefore forgets its previous state. When the request for communication is answered, the query state is replaced by the queried automaton’s current state. If the queried automaton is also in a query state, this pending query must be answered first before any dependent communication can be resolved. Therefore, when a PCFA enters a configuration with cyclic communication requests, the system is in a deadlock and halts. It has already been established that some variants of PCFA are as powerful as multi-head automata (see [ 9 ] , [ 5 ] and [ 3 ] ). In addition to computational capacities, other properties of PCFA have already been studied. This includes decidability and hierarchies in regard to the number of automata which were investigated in [ 2 ] . Further, measures of communication have been examined in [ 4 ] . More recently, network topologies (see [ 11 ] ) and productiveness and succinctness (see [ 13 ] ) have been considered. It is to be noted that the authors of the latter used the definition introduced in [ 9 ] . The mentioned characteristics of the original PCFA, namely forgetting the previous state and the possibility of entering a deadlock, do not seem realistic when looking at current standards for computer networks or multi-agent systems but can rather be seen as problematic. Therefore, these problems will be addressed in this paper by introducing a new model of PCFA that can resolve cyclic communication requests and whose automata do not forget their current state when initiating communication. To reflect this, these newly introduced systems are termed ’’non-forgetting’’ 1 1 1 The non-forgetting PCFA are not to be confused with non-forgetting restarting automata from [ 10 ] . which is denoted by additing the prefix ”nf” to the abbreviation. To make a clear distinction, the original model of PCFA will be referred to as the ”forgetting” model in some instances. Both PCFA and nfPCFA can work in different modes. Firstly, they are categorized according to determinism. Further, systems can be centralized, where only one automaton is capable of initiating communication. Finally, they can work in returning mode, where an automaton returns to its initial state after communicating its state to another automaton. These modes are independent of each other and their combinations lead to eight different variants of both forgetting and non-forgetting PCFA. Though nfPCFA work in a very similar way as the classic forgetting model, there are two major differences between PCFA and nfPCFA. For one, nfPCFA do not allow \lambda -steps. Instead their mode of movement is inspired by multi-head automata and allows stationary moves. This decision was made to simplify the extension to the two way case. Secondly, nfPCFA differ in the way they conduct communication. A query state consists of a query symbol, denoting which automaton in the system is queried, and the automaton’s own state. Besides allowing the automata to remember their previous states, this also enables any automaton to communicate its state when it is queried by another automaton while also upholding a query. As a consequence, all queries can be answered immediately, there are no delays caused by preliminary communications, and cyclic requests do not lead to a deadlock. When the communication is answered, the query symbol in the query state is replaced by the state of the queried automaton. Then, an aggregation function is used to aggregate the querying automatons own state with the received state into the subsequent state. In the next section, the definition of non-forgetting PCFA will be introduced. Afterwards, the computational capacities will be investigated. All variants of non-forgetting PCFA are compared to multi-head finite automata as well as to the forgetting model. Supplementing the results for the forgetting model (see [ 9 ] , [ 5 ] and [ 3 ] ), it can be proved that all variants of the non-forgetting model are either equal to or properly included in the language families of multi-head finite automata. For the forgetting model, there are three variants whose relationship to their non-forgetting counterparts and therefore to multi-head automata remains open for now (see Figure 1 ). It is unclear whether nondeterministic centralized PCFA (in non-returning mode) are strictly less or equally as powerful as nondeterministic multi-head automata. For centralized PCFA in returning mode this question remains open in both the nondeterministic as well as the deterministic case. Non-forgetting PCFA give new characterizations of these open problems. 2 Definitions and Examples We assume the reader’s familiarity with fundamental concepts of formal languages and automata theory as in [ 12 ] or [ 7 ] . In the following, the empty word is represented by \lambda . The power set of set S is denoted by 2^{S} . The subset relationship between two sets is written as \subseteq and a proper subset is denoted by \subset . For some word w , its length is given by |w| . We use the notation w(i) for the i -th symbol of w . Further, w(i\colon) denotes the suffix u of word w that starts with the i -th symbol w(i) , i.e. w=w(1\colon) and w=w(1)w(2)w(3\colon) . For any n>|w| , we set w(n)=w(n\colon)=\lambda . Definition 1 . A non-forgetting Parallel Communicating Finite Automata System A of degree k , denoted by nfPCFA( k ), is defined as a (k+3) -tuple A=(\Sigma,A_{1},A_{2},\dots,A_{k},Q,\triangleleft) where \Sigma is the finite set of input symbols, Q =\{q_{1},q_{2},\dots,q_{k}\} is the finite set of query symbols, and \triangleleft \notin\Sigma is the