scientific article; zbMATH DE number 4041268

MaRDI QIDQ3779745zbMATH OpenFDO

Authors Shuhua Zhang

Publication date 1987

zbMATH Keywords

automaton automorphismautomorphism groupcomplexity analysisfinite automatagraph isomorphismstrongly connected automaton isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Equivalence in the complexity of several problems
• Complexity of some problems from the theory of automata
• Some recognition problems related to graph isomorphism
• scientific article; zbMATH DE number 4011932
• scientific article; zbMATH DE number 5041651

Cited in

(11)

• Testing homotopy equivalence is isomorphism complete
• Polynomial-time algorithms for testing strong isomorphism and computing the automorphism group of \(R\)-strongly connected automata
• Computational complexity of decision problems on self-verifying finite automata
• Exact complexity of problems of incompletely specified automata
• The complexity of compressed membership problems for finite automata
• Complexity Analysis: Transformation Monoids of Finite Automata
• Equivalence in the complexity of several problems
• Complexity of some problems from the theory of automata
• scientific article; zbMATH DE number 4026835 (Why is no real title available?)
• scientific article; zbMATH DE number 123401 (Why is no real title available?)
• A Correction and Some Comments Concerning Graph Isomorphism by Finite Automata

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3779745)