Polynomial-time algorithms for testing strong isomorphism and computing the automorphism group of \(R\)-strongly connected automata
DOI10.1016/0304-3975(92)90268-KzbMath0745.68063OpenAlexW2060549410MaRDI QIDQ1184982
Publication date: 28 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90268-k
strong isomorphismgraph isomorphism problemPolynomial-time algorithmsautomorphism group of \(R\)-strongly connected automataisomorphism-complete problems
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Characterization of state-independent automata
- Group-theoretic algorithms and graph isomorphism
- The amalgamation of automata
- On the transformation semigroups of finite automata
- On the computational power of pushdown automata
- The complexity of computing the automorphism group of automata and related problems
- Group-Type Automata
- Structure and Transition-Preserving Functions of Finite Automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Polynomial-time algorithms for testing strong isomorphism and computing the automorphism group of \(R\)-strongly connected automata
