Ivan Hal Sudborough

TCS Journal 2000 Journal Article

Leftmove-bounded picture languages

• Changwook Kim
• Ivan Hal Sudborough

Let Π={u, d, r, l} be the chain-code picture alphabet such that u(d, r, l) denotes the graphics command to move the drawing pen up (down, right, left) in the 2D Cartesian plane. It is known that the picture membership problem can be solved in polynomial time for each context-free language over {u, d, r} and is NP-complete for a so-called retreat-bounded regular (or reversal-bounded linear) language over Π. Imposing both retreat and reversal bounds on languages over Π results in the leftmove-bounded languages whose words describe pictures by making no more than a bounded number of left moves. The picture membership problem can be solved in polynomial time for each leftmove-bounded context-free language over Π and is NP-complete for a leftmove-unbounded (but retreat-bounded) linear language over {u, d, lr}. There exists a context-sensitive language over {u, d, r} (or {u, d, lr}) for which the picture membership problem is undecidable.

TCS Journal 1992 Journal Article

On reversal-bounded picture languages

• Changwook Kim
• Ivan Hal Sudborough

For an integer k⩾0, a k-reversal-bounded picture language is a chain-code picture language which is described by a language L over the alphabet π = {u, d, r, l} such that, for every word x in L, the number of alternating occurrences of r's and l's in x is bounded by k. It is shown that the membership problem can be solved in O(n 4k + 4) time for k-reversal-bounded regular picture languages, for every k⩾1, and is NP-complete for 1-reversal-bounded stripe linear picture languages. The membership problem is known to be NP-complete for regular and context-free picture languages without restriction on the number of reversals and solvable in O(n) time (O(n 12) time) for 0-reversal-bounded regular (context-free) picture languages. Whether the membership problem for stripe context-free picture languages could be solved in polynomial time has been an open problem. Other basic properties of reversal-bounded picture languages are also presented.

MFCS Conference 1988 Invited Paper

Comparing Interconnection Networks

• Burkhard Monien
• Ivan Hal Sudborough

Abstract We review results on embedding network and program structures into popular parallel computer structures. Such embeddings can be viewed as high level descriptions of efficient methods to simulate an algorithm designed for one type of architecture on a different network structure and/or techniques to distribute data/program variables to achieve optimum use of all available processors.

TCS Journal 1987 Journal Article

The membership and equivalence problems for picture languages

• Changwook Kim
• Ivan Hal Sudborough

The paper describes two principal results: (1) there is a nondeterministic polynomial-time algorithm to determine whether an arbitrary picture is a member of a context-free picture language and (2) the equivalence problem for regular picture languages is not decidable (not even partially decidable). This solves open questions described in earlier publications. Furthermore, these results are best possible. That is, the membership problem for context-free picture languages was earlier shown to be NP-hard and the complement of the equivalence problem for regular picture languages is easily seen to be partially decidable.

TCS Journal 1985 Journal Article

Bandwidth constrained NP-complete problems

• Burkhard Monien
• Ivan Hal Sudborough

Bandwidth restrictions are considered on several NP-complete problems, including the following: 3Satisfiability, Independent Set, Vertex Cover, Hitting Set, Simple Max Cut, 3-Dimensional Matching, Exact Cover By 3 Sets, Partition Into Triangles, 3-Colorability (even for planar graphs with maximum vertex degree four), Directed And Undirected Hamiltonian Circuit and Bandwidth Minimization. It is shown that these problems when restricted to graphs, formulae, sets of triples, etc. , of bandwidth ƒ(n) are log space hard for the class of problems solvable by polynomial time nondeterministic algorithms that use simultaneously at most ƒ(n) space. This class is denoted by Ntisp(poly, ƒ(n)). In fact, all of these problems restricted to bandwidth ƒ(n), except for Hamiltonian Circuit and Bandwidth Minimization, are shown to be log space complete for Ntisp(poly, ƒ(n)). Since Ntisp(poly, log n) = Nspace(log n), this means we give several new additional examples of Nspace(log n) complete problems. It also means that NP = Nspace(log n) if and only if 3SAT ⩽log3SAT restricted to well-formed formulae with bandwidth log n. Since it seems unlikely that all problems in Ntisp(poly, ƒ(n)) can be solved in polynomial time by deterministic algorithms, even for functions ƒ as small as log1 + ϵn, for ϵ > 0, our results suggest that NP-complete problems remain intractable even when restricted to small bandwidth. The problems become easier with diminishing bandwidth, but presumably remain intractable unless the bandwidth is restricted to c log2 n, for some c > 0.

