TY - JOUR

T1 - A linear time solution to the single function coarsest partition problem

AU - Paige, Robert

AU - Tarjan, Robert E.

AU - Bonic, Robert

N1 - Funding Information:
* A preliminary version of this paper appeared in the Conference Record of the 11th Colloquium on Automata, Languages and Programming, July 1984 \[14\]. ** Part of this work was done while this author was visiting Yale University on sabbatical from Rutgers University, and is partly based upon work supported by the National Science Foundation under grant No. MCS-8212936, and by the Office of Naval Research under Grant No. N00014-84-K-~..~. *** Part of this was done while this author was visiting Rutgers University on leave from Pace University, and is partly based upon work supported by the National Science Foundation under grant No. MCS-8212936, and by the Office of Naval Research under grant No. N00014-84-K-0444.

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0021482623&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021482623&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(85)90159-8

DO - 10.1016/0304-3975(85)90159-8

M3 - Article

AN - SCOPUS:0021482623

SN - 0304-3975

VL - 40

SP - 67

EP - 84

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -