9
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

The complexity of computing the automorphism group of automata and related problems

Pages 17-31 | Received 01 Feb 1987, Published online: 19 Mar 2007

References

  • Fleck , A.C. 1962 . Isomorphism groups of automata . J. Assoc. Comput. Mach , 9 : 469 – 476 .
  • Fleck , A.C. 1965 . On the automorphism group of an automaton . J. Assoc. Comput. Mach , 12 : 566 – 569 .
  • Weeg , G. 1962 . The structure of an automaton and its operation-preserving transformation group . J. Assoc. Comput. Mach , 9 : 345 – 349 .
  • Arbib , M.A. 1967 . Automaton automorphism . Inform. Contr , 11 : 147 – 154 .
  • Bavel , Z. 1968 . Structure and transition-preserving functions of finite automata . J.Assoc. Comput. Mach , 15 : 138 – 158 .
  • Ito , M. 1978 . A representation of strongly connected automata and its applications . J.Comput. System Sci , 17 : 65 – 80 .
  • Jump , J.R. 1969 . A note on the iterative decomposition of finite automata . Inform.Contr , 15 : 424 – 435 .
  • Grzymala-Busse , J.W. 1971 . Operation-preserving functions and automous factors of finite automata . J. Comput. System Sci , 5 : 465 – 474 .
  • Tiuryn , J. 1978 . Some results on the decomposition of finite automata . Inform. Contr , 38 : 298 – 309 .
  • Watanabe , T. and Noguchi , S. 1977 . The amalgamation of automata . J. Comput. System Sei , 15 : 1 – 16 .
  • Booth , K.S. 1978 . Isomorphism testing of graphs, semigroups and finite automata are polynomially equivalent problems . SIAM J. Comput , 3 : 273 – 279 .
  • Colbourn , N.J. and Colburn , C.J. 1981 . Concerning complexity of deciding isomorphism of block designs . Discrete Applied Mathematics , 3 : 155 – 162 .
  • Hoffman , C.M. 1982 . Group-Theoretic Algorithms and Graph Isomorphism , Vol. 136 , Berlin : Springer-Verlag . Lecture notes in Computer Science, Heidelberg, New York
  • Miller , G.L. 1979 . Graph isomorphism, general remark . J. Comput. System. Sei , 18 : 128 – 142 .
  • Ginzburg , A. 1968 . Algebraic Theory of Automata , New York : Academic Press .
  • Luks , E.M. 1982 . Isomorphism of graphs of bounded valence can be tested in polynomial time . J. Comput. System. Sei , 25 : 42 – 65 .
  • Karp , R.M. 1972 . “ Reducibility among combinatorial problems ” . In Complexity of Computer Computations , Edited by: Miller , R.E. and Thatcher , J.W. Plenum, New York : Academic Press .
  • Garey , M.R. and Johnson , D.S. 1978 . Computers and Intractability—A Guide to the Theory of NP-Completeness , San Francisco : W. H. Freeman .
  • Read , R.C. and Corneil , D.G. 1977 . The graph isomorphism disease . J. Graph Theory , 1 : 239 – 363 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.