A linear time solution to the single function coarsest partition problem

Robert Paige, Robert E. Tarjan, Robert Bonic

Research output: Contribution to journalArticlepeer-review

59 Scopus citations

Abstract

The problem of finding the coarsest partition of a set S with respect to another partition of S one or more functions on S has several applications, one of which is the state minimization of finite state automata. In 1971, Hopcroft presented an algorithm to solve the many function coarsest partition problem for sets of n elements in O(n log n) time and O(n) space. In 1974, Aho, Hopcroft and Ullman presented an O(n log n) algorithm that solves the special case of this problem for only one function. Both these algorithms use a negative strategy that repeatedly refines the original partition until a solution is found. We present a new algorithm to solve the single function coarsest partition problem in O(n) time and space using a different, constructive approach. Our algorithm can be applied to the automated manufacturing of woven fabric.

Original languageEnglish (US)
Pages (from-to)67-84
Number of pages18
JournalTheoretical Computer Science
Volume40
Issue numberC
DOIs
StatePublished - 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A linear time solution to the single function coarsest partition problem'. Together they form a unique fingerprint.

Cite this