Search results for "Hopcroft'algorithm"

showing 1 items of 1 documents

Circular sturmian words and Hopcroft’s algorithm

2009

AbstractIn order to analyze some extremal cases of Hopcroft’s algorithm, we investigate the relationships between the combinatorial properties of a circular sturmian word (x) and the run of the algorithm on the cyclic automaton Ax associated to (x). The combinatorial properties of words taken into account make use of sturmian morphisms and give rise to the notion of reduction tree of a circular sturmian word. We prove that the shape of this tree uniquely characterizes the word itself. The properties of the run of Hopcroft’s algorithm are expressed in terms of the derivation tree of the automaton, which is a tree that represents the refinement process that, in the execution of Hopcroft’s alg…

Discrete mathematicsReduction (recursion theory)Fibonacci numberGeneral Computer ScienceHopcroft'algorithmSturmian wordSturmian wordSturmian morphismsTheoretical Computer ScienceCombinatoricsTree (descriptive set theory)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESComputer Science::Discrete MathematicsDeterministic automatonHopcroft’s minimization algorithmCircular sturmian wordsTree automatonDeterministic finite state automataTime complexityAlgorithmComputer Science::Formal Languages and Automata TheoryWord (group theory)Computer Science(all)MathematicsTheoretical Computer Science
researchProduct