Arrow Research search

Author name cluster

Joel I. Seiferas

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

I&C Journal 1991 Journal Article

A note on almost-everywhere-complex sets and separating deterministic-time-complexity classes

  • John G. Geske
  • Dung T. Huynh
  • Joel I. Seiferas

For each time bound T: {input strings} → {natural numbers} that is some machine's exact running time, there is a {0, 1}-valued function f T that can be computed within time proportional to T, but that cannot be computed within any time bound T′ that is infinitely often significantly smaller than T (T′ ≠ Ω(T), typically). Equivalently, every algorithm to compute f T requires time T′ on almost every input if T′ is almost everywhere significantly smaller than T (T′ = o(T), typically).

Details DOI

STOC Conference 1981 Conference Paper

Time-Space-Optimal String Matching

  • Zvi Galil
  • Joel I. Seiferas

In this paper we describe a new linear-time string-matching algorithm requiring neither dynamic storage allocation nor other high-level capabilities. The algorithm can be implemented to run in linear time even on a six-head two-way finite automaton. Moreover, the automaton requires only “{= , ≠}- branching” [1]. (Decisions depend on which of the six scanned pattern or text symbols and positions are the same, but not on the particular symbols or how many symbols there are. Hence the same algorithm works even for an infinite alphabet.) A “real-time” implementation is possible on such a multihead finite automaton with a few more heads.

Details

FOCS Conference 1976 Conference Paper

Recognizing Certain Repetitions and Reversals Within Strings

  • Zvi Galil
  • Joel I. Seiferas

Let P1 = {w ε Σ*: w = wR, |w| ≫ 1} be the set of all nontrivial palindromes over Σ. In Part I, we present a linear-time on-line recognition algorithm for P1* ("palstar") on a random-access machine with addition and uniform cost criterion. We also present a lineartime on-line recognition algorithm for P12 on a multitape Turing machine and a recognition algorithm for P12 on a two-way deterministic pushdown automaton. The correctness of these algorithms is based on new "cancellation lemmas" for the languages P1* and P12. In Part II, we present real-time recognition algorithms for the languages {wxyxz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} and {wxyxRz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} on multitape Turing machines, for arbitrary fixed r, s, and t.

Details
v2026.09.13