Author name cluster
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.
I&C Journal 2004 Journal Article
An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m 1×m 2 pattern is given. The algorithm takes O(loglogm) time and does O(m 1×m 2) work, where m=max{m 1, m 2}. This yields a work optimal algorithm for 2D pattern matching which takes O(loglogm) preprocessing time and O(1) text processing time.
I&C Journal 1997 Journal Article
There is a way to transform the All Pairs Shortest Distances (APSD) problem where the edge lengths are integers with small (⩽M) absolute value into a problem with edge lengths in {−1, 0, 1}. This transformation allows us to use the algorithms we developed earlier ([1]) and yields quite efficient algorithms. In this paper we give new improved algorithms for these problems. Forn=|V| the number of vertices, Mthe bound on edge length, andωthe exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSD(n, M) algorithm which runs inO(T(n, M)) time, where[formula]2. A undirected APSD(n, M) algorithm which runs inO(M (ω+1)/2 n ω log(Mn)) time.
TCS Journal 1995 Journal Article
This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string: 1. 1. An O(log n) time, n-processor algorithm over general alphabets. In the case of constant size alphabets the algorithm requires only n log n processors, and thus achieves an optimalspeedup. 2. 2. An O(log log n) time, n log n loglog n-processor algorithm over general alphabets. This is the fastest possible time with the number of processors used. These new results improve on the known parallel palindrome detection algorithms by using smaller auxiliary space and either by making fewer operations or by achieving a faster running time.
FOCS Conference 1995 Conference Paper
Byzantine Agreement among processors is a basic primitive in distributed computing. It comes in a number of basic fault models: "Crash", "Omission" and "Malicious" adversarial behaviors. The message complexity of the primitive has been known for the strong failure models of Malicious and Omission adversary since the early 80's, while the question for the more benign Crash failure model has been open. We show how to solve agreement in the presence of crash failures using O(n) messages which is optimal, thus settling a thirteen year old open problem. Our solution has almost linear time and our new algorithmic techniques have further implications: a family of "early stopping" agreement protocols with improved message-complexity; and a new solution to "Checkpoint" yielding a substantial improvement of the protocol for distributed work performance under adaptive parallelism in a network of workstations.
STOC Conference 1995 Conference Paper
STOC Conference 1995 Conference Paper
FOCS Conference 1993 Conference Paper
We initiate a graph-theoretic approach to study the (information-theoretic) maintenance of privacy in distributed environments in the presence of a bounded number of mobile eavesdroppers ("bugs"). For two fundamental privacy problems-secure message transmission and distributed database maintenance-we assume an adversary is "playing eavesdropping games, " coordinating the movement of the bugs among the sites to learn the current memory contents. We consider various mobility settings (adversaries), motivated by the capabilities (strength) of the bugging technologies (e. g. , how fast can a bug be reassigned). We combinatorially characterize and compare privacy maintenance problems, determine their feasibility (under numerous bug models), suggest protocols for the feasible cases, and analyze their computational complexity. >
FOCS Conference 1993 Conference Paper
All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long substring in constant time. This problem used to be a bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log/sup 2/ m/log log m). We use this algorithm to obtain the following results. 1. Improving the preprocessing of the constant-time text search algorithm from O(log/sup 2/ m/log log m) to n(log log m), which is now best possible. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n=/spl Omega/(m/sup 1+/spl epsiv//) for a constant /spl epsiv/>0. 3. A simple probabilistic string-matching algorithm that has constant time with high probability for random input. 4. A constant expected time Las-Vegas algorithm for computing the period of the pattern and all witnesses and thus string matching itself, solving the main open problem remaining in string matching. >
STOC Conference 1993 Conference Paper
FOCS Conference 1993 Conference Paper
We define two conditions on a random access machine (RAM) with arithmetic and Boolean instructions and possible bounds on word and memory sizes. One condition asserts that we either restrict attention to short words or allow non-uniform programs. The second asserts that we either allow a large memory or a double-precision multiplication. Our main theorem shows that the RAM can sort in o(nlog n) time if and only if both of these conditions hold. This theorem breaks down into four upper bounds only one of which has been known before, and two lower bounds neither of which has been known. >
STOC Conference 1992 Conference Paper
Given a pattern string, we describe a way to preprocess it. We design a constant-time optimal parallel algorithm for finding all occurences of the (preprocessed) pattern in any given text.
TCS Journal 1992 Journal Article
Dynamic programming is a general problem-solving technique that has been widely used in various fields such as control theory, operations research, biology and computer science. In many applications dynamic programming problems satisfy additional conditions of convexity, concavity and sparsity. This paper presents a classification of dynamic programming problems and surveys efficient algorithms based on the three conditions.
STOC Conference 1992 Conference Paper
TCS Journal 1992 Journal Article
Recent algorithms for computing the modified edit distance given convex or concave gap cost functions are shown to require Ω(n2) space for certain input.
FOCS Conference 1992 Conference Paper
The authors provide data structures that maintain a graph as edges are inserted and deleted, and keep track of the following properties: minimum spanning forests, best swap, graph connectivity, and graph 2-edge-connectivity, in time O(n/sup 1/2/log(m/n)) per change; 3-edge-connectivity, in time O(n/sup 2/3/) per change; 4-edge-connectivity, in time O(n alpha (n)) per change; k-edge-connectivity, in time O(n log n) per change; bipartiteness, 2-vertex-connectivity, and 3-vertex-connectivity, in time O(n log(m/n)) per change; and 4-vertex-connectivity, in time O(n log(m/n)+n alpha (n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. The algorithms are based on a technique that transforms algorithms for sparse graphs into ones that work on any graph, which they call sparsification. >
FOCS Conference 1992 Conference Paper
A. Amir, G. Benson and M. Farach (see Proc. 24th STOC, p. 59-68 (1992)) gave an algorithm for two-dimensional pattern matching (ABF for short) whose text processing is independent of the alphabet and takes O(n/sup 2/) time, but whose pattern processing is dependent on the alphabet and takes O(m/sup 2/log mod Sigma mod ) time. The authors present an algorithm that is truly independent of the alphabet and takes linear O(m/sup 2/+n/sup 2/) time. As in the Knuth-Morris-Pratt algorithm, the only operation on the alphabet is the equality test of two symbols. All previous algorithms except the ABF algorithm reduce the two-dimensional problem into one-dimensional string matching, and use known techniques in string matching. The ABF algorithm uses two-dimensional periodicity for text processing, but their pattern processing resorts to one-dimensional techniques. The authors present a two-dimensional technique for both pattern processing and text processing. >
FOCS Conference 1992 Conference Paper
The subcubic (O(n/sup w/) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A. B but if C/sub ij/=1 they do not find an index k (a witness) such that A/sub ik/=B/sub kj/=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(n/sup w/) time, where here O(n/sup w/) denotes O(n/sup w/(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from v/sub i/ to v/sub j/ is an index k such that v/sub k/ is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances; namely O(n/sup (3+w)/2/) time in the directed case and O(n/sup w/) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication. >
STOC Conference 1991 Conference Paper
TCS Journal 1991 Journal Article
In this paper we classify all the minimal bilinear algorithms for computing the coefficients of (Σ n−1 i=0 xi ui ) (Σ n−1 i=0 yi ui ) mod Q(u) l where deg Q(u)=j, jl=n and Q(u) is irreducible (over G) is studied. The case where l = 1 was studied in [8]. For l > 1 the main results are that we have to distinguish between two cases: j > 1 and j = 1. The case where j > 1 was studied in [1]. For j = 1 it is shown that up to equivalence, every minimal (2n − 1 multiplications) bilinear algorithm for computing the coefficients of (Σ n−1 i=0 xi ui ) (Σ n−1 i=0 yi ui ) mod un is done either by first computing the coefficients of (Σ n−1 i=0 xi ui ) (Σ n−1 i=0 yi ui ) and then reducing them modulo un or by first computing the coefficients (Σ n−2 i=0 xi ui ) (Σ n−1 i=0 yi ui ) and then reducing them modulo un and adding xn−1 y 0 u n−1 or by first computing the coefficients (Σ n−2 i=0 xi ui ) (Σ n−2 i=0 yi ui ) and then reducing them modulo un and adding (xn−1 y 0 + x 0 yn−1)un−1.
STOC Conference 1991 Conference Paper
FOCS Conference 1991 Conference Paper
A technique is described for deriving lower bounds and tradeoffs for data structure problems. Two quantities are defined. The output variability depends only on the model of computation. It characterizes in some sense the power of a model. The problem variability depends only on the problem under consideration. It characterizes in some sense the difficulty of the problem. The first theorem states that if a model's output variability is smaller than the problem variability, a lower bound on the worst case (average case) time for the problem follows. A RAM that can add, subtract and compare unbounded integers is considered. The second theorem gives an upper bound on the output variability of this model. The two theorems are used to derive lower bounds for the union-find problem in this RAM. >
FOCS Conference 1991 Conference Paper
FOCS Conference 1990 Conference Paper
Recently, R. Kosaraju (Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, p. 178-83) gave an O(nm/sup 0. 75/ polylog(m))-step algorithm for tree pattern matching. The authors improve this result by designing a simple O(n square root m polylog (m)) algorithm. >
FOCS Conference 1990 Conference Paper
The maximal number of character comparisons made by a linear-time string matching algorithm, given a text string of length n and a pattern string of length m over a general alphabet, is investigated. The number is denoted by c(n, m) or approximated by (1+C)n, where C is a universal constant. The subscript 'online' is added when attention is restricted to online algorithms, and the superscript '1' is added when algorithms that find only one occurrence of the pattern in the text are considered. It is well known that n >
SODA Conference 1990 Conference Paper
STOC Conference 1989 Conference Paper
TCS Journal 1989 Journal Article
Consider the problem of computing E[j]= min 0⩽k⩽j−1 {D[k]+w(k, j)}, j=1, …, n, where w is a given weight function, D[0] is given and for every k=1, …, n, D[k] is easily computable from E[k]. This problem appears as a subproblem in dynamic programming solutions to various problems. Obviously, it can be solved in time O(n 2), and for a general weight function no better algorithm is possible. We consider two dual cases that arise in applications: In the concave case, the weight function satisfies the quadrangle inequality: w(k, j)+w(l, j′)⩽w(l, j)+w(k, j′) for all k⩽l⩽j⩽j′. In the convex case, the weight function satisfies the inverse quadrangle inequality. In both cases we show how to use the assumed property of w to derive an O(n log n) algorithm. Even better, linear-time algorithms are obtained if w satisfies the following additional closest zero property: for every two integers l and k, l<k, and real number a, the smallest zero of f(x)=w(l, x)−w(k, x)−a which is larger than k can be found in constant time. The two algorithms speed up several dynamic programming routines that solve as a subproblem the problem above. The speed-up is from O(n 3) to O(n 2log n) or O(n 2). Applications include algorithms for comparing DNA sequences and algorithms used in speech recognition and geology. One typical problem is the following: given the cost of substituting any pair of symbols and a convex cost function g for gaps (where g(r) is the cost of a gap of size r), compute the modified edit distance between the two given sequences.
TCS Journal 1988 Journal Article
In this paper we will classify all the minimal bilinear algorithms for computing the coefficients of (∑ i=0 n-1 xiui) ( ∑ i=0 n-1 yiui) mod Q(u)l where deg Q(u)=j, jl=n and Q(u) is irreducible. The case where l=1 was studied in [1]. For l>1 the main results are that we have to distinguish between two cases: j>1 and j=1. The first case is discussed here while the second is classified in [4]. For j>1 it is shown that up to equivalence every minimal (2n-1 multiplications) bilinear algorithm for computing the coefficients of (∑ i=0 n-1 xiui) ( ∑ i=0 n-1 yiui) mod Q(u) l is done by first computing the coefficients of (∑ i=0 n-1 xiui) ( ∑ i=0 n-1 yiui) and then reducing it modulo Q(u) l (similar to the case l = 1, [1]).
FOCS Conference 1988 Conference Paper
The problem of determining the cost of random-access memory (RAM) is addressed by studying the simulation of random addressing by a machine which lacks it, called a pointer machine. The model allows the use of a data type of choice. A RAM program of time t and space s can be simulated in O(t log s) time using a tree. However, this is not an obvious lower bound since a high-level data type can allow the data to be encoded in a more economical way. The major contribution is the formalization of incompressibility for general data types. The definition extends a similar property of strings that underlies the theory of Kolmogorov complexity. The main theorem states that for all incompressible data types an Omega (t log s) lower bound holds. Incompressibility is proved for the real numbers with a set of primitives which includes all functions which are continuously differentiable except on a countable closed set. >
FOCS Conference 1988 Conference Paper
A number of important computational problems in molecular biology, geology, speech recognition, and other areas can be expressed as recurrences which have typically been solved with dynamic programming. By using more sophisticated data structures, and by taking advantage of further structure from the applications, the authors speed up the computation of several of these recurrences by one or two orders of magnitude. The algorithms used are simple and practical. >
TCS Journal 1987 Journal Article
In this paper we consider a synchronous broadcasting network, a distributed computation model which represents communication networks that are used extensively in practice. We consider a basic problem of information sharing: the computation of the multiple identification function. That is, given a network of p processors, each of which contains an n-bit string of information, how can every processor compute efficiently the subset of processors which have the same information as itself? The problem was suggested by Yao as a generalization of the two-processor case studied in his classic paper on distributed computing (Yao, 1979). The naive way to solve this problem takes O(np) communication time, where a time unit is the time to transfer one bit. We present an algorithm which takes advantage of properties of strings and is O(n log 2 p + p) time. A simulation of sorting networks by the distributed model yields an O(n log p + p) (impractical) algorithm. By applying Yao's probabilistic implementation of the two-processor case to both algorithm we get probabilistic versions (with small error) where n is replaced by log n in the complexity expressions. We also present lower bounds for the problem: an Ω(n) and an Ω(p) bound are shown.
I&C Journal 1987 Journal Article
We prove the following four results on communication complexity: (1) For every k ≥ 2, the language of encodings of directed graphs of out-degree one that contain a path of length k + 1 from the first vertex to the last vertex can be recognized by exchanging O(k log n)1 bits using a simple k-round protocol and requires the exchange of Ω( n 1 2 (k4 log 3 n) ) bits by any (k − 1)-round protocol. (2) For every k ≥ 1 and for infinitely many n ≥ 1, there exists a collection of sets L k n ⊆ {0, 1}2n that can be recognized by exchanging O(k log n) bits using a k-round protocol, and any (k − 1)-round protocol recognizing L k n requires the exchange of Ω( n k ) bits. (3) Given a set L ⊆ {0, 1}2n, there is a set L ⊆ {0, 1}8n such that any (k-round) protocol recognizing L can be transformed to a (k-round) fixed-partition protocol recognizing L with the same communication complexity, and vice versa. (4) For every integer function f, 1 ≤ f(n) ≤ n, there are languages recognizable by a one-round deterministic protocol exchanging f(n) bits, but not by any nondeterministic protocol exchanging f(n) − 1 bits. The first two results show in an incomparable way an exponential gap between (k − 1)-round and k-round protocols, settling a conjecture by Papadimitriou and Sipser. The third result shows that as long as we are interested in existence proofs, a fixed partition of the input is not a restriction. The fourth result extends a result by Papadimitriou and Sipser who showed that for every integer function f, 1 ≤ f(n) ≤ n, there is a language accepted by a deterministic protocol exchanging f(n) bits but not by any deterministic protocol exchanging f(n) − 1 bits.
TCS Journal 1987 Journal Article
Two improved algorithms for string matching with k mismatches are presented. One algorithm is based on fast integer multiplication algorithms whereas the other follows more closely classic string-matching techniques.
FOCS Conference 1987 Conference Paper
We introduce new techniques for deriving lower bounds on the message complexity in asynchronous distributed computation. These techniques combine the choice of specific patterns of communication delays and crossing sequence arguments with consideration of the speed of propagation of messages, together with careful counting of messages in different parts of the network. They enable us to prove the following results, settling two open problems: An Ω(n log* n) lower bound for the number of messages sent by an asynchronous algorithm for computing any nonconstant function on a bidirectional ring of n anonymous processors. An Ω(n log n) lower bound for the average number of messages sent by any maximum finding algorithm on a ring of n processors, in case n is known.
FOCS Conference 1986 Conference Paper
The minimum-cost flow problem is the following: given a network with n vertices and m edges, find a maximum flow of minimum cost. Many network problems are easily reducible to this problem. A polynomial-time algorithm for the problem has been known for some time [EK], but only recently a strongly polynomial algorithm was discovered [Ts]. In this paper we design an O(n2(m + n log n)log n) algorithm. The previous best algorithm had an O(m2 (m + n log n) log n) time bound ([F], [O]). Thus, we obtain an improvement of two orders of magnitude for dense graphs. Our algorithm is based on Fujishige's algorithm [F] (which is based on Tardos' algorithm [Ts]). Fujishige's algorithm consists of up to O(m log n) steps. Each step solves a single source shortest path problem with nonnegative edge lengths. We modify this algorithm in order to make an improved analysis possible. The new algorithm may still consist of up to m iterations, and an iteration may still consist of up to O(m log n) steps, but we can still show that the total number of steps is bounded by O(n2 log n). The improvement is due to a new technique that relates the time spent to the progress achieved.
STOC Conference 1986 Conference Paper
FOCS Conference 1985 Conference Paper
FOCS Conference 1985 Conference Paper
FOCS Conference 1984 Conference Paper
We define a graph problem which we refer to as the component merging problem. Versions of the problem appear as bottlenecks in various graph algorithms. We show how to solve an important special case of the problem.
STOC Conference 1984 Conference Paper
We prove the following four results on communication complexity: 1) For every k ≥ 2, the language L k of encodings of directed graphs of out degree one that contain a path of length k+1 from the first vertex to the last vertex and can be recognized by exchanging O(k log n) bits using a simple k-round protocol requires exchanging Ω(n 1/2 /k 4 log 3 n) bits if any (k-1)- round protocol is used. 2) For every k ≥ 1 and for infinitely many n ≥ 1, there exists a collection of sets L n k @@@@ {0,1} 2n that can be recognized by exchanging O(k log n) bits using a k-round protocol, and any (k-1)-round protocol recognizing L n k requires exchanging Ω(n/k) bits. 3) Given a set L @@@@ {0,1} 2n , there is a set L@@@@{0,1} 8n such that any (k-round) protocol recognizing L@@@@ can be transformed to a (k-round) fixed partition protocol recognizing L with the same communication complexity, and vice versa. 4) For every integer function f, 1 ≤f(n) ≤ n, there are languages recognized by a one round deterministic protocol exchanging f(n) bits, but not by any nondeterministic protocol exchanging f(n)-1 bits. The first two results show in an incomparable way an exponential gap between (k-1)-round and k-round protocols, settling a conjecture by Papadimitriou and Sipser. The third result shows that as long as we are interested in existence proofs, a fixed partition of the input is not a restriction. The fourth result extends a result by Papadimitriou and Sipser who showed that for every integer function f, 1 ≤ f(n) ≤ n, there is a language accepted by a deterministic protocol exchanging f(n) bits but not by any deterministic protocol exchanging f(n) - 1 bits.
STOC Conference 1983 Conference Paper
FOCS Conference 1982 Conference Paper
The main results of this paper are an O(n3) probabilistic algorithm and an O(n3 log n) deterministic algorithm that test whether two given trivalent graphs are isomorphic. In fact, the algorithms construct the set of all isomorphisms of the two graphs. Variants of these algorithms construct the set of all automorphisms of a trivalent graph. The algorithms make use of some new improved permutation group algorithms that exploit the fact that the groups involved are 2-groups. A remarkable property of the probabilistic algorithm is that it computes Isoe, ei(X, Y), i = 1, .. ., m, m = O(n) (the set of all isomorhisms φ: X → Y with φ(e)=ei) for the cost of computing the single set Isoe, el(X, Y).
TCS Journal 1982 Journal Article
We define a language L and show that it cannot be recognized by any two way deterministic counter machine. It is done by fooling any given such machine; i. e. showing that if it accepts L' ⊇ L, then L' − L ≠ Ø. For this purpose, an argument stronger than the well-known crossing sequence argument needs to be introduced. Since L is accepted by a two-way deterministic pushdown automation, we consequently show that one pushdown stack is more powerful than one counter for deterministic two way machines.
FOCS Conference 1982 Conference Paper
We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes O(log n) time. We use these generalized priority queues to construct an O(EV log V) algorithm for finding a maximal weighted matching in general graphs.
STOC Conference 1982 Conference Paper
FOCS Conference 1981 Conference Paper
We define a language L and show that its time and space complexities T and S must satisfy T2S ≥ cn3 even allowing machines with multiple (non random) access to the input.
STOC Conference 1981 Conference Paper
STOC Conference 1981 Conference Paper
TCS Journal 1981 Journal Article
We report a linear-time string-matching algorithm for a random-access machine without dynamic storage allocation. To do this, we tell how to adapt a cited algorithm to fill its dynamic storage needs by temporarily borrowing some of the space occupied by the input pattern. In automata-theoretic terms, we tell how to adapt the cited algorithm to run on a writing multihead finite automaton with a restricted writing alphabet.
TCS Journal 1981 Journal Article
The time bounds of various algorithms for finding the maximal flow in networks are shown to be tight by constructing one parametrized family of network flow problems and showing that the algorithms achieve the corresponding bounds on inputs from this family.
STOC Conference 1981 Conference Paper
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.
FOCS Conference 1979 Conference Paper
STOC Conference 1979 Conference Paper
STOC Conference 1979 Conference Paper
We review the motivation underlying the study of data encodings and the formal framework of the study. We then present a series of results whose main message is that (complete) trees are materially less congenial storage representations for tree-like data structures than they have been shown to be for array-like data structures. In response to these results, we propose a new data structure, called a dree , which we show to share the advantages of trees, but not to suffer their disadvantages, when used as a storage structure.
FOCS Conference 1978 Conference Paper
A new algorithm for finding the maximal flow in a given network is presented. The algorithm runs in time O(V5/3E2/3) or O(n2. 33) where n = V + E is the length of the input.
TCS Journal 1977 Journal Article
The cyclic ordering problem is to recognize whether a collection of cyclically ordered triples of elements of a set T is derived from an arrangement of all the elements of T on a circle. This problem is shown to be NP-complete.
TCS Journal 1977 Journal Article
For infinitely many n > 0 we construct contradictory formulas α n in conjunctive form with n literals such that every regular proof tree which proves the contradiction must contain 2 cn distinct clauses for some c > 0. This implies a 2 cn lower bound for the number of distinct clauses which are generated by the Davis-Putnam procedure applied to α n using any order of variable elimination.
FOCS Conference 1977 Conference Paper
STOC Conference 1976 Conference Paper
We give a sufficient condition when an on-line algorithm can be transformed into a real-time algorithm. We use this condition to construct real-time algorithms for string-matching and palindrome recognition problems by random access machines and by Turing machines.
FOCS Conference 1976 Conference Paper
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.
MFCS Conference 1975 Conference Paper
Abstract We explore the concept of local transformations of monotone switching circuits, i. e. what kind of local changes in a circuit leave the functions computed by the circuit invariant. We obtain several general theorems in this direction. We apply these results to boolean matrix product and prove that the school-method for matrix multiplication yields the unique monotone circuit.
STOC Conference 1975 Conference Paper