Wolfgang J. Paul

STOC Conference 1984 Conference Paper

On Monotone Formulae with Restricted Depth (Preliminary Version)

• Maria M. Klawe
• Wolfgang J. Paul
• Nicholas Pippenger
• Mihalis Yannakakis

STOC Conference 1983 Conference Paper

Bounds for Width Two Branching Programs

• Allan Borodin
• Danny Dolev
• Faith Ellen
• Wolfgang J. Paul

FOCS Conference 1983 Conference Paper

On Determinism versus Non-Determinism and Related Problems (Preliminary Version)

• Wolfgang J. Paul
• Nicholas Pippenger
• Endre Szemerédi
• William T. Trotter

We show that, for multi-tape Turing machines, non-deterministic linear time is more powerful than deterministic linear time. We also discuss the prospects for extending this result to more general Turing machines.

STOC Conference 1983 Conference Paper

Two Nonlinear Lower Bounds

• Pavol Duris
• Zvi Galil
• Wolfgang J. Paul
• Rüdiger Reischuk

FOCS Conference 1982 Conference Paper

On-Line Simulation of k+1 Tapes by k Tapes Requires Nonlinear Time

• Wolfgang J. Paul

On-line simulation of real-time (k+1)-tape Turing machines by k-tape Turing machines requires time n(log n)1/(k+1).

STOC Conference 1981 Conference Paper

An Efficient General Purpose Parallel Computer

• Zvi Galil
• Wolfgang J. Paul

FOCS Conference 1981 Conference Paper

On Heads Versus Tapes

• Wolfgang J. Paul

2-dimensional 2-tape Turing machines cannot simulate 2-dimensional Turing machines with 2 heads on 1 tape in real time.

STOC Conference 1980 Conference Paper

An Information-Theoretic Approach to Time Bounds for On-Line Computation (Preliminary Version)

• Wolfgang J. Paul
• Joel I. Seiferas
• Janos Simon

FOCS Conference 1979 Conference Paper

On Time versus Space II

• Wolfgang J. Paul
• Rüdiger Reischuk

Logarithmically t(n)-time bounded RAMs can be simulated by t(n)/log t(n)-tape bounded Turing machines, t(n)-time bounded multidimensional multitape Turing machines can be simulated by t(n) loglog t(n)/log t(n)-tape bounded Turing machines.

FOCS Conference 1978 Conference Paper

On Alternation (Preliminary Version)

• Wolfgang J. Paul
• Ernst-Jürgen Prauß
• Rüdiger Reischuk

Every alternating t(n) -time bounded multitape Turing machine can be simulated by an alternating t(n) -time bounded 1-tape Turing machine. Every nondeterministic t(n) -time bounded 1-tape Turing machine can be simulated by an alternating O(n+(t(n))1/2) -time bounded 1-tape Turing machine. For well-behaved functions t(n) every nondeterministic t(n) -time bounded 1-tape Turing machine can be simulated by a deterministic ((n log n)1/2 + (t(n))1/2) -tape bounded off-line Turing machine. These results improve or extend results by Chandra-Stockmeyer, Lipton-Tarjan and Paterson.

STOC Conference 1977 Conference Paper

On Time Hierarchies

• Wolfgang J. Paul

For fixed k ≥ 2 we tighten the time hierarchy for k-tape Turing machines. Also for fixed k ≥ 2 we exhibit infinite hierarchies of languages recognizable by k-tape machines with increasing amount of time on the same amount of space.

TCS Journal 1976 Journal Article

Realizing Boolean functions on disjoint sets of variables

• Wolfgang J. Paul

For switching functions f let C(f) be the combinational complexity of f. We prove that for every ε>0 there are arbitrarily complex functions f: {0, 1} n →{0, 1} n such that C(f×f)⩽ (1+ε)C(f) and arbitrarily complex functions f: {0, 1} n →{0, 1} such that C(v∘(fxf)⩽ (1+ε)C(f). These results and the techniques developed to obtain them are used to show that Ashenhurst decomposition of switching functions does not always yield optimal circuits, and to prove a new result concerning the gap between circuit size and monotone circuit size.

STOC Conference 1976 Conference Paper

Space Bounds for a Game of Graphs

• Wolfgang J. Paul
• Robert Endre Tarjan
• James R. Celoni

We study a one-person game played by placing pebbles, according to certain rules, on the vertices of a directed graph. In [3] it was shown that for each graph with n vertices and maximum in-degree d, there is a pebbling strategy which requires at most c(d) n/log n pebbles. Here we show that this bound is tight to within a constant factor. We also analyze a variety of pebbling algorithms, including one which achieves the 0(n/log n) bound.

STOC Conference 1975 Conference Paper

A 2. 5 n-lower Bound on the Combinatorial Complexity of Boolean Functions

• Wolfgang J. Paul

FOCS Conference 1975 Conference Paper

On Time versus Space and Related Problems

• John E. Hopcroft
• Wolfgang J. Paul
• Leslie G. Valiant