A Linear Time Solution to the Single Function Coarsest Partition Problem

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.

Department(s)

Mathematics and Statistics

International Standard Serial Number (ISSN)

0304-3975

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1985 Elsevier, All rights reserved.

Publication Date

01 Jan 1985

Link to Full Text

Share

 
COinS