Abstract
We study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the nondeterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with nonreversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or nonreturning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not contextfree. We also separate the deterministic and nondeterministic variants in the case of systems with nonreturning communication. We show that there are languages accepted by nondeterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type.
Introduction
Parallel communicating finite automata (PCFA) are systems of several finite state automata processing the same input word in an autonomous and synchronized way. In certain situations, automata of the system, depending on the state reached, may request the state of another automaton. The concept of PCFA has been introduced in [17] and further investigated in, e.g., [3,4,5, 7]. The concept can be viewed as a simple model of computer networks, falling into the line of research as of, e.g., [6] or [11].
In PCFA, spontaneous transitions are allowed so that different automata of a system can read different symbols of the input word at the same time during computations. This is similar to multihead finite automata [20] which are shown to be computationally equivalent to PCFA, see [17] and [7] for the nondeterministic case and [4] for the deterministic case. Inspired by parallel communicating grammar systems which have been investigated as string generating variants of the classroom model known from artificial intelligence [8], one distinguishes between the returning and nonreturning working modes. In PCFA, these working modes refer to the state in which an automaton continues its computation after it has sent its state to another automaton upon request: In the returning mode, the automaton is set back to its initial state, while in the nonreturning mode, it just keeps the state it has communicated to another automaton. An interesting special case is centralized PCFA, where only one designated automaton is allowed to send communication requests to other automata of the system. This models a particular, starlike network architecture with restricted power, leading to subclasses in the hierarchy of language families, strict in most cases [4].
In the present paper, the concept of reversibility is added to PCFA. Roughly, reversibility means that no information is lost during the computation. This is of interest due to the physical observation that loss of information involves heat dissipation [2, 16]. In abstract models, a computation is reversible if every configuration has a unique predecessor configuration. Thus, in deterministic devices the computation step relation is injective. For example, reversible Turing machines have been investigated in [2] where it is shown that for every Turing machine, there is an equivalent reversible one. Many other automata models have been considered under the restriction of reversibility such as the massively parallel cellular automata, see, e.g., [18], pushdown automata [13], their input driven variants [15], twoway multihead finite automata [1, 19] and oneway multihead finite automata [14]. In [10], reversible nondeterministic finite automata have been considered. Different aspects of reversibility in a setting of computing devices with a finite number of discrete internal states and a readonly input tape are addressed in [12]. This work also contains many further references about reversibility in automata models.
PCFA were also considered from the point of view of reversibility in [9] where the authors showed that parallel communicating systems of reversible (deterministic) finite automata are able to accept all regular languages. They also considered an intuitive notion of the reversibility of PCFA systems when they remarked that such a system is not necessarily reversible as a whole, although all of its components are reversible.
In the present paper, we first give a definition of the notion of reversibility for PCFA by formalizing the way the predecessor configurations are computed, particularly in the case when communication may have happened. We also discuss the relation between the reversibility of parallel communicating systems and the reversibility of their components, and then, we focus on the computational power of reversible systems. Throughout the paper, both the deterministic and nondeterministic variants are taken into consideration.
Definitions and basic properties
We assume that the reader is familiar with basic concepts and terminology of automata theory as it can be found, e.g., in [22]. We shall use the following notation. For a set S, its powerset is designated by \(2^S\) and its cardinality by S. The symbols \(\subseteq \) and \(\subset \) are used for set inclusion and strict set inclusion, respectively. For a word w, its length is designated by w, w(i) denotes the ith symbol of w, for \(1\le i\le w\), and \(w^R\) is the reverse (mirror image) of w. The symbol \(\lambda \) is used for the empty word. Let \(\Sigma \) be an alphabet. The notation \(\Sigma ^*\) is used for the set of all words over \(\Sigma \) including \(\lambda \), while \(\Sigma ^+=\Sigma ^*\setminus \{\lambda \}\).
Let \(A=(S,\Sigma ,s_0,\delta ,F)\) be a nondeterministic finite automaton (NFA), where S is the finite set of states, \(\Sigma \) is the alphabet of input symbols, \(s_0\in S\) is the initial state, \(\delta :\,S\times \Sigma \rightarrow 2^S\) is the transition function and \(F\subseteq S\) is the set of accepting states. The automaton is deterministic if \(\delta (s,a)=1\) for all \(s\in S\) and \(a\in \Sigma \). A configuration of A is a pair in \(S\times \Sigma ^*\). A computation of A on input word w is a sequence of configurations \(c_0,c_1,\ldots c_k\), for some \(k\ge 0\) such that \(c_0\) is the initial configuration \((s_0,w)\), and \(c_i=(s,v)\) if \(c_{i1}=(q,av)\) and \(s\in \delta (q,a)\), for \(1\le i\le k\). We write \(c_{i1}\vdash c_i\), \(1\le i\le k\).
An NFA \(A=(S,\Sigma ,s_0,\delta , F)\) is reversible according to [10] if there is no internal state \(s\in S\), such that \(s\in \delta (p,a)\cap \delta (r,a)\) holds for some \(a\in \Sigma \) and states \(p,r\in S\) with \(p\not =r\).
A nondeterministic parallel communicating finite automata system of degree k (PCFA(k)) is a tuple \(\mathcal A=(\Sigma ,A_1,A_2,\ldots ,A_k,Q,\triangleleft )\) where \(\Sigma \) is the input alphabet, \(A_i=(S_i,\Sigma ,\delta _i,s_{0,i},F_i)\) for each \(i,\ 1\le i\le k\), is a nondeterministic finite automaton (the ith component of \(\mathcal A\)) with \(S_i\) being the set of states, \(s_{0,i}\in S_i\) the initial state, \(F_i\subseteq S_i\) the set of accepting states, and \(\delta _i: S_i\times (\Sigma \cup \{\lambda ,\triangleleft \})\rightarrow 2^{S_i}\) the transition function. Further, \(Q\subseteq \{q_1,q_2,\ldots ,q_k\}\) is the set of query states, \(Q\subseteq \bigcup _{i=1}^k S_i\), and \(\triangleleft \not \in \Sigma \) is the endofinput symbol.
A configuration \(c=(w, s_1,p_1,\ldots , s_k,p_k)\in \Sigma ^*\times S_1\times \mathbb N\times \ldots \times S_k\times \mathbb N \) of \(\mathcal A\) represents the tape contents with input word \(w\in \Sigma ^*\), the current states \(s_i\in S_i\), and the current positions \(p_i\ge 1\) of the reading heads of the component automata \(A_i,\ 1\le i\le k\), where \(p_i>w\) means that \(A_i\) is scanning the endofinput symbol \(\triangleleft \). For a word w and an integer \(i\ge 1\), let w(i) denote the ith symbol of w if \(1\le i\le w\), and \(w(i)=\triangleleft \) if \(i>w\).
An initial configuration is of the form \((w, s_{0,1}, 1, s_{0,2}, 1, \dots , s_{0,k}, 1)\), that is, each component is in its initial state and scans the first symbol of an input word \(w\in \Sigma ^*\). The definition of the successor configuration relation \(\vdash _A\) of A is defined as follows. (We may omit the subscript A in \(\vdash _A\) if there is no risk of confusion.) For any \(w\in \Sigma ^*\),
if either

