Thomas G. Szymanski

STOC Conference 1979 Conference Paper

The Complexity of Finding Periods

• Robert Sedgewick
• Thomas G. Szymanski

Given a function f over a finite domain D and an arbitrary starting point x , the sequence x,f(x),f(f(x)), ... is ultimately periodic. Such sequences typically are used for constructing random number generators. The cycle problem is to determine the first repeated element f n (x) in the sequence. Previous algorithms for this problem have required 3 n operations. In this paper we present an algorithm which only requires n (1+ O (1/(@@@@) M )) steps, if M memory cells are available to store values of the function. By increasing M , this running time can be made arbitrarily close to the information-theoretic lower bound on the running time of any algorithm for the cycle problem. Our treatment is novel in that we explicitly consider the performance of the algorithm as a function of the amount of memory available as well as the relative cost of evaluating f and comparing sequence elements for equality.

STOC Conference 1978 Conference Paper

The Macro Model for Data Compression (Extended Abstract)

• James A. Storer
• Thomas G. Szymanski

A general model for data compression is presented which includes most data compression systems in the literature as special cases. All macro schemes are based on the principle of finding redundant strings or patterns and replacing them by pointers to a common copy. Different varieties of macro schemes may be defined by varying the interpretation of pointers, for instance, a pointer may indicate a substring of the compressed string, a substring of the original string, or a substring of some other string such as an external dictionary. Other varieties of macros schemes may be defined by restricting the type of overlapping or recursion that may be used. Trade-offs between different varieties of macro schemes, exact lower bounds on the amount of compression obtainable, and the complexity of encoding and decoding are discussed as well as how the work of other authors (such as Lempel-Ziv) relates to this model.

TCS Journal 1977 Journal Article

Economy of description by parsers, DPDA's, and PDA's

• Matthew M. Geller
• Harry B. Hunt
• Thomas G. Szymanski
• Jeffrey D. Ullman

It is shown that there is a sequence of languages E 1, E 2, … such that every correct prefix parser (one which detects errors at the earliest possible moment, e. g. , LR or LL parsers) for E n has size 2 cn, yet a deterministic PDA recognizing E n exists and has size O(n 2). There is another easily described sequence of languages N 1, N 2, … for which N has a nondeterministic PDA of size O(n 2), but no deterministic PDA of size less than 2 cn. It is shown moreover, that this latter gap can be made arbitrarily large for different sequences of languages.

TCS Journal 1976 Journal Article

Concerning bounded-right-context grammars

• Thomas G. Szymanski

Consider the problem of testing whether a context-free grammar is an (m, n)-BRC grammar. Let ‖G‖ denote the size of the grammar G. It is first shown that G is (m, n)-BRC if and only if G is (m 0, n)-BRC where m 0=4·‖G‖2·(n + 1)2. Deterministic and nondeterministic algorithms are then presented for testing whether an arbitrary grammar has the (m, n)-BRC property for fixed values of m and n. The running times of both algorithms are low degree polynomials which are independent of m.

STOC Conference 1976 Conference Paper

Dichotomization, Reachability, and the Forbidden Subgraph Problem (Extended Abstract)

• Harry B. Hunt III
• Thomas G. Szymanski

FOCS Conference 1975 Conference Paper

Economy of Descriptions by Parsers, DPDA's, and PDA's

• Matthew M. Geller
• Harry B. Hunt III
• Thomas G. Szymanski
• Jeffrey D. Ullman

It is shown that there is a sequence of languages E1, E2, .. . such that every correct prefix parser (one which detects errors at the earliest possible moment, e. g. , LR or LL parsers) for En has size 2cn, yet a deterministic PDA recognizing En exists and has size O(n2). There is another easily described sequence of languages N1, N2, .. . for which Nn has a nondeterministic PDA of size O(n2) but no deterministic PDA of size less than 2cn. It is shown moreover, that this latter exponential gap can be made arbitrarily large for different sequences of languages.

FOCS Conference 1975 Conference Paper

Evaluating Relational Expressions with Dense and Sparse Arguments

• Thomas G. Szymanski
• Jeffrey D. Ullman

We consider expressions whose arguments are relations and whose operators are chosen from among ∪, ο, *, and -1. We further assume that operands may be designated "sparse" or "dense", in a manner to be made formal subsequently. Our aim is to determine whether the evaluation of such an expression is (a) as hard as general transitive closure (b) as hard as transitive closure for sparse graphs. (c) as hard as connected components of an undirected graph.

STOC Conference 1975 Conference Paper

On the Complexity of Grammar and Related Problems

• Harry B. Hunt III
• Thomas G. Szymanski