Branching Programs

Another way to approach parallel computation is to use branching programs (BPs).

Informally, a BP is represented as a directed acyclic graph (DAG) with a unique source vertex and one or more terminal vertices called sinks. Non-sink vertices are labeled by the program’s variables, while edges out of vertices by values of these variables. The sink vertices are each labeled by an output value. Each path from the source vertex to a sink represents a computation path in a BP which depends on the values of the input variables. These values prescribe which arcs to follow in the computation path.

The maximum length of paths in a BP, i.e., the depth of the BP, corresponds to time in sequential computation, while the logarithm of the number of vertices in a BP, i.e., the logarithm of the size of a BP, corresponds to sequential space. BPs have been introduced in [129], under the name of binary decision programs, as an alternative to Boolean circuits. They have been further studied in [3,7,8,9,177,201,209]. Formally, we have

Definition 4.13. LetDandX be two finite sets, whereDis the domain of the variables in X and |D| =q. A q-way deterministic branching program B over D is a DAG that satisfies the properties:

(i) B has exactly one vertex with in-degree 0 called thesource vertex of B.

(ii) Each vertex of a non-zero out-degree is labeled by an element inX, and it has the out-degree equal toq. Each of theq edges leaving such a vertex is distinctly labeled by an element inD.

(iii) There are exactly two vertices with out-degree 0 called the sinkvertices of B. One of the sink vertex is labeled by 1, and represents acceptance. The other one is labeled by 0, and represents rejection.

A computation on an input α = α₁α₂...α_n ∈ Dⁿ begins at the source vertex of B. If at the i^th step the computation reaches a non-sink vertex labeled by xi ∈ X, then the computation of B proceeds along the edge labeled by the value assigned to variable x_i. The procedure continues in this way until a sink vertex is reached. The sequence of vertices and edges encountering during the computation forms the computation path associated with α. The input α is accepted or rejected depending on whether the sink vertex is labeled by1or by0, respectively. Thus,Bcomputes a functionfB:Dⁿ→ {0,1}

defined by setting f_B equal to the label of the sink reached when Baccepts α.

The BP model described above has the property that a single BP can only work on inputs of a fixed length. Therefore BPs accepts only subsets of Dⁿ. If we consider the infinite union of BPs such that for each n there exists a BP that accepts an input of length n, then this family recognizes a language in D^∗. Due to this property the BP model is a non-uniform computation model.

Chapter 4. Asymptotic Growth, Computational Models, and Complexity Classes

If in Definition4.13 we have q = 2, thenB is a 2-way deterministicBP, known also as Boolean deterministic BP. If in Definition4.13 we allow that each vertex of a non-zero out-degree has an unrestricted number of outgoing edges labeled by elements in D, so that they are not necessarily distinctly labeled, thenB is anondeterministic BP.

The sizeof a BP B, denotedsize(B), is the number of computation vertices in B. The length of the longest directed path in B, denoted depth(B), is called the depth of B.

The complexity of a BP is measured in terms of depth (time) and program size (space).

LetB be aq-way BP. If sis the size of B, then the space complexityof Bis logqs. The time complexityof B is the depth of B.

Lett:N→N(s:N→N) be a time (respectively, space) constructible function. We say that a family of BPsB={B_i}^∞_i=1 has thetime complexityt(spacecomplexitys) if and only if for every input of lengthn,B_i has the time complexity t(n) (respectively, space complexitys(n)).

A BP of depthdisleveledif its vertices can be partitioned intodordered disjoint subsets V₀,V₁,...,V_d, calledlevels, such thatV₀ contains only the source vertex,V_d is the set of the sink vertices, and each directed edge that goes out fromVi enters inVi+1, 0≤i < d.

Every deterministic (nondeterministic) BP of sizes and depth dcan be converted into a leveled deterministic (respectively, nondeterministic) BP of the same depth with at mostsvertices in each level, without affecting its computational power [177].

Thewidth of a BPB, denotedwidth(B), is the size of the largest level of B. A BP is of widthc if it is leveled and each level has at mostcvertices. Abounded width branching program (BWBP) is a BP of widthc and polynomial size, wherec is a constant.

Denote by BW BP the class of languages generated by BWBPs. We have BW BP ^[7]

= N C¹, equality that holds for both uniform and non-uniform cases. Hence,ALOGT IM E= U_L-BW BP =U_E-N C¹=U_E^∗-N C¹.

Definition 4.14. A read k-time branching program (k-time BP) B is a BP with the property that no input variable xi occurs more than k times on any path from the source vertex to a sink. If k= 1 then Bis a read 1-time branching program (each varia-ble is tested only one time on each path from the source vertex to a sink vertex of B.) Read (k+ 1)-times BPs are strictly more powerful thank-times BPs [201], and therefore an infinite hierarchy on read-times BPs exists.

Definition 4.15. A BP is called oblivious if it is leveled, and on each path, from the source vertex to a sink vertex of B, all variables are tested in the same order.

The Complexity of Szilard Languages of Chomsky

Grammars

You are doomed to make choices. This is life’s greatest paradox. [...] Our lives are a sum total of the choices we have made. (Wayne Dyer, Co-creating at Its Best - A Conversation Between Master Teachers)

