Some elements of a Galois theory of the structure and complexity of the tree automorphism problem

DOI10.1016/0304-3975(81)90002-5zbMath0466.68033OpenAlexW2148272292MaRDI QIDQ1155358

Georg Gati

Publication date: 1981

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(81)90002-5

zbMATH Keywords

Galois grouptime complexityproblem difficulty

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automorphisms and endomorphisms (16W20) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Complexity of computation (including implicit computational complexity) (03D15) Algorithms in computer science (68W99)

Related Items

Generalized galois theory and its application to complexity, Maximizing a lower bound on the computational complexity

Cites Work

• Generalized galois theory and its application to complexity
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On the computational power of pushdown automata
• Further annotated bibliography on the isomorphism disease
• The graph isomorphism disease
• Endliche Gruppen I
• Unnamed Item
• Unnamed Item
• Unnamed Item