1.
(Reading step) \(Q\cap \{s_1,s_2,\dots ,s_k\} = \emptyset \), \(s_i'\in \delta _i(s_i,a_i)\) with \(a_i\in \{w(p_i),\lambda \}\), and \(p_i'=p_i\) if \(a_i=\lambda \) and \(p_i'=p_i+1\) otherwise, \(1\le i \le k\), or

2.
(Communication step) for all \(i,\ 1\le i\le k\), we have \(p_i'=p_i\) and, if \(s_i = q_j\) with \(q_j\in Q\) and \(s_j\notin Q\), then \(s_i'=s_j\); furthermore,

(a)
\(s_r'=s_r\) for all the other r, \(1\le r\le k\) (nonreturning communication) or, alternatively,

(b)
\(s_j'=s_{0,j}\), and \(s_r'=s_r\) for all the other r, \(1\le r\le k\) (returning communication).

(a)
In a reading step, all components are in nonquery states and perform an ordinary (noncommunicating) step independently (which may also be a \(\lambda \)step). Notice that components with head positions greater than the input length will always scan the endofinput symbol in non\(\lambda \) reading steps. In a communication step, components in query states receive the requested states as long as the sender is not in a query state itself. This process is repeated until all requests are resolved, if possible. If the requests are cyclic, no successor configuration exists. As mentioned above, we distinguish nonreturning communication, that is, the sender remains in its current state, and returning communication, that is, the sender is reset to its initial state. Both in returning and nonreturning communication steps, the heads do not move. In what follows, every PCFA consistently work with either returning or nonreturning communication steps; thus, we either have returning or nonreturning systems.
A computation halts when the successor configuration is not defined for the current situation. In particular, this may happen when cyclic communication requests appear, or when the transition function of one component is not defined. (We regard the transition function as undefined whenever it maps to the empty set.) The language \(L(\mathcal {A})\) accepted by a \(\text {PCFA}(k)\) \(\mathcal {A}\) is precisely the set of words w such that there is some computation beginning with w on the input tape and halting with at least one component having an undefined transition function and being in an accepting state. Let \(\vdash _A^*\) denote the reflexive and transitive closure of \(\vdash _A\) and set \(L(\mathcal {A}) = \{\,w\in \Sigma ^* \mid (w, s_{0,1}, 1, s_{0,2}, 1, \dots , s_{0,k}, 1) \vdash _A^* (w, t_1, r_1, t_2, r_2, \dots , t_k, r_k),\) for some i, \(1\le i\le k\), such that \(t_i\in F_i\) and \(\delta _i(t_i,w(r_i))\) is undefined \(\}\).
If all components \(A_i\) are deterministic finite automata, that is, for all \(s\in S_i\) and for all \(a\in \Sigma \), the transition function \(\delta _i(s,a)\) maps to a set of at most one state and is undefined whenever \(\delta _i(s,\lambda )\) is defined, then the whole system is called deterministic, and we add the prefix D (to PCFA) to denote it. The absence or presence of an R in the type of the system denotes whether it works in nonreturning or returning mode, respectively. Finally, if there is just one component, say \(A_1\), that is allowed to query for states, that is, \(S_i\cap Q=\emptyset \), for \(2\le i\le k\), then the system is said to be centralized. In this case, we refer to \(A_1\) as the master component and add a C to the notation of the type of the system. Whenever the degree is missing, we mean systems of arbitrary degree. The family of languages accepted by devices of type X (with degree k) is denoted by \(\mathscr {L}(X)\) (\(\mathscr {L}(X(k))\)).
For the definition of reversibility of a PCFA, we introduce the following notion. A configuration \((w, t_1, r_1, t_2, r_2, \dots , t_k, r_k)\) is reachable by a PCFA A, if there is a computation \((w, s_{0,1}, 1, s_{0,2}, 1, \dots , s_{0,k}, 1) \vdash _A^* (w, t_1, r_1, t_2, r_2, \dots , t_k, r_k)\).
Definition 1
A PCFA(k) is reversible if considering any reachable configurations \((w, s_1,p_1,\ldots , s_k,p_k)\) and \((w, s_1',p_1',\ldots , s_k',p_k')\), if there are computational steps
and
then the following holds:

If \((s_1,\ldots , s_k)=(s_1',\ldots , s_k')\), then \(p_ir_i=p_i'r_i'\) for all \(i,\ 1\le i\le k\), and moreover,

if \(w(r_i)=w(r_i')\) for all i with \(p_i\not =r_i,\ 1\le i\le k\), then \((t_1,\ldots , t_k)=(t_1',\ldots , t_k')\).
Intuitively, if two reachable configurations cannot be distinguished by the states reached, then it is determined which positions have been increased in the previous computation step and which have not. This way one can identify the symbols which have been read in the previous computation step. If the read symbols are identical, then also the states of the two predecessor configurations have been the same.
In the definition, one might alternatively take all configurations into account instead of only reachable ones. Due to the motivation of the concept of reversibility, computations should be reversible that can be performed by the machine model. Therefore, we restrict to reachable configurations in the definition.
For all the language classes \(\mathcal L(X\text{ PCFA})\) and \(\mathcal L(X\text{ PCFA }(k))\) with \(X\in \{\lambda ,\) R, C, DR, DC, DRC\(\}\), we add the prefix “rev” in order to refer to the corresponding families of languages accepted by reversible PCFA.
Example 1
Consider the deterministic nonreturning PCFA with two components (DCPCFA(2) in short) \(\mathcal A=(\{a,b,\$,\cent \}, A_1,A_2,\{q_2\},\triangleleft )\) where for \(i\in \{1,2\}\)
with
and
We show that \(\mathcal A\) is reversible and it accepts the language \(L(\mathcal A)=\{\cent w\$ w\mid w\in \{a,b\}^*\}\).
To see how \(\mathcal A\) works, consider an initial configuration \((\alpha ,s_{0,1},1,s_{0,2},1).\) Notice that \(\alpha =\cent \alpha '\) or the second component cannot start reading the input which results in a nonaccepting blocking configuration. Moreover, \(\alpha '\) contains exactly one $ symbol or the second component cannot reach the endofinput symbol \(\triangleleft \), so the first component (hence, the system) cannot enter the accepting state. This means that the input string must be of the form \(\cent w\$ w' \) with \(w,w'\in \{a,b\}^* \).
The transition relations are defined in such a way that the computation must start with
and then
where \(\cent w\$ w'(k)={\$}\), that is, the kth symbol of the input is the \(\$ \) symbol and it has just been read by the second component.
We can check that this phase of the computation is reversible by considering the following.

If the states of the components are \((s_1,s_1)\) or \((s_\$,s_\$)\), then the previous computational step must have been a communication step, so for any configuration \((\cent w\$ w', s_{1},i, s_{1},j)\) or \((\cent w\$ w', s_{\$},i, s_{\$},j)\) with \(i,j\ge 1\), the previous configuration must have been \((\cent w\$ w', q_2,i, s_{1},j)\) or \((\cent w\$ w', q_2,i, s_{\$},j)\), respectively.

If the states of the components are \((q_2,s_1)\), then the previous computational step must have been a reading step where the second component made a non\(\lambda \)move. As the second component is in \(s_1\), it has never sent a state from \(\{s_\$,s_a,s_b\}\) to the first component by a communication step. Therefore, the first component must have entered state \(q_2\) by a \(\lambda \)move. If the symbol read by the second component was \(\cent \), then for any configuration \((\cent w\$ w', q_2,i, s_{1},j)\) with \(i\ge 1\), \(j>1\), the previous configuration must have been \((\cent w\$ w', s_{0,1},i, s_{0,2},j1)\) which is only reachable if it is the initial configuration \((\cent w\$ w', s_{0,1},1, s_{0,2},1)\). If the symbol read by the second component was a or b, then the previous configuration is \((\cent w\$ w', s_{1},i, s_{1},j1)\).

Similarly, if the states of the components are \((q_2,s_\$)\), then the previous computational step must have been a reading step where the first component made a \(\lambda \)move, and the second component made a non\(\lambda \)move. The symbol read by the second component must have been a \({\$}\), so the previous configuration for any \((\cent w\$ w', q_2,i, s_{\$},j)\) with \(i,j\ge 1\), is \((\cent w\$ w', s_{1},i, s_{1},j1)\).
Notice that \(i=1\) in any reachable configuration of these forms.
Continuing the computation, we have
where \(x\in \{a,b,\triangleleft \}\) depending on the \((k+1)\)st symbol on the input tape. First, let \(x\in \{a,b\}\). If the second symbol of the input is also x, the computation can continue with
where \(x'\in \{a,b,\triangleleft \}\) now depends on the \((k+2)\)nd symbol on the input tape. Repeating similar steps, the system now is able to check whether \(w=w'\) in the input string \(\cent w\$w'\). The first component can only read the jth symbol of w (which is the \((1+j)\)th symbol on the tape), if it is the same as the jth symbol of \(w'\) (which is the \((k+j)\)th symbol on the tape) that was read in the previous noncommunication step by the second component and transferred in the previous communication step to the first component as the state \(s_x\), \(x\in \{a,b,\triangleleft \}\).
This phase of the computation is also reversible, as can be seen by the following.

If the states of the components are \((s_x,s_x)\) for some \(x\in \{a,b,\triangleleft \}\), then the previous computational step must have been a communication step, so for any configuration \((\cent w\$ w', s_{x},i, s_{x},j)\) with \(i,j>1\), the previous configuration must have been \((\cent w\$ w', q_2,i, s_{x},j)\).

If the states of the components are \((q_2,s_x)\) for some \(x\in \{a,b,\triangleleft \}\), then the previous computational step must have been a reading step where both components made a non\(\lambda \)move. If the symbol read by the first component is \(y\in \{a,b,\$\}\), then for any configuration \((\cent w\$ w', q_2,i, s_{x},j)\) with \(i,j> 1\), the previous configuration must have been \((\cent w\$ w', s_{y},i1, s_{y},j1)\). (Note that configurations of the form \((\cent w\$ w', s_x,i, s_{x'},j)\) for \(x\not =x'\) are not reachable by the system. Moreover, \(j=k+i\) holds in every reachable configuration of this form.)
Now, we consider situations in which the second component reaches the endofinput symbol \(\triangleleft \). If the first component reaches the \({\$}\) symbol before the second component reaches the endofinput symbol \(\triangleleft \), then the system is blocked in a nonaccepting state of the form \((\cent w\$ w', s_{x},i, s_{x},j)\) where \(\cent w\$ w'(i)=\$ \), so in order for the computation to be successful, the second component must reach the endofinput symbol first through a computational step
followed by the communication
Now, if the first component is scanning an a or b symbol, then the computation is blocked in a nonaccepting state. On the other hand, if the first component is scanning the \({\$}\) symbol (that is, if the input string is of the form \(\cent w\$ w\)), the system reaches the accepting configuration
where the \({\$}\) symbol is on the kth position of the input string, that is, \(j=k2\) for \(\cent w\$ w=2k2\).
The last step of the computation is also reversible, as having the current states \((s_\mathrm{acc},s_f)\) implies that the two components made a non\(\lambda \)move and a \(\lambda \)move, respectively, and the states of the previous configuration must have been \(s_\triangleleft \) for both of them.
The next example shows that a similar language can also be accepted by returning systems.
Example 2
Consider the DRCPCFA(2) \(\mathcal A=(\{a,b,\$_1,\$_2,\cent \}, A_1,A_2,\{q_2\},\triangleleft )\) where
with \(S_1=\{s_{0,1},s_{0,1}', s_1, s_1',s_a,s_b,s_{\$_1},s_{\cent },s_\mathrm{acc},q_2\}\) and
Further,
with \(S_2=\{s_{0,2},s_a,s_b,s_{\$_1},s_{\$_2},s_{\cent }\}\) and
We show that \(\mathcal A\) is reversible and accepts the language \(L(\mathcal A)=\{\cent w\$_1\$_2 w\mid w\in \{a,b\}^*\}\).
To see how \(\mathcal A\) works, consider an initial configuration \( (\alpha ,s_{0,1},1,s_{0,2},1). \) Notice that \(\alpha =\cent \alpha '\) or the first component cannot perform more than one computational step on the input, which results in a nonaccepting blocking configuration of the form \((\alpha ,s_{0,1}',1,s_x,2)\) with \(x\in \{a,b,\$_1,\$_2\}\). Such computational step is reversible as it can only be reached from the initial configuration according to the definition of \(\delta _1\). Moreover, the first component, thus the system, cannot read more than one \(\cent \) symbol, so the leading \(\cent \) is the only such symbol in the input string. Similarly, the first component must read exactly one \(\$_1\) symbol, or it cannot reach the accepting state. As a consequence, \(\alpha '\) must contain exactly one \(\$_2\) symbol, since the first component may read \(\$_2\) only after receiving state \(s_{\cent }\) from the second component, which can happen only once, as there is only one \(\cent \) symbol in the input string and \(\mathcal {A}\) works in returning mode. Note also that the \(\$_1\), \(\$_2\) symbols must be adjacent, or the first component cannot reach the accepting state. To see this, note that the first component initiates the first query after reading the symbol \(\$_1\). Since leftmost input symbol is \(\cent \), the second component must respond to this query by sending the state \(s_{\cent }\), and after receiving \(s_{\cent }\), the first component can only continue by reading a \(\$_2\) symbol. This means that the input string must be of the form \(\cent \alpha '\) where \(\alpha '\) contains exactly one occurrence of the substring \(\$_1\$_2\).
The transition relations are defined in such a way that the computation must start with
and then
where \(\cent w\$_1\$_2 w'(k)=\$_1\), that is, the kth symbol of the input is the \(\$_1 \) symbol and it has just been read by the first component.
To see that this phase of the computation is reversible, consider the following.

If the states of the components are \((s_{0,1}',s_{\cent })\), then the previous computational step must have been a reading step where the first component made a \(\lambda \)move, and the second component made a non\(\lambda \)move, so for any configuration \((\cent w\$_1\$_2 w', s_{0,1}',i, s_{\cent },j)\) with \(i,j\ge 1\), the previous configuration must have been \((\cent w\$_1\$_2 w', s_{0,1},i, s_{0,2},j1)\). (This actually must be the initial configuration of the system, since \(s_{0,1}\) cannot be reached by the first component later during the computation.)

If the states of the components are \((s_1,s_{\cent })\), then the previous computational step must have been a reading step where the first component made a non\(\lambda \)move, and the second component made a \(\lambda \)move (without changing the internal state). If the symbol read by the first component was \(\cent \), then the previous configuration must have been \((\cent w\$_1\$_2 w', s_{0,1}',i1, s_{\cent },j)\) for any configuration \((\cent w\$_1\$_2 w', s_{1},i, s_{\cent },j)\), \(i,j> 1\). If the symbol read by the first component was a or b, then the previous configuration must have been \((\cent w\$_1\$_2 w', s_{1},i1, s_{\cent },j)\). (Notice that \(j=2\) in reachable configurations of these forms. Moreover, computational steps in which the first component has read a different symbol (\(\$_1\), \(\$_2\) or \(\triangleleft \)) are not possible.)

If the states of the components are \((s_{1}',s_{\cent })\), then the previous computational step must have been a reading step where the first component made a non\(\lambda \)move, and the second component made a \(\lambda \)move (without changing the internal state). The symbol read by the first component must have been \(\$_1\), so the previous configuration must have been \((\cent w\$_1\$_2 w', s_{1},i1, s_{\cent },j)\) for any configuration \((\cent w\$_1\$_2 w', s_{1}',i, s_{\cent },j)\), \(i,j> 1\).

If the states of the components are \((q_2,s_{\cent })\), then the previous computational step must have been a reading step where both components made \(\lambda \)moves, what is seen as follows. The first component can enter state \(q_2\) in a non\(\lambda \)move only from one of the states \(s_{\cent }\), \(s_a\) or \(s_b\). But none of these states can be received by the first component in a communication step as long as the second component is in \(s_{\cent }\) (in reachable configurations). If the second component would perform a non\(\lambda \) reading step when entering state \(s_{\cent }\), then it must read a \(\cent \) symbol while changing state \(s_{0,2}\) to \(s_{\cent }\). This \(\cent \) symbol cannot be the very first symbol of the input string since the first component cannot reach state \(q_2\) in the very first step. But it can also not be another occurrence of the \(\cent \) symbol as it has been argued further above. Therefore, we can conclude that the second component must have been in state \(s_{\cent }\) in the previous configuration, if reachable, which must have been \((\cent w\$_1\$_2 w', s_{1}',i, s_{\cent },j)\) for any configuration \((\cent w\$_1\$_2 w', q_2,i, s_{\cent },j)\), \(i,j\ge 1\).

If the states of the components are \((s_{\cent },s_{0,2})\), then the previous computational step must have been a communication step with the previous configuration \((\cent w\$_1\$_2 w', q_2,i, s_{\cent },j)\) for any \((\cent w\$_1\$_2 w', s_{\cent },i, s_{0,2},j)\), \(i,j\ge 1\).
Continuing the computation, we have
where x depends on the second symbol on the input tape. Now, if \(x\in \{a,b\}\) and the \((k+2)\)nd symbol of the input is also x, the computation can continue with
where \(x'\) now depends on the third symbol on the input tape. Repeating similar steps, the system is now able to check whether \(w=w'\) in the input string \(\cent w\$_1\$_2w'\). The first component can only read the jth symbol of \(w'\) (which is the \((k+1+j)\)th symbol on the tape), if it is the same as the jth symbol of w (which is the \((1+j)\)th symbol on the tape) that was read in the previous noncommunication step by the second component and transferred in the previous communication step to the first component as the state \(s_x\), for \(x\in \{a,b\}\).
This phase of the computation is also reversible, as can be seen by the following.

If the states of the components are \((q_2,s_x)\) for some \(x\in \{a,b\}\) then the previous computational step must have been a reading step where both components made a non\(\lambda \)move. To see that the first component must also have made a non\(\lambda \)move, note that this configuration cannot be the first configuration of the computation where \(q_2\) appears, since if this was the case, then the second component would be in state \(s_{\cent }\). This implies that the first component cannot enter the state \(q_2\) with a \(\lambda \)move from state \(s_1'\), since it can only be in state \(s_1'\) before any communication happened. If the symbol read by the first component is \(y\in \{a,b\}\), then for any configuration \((\cent w\$_1\$_2 w', q_2,i, s_{x},j)\) with \(i,j>1\), the previous configuration must have been \((\cent w\$_1\$_2 w', s_{y},i1, s_{0,2},j1)\).

If the states of the components are \((s_x,s_{0,2})\) for some \(x\in \{a,b\}\), then the previous computational step must have been a communication step, so for any configuration \((\cent w\$_1\$_2 w', s_{x},i, s_{0,2},j)\) with \(i,j\ge 1\), the previous configuration must have been \((\cent w\$_1\$_2 w', q_2,i, s_{x},j)\).
If the second component reaches the \(\$_2\) symbol before the first component reaches the endofinput \(\triangleleft \), that is, the configuration reached would be of the form \((\cent w\$_1\$_2 w', s_{{\$_1}},2k, s_{0,2},k+1)\) where \(\cent w\$_1\$_2 w'(k+1)=\$_2 \) and \(\cent w\$_1\$_2 w'(2k)\not =\triangleleft \), then the system is blocked in nonaccepting states, because the first component can continue from state \(s_{\$_1}\) only when reading the endofinput symbol. If the first component reaches the endofinput symbol \(\triangleleft \) before the second component reaches the \(\$_2\) symbol, the system is blocked in \((\cent w\$_1\$_2 w', s_{{x}},2j1, s_{0,2},j)\) for some \(x\in \{a,b\}\) and some \(j>k+1\) which is not accepting. Note also that the communication steps before these blocking configurations are reversible.
Thus, in order for the computation to be successful, the two components must reach the endofinput symbol \(\triangleleft \) and the symbol \(\$_2\) simultaneously through the computational steps
These steps of the computation are also reversible, since

having the current states \((q_2,s_{\$_1})\) implies that the previous step was a reading step in which both heads have moved on, because in reachable configurations, the first component has already passed beyond \(\$_2\) (\(k\ge 2\), so \(2k>k+1\)). The state of the first component must have been \(s_x\) with \(x=\alpha (2k1)\), \(x\in \{a,b\}\), and the state of the second component must have been \(s_{0,2}\).

Having the current states \((s_{\$_1},s_{0,2})\) implies that the previous step was a communication step, so for any configurations \((\cent w{\$}_1\$_2 w', s_{{\$}_1},i, s_{0,2},j), i,j \ge 1\), the previous configuration must have been \((\cent w\$_1\$_2 w', q_2,i, s_{\$_1},j)\).

If the current states are \((s_\mathrm{acc},s_{{\$}_2})\), the two components performed reading move in the previous computational steps, and the states of previous configuration must have been \(s_{\$_1}\) and \(s_{0,2}\), respectively.
As the components of PCFA are nondeterministic finite automata (NFA), we may consider the relationship of the reversibility of a PCFA and the reversibility of its components. Since in PCFA, there is an endofinput symbol \(\triangleleft \) and \(\lambda \)steps are allowed in the component automata, we extend the definition of reversibility of NFA as it is given in [10] as follows: Let \(\Sigma '=\Sigma \cup \{\triangleleft \}\). An NFA \(A=(S,\Sigma ,s_0,\delta , F)\) is reversible if

1.
there is no internal state \(s\in S\), such that \(s\in \delta (p,a)\cap \delta (r,a)\) holds for some \(a\in \Sigma '\) and states \(p,r\in S\) with \(p\not =r\);

2.
there is no internal state \(s\in S\), such that \(s\in \delta (p,a)\cap \delta (r,\lambda )\) holds for some \(a\in \Sigma '\cup \{\lambda \}\) and states \(p,r\in S\) with \(p\not =r\).
Note that the fact that systems of (deterministic) reversible automata are not necessarily reversible was already remarked in [9] without giving a formal definition of the notion of reversibility for PCFA systems. In the second part of the following proposition, we give a similar, but more simple demonstration than the one in [9].
Proposition 1

1.
There are reversible PCFA \(\mathcal A=(\Sigma ,A_1,A_2,\ldots ,A_k,Q,\triangleleft )\) such that there is i, \(1\le i\le k\), where \(A_i\) is not reversible.

2.
There are PCFA \(\mathcal A=(\Sigma ,A_1,A_2,\ldots ,A_k,Q,\triangleleft )\) such that the components \(A_i\) are reversible for all \(i,\ 1\le i\le k\), and the system \(\mathcal A\) is not reversible.
Proof
To show that the first statement holds, we can use the reversible PCFA of Example 1. Obviously, neither \(A_1\) nor \(A_2\) are reversible components. Consider for example \(\delta _2 (s_\$,a)=\delta _2(s_a,a)= \delta _2(s_b,a)=s_a\).
To prove the second statement, consider the PCFA \(\mathcal A=(\{a,b\},A_1,A_2,\{q_2\},\triangleleft ) \) where the first component is \( A_1=(\{s_{0,1},s_a,s_a',q_2\},\{a,b\},s_{0,1},\delta _1,\emptyset ) \) with
The second component is defined as \( A_2=(\{s_a,s_1,s_\mathrm{acc}\},\{a,b\},s_{a},\delta _2,\{s_\mathrm{acc}\}) \) with
The reader may easily check that both components are reversible. To see that the system \(\mathcal A\) is not reversible, consider, for example, the computation
If the states of the two components are \((s_a,s_a)\), the previous computational step is not unique. (Therefore, the set of possible previous configurations contains more than one element.) More formally (see Definition 1), there are computational steps
and
which lead to the same pair of states \((s_a,s_a)\), but \(33\not =54\) (since the first one is a communication step, while the second is a non\(\lambda \) reading step).
Notice that we used deterministic centralized systems of degree 2 in both cases.
Some results on the computational capacity
First, we prove that reversible deterministic PCFA are more powerful than reversible deterministic finite automata. It turns out that for accepting a nonreversible regular language with deterministic PCFA, communication is even unnecessary.
Theorem 1
There is a language in \(\mathcal L(\text {revDCPCFA}(2))\cap \mathcal L(\text {revDRCPCFA}(2))\) that cannot be accepted by any reversible deterministic finite automaton.
Proof
First, we prove that for the language \(L=\{\,01^k\mid k\ge 1\,\}\), there is no reversible deterministic finite state automaton. Let A be any deterministic finite automaton accepting L. Assume the number of states of A be n. Let
be the accepting computation for \(01^{n}\), in A, where \(n>2\), which is seen as follows. If \(q_0=p_i\) for some i, \(0\le i\le n\), then the input word \(1^{ni}\) would be accepted. Hence, \(q_0\not =p_i\) for all i, \(0\le i\le n\). Furthermore, state \(p_0\) is not accepting, while every state \(p_i\) with \(i> 1\) is accepting. Thus, \(p_0\not =p_i\), for \(1\le i\le n\). Since A has n states, there are i and j, \(1\le i,j\le n\), with \(i\not =j\), and \(p_i=p_j\). Consider the smallest such i, that is, let i be the smallest number greater than 0 such that there is \(j>i\) and \(p_i=p_j\). Then, \(\delta (p_{i1},1)\cap \delta (p_{j1},1)=p_i\) and \(p_{i1}\not =p_{j1}\). Therefore, A is not reversible.
It is left to show that \(L\in \mathcal L(\text {revDCPCFA}(2))\cap \mathcal L(\text {revDRCPCFA}(2))\). For proving this, we consider the deterministic PCFA
where \( A_1=(\{s_{0,1},s_1,s_2\},\{0,1\},s_{0,1},\delta _1,\{s_2\}) \) with
and \( A_2=(\{s_{0,2},p_1,p_2\},\{0,1\},s_{0,2},\delta _2,\emptyset ) \) with
For any \(01^k\), \(k\ge 1\), the computation of \(\mathcal A\) is as follows:
This computation is accepting as \(\delta _1(s_2,\triangleleft )\) is undefined and \(s_2\) is an accepting state of \(A_1\). As the set of query states is empty, one may consider the DPCFA \(\mathcal A\) to be centralized and both returning and nonreturning. It is left to prove that the PCFA \(\mathcal A\) is reversible.

If, in a configuration reached, the pair of states is \((s_1,p_1)\), then the first component has made a move reading 0 from \(s_{0,1}\), while the second component has made a \(\lambda \)move coming from \(s_{0,2}\), and the predecessor configuration must have been the initial one.

If the states reached are \((s_2,p_2)\), then both components made a non\(\lambda \)move. If the symbol read by the second component was 0, then, for any configuration \((01^k,s_2,i,p_2,j)\), the predecessor configuration must have been the configuration \((01^k,s_1,i1,p_1,j1)\). In fact, in reachable configurations, \(i=3\) and \(j=2\) must hold. If the symbol read by the second component was 1, then the predecessor configuration of \((01^k,s_2,i,p_2,j)\) must have been \((01^k,s_2,i1,p_2,j1)\).

Configurations with other states are not reachable.
Examples 1 and 2 show that the following theorem holds.
Theorem 2
There are noncontextfree languages in \(\mathcal L(\text {revDCPCFA}(2))\) and in \(\mathcal L(\text {revDRCPCFA}(2))\).
Next, we study the relationship of deterministic and nondeterministic centralized systems. In the not necessarily reversible case, deterministic systems are strictly weaker both in returning and nonreturning modes, see [4] for details. For reversible PCFA, we can show a similar result for the nonreturning case.
Theorem 3
\(\mathcal L(\text {revDCPCFA})\subset \mathcal L(\text {revCPCFA})\).
Proof
We show that \(L_\mathrm{nonpal}=\{\, \$w\mid w\in \{a,b\}^+,\ w\not =w^R\, \}\) \(\in \mathcal L(\text {revCPCFA})\). This is sufficient, since \(\mathcal L(\text {revDCPCFA}(k))\subseteq \mathcal L(\text{ DCPCFA }(k))\subseteq \mathcal L(k\text{DFA })\), where \(\mathcal L(k\text{DFA })\) is the family of languages accepted by khead deterministic finite automata as defined in, e.g., [20]. But \(L_\mathrm{nonpal}\not \in \mathcal L(k\text{DFA })\) for any \(k\ge 1\). To see this, recall that \(\mathcal L(k\text{DFA })\) is closed under complementation and under intersection with regular sets, thus, \(L_\mathrm{nonpal}\in \mathcal L(k\text{DFA })\) would imply that \(\overline{L_\mathrm{nonpal}}\cap (\{{\$}\}\{a,b\}^*)=\{{\$}\}\{\ w\mid w\in \{a,b\}^*,\ w=w^R\ \} \in \mathcal L(k\text{DFA })\), but this is not the case, as stated, for example, in [21].
To see that \(L_\mathrm{nonpal}\in \mathcal L(\text {revCPCFA})\), consider the centralized PCFA system
where \( A_1=(\{s_{0,1},s_a,s_a',s_b,s_b',s_\mathrm{acc},q_2,q_3\},\{\$,a,b\},s_{0,1},\delta _1,\{s_\mathrm{acc}\}) \) with
The second component is \( A_2=(\{s_{0,2},s_a,s_b,s_\triangleleft ,s_f\},\{a,b\},s_{0,2},\delta _2,\emptyset \}) \) with
and the third component is \( A_3=(\{s_{0,3},s_\mathrm{acc}\},\{a,b\},s_{0,3},\delta _3,\emptyset \}) \) with
We show that this system is reversible and it accepts the language \(L_\mathrm{nonpal}=\{\, \$w\mid w\in \{a,b\}^+,\ w\not =w^R\, \}\) To see how \(\mathcal A\) works, consider first an initial configuration \( (\alpha ,s_{0,1},1,s_{0,2},1,s_{0,3},1). \) Notice that \(\alpha =\$\alpha '\) for some \(\alpha '\in (a+b)^*\) or the second component cannot read through the input. Note also that if \(\$w\) is accepted, then \(w\ge 2\). To see this, consider a computation on a (shorter) input of the form \(\$x,\ x\in \{\lambda ,a,b\}\). The first step of the computation of \(\mathcal A\) is
where \(s\in \{s_{0,1},q_2\},\ y\in \{a,b\}\). Note that this computational step is reversible, since the states imply that the first component made a \(\lambda \)reading step with the previous state being \(s_{0,1}\), while the other two components made non\(\lambda \)reading steps. Considering that the \({\$}\) symbol was read by these components, we can also deduce that their previous states were \(s_{0,2}\) and \(s_{0,3}\), respectively. Now, if \(x=\lambda \) or \(y\not =x\), then the system is in a nonaccepting blocking configuration (or enters such a configuration with the following—also reversible—communication step) because of the definition of \(\delta _2\). Because of these observations, it is sufficient to consider
with \(x\in \{a,b\}\). If \(s=s_{0,1}\), we have
with \(s\in \{s_{0,1},q_2\},\ y\in \{a,b,\triangleleft \}\). If \(y\not =\triangleleft \), then the system is in a nonaccepting blocking configuration (or enters such a configuration with the following communication), so we must have
with \(s\in \{s_{0,1},q_2\}\), or
In both of these cases, the system is in a nonaccepting blocking configuration (or enters such a configuration with the following communication step), and it is not difficult to see that all the above steps are also reversible. On the other hand, if in (1) we have \(s=q_2\), then
where \(x\in \{a,b\},\ y\in \{a,b,\triangleleft \}\). These steps are reversible, as \(s_x\) at the first component implies that the previous step was a communication, and the states \((s_x',s_y,s_{0,3})\) imply that all components performed non\(\lambda \)reading steps. Further, since the first component read the \({\$}\) symbol, its previous state must be \(s_x\), while the reading of an \(z\in \{a,b,\triangleleft \}\) by the second component implies that its previous state is \(s_z\).
Now, if \(y\not =\triangleleft \), then the system is in a nonaccepting blocking configuration, so we must have
which is also a nonaccepting blocking configuration, since, e.g., the first component has no transition for reading the endofinput symbol \(\triangleleft \) in state \(s_x'\). (Note that this last step is also reversible.)
Consider now the computations on an input \(\$w,\ w\ge 2\). These computations must start with
for some \(s\in \{s_{0,1},q_2\},\ x\in \{a,b\}\). If \(s=q_2\), we get
Similarly, if the first component enters the query state \(q_2\) in a later step, we have
for \(x',y\in \{a,b,\triangleleft \}\) and some head position k. In any of these cases, the system reaches a configuration
where \(x\in \{a,b,\triangleleft \}\) and \(k\ge 2\). If \(\$w(k) \not = x\), then this configuration is a nonaccepting blocking one due to the definition of \(\delta _2\). Otherwise, such a configuration records the information that the kth symbol on the input tape is x (where k is “nondeterministically chosen”). This ends the first phase of the computation.
To see that this phase is reversible, consider the following.

If the states of the components are \((s_{0,1},s_x,s_{0,3})\) or \((q_2,s_x,s_{0,3}),\ x\in \{a,b,\triangleleft \}\), then the first component made a \(\lambda \) reading step, the second and the third non\(\lambda \) reading steps. If the symbol read by the second component was a \({\$}\), then the previous configuration must have been \((\$ w, s_{0,1},1, s_{0,2},1,s_{0,3},1)\), the initial configuration. If the second component read a symbol \(y\in \{a,b\}\), then for any configuration \((\$ w, s,1, s_{x},i,s_{0,3},i)\) with \(s\in \{s_{0,1},q_2\}\), \(i\ge 2\), the previous configuration must have been \((\$ w, s_{0,1},1, s_{y},i1,s_{0,3},i1)\). (Note that in any reachable configuration, if the state of the first component is \(s_{0,1}\) or \(q_2\), then its head is on position 1.)

If the states of the components are \((s_x,s_x,s_{0,3})\), for some \(x\in \{a,b,\triangleleft \}\), then the previous computational step was a communication, so for any configuration \((\$ w, s_x,1, s_{x},i,s_{0,3},i)\), \(i\ge 2\), the previous configuration must have been \((\$ w, q_2,1, s_{x},i,s_{0,3},i)\). (Note that in any reachable configuration with states \((s_x,s_x,s_{0,3})\), the heads of the three components must be on positions (1, i, i) for some \(i\ge 2\).)
Consider now how the computation continues from the configuration
recording the information that the kth symbol on the input tape is x for some \(k\ge 2\) and \(x\in \{a,b\}\). (If \(\$w(k)\not = x\) or \(x=\triangleleft \), then the computation cannot continue.) The next phase of the computation makes sure that w is not a palindrome by checking that the symbol at position \((\$w(k2))\) of the input (the kth position counting from the end of the input) is different from x.
The computation continues by
where \(y,y'\in \{a,b,\triangleleft \},\ j\ge 1\). Now, due to the construction of \(\delta _1\), if in such a configuration the first component enters the communication state \(q_3\), then the \((j+1)\)st symbol of the input word is different from x. Thus, if the step
is performed, then \(\$w(j+1)\not =x\). Now, it remains to be seen that the accepting configuration can only be reached if \(j+1=(\$w(k2))\), that is, if w is a nonpalindrome. In order to successfully terminate, the configurations above must be with \(s_{y'}=s_\triangleleft ,\ s=s_f\) and \(s'=s_\mathrm{acc}\), then we get
which is an accepting configuration. Since the position of the endofinput symbol on the tape is the \((k+j)\)th position, we have that \(\$w=k+j1\) which means that \((\$w(k2))=j+1\), so the input must have been a nonpalindrome.
If j has a different value as above, then either we have a nonaccepting blocking configuration of the form
or we have
for \(y\in \{a,b,\triangleleft \}\), and then a nonaccepting blocking configuration after the communication, namely
From these considerations, we can see that \(L(\mathcal A)=L_\mathrm{nonpal}\), what remains to be shown is the reversibility of the second phase of the computation. To this aim, consider the following.

If the states of the components are \((s_{x'},s_y,s_{0,3})\), then all three components made non\(\lambda \) reading steps. If the symbol read by the first component was a \({\$}\), and the symbol read by the second component was \(z\in \{a,b\}\), then for any configuration \((\$ w, s_{x'},1+i, s_{y},k+i,s_{0,3},k+i)\), the previous configuration must have been \((\$ w, s_{x},i, s_{z},k+i1,s_{0,3},k+i1)\). If the symbol read by the first component was different from \({\$}\), then the previous configuration is \((\$ w, s_{x'},i, s_{z},k+i1,s_{0,3},k+i1)\).

If the states of the components are \((q_3,s_f,s_\mathrm{acc})\), then all components performed non\(\lambda \) reading steps. If the symbol read by the first component was \(x\in \{a,b\}\), then for any configuration \((\$ w, q_3,1+i, s_{f},k+i,s_\mathrm{acc},k+i)\), the previous configuration must have been \((\$ w, s_y',i, s_{\triangleleft },k+i1,s_{0,3},k+i1)\) where \(y\not =x\).

If the states of the components are \((q_3,s_y,s_{0,3})\) for some \(y\in \{a,b,\triangleleft \}\), then all components performed non\(\lambda \) reading steps. If the symbol read by the first and the second components was x and z in \(\{a,b\}\), respectively, then for any configuration \((\$ w, q_3,1+i, s_{y},k+i,s_{0,3},k+i)\), the previous configuration must have been \((\$ w, s_y',i, s_{z},k+i1,s_{0,3},k+i1)\) where \(y\not =x\).

If the states of the components are \((s_x',s_f,s_\mathrm{acc})\), then all components performed non\(\lambda \) reading steps. If the symbol read by the first component was \({\$}\), then for any configuration \((\$ w, s_x',1+i, s_{f},k+i,s_\mathrm{acc},k+i)\), the previous configuration must have been \((\$ w, s_x,i, s_{\triangleleft },k+i1,s_{0,3},k+i1)\). If the symbol read by the first component was different from \({\$}\), then the previous configuration must have been \((\$ w, s_x',i, s_{\triangleleft },k+i1,s_{0,3},k+i1)\).

If the states of the components are \((s_\mathrm{acc},s_f,s_\mathrm{acc})\) or \((s_{0,3},s_x,s_{0,3})\) for some \(x\in \{a,b,\triangleleft \}\), then the previous computational step was a communication. In this case, for any configuration \((\$ w, s_\mathrm{acc},1+i, s_{f},k+i,s_\mathrm{acc},k+i)\) or \((\$ w, s_{0,3},1+i, s_{x},k+i,s_{0,3},k+i)\), the previous configurations must have been \((\$ w, q_3,1+i, s_{f},k+i,s_\mathrm{acc},k+i)\) or \((\$ w, q_3,1+i, s_{x},k+i,s_{0,3},k+i)\), respectively.
Concluding remarks
In this paper, a definition of the concept of reversibility for systems of parallel communicating finite automata (PCFA) has been suggested. The definition covers also nondeterministic PCFA. It was shown that there are reversible PCFA that have nonreversible components and there are nonreversible PCFA in which every component is a reversible finite state automaton. Examples demonstrate that the weakest types of (nontrivial) reversible PCFA, namely reversible deterministic centralized PCFA of degree 2, can recognize noncontextfree languages, both in returning and in nonreturning communication mode. Furthermore, there is a language which can be recognized with a reversible nondeterministic centralized PCFA in nonreturning mode, but it cannot be accepted by any deterministic PCFA. The question whether or not the same statement is true also for reversible nondeterministic returning centralized PCFA is left open here. But there are many more questions regarding the computational power of reversible PCFA that are left for future research work, for instance:

What is the relation between reversible centralized and noncentralized PCFA (deterministic or not)?

What is the relation between reversible centralized returning and nonreturning PCFA (deterministic or not)?

What is the relation between reversible PCFA and reversible oneway multihead finite automata (deterministic or not)?
As to the latter question, it is obvious that deterministic (nondeterministic) reversible oneway multihead finite automata can simulate any type of reversible deterministic (nondeterministic) PCFA. It is to be examined whether the proofs showing the other direction (e.g., see [4]) can be adapted to the reversible case.
Moreover, several decidability problems should be investigated in future research on reversible PCFA, such as:

Given a PCFA \(\mathcal {A}\), is \(\mathcal {A}\) reversible?

Given a PCFA language L, can L be accepted by a reversible PCFA (of the same type)?
References
 1.
Axelsen, H.B.: Reversible multihead finite automata characterize reversible logarithmic space. In: Okhotin, A., MartinVide, C., Shapira, D. (eds.) Language and Automata Theory and Applications (LATA, 2012), Volume 7183 of LNCS, pp. 95–105. Springer, Berlin (2012)
 2.
Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17, 525–532 (1973)
 3.
Bordihn, H., Kutrib, M., Malcher, A.: Undecidability and hierarchy results for parallel communicating finite automata. Int. J. Found. Comput. Sci. 22, 1577–1592 (2011)
 4.
Bordihn, H., Kutrib, M., Malcher, A.: On the computational capacity of parallel communicating finite automata. Int. J. Found. Comput. Sci. 23, 713–732 (2012)
 5.
Bordihn, H., Kutrib, M., Malcher, A.: Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities. Int. J. Found. Comput. Sci. 26, 1101–1126 (2015)
 6.
Brand, D., Zafiropulo, P.: On communicating finitestate machines. J. ACM 30, 323–342 (1983)
 7.
Choudhary, A., Krithivasan, K., Mitrana, V.: Returning and nonreturning parallel communicating finite automata are equivalent. RAIRO Inform. Théor. 41, 137–145 (2007)
 8.
CsuhajVarjú, E., Dassow, J., Kelemen, J., Păun, Gh.: Grammar Systems: A Grammatical Approach to Distribution and Cooperation. Gordon and Breach, Yverdon (1984)
 9.
Ganguly, D., Chatterjee, K., Ray, K.S.: Parallel communicating oneway reversible finite automata system. ArXiv:1903.10428 (2019)
 10.
Holzer, M., Kutrib, M.: Reversible nondeterministic finite automata. In: Phillips, I., Rahaman, H. (eds.) Reversible Computing (RC 2017), Volume 10301 of LNCS, pp. 35–51. Springer, Berlin (2017)
 11.
Klemm, R.: Systems of communicating finite state machines as a distributed alternative to finite state machines. Ph.D. Thesis (Pennsylvania State University) (1996)
 12.
Kutrib, M.: Aspects of reversibility for classical automata. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Computing with New Resources, Volume 8808 of LNCS, pp. 83–98. Springer, Berlin (2014)
 13.
Kutrib, M., Malcher, A.: Reversible pushdown automata. J. Comput. Syst. Sci. 78, 1814–1827 (2012)
 14.
Kutrib, M., Malcher, A.: Oneway reversible multihead finite automata. Theor. Comput. Sci. 682, 149–164 (2017)
 15.
Kutrib, M., Malcher, A., Wendlandt, M.: When inputdriven pushdown automata meet reversiblity. RAIRO Theor. Inf. Appl. 50, 313–330 (2016)
 16.
Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 18–191 (1961)
 17.
MartínVide, C., Mateescu, A., Mitrana, V.: Parallel finite automata systems communicating by states. Int. J. Found. Comput. Sci. 13, 733–749 (2002)
 18.
Morita, K.: Reversible simulation of onedimensional irreversible cellular automata. Theor. Comput. Sci. 148, 157–163 (1995)
 19.
Morita, K.: Twoway reversible multihead finite automata. Fund. Inf. 110, 241–254 (2011)
 20.
Rosenberg, A.L.: On multihead finite automata. IBM J. Res. Dev. 10, 388–394 (1966)
 21.
Wagner, K., Wechsung, G.: Computational Complexity. Reidel, Dordrecht (1986)
 22.
Wood, D.: Theory of Computation. Wiley, New York (1987)
Funding
Open Access funding enabled and organized by Projekt DEAL.
Author information
Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Research supported in part by Project No. K 120558, implemented with the support provided from the National Research, Development and Innovation Fund of Hungary, financed under the K 16 funding scheme.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Bordihn, H., Vaszil, G. Reversible parallel communicating finite automata systems. Acta Informatica 58, 263–279 (2021). https://doi.org/10.1007/s00236021003969
Received:
Accepted:
Published:
Issue Date:
Keywords
 Finite automata
 Reversibility
 Systems of parallel communicating automata