TCS Journal 1983 Journal Article

Bandwidth constraints on problems complete for polynomial time

• Ivan Hal Sudborough

A graph G=(V, E) has bandwidth k under a layout L: V →1 1{1, …, ¦V¦} if, for all {x, y}∈E, ¦L(x, −L(y)¦⩽k. Bandwidth constraints on several problems that are complete for P (under long space reductions) are considered. In particular, the solvable path system problem and the and⧹or graph accessibility problem under various bandwidth constraints are used to prove results about subclasses of P. In general, restricting the bandwidth of problems complete for P results in complete problems for subclasses of P defined by simultaneous time-space bounds or defined by space bounds on alternating Turing machines. For instance, these results are used to show that the class SC, of sets accepted in polynomial time and simultaneous polylog space, can be characterized as the class reducible by log space transformations to sets accepted by one-way log log n space bounded alternating Turing machines. An upper bound on the space requirements for the solvable path system problem under various bandwidth constraints is given by SPS(t(n))∈DSPACE(f(n)log n). This yields, as a corollary, the result ASPACE(f(n)) (- ∪ k →lcub0rcub) DSPACE(2kf(n)) for functions f that are suitably constructible and do not grow more rapidly than some logarithm function. This extends the known result: ASPACE(f(n)) = ∪k→lcub0rcub) DTIME(2kf(n)), which only applies to functions that grow at least as rapidly as a logarithm function.

TCS Journal 1982 Journal Article

On eliminating nondeterminism from turing machines which use less than logarithm worktape space

• Burkhard Monien
• Ivan Hal Sudborough

The graph accessibility problem restricted to graphs whose bandwidth is bounded by a function S(n), denoted by GAP(S(n)), is considered. An algorithm is presented to solve GAP(S(n)) deterministically in space log S(n)×logn, {GAP((S(n)) k )} k⩾1 is a log space complete family of problems for NSPACE(log S(n)), for appropriately constructible S(n)∈O(n)−o(log n). Thus, for well-behaved S(n)∈O(log n)−O(log log n), we obtain: NSPACE(S(n))⊆DSPACE(S(n)×log n).

FOCS Conference 1982 Conference Paper

Polynomial Time Algorithms for the Min Cut Problem on Degree Restricted Trees

• Moon-Jung Chung
• Fillia Makedon
• Ivan Hal Sudborough
• Jonathan S. Turner

Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in O(n(logn)d-2) steps. This also yields an algorithm for determining the black/white pebble demand of degree three trees. A forbidden subgraph characterization is given for degree three trees having cutwidth k. This yields an interesting corollary: for degree three trees, cutwidth is identical to search number.

STOC Conference 1981 Conference Paper

Bandwidth Constrained NP-Complete Problems

• Burkhard Monien
• Ivan Hal Sudborough

MFCS Conference 1981 Invited Paper

Time and Space Bounded Complexity Classes and Bandwidth Constrained Problems (A Survey)

• Burkhard Monien
• Ivan Hal Sudborough

