Search
Join ACM

Thomas G. Szymanski

Research and Advances Apr 1 1978

Assembling code for machines with span-dependent instructions

Many modern computers contain instructions whose lengths depend on the distance from a given instance of such an instruction to the operand of that instruction. This paper considers the problem of minimizing the lengths of programs for such machines. An efficient solution is presented for the case in which the operand of every such “span-dependent” instruction is either a label or an assembly-time expression of a certain restricted form. If this restriction is relaxed by allowing these operands to be more general assembly-time expressions, then the problem is shown to be NP-complete.
Computing Applications

Advertisement

Author Archives

Research and Advances May 1 1977

A fast algorithm for computing longest common subsequences

Previously published algorithms for finding the longest common subsequence of two sequences of length n have had a best-case running time of O(n2). An algorithm for this problem is presented which has a running time of O((r + n) log n), where r is the total number of ordered pairs of positions at which the two sequences match. Thus in the worst case the algorithm has a running time of O(n2 log n). However, for those applications where most positions of one sequence match relatively few positions in the other sequence, a running time of O(n log n) can be expected.
Research and Advances Dec 1 1975

On the complexity of LR(k) testing

The problem of determining whether an arbitrary context-free grammar is a member of some easily parsed subclass of grammars such as the LR(k) grammars is considered. The time complexity of this problem is analyzed both when k is considered to be a fixed integer and when k is considered to be a parameter of the test. In the first case, it is shown that for every k there exists an O(nk+2) algorithm for testing the LR(k) property, where n is the size of the grammar in question. On the other hand, if both k and the subject grammar are problem parameters, then the complexity of the problem depends very strongly on the representation chosen for k. More specifically, it is shown that this problem is NP-complete when k is expressed in unary. When k is expressed in binary the problem is complete for nondeterministic exponential time. These results carry over to many other parameterized classes of grammars, such as the LL(k), strong LL(k), SLR(k), LC(k), and strong LC(k) grammars.
Computing Applications

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved