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 -