Accession Number:

AD0627682

Title:

HOMOMORPHISMS OF GRAPHS.

Descriptive Note:

Technical rept.,

Corporate Author:

MICHIGAN UNIV ANN ARBOR COLL OF LITERATURE SCIENCE AND THE ARTS

Personal Author(s):

Report Date:

1965-12-01

Pagination or Media Count:

81.0

Abstract:

The works of Hartmanis and Stearns, Krohn and Rhodes, Yoeli and Ginzburg, and Zeiger amply demonstrate the usefulness of homomorphisms in studying decompositions of finite automata. Yoeli and Ginzburgs approach is slightly different from the tohers in that it is more concerned with aspects of the state transition graphs of finite automata. In their paper, On Homomorphic Images of Transition Graphs, they give a complete characterization of the class of homomorphisms of the graphs which correspond to input-free automata. This paper was motivated by an interest in extending these results of Yoeli and Ginzburg in the direction of a characterization of the class of homomorphisms of graphs which correspond to arbitrary finite automata. It is a review and a classification of most of the published definitions and results on mappings of graphs which have been called homomorphisms. The paper contains, in addition, several new results and several new definitions of homomorphisms of graphs. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE