Norbert Blum

TCS Journal 2001 Journal Article

On parsing LL-languages

• Norbert Blum

Usually, a parser for an LL(k)-grammar G is a deterministic pushdown transducer which produces a leftmost derivation for a given input string x∈L(G). Ukkonen (JCCS 26(1983)153–170) has given a family of LL(2)-grammars proving that every parser for these grammars has exponential size. If we add to a parser the possibility to manipulate a constant number of pointers which point to positions within the constructed part of the leftmost derivation and to change the output in such positions, we obtain an extended parser for the LL(k)-grammar G. Given an arbitrary LL(k)-grammar G, we will show how to construct an extended parser of polynomial size manipulating at most k2 pointers.

TCS Journal 1985 Journal Article

An Ω(n43) lower bound on the monotone network complexity of the nth degree convolution

• Norbert Blum

STOC Conference 1984 Conference Paper

An Area-Maximum Edge Length Tradeoff for VLSI Layout

• Norbert Blum

TCS Journal 1983 Journal Article

A Boolean function requiring 3n network size

• Norbert Blum

Paul (1977) has proved a 2. 5n-lower bound for the network complexity of an explicit Boolean function. We modify the definition of Paul's function slightly and prove a 3n-lower bound for the network complexity of that function.

TCS Journal 1983 Journal Article

More on the power of chain rules in context-free grammars

• Norbert Blum

For all ε > 0 we prove for every sufficiently large n: There exists a context-free language CL n with the following properties: 1. (a) CL n has a cfg of size 0(n). 2. (b) Fach chain rule free cfg for CL n has size Ω(ε1 n 3 2 1).

FOCS Conference 1981 Conference Paper

An Omega(n^4/3) Lower Bound on the Monotone Network Complexity of n-th Degree Convolution

• Norbert Blum

We prove an Ω(n4/3) lower bound for the number of ∧-gates in any monotone network computing n-th degree convolution.

TCS Journal 1980 Journal Article

On the average number of rebalancing operations in weight-balanced trees

• Norbert Blum
• Kurt Mehlhorn

It is shown that the average number of rebalancing operations (rotations and double rotations) in weight-balanced trees is constant.