International Journal of Foundations of Computer Science
c World Scienti c Publishing Company
Parallel Communicating Pushdown Automata Systems ERZSE BET CSUHAJ-VARJU Computer and Automation Research Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111 Budapest, Hungary E-mail:
[email protected] CARLOS MARTIN-VIDE Research Group in Mathematical Linguistics and Language Engineering Rovira i Virgili University Pca. Imperial Tarraco 1, 43005 Tarragona, Spain E-mail:
[email protected] VICTOR MITRANA University of Bucharest, Faculty of Mathematics Str. Academiei 14, 70109, Bucharest, Romania E-mail:
[email protected] GYO RGY VASZIL Computer and Automation Research Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111 Budapest, Hungary E-mail:
[email protected] Received (received date) Revised (revised date) Communicated by Editor's name ABSTRACT We consider automata systems consisting of several pushdown automata working in parallel and communicating the contents of their stacks by request, using a communication strategy borrowed from grammar system theory. We investigate the computational power of these mechanisms. We prove that non-centralized parallel communicating pushdown automata systems with a bounded number of components, where each automaton is allowed to issue a query, are able to recognize all recursively enumerable languages. We also present homomorphical characterizations of the class of recursively enumerable languages for the centralized variants, where only a distinguished automaton issues queries. Moreover, we show that these centralized variants are at least as powerful as one-way multihead pushdown automata. Finally, some open problems and further directions of research are discussed. Keywords: parallel communicating systems, pushdown automata, two-stack pushdown automata, n-head pushdown automata
1
1. Introduction Cooperating automata systems with di erent strategies coordinating the work of their components in order to perform computations have been studied for a long time. Without the aim of completeness, we brie y mention some important models. A multiprocessor automaton consists of several nite automata, called processors [1], which are coordinated by a central processing unit that decides which processor is to become active or \frozen" at a given step. Each processor works independently from the other ones according to its internal transition function which depends on the internal state of the processor and the current input symbol. The central processing unit inspects the current states of the processors (a frozen processor preserves its internal state and reading head position) and determines which processors will be active or frozen at the next step. Note that the states achieved by the processors depend exclusively on their current state and input symbol. The strategy of cooperation takes into consideration all internal states at a given step and is limited to timing through which the central unit lets some processors proceed. In another model each automaton is allowed to know the states of all automata. The transition function of one automaton depends on the input symbol currently read and the states of all automata determining a move of its reading head and a new state. An equivalent form of this system is the multihead automaton which reduces all components to just reading heads controlled by a single processing unit with nitely many internal states. Parallel communicating nite automata systems are somewhere in between these extremes. Their components are nite automata working independently but communicating states to each other by request. These systems, whose components communicate with each other under similar protocols to those considered for parallel communicating grammar systems [5, 13], have been introduced in [12]. Every component is entitled to request the state of any other component; the contacted component communicates its current state and remains in the same state (in the non-returning strategy) or enters again the initial state (in the returning strategy). In centralized systems only one component (the master of the system) is allowed to ask a state from the others. We want to stress that each step in an automata system is either a usual accepting step or a communication one; moreover, the communication steps have priority to the accepting ones. We also mention that whenever a component requests a state, the state must be communicated. Another approach along the same lines can be found in [6], where the strategies considered for multistack pushdown automata are similar to those de ned for cooperating distributed grammar systems [5]. The present paper continues the investigation of the e ect of these strategies of communication for systems of automata whose components are pushdown automata. Thus, we distinguish two possible directions: communication by states or by stacks. Since one can easily observe that every two-stack pushdown automaton [11] can be simulated by a parallel communicating pushdown automata system whose components communicate states to each other, we focus our attention on the other way of communication, namely, communication by stacks. 2
In this paper we consider systems which consist of several pushdown automata working in parallel and communicating the contents of their stacks to each other by request. Analogously to the parallel communicating grammar system [13], a similar generative model, we distinguish several variants. In a non-centralized parallel communicating pushdown automata system every automaton is allowed to ask for the contents of the stack of any other component automaton which must satisfy this request. After receiving the stack contents, the receiver automaton stores it in its stack in a LIFO manner while the sender pushdown memory may either remain unchanged (non-returning strategy) or may change to the initial contents (returning strategy). In a centralized system only a distinguished component (the master) is allowed to ask the stack contents of any other component. Note here the di erences between these systems and other mechanisms like multi-head pushdown automata [8, 9], multi-stack pushdown automata or multi-push-down automata [2]. We compare the devices introduced here with all aforementioned devices from the point of view of their computational power. The paper is organized as follows. The next section gives the de nitions of parallel communicating pushdown automata systems and their cooperation protocols, illustrated by two examples. Afterwards, we investigate the computational power of the non-centralized variants. We show that systems with non-returning strategy can be simulated with returning systems of size twice as big as the original size. Then a characterization of the class of recursively enumerable languages is given, systems with two and three components suce for recognizing all recursively enumerable languages under the non-returning and the returning strategy, respectively. We also investigate the centralized variants. These systems are at least as powerful as multi-head pushdown automata irrespectively of the strategy. Moreover, each multi-push-down automaton can be simulated by a centralized parallel communicating pushdown automaton under the non-returning strategy. Finally, homomorphical characterizations of recursively enumerable languages are presented. The closing section brie y discusses some open problems and directions for future research.
2. De nitions and examples We assume the reader to be familiar with the basic concepts of formal language and automata theory, particularly the notions of grammars and pushdown automata. More details can be found in [14]. An alphabet is a nite set of symbols, the set of all words over an alphabet V is denoted by V . The empty word is written as " and V + = V ? f"g. For nite set A we denote by card(A) the cardinality of A; for a word w 2 V , jwjA denotes the number of symbols from set A V in w. Now we introduce the notion of a parallel communicating pushdown automata system. A parallel communicating pushdown automata system of degree n is a construct A = (V; ; A1 ; A2 ; : : : ; An ; K ); where 3
V is the input alphabet, is the alphabet of pushdown symbols, for each 1 i n, Ai = (Qi ; V; ; fi ; qi ; Zi ; Fi ) is a pushdown automaton with the set of states Qi , the initial state qi 2 Qi ; the alphabet of input
symbols V; the alphabet of pushdown symbols ; the initial contents of the pushdown memory Zi 2 ; the set of nal states Fi Qi ; and the transition mapping fi from Qi V [ f"g into the nite subsets of Qi , K fK1; K2 ; : : : ; Kng is the set of query symbols. The automata A1 ; A2 ; : : : ; An are called the components of the system A. If there exists only one component Ai ; 1 i n, such that (r; ) 2 fi (q; a; A) with 2 ; j jK > 0, for some r; q 2 Qi , a 2 V [ f"g, A 2 , then the system is said to be centralized and Ai is said to be the master of the system. For the sake of simplicity, whenever a system is centralized its master is the rst component. A parallel communicating pushdown automata system is schematically represented in Figure 1. input tape
input tape
:::
-
:::
?
-
control unit
-
input tape
::::::
?
-
control unit
-
:::
pd-tape pd-tape Fig. 1. A parallel communicating pushdown automata system.
? control unit
-
pd-tape
As one can see in Figure 1, all stacks are connected with each other, each stack can send its contents to any other stack or receive the contents of any other stack. In the centralized case all stacks send their contents to a distinguished stack. In the case of the non-returning strategy, every stack preserves its contents after sending a copy of it to another component while in the case of the returning strategy the stack returns to its initial contents after communication. 4
By a con guration of a parallel communicating pushdown automata system as above we mean a 3n-tuple (s1 ; x1 ; 1 ; s2 ; x2 ; 2 ; : : : ; sn ; xn ; n ) where for 1 i n,
si 2 Qi is the current state of the component Ai , xi 2 V is the remaining part of the input word which has not yet been read by Ai ,
i 2 is the contents of the ith stack, its rst letter being the topmost symbol.
We de ne two variants of transition relations on the set of con gurations of A in the following way: 1. (s1 ; x1 ; B1 1 ; : : : ; sn ; xn ; Bn n ) ` (p1 ; y1 ; 1 ; : : : ; pn ; yn ; n ); where Bi 2 ; i ; i 2 ; 1 i n; i one of the following two conditions holds: (i) (ii)
K \ fB1 ; B2 ; : : : ; Bn g = ; and xi = ai yi ; ai 2 V [ f"g; (pi ; i0 ) 2 fi (si ; ai ; Bi ); i = i0 i ; 1 i n; for all i; 1 i n such that Bi = Kj and Bj 2= K; i = Bj j i ; for all other r; 1 r n; r = Br r ; and yt = xt ; pt = st ; for all t; 1 t n: i
i
i
i
2. (s1 ; x1 ; B1 1 ; : : : ; sn ; xn ; Bn n ) `r (p1 ; y1 ; 1 ; : : : ; pn ; yn ; n ); where Bi 2 ; i ; i 2 ; 1 i n; i one of the following two conditions holds: (i) (ii)
K \ fB1 ; B2 ; : : : ; Bn g = ; and xi = ai yi ; ai 2 V [ f"g; (pi ; i0 ) 2 fi (si ; ai ; Bi ); i = i0 i ; 1 i n; for all 1 i n such that Bi = Kj and Bj 2= K; i = Bj j i ; and j = Zj ; for all the other r; 1 r n; r = Br r ; and yt = xt ; pt = st ; for all t; 1 t n: i
i
i
i
i
i
The two transition relations de ned above di er when the topmost symbols of some stacks are query symbols. In this case, the components execute a communication step replacing each query symbol with the requested stack contents of the corresponding component. If the topmost symbol of the queried stack is also a query symbol, then rst this query symbol must be replaced with the contents of the corresponding stack. The top of each communicated stack must be a non-query symbol before its contents can be sent to another component. If this condition cannot be 5
ful lled, (a circular query appeared), then the work of the automaton system is blocked. After communication, the stack contents of the sending components remains the same in the case of relation `; whereas it becomes the initial pushdown memory symbol in the case of relation `r : A parallel communicating pushdown automata system whose computations are based on relation ` is said to be non-returning; if its computations are based on relation `r it is said to be returning. The language accepted by a parallel communicating automata system A as above is de ned as
Rec(A) = fx 2 V j (q1 ; x; Z1 ; : : : ; qn ; x; Zn ) ` (s1 ; "; 1 ; : : : ; sn ; "; n ); si 2 Fi ; 1 i ng; Recr (A) = fx 2 V j (q1 ; x; Z1 ; : : : ; qn ; x; Zn ) `r (s1 ; "; 1 ; : : : ; sn ; "; n ); si 2 Fi ; 1 i ng; where ` and `r denote the re exive and transitive closure of ` and `r respectively. In the following we use the notations
rcpcpa(n) - for returning centralized parallel communicating pushdown automata systems of degree n, rpcpa(n) - for returning parallel communicating pushdown automata systems of degree n, cpcpa(n) - for centralized parallel communicating pushdown automata systems of degree n, pcpa(n) - for parallel communicating pushdown automata systems of degree n. If x(n) is a type of automata system, then X (n) is the class of languages accepted by pushdown automata systems of type x(n). For example, RCPCPA(n) is the class of languages accepted by automata of type rcpcpa(n) (returning centralized parallel communicating pushdown automata systems of degree n).
We give now two examples to help the better understanding of the notions de ned above. Example 1: Let us consider the following rpcpa(4) given by the transition mappings of its components.
f1 (q1 ; "; Z1 ) f1 (s1 ; "; Z1 ) f1 (p1 ; "; Z1 ) f1 (h1 ; "; Z1 ) f1 (t1 ; "; a) f1 (r1 ; a; Z1 )
= = = = = =
f(s ; a)g; f(p ; Z )g; f(h ; Z )g; f(r ; Z ); (t ; K )g; f(s ; a)g; f(r ; Z )g;
f2 (q2 ; "; Z2 ) f2 (s2 ; "; a) f2 (p2 ; "; Z2 ) f2 (h2 ; "; Z2 ) f2 (r2 ; a; Z2 )
1
1
1
1
1
1
1
1
3
1
1
1
6
= = = = =
f(s ; K )g; f(p ; a)g; f(h ; Z )g; f(r ; Z ); (q ; Z )g; f(r ; Z )g; 2
1
2
2
2
2
2
2
2
2
2
f4(q4 ; "; Z4) = f(s4 ; Z4 )g; f4 (s4 ; "; Z4) = f(h4 ; Z4 )g; f4 (h4 ; "; Z4) = f(t4 ; Z4 ); (v4 ; K3 Z4 )g; 3 f4 (t4 ; "; Z4) = f(u4 ; Z4 )g; 3 f4 (u4 ; "; Z4) = f(s4 ; Z4 )g; 3 3 f4 (v4 ; "; a) = fp4 ; a)g; 3 3 f4 (p4 ; a; a) = f(p4 ; ")g; f4 (p4 ; "; Z4) = f(r4 ; Z4 )g: The sets of nal states are F1 = fr1 g, F2 = fr2 g, F3 = fr3 g, F4 = fr4 g. We explain how this automata system accepts the language fa2 j n 1g: The f3 (q3 ; "; Z3 ) f3 (s3 ; "; a) f3 (p3 ; "; a) f3 (h3 ; "; a) f3 (h3 ; "; Z3 ) f3 (r3 ; a; Z3 )
= = = = = =
f(s ; K )g; f(p ; K a)g; f(h ; a)g; f(q ; a)g; f(r ; Z )g; f(r ; Z )g: 3
1
3
2
n
idea behind the above construction is as follows. At the rst communication step the contents of the rst stack, which consists of just one a, is requested by the second and the third components. In the next communication step the contents of the third stack is doubled by receiving the contents of the second stack. Now, the rst two components receive simultaneously the contents of the third stack such that both of them have the same contents which is an , where n is a power of 2. Nondeterministically, the fourth component requests the stack contents of the rst component and starts to check whether the input string has exactly as many as as its stack has. This is the only condition in which the fourth component can successfully end its computation. During this phase no communication step involving the fourth component is possible anymore and the other components may enter their nal states. Note that at every step each stack contains either a number of as which is a power of 2 or its initial symbol. Consequently, the language accepted by this automata system is fa2 j n 1g: Example 2: A more intricate way of computation can be observed in the following cpcpa(2). n
f1 (q1 ; X; Z1 ) = f(q1 ; Z1 )g; f2 (q2 ; X; Z2 ) = f(q2 ; XZ2)g; f1 (q1 ; c; Z1 ) = f(s1 ; K2Z1 )g; f2 (q2 ; X; Y ) = f(q2 ; XY )g; f1 (s1 ; "; X ) = f(s1 ; K2X )g; f2 (q2 ; c; X ) = f(s2 ; X )g; f1 (s1 ; "; Z2 ) = f(p1 ; ")g f2(s2 ; "; X ) = f(s2 ; ")g; f1 (p1 ; X; X ) = f(p2 ; ")g; f2 (s2 ; "; Z2 ) = f(sf ; Z2 )g; f1 (p2 ; "; X ) = f(p2 ; ")g; f2 (sf ; "; Z2 ) = f(sf ; Z2 )g; f1 (p2 ; "; Z2 ) = f(p1 ; ")g f2 (sf ; X; Z2 ) = f(sf ; Z2 )g; f1 (p1 ; "; Z1 ) = f(pf ; Z1 )g; where X; Y 2 fa; bg, and the sets of nal states are F1 = fpf g, F2 = fsf g. The language recognized by this system is fxcx j x 2 fa; bg+g, which can be seen as follows. Both components move their reading heads to the right until the symbol c is scanned, the second component storing the currently read symbols in its memory. When the rst component, the master, scans the symbol c; it requests the contents of the second stack which is mi(x)Z2 (here mi(x) denotes the mirror image of x) where xcy is the input word. Now, at every further step the second component erases the top of its stack and sends the new stack contents to the master till the second stack memory is reduced 7
to Z2 . At this moment the stack contents of the master is
Z2 mi(x(1) )Z2 mi(x(2) )Z2 : : : Z2 mi(x(jxj?1))Z2 mi(x)Z2 where x(k) denotes the pre x of x of length k. Then, the rst component checks whether or not
y = (mi(x(1) ))(1) (mi(x(2) ))(1) : : : (mi(x(jxj?1) ))(1) (mi(x))(1) ; that is, y = x holds. The following relations follow directly from de nitions.
Lemma 1:
1. RCPCPA(n) RPCPA(n) and CPCPA(n) PCPA(n) for all n 1. 2. X (1) equals the family of context-free languages and X (n) X (n + 1) for X 2 fRCPCPA; RPCPA; CPCPA; PCPAg; n 1.
3. Computational power We start by showing how non-returning parallel communicating pushdown automata systems can be simulated with returning systems. Theorem 2: PCPA(n) RPCPA(2n) for all n 2. Proof. Let A = (V; ; A1 ; A2; : : : ; An; K ) be a pcpa(n) with Ai = (Qi , V , ; fi; qi ; Zi ; Fi ), 1 i n. We construct the rpcpa(2n) A0 = (V; 0 ; A01 ; A1 ; A02 ; A2 ; : : : ; A0n ; An ; K 0); where K 0 = fK10 ; K20 ; K30 ; : : : ; Kn0 g [ fK 1 ; K 2; K 3 ; : : : ; K ng, and for all 1 i n, A0i = (Qi [ fq0 j q 2 Qi g; V; [ fK i g; fi0; qi ; Zi ; Fi ); with
(1) fi0 (q; a; A) = f(r0 ; x) j (r; x) 2 fi (q; a; A)g; (2) fi0 (q0 ; "; Zi ) = f(q; K i )g; where q; r 2 Qi ; a 2 V [ f"g; A 2 , and Ai = (fqi g; V; [ fZi ; Ki0g; fi ; qi ; Zi ; fqi g); with
(3) fi (qi ; a; Zi ) = f(qi ; Ki0 )g; (4) fi (qi ; "; A) = f(qi ; A)g; where a 2 V [ f"g; A 2 . As one can easily see, every component of A has a \satellite" component in A0 . Each accepting step in A is simulated by two accepting and two communication steps in A0 in the following way: 8
In the rst accepting step A0i and Ai use the rules (1) and (3), respectively. Now the stacks of all components A0i have the same contents as the corresponding ones in A. Moreover, the current states of A0i are copies of the current states of the corresponding ones in A. In the rst communication step each satellite Ai receives the stack contents of the associate component A0i . Notice that the memory contents of several components in the set fA01 ; A02 ; : : : ; A0n g can be requested simultaneously by their satellites as well as by other components in the same set. In the second accepting step components Ai preserve their memories by means of rules (4), while components A0i request the memory contents of their satellites using rules (2). Finally, in the second communication step A0i recover their memories in the same states as the corresponding components in A. By these explanations we can see that Rec(A) = Recr (A0 ). 2 We continue with the discussion of the computational power of non-returning parallel communicating pushdown automata systems. We show that any two-stack pushdown automaton can be simulated with a pcpa(2). It is known that every recursively enumerable language is accepted by a two-stack pushdown automaton [11] and thus pcpa(2)s form a class of computationally complete devices. A two-stack pushdown automaton is a construct A = (Q; V; ; f; q0 ; Z01; Z02 ; F ) where Q; V; ; q0 ; F are parameters of the same meaning as in a usual pushdown automaton, Z01 and Z02 are the initial contents of the two stacks, respectively, and f is a mapping from Q V [ f"g 2 into the nite subsets of Q . Informally, (q; ; ) 2 f (s; a; A1 ; A2 ) indicates that the automaton in state s with A1 and A2 as the top symbols of the stacks, reading a on the input tape, may enter state q and write ; in the two stacks, respectively. Acceptance is de ned in the usual way. Theorem 3: PCPA(2) equals the family of recursively enumerable languages. Proof. Let A = (Q; V; ; f; q; B1; B2; F ) be a two-stack pushdown automaton. We construct the pcpa(2)
A = (V; 0 ; A ; A ; fK ; K g) with 0 = [ fZi ; [q; a; X; Y; ; ]i j (q; ; ) 2 f (r; a; X; Y ); q; r; 2 Q; a 2 V [ f"g; X; Y 2 ; 1 i 2g; and Ai = (Qi ; V; 0 ; fi ; qi ; Zi ; F 0 ); 1 i 2; where Qi = fqch; qrec ; qw ; [q; ]; [q; ] j (q; ; ) 2 f (r; a; X; Y ); q; r; 2 Q; a 2 V [ f"g; X; Y 2 g [ fhq; X i j q 2 Q; X 2 g [ fq ; q g; and F 0 = fqch; qrec j q 2 F g. 1
2
1
1
The transition mappings are de ned as follows.
2
2
(1) f1(q1 ; "; Z1 ) = f(qch ; B1 Z1 )g; f2(q2 ; "; Z2 ) = f(qrec ; B2 Z2 )g: 9
This is the initial step in which both components change their states and stack contents in order to begin the simulation. (2) f1 (qch ; a; X ) = f(qch ; [r; a; X; Y; ; ]1 ) j (r; ; ) 2 f (q; a; X; Y ); Y 2 g; f2 (qrec ; "; X ) = f(hq; X i; K1)g;
f1 (qrec ; "; X ) = f(hq; X i; K2)g; f2 (qch ; a; Y ) = f(qch ; [r; a; X; Y; ; ]2 ) j (r; ; ) 2 f (q; a; X; Y ); X 2 g; where a 2 V [ f"g; X 2 : The rst automaton, being in a state qch ; q 2 Q, reading a 2 V [f"g on its input tape and X from its memory, chooses a possible move of the two-stack automaton in the same state, reading the same input symbol and reading X from its rst stack. This move is encoded in one pushdown memory symbol and stored in the memory of the rst component. The other component, being in state qrec ; q 2 Q requests the memory contents of the rst component without moving its reading head. With the second group of transitions of (2) the same process can be done, but with A2 choosing a possible transition of A to be simulated. In the course of the simulation A1 and A2 take turns in choosing the simulated transitions. (3) f1(qch ; "; [r; a; X; Y; ; ]1 ) f1 (qw ; "; X ) f2 (hq; Y i; a; [r; a; X; Y; ; ]1 ) f2 ([q; ]; "; X ) f2 ([q; ]; "; Z1 )
= = = = =
f(rw ; )g; f(qw ; X ); (qrec; X )g; f([r; ]; ")g; f([q; ]; ")g; f(qch ; )g;
f2(qch ; "; [r; a; X; Y; ; ]2 ) f2 (qw ; "; X ) f1 (hq; X i; a; [r; a; X; Y; ; ]2 ) f1 ([q; ]; "; X ) f1 ([q; ]; "; Z2 )
= = = = =
f(rw ; )g; f(qw ; X ); (qrec; X )g; f([r; ]; ")g; f([q; ]; ")g; f(qch ; )g;
where q 2 Q and a 2 V [ f"g. Now, the second component checks whether the top of its stack ts the move chosen by the rst component at the previous step. If it does not t, then the system is blocked because the second component remains blocked. Otherwise, this component moves its reading head to the same position where the reading head of the rst component is, stores the word that is to be pushed into its memory according to the aforementioned move of the two-stack automaton, and deletes the copy of the stack contents of the rst automaton received in the previous communication step. This part is completely removed when the symbol Z2 appears on the top of the stack. After these deletions, the second component rewrites its stack and gets 10
ready to choose the next transition to be simulated. This will be done with the second group of rules in (2). In the same time the rst component changes its state and the top of its stack according to the transition chosen before, and waits for the second component to choose the next transition. With the second group of transitions in (3), the same process is done by exchanging the roles of A1 and A2 . Consequently, Rec(A) = Rec(A). Thus we proved that every recursively enumerable language can be obtained by a pcpa(2): Since the languages accepted by pcpas are recursively enumerable, the statement follows. 2 By Theorem 2 rpcpa(4)s are also computationally complete. However, the next statement demonstrates that returning parallel communicating automata systems are almost as economical devices for describing the class of recursively enumerable languages as the non-returning variants. Theorem 4: RPCPA(3) equals the family of recursively enumerable languages. Proof. We rst show that for every two-stack pushdown automaton we can construct an rpcpa sytem with three components such that the two devices accept the same language. Let A = (Q; V; ; f; q0 ; Z01 ; Z02; F ) be a two-stack pushdown automaton. Let us associate to any transition (r; ; ) 2 f (q; a; A; B ); where q; r 2 Q; a 2 V [ f"g; A; B 2 ; ; 2 a new symbol [q; a; A; B; r; ; ] and let us denote the set of these symbols by t : Moreover, let Q0 = fq0 j q 2 Qg and Qc = fhq; x; X i j q 2 Q; x 2 V [ f"g; X 2 g: The simulating rpcpa A is constructed as follows:
A = (V; A ; A ; A ; A ; fK g); where A = fZ ; Z ; Z ; g [ [ t ; and A = (Q [ Q0 ; V; A ; f ; q ; Z ; F ) A = (Q [ Qc; V; A ; f ; q ; Z ; F ) A = (Q [ Qc; V; A ; f ; q ; Z ; F ): 1
1
2
2
3
1
3
1
1
0
1
2
2
0
1 0
3
3
0
2 0
We de ne the transition mappings of the components as follows: (1) f1 (q; a; Z1 ) = f(r0 ; [q; a; A; B; r; ; ]) j [q; a; A; B; r; ; ] 2 t g; f2(q; a; A) = f(hq; a; Ai; K1 )g; f3 (q; a; B ) = f(hq; a; B i; K1 )g; where q 2 Q; a 2 V [ f"g; A; B 2 , (2)
f1 (r0 ; "; Z1 ) = (r; Z1 ); f2 (hq; a; Ai; "; [q; a; A; B; r; ; ]) = f(r; )g; f3 (hq; a; B i; "; [q; a; A; B; r; ; ]) = f(r; )g;
where r0 2 Q0 ; [q; a; A; B; r; ; ] 2 t . 11
The equal accepting power of the two devices can easily be veri ed. Suppose that the two-stack pushdown automaton in state q reads symbol a (or the empty word) from its input tape and has the topmost symbols A and B , respectively. In the next computation step it removes symbols A and B , enters state r and appends strings and to the contents of its stacks. This transition can be simulated in A as follows: The rst component, A1 ; in state q reads symbol a (or the empty word) from the input tape and replaces symbol Z1; the top symbol of its pushdown memory, with the symbol [q; a; A; B; r; ; ] to indicate which transition of A will be simulated. At the same time, components A2 and A3 ; both being in state q, read symbols x and y (or the empty word), from their input tapes, and symbols X and Y from their stacks, and enter states hq; x; X i and hq; y; Y i; respectively. Moreover, they issue a query asking for the memory contents of the rst component, [q; a; A; B; r; ; ]. After communication, the next step will be successful if and only if x = y = a; X = A; and Y = B hold. If these conditions are ful lled, A2 and A3 push strings and into their stacks, respectively, and enter state r without moving their reading heads, while A1 also enters the state r indicating that the system is ready for simulating another transition of A. Each transition of A can be simulated with two consecutive transitions of A: By the construction of A; any successful computation in A is a sequence of consecutive transitions of type (1) and (2), thus, the equality of the languages accepted by A and A follows. Since any recursively enumerable language can be accepted by a two-stack pushdown automaton, the statement of the theorem holds. 2
4. Centralized systems We start this section by comparing the computational power of the centralized variants of automata systems with the computational power of multi-head pushdown automata. We shall use here the following de nition of multi-head pushdown automata. A k-head pushdown automaton is a construct A = (k; Q; V; ; f; q0; Z0 ; F ); where Q; V; ; q0; Z0 ; F have the same meaning as for a usual pushdown automaton, and f is a mapping from Q (V [ f"g)k into the set of nite subsets of Q . The above de nition is similar to the one found in [8] and [9]. Thus, (q; x) 2 f (s; a1 ; a2 ; : : : ; ak ; A) indicates that the automaton in state s, with symbol A on the top of its stack, the ith head reading ai may enter state q and write x in the pushdown memory. The input heads may pass over one another freely and they are prevented from going o the right end of the input. If a head reads ", it does not move to the right and if it reads a symbol in V , it moves to the right one position. A string is accepted if the automaton starts in the initial state with the string on the input tape and Z0 in the pushdown memory, all heads being positioned on the leftmost symbol of the input, and enters, after nitely many moves, in a nal state, the input being completely read by all heads. For a multi-head pushdown automaton A as above we denote by Rec(A) the set of strings accepted by A. Theorem 5: Each language accepted by an n-head pushdown automaton is accepted by an automata system x(n) with x 2 frcpcpa; cpcpag. Proof. First we to give the proof for rcpcpas. Let A = (n; Q; V; ; f; q0; Z0; F ) be 12
an n-head pushdown automaton. We construct the following automata system
A = (V; 0 ; A ; A ; : : : ; An ; fK ; K ; : : : ; Kng) where 0 = [ (V [ f"g)0 [ fZ ; Z ; : : : ; Zn g, A1 = (Q [
n[ ?1 k=1
1
2
2
3
2
3
(Q (V [ f"g)k ); V; 0 ; f1 ; q0 ; Z0 ; F );
Ai = (fqi g; V; 0 ; fi ; qi ; Zi ; fqi g); where 2 i n; and (V [ f"g)0 denotes the set of symbols fX 0 j X 2 V [ f"gg: The transition mappings are de ned by
f1 (q; "; Y ) f1 (q; "; X 0 ) f1 ([q; X2 ; : : : ; Xj ]; "; X 0 ) f1 ([q; X2 ; : : : ; Xn?1]; "; X 0 ) f1 ([q; X2 ; : : : ; Xn ]; X; A)
= = = = =
f(q; K Y )g; f([q; X ]; K )g; f([q; X ; : : : ; Xj ; X ]; Kj )g; f([q; X ; : : : ; Xn? ; X ]; "g; 2
3
2
2
+2
1
f (q; X; X2 ; : : : ; Xn ; A);
where Y 2 ; X 2 V [ f"g; 2 j n ? 2; and
fi (qi ; X; Zi ) = f(qi ; X 0)g; fi (qi ; "; X 0 ) = f(qi ; X 0)g; for X 2 V [ f"g, and 2 i n. The whole system behaves as an n-head automaton because each component of the system, except the master, simulates a head of the automaton by reading a symbol or " and sending this information to the master. The master collects, in turn, all these symbols, then it reads a symbol on its input tape and e ectively simulates a move in the automaton A. Therefore, Recr (A) = Rec(A) holds, which concludes the rst part of our proof. Let us modify the mappings fi , 2 i n, from above as follows:
fi (qi ; X; Zi ) fi (qi ; "; X 0) fi (sj ; "; X 0) fi (sn ; "; X 0)
= = = =
f(qi ; X 0 )g; f(s ; X 0)g; f(sj ; X 0 )g; f(qi ; Zi )g; 2
+1
where 2 j n ? 1 and X 2 V [ f"g, adding the new states to the corresponding sets of states. It is easy to note that the new automata system recognizes, in the non-returning strategy, the language Rec(A). 2 Ibarra showed that the languages accepted by multihead nondeterministic pushdown automata satisfy the semilinear property [10]. By Example 1 we obtain that rpcpas are strictly more powerful than multihead pushdown automata. We shall 13
prove now that cpcpas are at least as powerful as multi-pushdown automata introduced in [2] which are actually multi-stack pushdown automata working under a very particular strategy. This strategy assumes that the stacks, which might be empty, are arranged in a linear order, only the top symbol of the rst non-empty stack being available. One cannot read the top of the other stacks but one can write on all of them (including the empty ones) in a LIFO manner. We recall below the de nition and the working mode of these automata in an informal way. The reader interested in more detail is referred to [2]. An n-pushdown automaton, n 1, is a construct M = (n; Q; V; ; f; q0 ; Z0 ; F ), where Q; V; ; q0 ; Z0 ; F have the same meaning as for a usual pushdown automaton, and f is a mapping from Q (V [ f"g) into the set of nite subsets of Q ( )n . With the move (s; x1 ; x2 ; : : : ; xn ) 2 f (q; a; A) the automaton M performs the following actions: Reads a from the input tape and moves past the read symbol (note that a may be "). Reads A which is the top symbol of the rst non-empty stack. Enters the state s. Writes in parallel the strings xi on the i-th stack, 1 i n. A string w is accepted by M if and only if there is a computation in M which starts in the initial state q0 with w on the input tape and Z0 in the rst stack, the other stacks being empty, and ends in a nal state after completely reading the input string. The next result shows that the centralized pcpas are at least as powerful as multi-pushdown automata. Theorem 6: Every language accepted by an n-pushdown automaton is accepted by a cpcpa(n + 1), n 1. Proof. Let M = (n; Q; V; ; f; q0; Z0; F ) be an n-pushdown automaton. Without loss of generality we may assume that at least one stack is non-empty at every computational step in M . We construct the following cpcpa(n + 1):
A = (V; 0 ; A ; A ; A ; : : : ; An ; fK ; K ; : : : ; Kn g); where 0 = [ fYi j 0 i ng [ f[q; a; A; s; B; xi ; r] j (s; x ; x ; : : : ; xn ) 2 f (q; a; B ) for some a 2 V [ f"g; A; B 2 ; r = 0; 1; 1 i ng; and 0
1
2
1
2
1
2
Ai = (Qi ; V; 0 ; fi ; s0 ; Yi ; F ); for 0 i n, with
Q0 = Q [ fqe ; s0 g [ n [ fhq; a; s; x1 ; x2 ; : : : ; xi ; B i j q; s 2 Q; (s; x1 ; x2 ; : : : ; xn ) 2 f (q; a; A) i=1
for some a 2 V [ f"g; B 2 [ f"g; A 2 g [ fq0 j q 2 Qg; Qi = Q [ fs0 g [ fqj j q 2 Q; 1 j ng; 14
for 1 i n, and the transition mappings fi , 0 i n, are de ned as follows:
fi (s0 ; "; Yi ) =
f(q ; Yi )g; if i 6= 1; f(q ; Z Y )g; if i = 1: 0 0
0
1
The components Ai , 1 i n, work independently from each other in order to simulate the corresponding stacks of M . Clearly, one needs a control mechanism which makes sure that the independent choice of each component is the correct one, that is all reading heads are on the same position on their input tapes, the current state is the same for all components, and the operations in each stack are done according to the transition mapping f . This control is accomplished by the master of the system which is A0 . The master gets into communication with all components, in turn, and checks whether or not their choices were made correctly. After the rst step of any computation all components of A are in the same state, q0 , and the contents of their stacks is the same as those of M; except the initial symbols Yi ; 1 i n, which are used to mark the bottom of the stacks. Let for all 1 i n,
fi (q; a; A) = f(p1 ; [q; a; A; p; B; x; r]) j (p; x1 ; : : : ; xi = x; : : : ; xn ) 2 f (q; a; B ); B 2 ; r = 0; 1g; where q 2 Q; a 2 V [ f"g; A 2 [ fYi g; and
fi (pj ; "; X ) = f(pj+1 ; X )g; for X 2 0 n ( [ fYi g), 1 j n, and f(p; xA)g; if r = 0; fi (pn+1 ; "; [q; a; A; p; B; x; r]) = f(p; x)g; if r = 1: Each component makes a choice which is encoded in the top symbol of its stack and then waits for the master to check the correctness of all choices. The coded choice [q; a; A; p; B; x; r] of Ai means the following: If r = 1 then the rst non-empty stack of M is the i-th one, M is in state q; reads a on the input tape and A = B is the topmost symbol of the i-th stack. Then M enters state p and writes x on the i-th stack. If r = 0 then A is the topmost stack symbol of the i-th stack or Yi if the i-th stack is empty, the symbol B is read from the rst non-empty stack of M which is di erent from the i-th one. The waiting phase is realized by means of the intermediate states pj , 1 j n. Now the master starts to check whether each component has made a correct choice. It requests the contents of the stacks in the order 1; 2; : : :; n.
f0 (q; "; Y0 ) = f(q0 ; K1)g; f(qe ; [q; a; A; p; B; x; 0])g; if A 6= Y1 ; f0 (q0 ; "; [q; a; A; p; B; x; 0]) = f(hq; a; p; x; "i; K2 )g; if A = Y1 ; f(qe ; [q; a; A; p; B; x; 1])g; if A 6= B; f0 (q0 ; "; [q; a; A; p; B; x; 1]) = f(hq; a; p; x; Ai; K2 )g; if A = B: 15
For all 1 i n ? 2,
f0 (hq; a; p; x1 ; : : : ; xi ; "i; "; [q; a; A; p; B; y; 0]) = f(qe ; [q; a; A; p; B; y; 0])g; if A 6= Yi+1 ; f(hq; a; p; x1 ; : : : ; xi ; y; "i; Ki+2 )g; if A = Yi+1 ; and for all 1 i n ? 1, f0 (hq; a; p; x81 ; : : : ; xi ; "i; "; [q; a; A; p; B; y; 1]) = < f(qe ; [q; a; A; p; B; y; 1])g; if A 6= B; a; p; x1 ; : : : ; xi ; y; Ai; Ki+2 )g; if A = B and 1 i n ? 2; : ff((hhq; q; a; p; x1 ; : : : ; xi ; y; Ai; Y0 )g; if A = B and i = n ? 1; f0 (hq; a; p; x1 ; : : : ; xi ; C i;"; [q; a; A; p; B; y; 0]) = f(hq; a; p; x1 ; : : : ; xi ; y; C i; Ki+2 )g; 1 i n ? 2; f(hq; a; p; x1 ; : : : ; xi ; y; C i; Y0 )g; i = n ? 1; f0 (hq; a; p; x1 ; : : : ; xi ; C i; "; [q; a; A; p; B; y; 1]) = f(qe ; [q; a; A; p; B; y; 1])g: If a component makes an incorrect choice, the system blocks, since the master enters the error state qe . If all components make correct choices, the master enters the state hq; a; p; x1 ; : : : ; xn ; Ai; which means that the system has performed a correct simulation of the move (p; x1 ; : : : ; xn ) 2 f (q; a; A) in M . By the transition
f0 (hq; a; p; x1 ; : : : ; xn ; Ai; a; Y0 ) =
f(p; Y )g; if (p; x ; : : : ; xn ) 2 f (q; a; A); f(qe ; Y ); otherwise, 0
1
0
the master resumes its work. Now all components are again in the same state, the stack contents of the last n components being the same as those of M , except the symbols Yi , 1 i n. Moreover, the reading heads are on the same position on their own input tapes. Since the set of nal states of all components is the same as that of M , the language recognized by A is included in the language recognized by M . From the above explanations one can see that the converse inclusion holds as well. 2 A natural problem arises: Are these systems powerful enough to recognize all recursively enumerable languages? We cannot answer this question but we provide homomorphical characterizations of recursively enumerable languages based on languages accepted by these variants of pushdown automata systems. To this end, we recall two operations on words and languages useful in our considerations. A homomorphism which erases some symbols and leaves unchanged the others is said to be a projection. A projection h : (V [ V 0 ) ?! V that erases the symbols in V 0 only is denoted by prV . The other operation is a well-known operation in formal language theory and in parallel programming theory, called shue. A shue of two strings is an arbitrary interleaving of the substrings of the original strings, like shuing two decks of cards. More precisely, the shue operation ? t on two strings 16
over an alphabet V is de ned in the following manner:
x ?t " = " ?t x = x; x 2 V ; ax ?t by = a(x ?t by) [ b(ax ?t y); x; y 2 V ; a; b 2 V: For two languages L1 ; L2 we de ne [ x ?t y: L1 ?t L2 = (i) (ii)
x2L1;y2L2
For an alphabet V we de ne the twin-shue S language TS (V ) over V as follows. t x, where x is obtained from x Let V = fa j a 2 V g and then TS (V ) = x2V x ? by replacing each letter in x with its barred version, the empty word is replaced by itself. We can nd the following representation of recursively enumerable languages in [7]: Theorem 7: Each recursively enumerable language L T can be written as L = prT (TS (V ) \ R), where V is an alphabet including T, R is a regular language and TS (V ) is the twin-shue language over the alphabet V. Then the next statement can be presented.
Theorem 8:
1. A language L T is recursively enumerable i L = prT (Recr (A)), where A is an automata system x(2) with x 2 frcpcpa; rpcpag. 2. A language L T is recursively enumerable i L = prT (Rec(A)), where A is a cpcpa(2). Proof. In [12] the reader can nd parallel communicating nite automata with two components recognizing the language TS (V ), for a given V . These mechanisms can be simulated by multihead nite automata (the same reference for a formal proof), hence, by Theorem 5, TS (V ) can be recognized by an x(2), x 2 frcpcpa; cpcpag, and then also by an rpcpa(2). By using standard methods we can construct an automata system to accept TS (V ) \ R; where R is a regular language. 2
5. Final remarks We start this section with some open problems. 1. What is the computational power of rpcpa(2)s? Are rpcpa(2)s less powerful than rpcpa(3)s ? 2. Can centralized automata systems recognize all recursively enumerable languages? 3. Which of the inclusions from Theorem 5 is strict? Are centralized nonreturning automata systems strictly more powerful than multi-push-down automata? 4. Is any of the hierarchies X (n) X (n + 1), X 2 fCPCPA, RCPCPAg, in nite? 17
Finally, we mention some further direction of research. It is known that every nondeterministic k-head pushdown automata language can be recognized by a deterministic Turing machine in n2:81k time, see, e.g., [15] or [4]. A similar result holds for multi-pushdown languages [3]. What can we say about the time complexity of languages recognized by pushdown automata systems of type rcpcpa or cpcpa? We have considered in this paper automata systems which accept by nal states. One can consider automata systems accepting by empty stacks. It is not dicult to notice that some results presented above, see, e. g., Theorems 2, 3, 4, hold for automata systems accepting in this way, too. Along the same lines, it would be of interest to consider deterministic pushdown automata systems as well.
Acknowledgements This research was supported in part by the grants of the Hungarian Scienti c Research Fund \OTKA" Grant No. T 029615, and the Direccion General de Ense~nanza Superior e Investigacion Cienti ca, SB 97{00110508.
References
1. A. O. Buda, \Multiprocessor automata," Inform. Process. Lett. 25 (1977) 257{261. 2. L. Breveglieri, A. Cherubini, C. Citrini, S. Crespi Reghizzi, \Multi-push-down languages and grammars," Internat. J. Found. Comput. Sci. 7 (1996) 253{291. 3. A. Cherubini, P. San Pietro, \A polynomial-time parsing algorithm for k-depth languages," J. Comput. System Sci. 52 (1996) 61{79. 4. S. A. Cook, \Characterizations of pushdown machines in terms of time - bounded computers," J. ACM 18 (1971) 4{18. 5. E. Csuhaj-Varju, J. Dassow, J. Kelemen, Gh. Paun, Grammar Systems. A grammatical approach to distribution and cooperation (Gordon and Breach, Amsterdam, 1994). 6. J. Dassow, V. Mitrana, \Stack cooperation in multi-stack pushdown automata," J. Comput. System Sci. 58 (1999) 611{621. 7. J. Engelfriet, G. Rozenberg, \Fixed point languages, equality languages, and representations of recursively enumerable languages," J. ACM 27 (1980) 499{518. 8. J. Hartmanis, \On nondeterminancy in simple computing devices," Acta Informatica 1 (1972) 336{344. 9. O. H. Ibarra, \On two-way multihead automata," J. Comput. System Sci. 7 (1973) 28{36. 10. O. H. Ibarra, \A note on semilinear sets and bounded-reversal multihead pushdown automata," Inform. Process. Lett. 3 (1974) 25{28. 11. M. A. Harrison, Introduction to Formal Language Theory (Addison-Wesley Publishing Co., Reading, Mass., 1978). 12. A. Mateescu, V. Mitrana, A. Salomaa, \Parallel nite automata systems communicating by states," submitted. 13. Gh. Paun, L. S^antean, \Parallel communicating grammar systems: the regular case," Ann. Univ. Bucharest, Ser. Matem.-Inform. 38 (1989) 55{63. 14. G. Rozenberg, A. Salomaa (eds.), The Handbook of Formal Languages, (Springer-
18
Verlag, Berlin 1997). 15. I. H. Sudborough, \Some remarks on multihead automata," RAIRO Informat. Theor. 11 (1977) 181{195.
19
