Arrow Research search

Author name cluster

Michael L. Fredman

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.

17 papers
2 author rows

Possible papers

17

TCS Journal 1996 Journal Article

Products of finite state machines with full coverage

  • David M. Cohen
  • Michael L. Fredman

Given a collection of finite state machines, M i, with the same input alphabet, let M be the product machine, M = ΠM j. In general, not every state in M is reachable. A natural question is whether there are any inherent limits to the number of reachable states in a system that is the product of many small finite state machines. This note constructs a family of product machines M where the number of states is doubly exponential in the number of states in any individual machine M i and every product state is reachable. Products of finite state machines such as discussed in this note occur when analyzing large collections of independently designed telecommunications services. These examples raise the possibility that product finite state machines modeling systems of independently designed services may have different characteristics from finite state machines modeling communications protocols. Consequently, analyzing collections of telecommunications services may require new heuristic methods.

Details DOI

FOCS Conference 1993 Conference Paper

Optimal Bi-Weighted Binary Trees and the Complexity of Maintaining Partial Sums

  • Haripriyan Hampapuram
  • Michael L. Fredman

Let A be an array. The partial sum problem concerns the design of a data structure for implementing the following operations. The operation update(j, x) has the effect, A[j]/spl larr/A[j]+x, and the query operation sum(j) returns the partial sum, /spl Sigma//sub i=1//sup j/A[i]. Our interest centers upon the optimal efficiency with which sequences of such operations can be performed, and we derive new upper and lower bounds in the semi-group model of computation. Our analysis relates the optimal complexity of the partial sum problem to optimal binary trees relative to a type of weighting scheme that defines the notion of bi-weighted binary tree. >

Details

FOCS Conference 1990 Conference Paper

Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths

  • Michael L. Fredman
  • Dan E. Willard

The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m+n log n/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic limitations. The extension of the fusion tree method involves the development of a new data structure, the atomic heap. The atomic heap accommodates heap (priority queue) operations in constant amortized time under suitable polylog restrictions on the heap size. The linear-time minimum spanning tree algorithm results from a direct application of the atomic heap. To obtain the shortest path algorithm, the atomic heap is used as a building block to construct a new data structure, the AF-heap, which has no size restrictions and surpasses information theoretic limitations. The AF-heap belongs to the Fibonacci heap family. >

Details

FOCS Conference 1988 Conference Paper

Three Stacks

  • Michael L. Fredman
  • Deborah L. Goldsmith

The storage allocation for three stacks has been traditionally accomplished by using pointers to store the stacks as linked lists or by relocating the stacks within memory when collisions take place. The former approach requires additional space to store the pointers, and the latter approach requires additional time. The authors explore the extent to which some additional space or time is required to maintain three stacks. They provide a formal setting for this topic and establish upper and lower complexity bounds on various aspects. >

Details

FOCS Conference 1984 Conference Paper

Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms

  • Michael L. Fredman
  • Robert Endre Tarjan

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in 0(log n) amortized time and all other standard heap operations in 0(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.

Details

FOCS Conference 1983 Conference Paper

Hash Functions for Priority Queues

  • Miklós Ajtai
  • Michael L. Fredman
  • János Komlós

The complexity of priority queue operations is analyzed with respect to the cell probe computational model of A. Yao. A method utilizing families of hash functions is developed which permits priority queue operations to be implemented in constant worst case time provided that a size constraint is satisfied. The minimum necessary size of a family of hash functions for computing the rank function is estimated and contrasted with the minimum size required for perfect hashing.

Details

FOCS Conference 1982 Conference Paper

Storing a Sparse Table with O(1) Worst Case Access Time

  • Michael L. Fredman
  • János Komlós
  • Endre Szemerédi

We describe a data structure for representing a set of n items from a universe of m items, which uses space n+o(n) and accommodates membership queries in constant time. Both the data structure and the query algorithm are easy to implement.

Details

FOCS Conference 1980 Conference Paper

The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries

  • Michael L. Fredman

A formal framework is presented in which to explore the complexity issues of data structures which accommodate various types of range queries. Within this framework, a systematic and reasonably tractable method for assessing inherent complexity is developed. Included among the interesting results are the following: the fact that non-linear lower bounds are readily accessible, and the existence of a complexity gap between linear time and n log n time.

Details

TCS Journal 1976 Journal Article

How good is the information theory bound in sorting?

  • Michael L. Fredman

We define a sorting problem on an n element set S to be a family 〈A 1, …, Ar 〉 of disjoint subsets of the set of n! linear orderings on S. Given an ordering ω ∈ ∪ j A j, we want to determine to which subset Aj the ordering ω belongs by performing a sequence of comparisons between the elements of S. The classical sorting problem corresponds to the case where the subsets Aj comprise the n! singleton sets of orderings. If a sorting problem is defined by r nonempty subsets Aj, then the information theory bound states that at least log2 r comparisons are required to solve that problem in the worst case. The purpose of this paper is to investigate the accuracy of this bound. While we show that it is usually very weak, we are nevertheless able to define a large class of problems for which this bound is good. As an application, we show that if X and Y are n element sets of real numbers, then the n 2 element set X + Y can be sorted with O (n 2) comparisons, improving upon the n 2 log2 n bound established by Harper et al. The problem of sorting X + Y was posed by Berkelamp.

Details DOI