Communication Complexity of PC Grammar Systems

Usually, complexity theory is concerned with the complexity measurement of compu-tations in terms of time and space. In 1979, Yao [217] introduced another manner to evaluate a computation, based on the communication spent by the system during the computation. To evaluate a system, by means of communication, he introduced the two-party communication model in which two players, each having access to half of the input, try to collaboratively evaluate a function by minimizing the communication be-tween them. In this model, the time and space required for the players’ computations are irrelevant. Only the type and the amount of the exchanged information matter.

The two-party communication model of Yao was generalized into the multiparty com-munication model [25]. In this model the input is split into k parts and distributed to k players that collaboratively try to evaluate a k-argument function. The players have unlimited computational power, and they communicate by writing bits on a blackboard seen by all players. They use a protocol of collaboration that, at each step of computa-tion, specifies which player writes the next bit on the blackboard and when the process ends up. The model captures the information overlapping phenomenon. The power of the model grows as the number of players increases. For k equal to two, the model is equivalent with the two-party model.

Informally, thecommunication complexityof a computation is the amount of information (e.g., the sum of the lengths of all messages) exchanged during a computational process

Chapter 7. Grammar Systems

between parts of the system that supports the computation. Communication complexity has been identified as an interesting tool for proving lower bounds in the study of small complexity classes.

PC grammar systems are an attracting topic not only because of their composite struc-ture and cooperating/distribuited manner in which the derivation evolves in a parallel fashion, but also because of the very complex communication strategy used by these sys-tems, which remembers about the inter-processors communication and the multiparty communication model. This is the main reason why the investigation of the communi-cation complexity of these systems was an unavoidable issue.

To achieve the communication complexity in PC grammar systems two communication complexity measures have been proved to be illustrative for them [109, 110, 165,166].

The first measure, introduced in [109, 110], is the communication structure of a PC grammar system. This is the shape of the communication graph consisting of directed communication links between the grammars. The second measure, introduced in [110, 165], is the communication complexity of a PC grammar system, and it represents the number of messages (communications) exchanged, during the derivation of a certain word, between the system’s components. This is a function of the length of the generated word. Hence, it is a computational complexity measure.

The communication graph of a PC grammar system [109, 110] is a directed graph in which the vertices are labeled by the system’s grammars and the edges are oriented from the grammar that contains on its sentential form a query symbol, to the grammar to which the query symbol belongs. If Γ is a PC grammar system, then adag-PCGS, tree-PCGS,two-way array-PCGS,one-way array-PCGS,two-way ring-PCGS,one-way ring-PCGS (cycle)is a PC grammar system whose communication graph is a directed acyclic graph, tree, two-way array, one-way array, two-way ring, one-way ring (cycle), respec-tively. Denote by Π(Γ) the communication graph associated to Γ. Letx-P CGSr be the class of PC grammar systems of degreerwhose communication graph is of typex, where² x∈ {c, dag, tree, two-way-array, one-way-array, two-way-ring, one-way-ring(cycle)}.

Denote byL(x-P CGSr) the family of languages generated byx−P CGSr’s whose com-munication graph is of typex, and byx-P CGS_r(f(n)) the class of PC grammar systems having a communication graph of typex, that use at mostf(n) communication steps to generate words of lengthn, and byL(x-P CGS_r(f(n))) the family of languages generated by PC grammar systems inx-P CGSr(f(n)). From [109] we have the next characteriza-tion oftree-P CGS by means of multicounter machines (Definition 4.11).

2Here,cstands forcentralized. Aring(orcycle) is a graph in which each vertex connects exactly two other vertices. Anarrayis a ring in which one of the edges is deleted.

Lemma 7.7. Let Γ be a tree-PCGS(f(n)) of degree m. For some positive integer m and for some function f:N →N, there exists a linear-time nondeterministic (m− 1)-multicounter automaton M, recognizing L(Γ) with 2f(n) reversals and f(n) zero-tests.

Tree-PCGSs and dag-PCGSs can be simulated by off-line multitape Turing machines in linear time, while the former class by using only logarithmic space. Formally we have Theorem 7.8. L(tree-P CGS)⊆N T IM E(n)∩N SP ACE(logn).

Theorem 7.9. L(dag-P CGS)⊆N T IM E(n).

Since for the case of centralized PC grammar systems (c-PCGSs), returning or not retur-ning, the communication graph is a star-tree (an one-level tree composed of the master grammar labeling the root and the other grammars labeling its children) we have Theorem 7.10. For any f:N→ N, f(n) 6∈Ω(n), and any m, k ∈ N, m ≥ 2, k≥ 1, the next relations hold

1. L(c-P CGS2(n))−S

m∈NL(tree-P CGSm(f(n)))6=∅, 2. L(c-P CGS_k+1(k))−S

m∈NL(tree-P CGS_m(k−1))6=∅,

3. L(one-way-array-P CGS_m(f(n)))⊂L(one-way-array-P CGS_m(n)), 4. L(c-P CGSm(f(n)))⊂L(c-P CGSm(n)),

5. L(tree-P CGS_m(f(n)))⊂L(tree-P CGS_m(n)),

6. L(X-P CGSk+1(k−1))⊂L(X-P CGSk+1(k)), X ∈ {c, tree, one-way-array}, 7. S

m∈NL(X-P CGS_m(k−1))⊂S

m∈NL(X-P CGS_m(k)),X∈{c, tree, one-way-array}.

Sketch of proof 1. The first claim is true, due to the existence of the language L = {aⁱ¹bⁱ¹aⁱ²bⁱ²...a^ikb^ikc|k≥1, ij ∈N, forj∈ {1, ..., k}} ∈L(c-P CGS2(n))−S