The aim of this chapter is twofold. First we make a brief survey of the most impor-tant complexity, descriptional, closure, and decidability results on Szilard languages of Chomsky grammars. Then we present our main contribution that strengthen some of the known results on the complexity of these languages.

5.1 A Brief Survey

When we consider a formal grammar one of the very first tasks is to study thederivation mechanism of the system in question. Once the derivation mechanism has been settled on, we can go further by studying the computational power, closure and decidability properties of that generative device.

One of the most important tools to investigate the derivation mechanism in formal language theory, is the Szilard language (defined in Subsection 2.3.2). The concept of Szilard language has been first introduced for Chomsky grammars in [82, 157, 175,

Chapter 5. The Complexity of Szilard Languages of Chomsky Grammars

189]. Roots of Szilard languages come from [4, 196]. The notion has been extended afterwards for several other generative devices, such as pure context-free grammars [137, 139], grammar systems [59, 150], and regulated rewriting grammars [60, 70, 168, 189].

If restrictions are imposed on the derivation order then particular classes of Szilard languages, such as leftmost Szilard languages [135, 137, 188], depth-first and breadth-first Szilard languages [134,137,138] are obtained.

Hierarchies and closure properties of Szilard languages associated with (pure) context-free grammars are considered in [137, 139, 140, 141, 175, 189]. Szilard languages of (pure) context-free grammars have very weak closure properties. They are not closed under union, concatenation, homomorphism and inverse homomorphism, +-Kleene, or intersection with regular languages. Hence, all of them are anti-AFL’s¹. In [189] it is proved that the closure of Szilard languages of context-free grammars under the in-tersection with regular languages equals the family of derivation languages associated with context-free matrix grammars (Section 6.1). Another characterization of context-free matrix languages by means of Szilard languages is provided in [47]. There exists a proper hierarchy of Szilard languages of pure context-free grammars with respect to the degree of grammars [139].

Decidability properties of Szilard languages associated with context-free grammars are investigated in [134,137,140,175]. The emptiness, finiteness, and equivalence problems are decidable for these languages [175]. The inclusion problem for leftmost Szilard languages is decidable [134,157], and for unrestricted Szilard languages it is NP-complete [141]. Several operations on Szilard languages and semilinearity properties of these languages are studied in [103] and [136], respectively.

Time and space bounds of Turing machines and multicounter machines to recognize Szilard languages associated with Chomsky grammars, are presented in [113, 176]. In [176] it is proved that (leftmost) Szilard languages of context-free grammars can be recognized by a linearly bounded² multicounter machine (Definition 4.11). Since each linearly bounded multicounter machine can be simulated by a deterministicoff-line Tur-ing machine (Subsection4.2.1) with logarithmic space [81], in terms of the length of the input string, it follows that the classes of Szilard languages and (leftmost) Szilard lan-guages associated with context-free grammars are contained in DSP ACE(logn) (Sub-section 4.2.1). In [42] (see also Subsection 5.2.1) we strengthen this result by proving that the above classes of Szilard languages can be accepted by an indexing alternating

1A family of languages is an abstract family of languages (AFL) if it is closed underλ-free homomor-phism, inverse homomorhomomor-phism, intersection with regular languages, union, concatenation, and +-Kleene operation.

2A multicounter machineMis linearly bounded if there exists a constantksuch that for any word w, belonging to the language accepted byM, the content of each counter used during the computation is less thank|w|, where|w|is the length ofw.

Turing machine (Definition 4.8) in logarithmic time and space. Since the class of lan-guages recognizable by indexing alternating Turing machines in logarithmic time equals the UE^∗-uniform N C¹ class [187] (see also Subsection 4.2.2), we obtain that the above classes of Szilard languages are strictly contained inN C¹, i.e., the class of Boolean func-tions computable by polynomial size Boolean circuits, with depthO(logn) and constant fan-in [209] (see also Subsection4.2.4).

Characterizations of (leftmost) Szilard languages of context-free and phrase-structure (unrestricted) grammars in terms of Turing machine resources are provided in [113]. It is proved that logn is the optimal space bound for an on-line³ deterministic Turing machine to recognize (leftmost) Szilard languages of context-free grammars. It is also an optimal bound for an off-line deterministic Turing machine to recognize leftmost Szilard languages of phrase-structure grammars. However, the optimal bound for an on-line deterministic Turing machine to recognize leftmost Szilard languages of context-free and phrase-structure grammars is n, where n is the length of the input word. As leftmost Szilard languages of phrase-structure grammars are off-line recognizable by a deterministic Turing machine that uses only logarithmic space, in terms of the length of the input string, leftmost Szilard languages of phrase-structure grammars are included in DSP ACE(logn). In [42] (see also Subsection5.2.2) we prove that the class of leftmost Szilard languages of phrase-structure grammars is strictly contained in N C¹ under the UE^∗-uniformity restriction. For a more complex survey on complexity, descriptional, closure and decidability results on Szilard languages of (pure) context-free grammars the reader is referred to [137]. All results in Section 5.2are selected from [42].