Abstract Bandwidth constraints on familiar natural computational problems are considered. It is seen that generally as the bandwidth of a problem decreases its space complexity decreases. More interestingly, for problems complete for a complexity class \(\mathbb{K}\), often as one decreases the bandwidth one obtains complete problems for space restricted subclasses of \(\mathbb{K}\). For example, (1) the \(\mathbb{N}\) SPACE(log n) complete graph accessibility problem (GAP), when restricted to graphs of bandwidth f k (n), for some k≥1, forms a complete family of problems for \(\mathbb{N}\) SPACE(log f(n)), (2) the \(\mathbb{P}\) complete and/or graph accessibility problem (AGAP), when restricted to graphs of bandwidth f(n), is complete for the simultaneous time-space complexity class \(\mathbb{D}\) TISP(poly, f(n)), (3) the \(\mathbb{N}\) P complete graph problems 3COLOR, SIMPLE MAX CUT, INDEPENDENT SET, VERTEX COVER, DOMINATING SET, and several others, when restricted to graphs of bandwidth f(n) are complete for the simultaneous time-space complexity class \(\mathbb{N}\) TISP(poly, f(n)), and (4) the \(\mathbb{P}\) -Space complete PEBBLE problem, when restricted to graphs of bandwidth f(n), can be solved in space f(n)×log 2 n. These results are used to show, for example, that: (1) \(\mathbb{N}\) SPACE( f(n)) ( \(\mathbb{D}\) SPACE( f(n)×max(f(n), log n) ), for all functions f, (2) The class SC, called Steve's class in honor of Stephen Cook who showed, for example, that all DCFL's are in SC 2 = \(\mathbb{D}\) TISP(poly, log 2 n), is identical to the log space closure of the class of sets accepted by one-way alternating Turing machines within loglog n space. ( Note: SC = U k≥1 \(\mathbb{D}\) TISP(poly, log k n) ) (3) The graph problems 3COLOR, SIMPLE MAX CUT, INDEPENDENT SET, VERTEX COVER, DOMINATING SET, and several other \(\mathbb{N}\) P complete problems, when restricted to graphs of bandwidth f(n), can be solved in polynomial time if and only if \(\mathbb{N}\) TISP(poly, f(n)) ( \(\mathbb{P}\).

FOCS Conference 1980 Conference Paper

Efficient Algorithms for Path System Problems and Applications to Alternating and Time-Space Complexity Classes

• Ivan Hal Sudborough

Let SPS(f(n)) denote the solvable path system problem for path systems of bandwidth f(n) and SPS (f(n)) the corresponding problem for monotone systems. Let DTISP (poly, f(n)) denote the polynomial time and simultaneous f(n) space class and SC = UkDTISP (poly, logkn). Let ASPACE (f(n)) denote the sets accepted by f(n) space bounded alternating TMs and ASPACE (f(n)) the corresponding one-way TM family. Then, for "well-behaved" functions fεO(n)-o(log n), (1) SPS (f(n)) is ≤log-complete for DTISP (poly, f(n)), (2) {SPS(f(n)k)}k≥1 is ≤log-complete for ASPACE (logf(n)), (3) {SPS (f(n)k)}k≥1 is ≤log-complete for ASPACE (log f(n)), (4) SPS(f(n)) ε DSPACE(f(n) × log n), (5) ASPACE(log f(n)) ⊆ UkDSPACE(f(n)k), and (6) SC = CLOSURE ≤log(ASPACE(log log n)).

STOC Conference 1977 Conference Paper

Separating Tape Bounded Auxiliary Pushdown Automata Classes

• Ivan Hal Sudborough

MFCS Conference 1977 Conference Paper

Time and Tape Bounded Auxiliary Pushdown Automata

• Ivan Hal Sudborough

Abstract We consider language families defined by nondeterministic and deterministic log(n)-tape bounded auxiliary pushdown automata within polynomial time. It is known that these families are precisely the set of languages which are (many-one) log tape reducible to context-free languages and deterministic context-free languages, respectively. The results described here relate questions concerning these classes to other complexity classes and to questions concerning the tape complexity of context-free languages, resolution based proof procedures, solvable path systems, and deterministic context-free languages.

STOC Conference 1976 Conference Paper

On Deterministic Context-Free Languages, Multihead Automata, and the Power of an Auxiliary Pushdown Store

• Ivan Hal Sudborough

MFCS Conference 1973 Conference Paper

On Families of Languages Defined by Time-Bounded Random Access Machines

• Ivan Hal Sudborough
• A. Zalcberg