TY - GEN

T1 - Hopcroft’s Algorithm and Tree-like Automata

AU - Restivo, Antonio

AU - Sciortino, Marinella

AU - Castiglione, Giuseppa

PY - 2009

Y1 - 2009

N2 - In order to analyze some extremal cases of Hopcroft’s algorithm we deepenedthe relationship between combinatorial properties of circular words and the ex-ecution of the algorithm on cyclic automata associated to such words.In this paper we highlight the notion of word tree and in particular, we char-acterize the word trees for which Hopcroft’s algorithm on the associated tree-likeautomata has a unique refinement process. Moreover, we show the relationshipbetween the time complexity of the refinements process of the Hopcroft’s algo-rithm on unary cyclic automata and binary tree-like automata. Such a resultallows to exhibit a family of tree-like automata representing the worst case ofthe algorithm.

AB - In order to analyze some extremal cases of Hopcroft’s algorithm we deepenedthe relationship between combinatorial properties of circular words and the ex-ecution of the algorithm on cyclic automata associated to such words.In this paper we highlight the notion of word tree and in particular, we char-acterize the word trees for which Hopcroft’s algorithm on the associated tree-likeautomata has a unique refinement process. Moreover, we show the relationshipbetween the time complexity of the refinements process of the Hopcroft’s algo-rithm on unary cyclic automata and binary tree-like automata. Such a resultallows to exhibit a family of tree-like automata representing the worst case ofthe algorithm.

KW - Automata minimization

KW - Hoprcroft's algorithm

KW - trees.

KW - Automata minimization

KW - Hoprcroft's algorithm

KW - trees.

UR - http://hdl.handle.net/10447/40016

M3 - Other contribution

ER -