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

DOI10.1080/00207168808803657zbMath0661.68057MaRDI QIDQ3811719

Lian Li, Shuhua Zhang

Publication date: 1988

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168808803657

zbMATH Keywords

automorphism group; cyclic automaton

Mathematics Subject Classification ID

20B25: Finite automorphism groups of algebraic, geometric, or combinatorial structures

68Q70: Algebraic theory of languages and automata

Related Items

Polynomial-time algorithms for testing strong isomorphism and computing the automorphism group of \(R\)-strongly connected automata

Cites Work

• Unnamed Item
• Concerning the complexity of deciding isomorphism of block designs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• The amalgamation of automata
• A representation of strongly connected automata and its applications
• Graph isomorphism, general remarks
• Operation-preserving functions and autonomous factors of finite automata
• Some results on the decomposition of finite automata
• The graph isomorphism disease
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• Automaton automorphisms
• A note on the iterative decomposition of finite automata
• Isomorphism Groups of Automata