Skip to main content
Passa alla visualizzazione normale.

MARINELLA SCIORTINO

Hopcroft’s Algorithm and Tree-like Automata

  • Authors: CASTIGLIONE, G; RESTIVO, A; SCIORTINO, M
  • Publication year: 2009
  • Type: Altro
  • Key words: Automata minimization, Hoprcroft's algorithm, trees.
  • OA Link: http://hdl.handle.net/10447/40016

Abstract

In order to analyze some extremal cases of Hopcroft’s algorithm we deepened the 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-like automata has a unique refinement process. Moreover, we show the relationship between the time complexity of the refinements process of the Hopcroft’s algo- rithm on unary cyclic automata and binary tree-like automata. Such a result allows to exhibit a family of tree-like automata representing the worst case of the algorithm.