m∈N L(tree-P CGS_m(f(n))). The second claim is true due to the existence of the language L_k = {aⁱ¹bⁱ¹aⁱ²bⁱ²...a^ikb^i1+i2+...+ikc|k ≥ 1, ij ∈ N, forj ∈ {1, ..., k}} ∈ L(c-P CGSk+1(k))− S

m∈NL(tree-P CGS_m(k−1)). Items 3 - 5 are direct consequences of 1, while 6 and 7

are consequences of 2.

From [109] we recall the following pumping lemma for dag-PCGSs.

Lemma 7.11. Let L be a language generated by a dag-PCGS of degree r > 1. There exists a natural numberN such that every word α∈Lwhose length is at least N can be decomposed as α =α₁β₁α₂β₂...α_mβ_mα_m+1, where β_i 6=λ for every i, 1 ≤ i≤ m, and 1≤ |{β₁, ..., βm}|≤n.Moreover, for all s≥0, the word α1β₁^sα2β₂^s...αmβ^s_mαm+1 is inL.

As a consequence of this pumping lemma we have

Theorem 7.12. L(tree-P CGSr)−L(dag-P CGSr−1)6=∅, for allr ≥1.

Chapter 7. Grammar Systems

Proof. Consider the languageLr={a^k+1₁ a^k+2₂ ...a^k+r_r |k≥0}, which can be generated by the following tree-PCGS Γ = (N, K, T,(P₁, S₁), . . . ,(P_r, S_r)), where

T ={a₁, a2, ..., ar}, N ={S₁, S2, ..., Sr}, K={Q₁, Q2, ..., Qr}, P₁ ={S₁−→a₁S₁, S_r −→a_r} ∪ {S_i−→a_iQ_i+1|1≤i≤r−1}, P_i ={S_i−→a_iS_i}, 2≤i≤r.

The above language cannot be generated by a dag-PCGS, of degreer−1 or smaller. To derive a contradiction, letN be the natural number provided by Lemma7.11andα∈Lr

of the formα=a^N+1₁ a^N+2₂ ...a^N+r_r . Then the wordα^(s), obtained fromαby pumping at mostr−1 different subwords of it belongs toL_r, too. On the other hand, the pumped subwords are in the set A={a^k_i|1≤i≤r}, of which cardinality is r. Hence, pumping onlyr−1 different strings belonging toA, and omitting, let say the stringa^k_l, for a fixed l, the exponent of al in the resulting string remain bounded, while the exponents of the other a_i,i6=l, grow arbitrarily large. Hence,α^(s) ∈/L_r, which leads to a contradiction.

ThusLr∈L(tree-P CGSr)−L(dag-P CGSr−1).

The following infinite hierarchies are consequences of the above theorem.

Corollary 7.13. For all r≥1,

1. L(dag-P CGS_r)−L(dag-P CGSr−1)6=∅ (hierarchy{L(dag-P CGS_r)}_r≥1 is infinite), 2. L(tree-P CGS_r)−L(tree-P CGSr−1)6=∅(hierarchy{L(tree-P CGS_r)}r≥1 is infinite).

Theorem 7.14.For allr≥1,L(x-P CGS_r+1)−L(x-P CGS_r)6=∅, wherex∈ {two-way-array, two-way-ring, one-way-ring}.

As a consequence of Theorem 7.14we have

Corollary 7.15. The hierarchies {L(x-P CGS_r)}_r≥1, where x∈ {way-array, two-way-ring, one-way-ring} are infinite.

Related to the Chomsky hierarchy, from [109,110], we have the following result

Theorem 7.16. LetΓbe a PC grammar system andΠ(Γ)the associated communicating graph. If the following properties hold:

1. Π(Γ) contains at most one cycle,

2. Π(Γ) contains a cycle, then this cycle involves the master grammar G₁, 3. Π(Γ) generates a language over one-letter alphabet.

Then L(Γ) is a regular language.

Corollary 7.17. Let Γ ∈ x-P CGS, x ∈ {cycle, dag}, generating a language over one letter alphabet. ThenL(Γ) is a regular language.

With respect to the communication complexity measure, in [109, 165], several class hi-erarchies are obtained along with several lower-bound results. In [165] it is proved that

k+ 1 communications are more powerful than kcommunications, independently of the length of the generated word. This is because, for any natural number k ≥ 1, there exists a language, e.g.,Lk={aⁱ¹bⁱ¹aⁱ²bⁱ¹⁺ⁱ²... a^ikb^i1+i2+...+ik|i_j ∈N}, which can be gen-erated by a PC grammar system with k communications, but it cannot be generated by any PC grammar system using k−1 communications. Hence, there exists an infi-nite hierarchy of constant communication complexity for PC grammar systems without restrictions on their communication graphs. There exists also an infinite hierarchy of O(√^k

n) communication complexity,k≥2.

Furthermore, every language over one-letter alphabet generated by a PC grammar sys-tem using constant communication complexity, is regular. The price to obtain non-regular languages over one letter alphabet is Ω(logn) communication complexity. In [165] it is proved that, if the communication cannot be bounded by any constant then it is at least Ω(logn), hence there is a gap between O(1) and Ω(logn) communication complexity. On the other hand, Ω(logn) is a sufficient and necessary condition to ob-tain nonregular languages that cannot be generated by using constant communication complexity. Therefore, this is a lower bound communication complexity for nonregular languages. A similar result is found in [109], where it is proved that the communication complexity of dag-PCGSs is either a constant or a linear function. Hence there is a gap betweenO(1) andO(n) communication complexity for PC grammar systems whose communication graph is a dag.

7.1.4 Complexity Results for Szilard Languages of PC Grammar