×

zbMATH — the first resource for mathematics

Minimal and canonical images. (English) Zbl 1439.20001
Assume \(G\) acts on a set \(\Omega\) and \(X\) is a subset of \(\Omega\). Let \(\Omega_1, \ldots,\Omega_n\) be the orbits of \(G\) on \(\Omega\). The problem is to write \(X\) as the union of \(\Omega_i \cap X\). The authors of this paper offer an algorithm to solve this problem. The idea is to use a so called canonical labelling function which gives a canonical image for each element in \(\Omega\). The purpose of the algorithm is to find the canonical image. Afterwards one can put the canonical image into equivalence classes. The canonical image problem goes back to J. S. Leon [J. Symb. Comput. 12, No. 4–5, 533–583 (1991; Zbl 0807.20001)] one of the pioneers of computational group theory. In this paper the authors prove correctness of the algorithm and compare it with existing algorithms.

MSC:
20-08 Computational methods for problems pertaining to group theory
20B99 Permutation groups
Software:
Ferret; GAP; images; nauty; Traces
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Darga, P. T.; Sakallah, K. A.; Markov, I. L., Faster symmetry discovery using sparsity of symmetries, (2008 45th ACM/IEEE Design Automation Conference, (June 2008)), 149-154
[2] Distler, Andreas; Jefferson, Chris; Kelsey, Tom; Kotthoff, Lars, The Semigroups of Order 10, 883-899, (2012), Springer: Springer Berlin, Heidelberg
[3] GAP - groups, algorithms, and programming, version 4.8.8, (2017)
[4] Gent, Ian P.; Smith, Barbara M., Symmetry breaking in constraint programming, (Proceedings of the 14th European Conference on Artificial Intelligence, (2000), IOS Press), 599-603
[5] Holt, Derek F.; Eick, Bettina; O’Brien, Eamonn A., Handbook of Computational Group Theory, Discrete Mathematics and Its Applications, (2005), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton · Zbl 1091.20001
[6] Jefferson, Christopher, Ferret - GAP package, version 1.0.0, (2018)
[7] Jefferson, Christopher; Jonauskyte, Eliza; Pfeiffer, Markus; Waldecker, Markus, Images - GAP package, version 1.1.0, (2018)
[8] Junttila, Tommi; Kaski, Petteri, Engineering an efficient canonical labeling tool for large and sparse graphs, (Applegate, David; Brodal, Gerth Stølting; Panario, Daniel; Sedgewick, Robert, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics, (2007), SIAM), 135-149
[9] Leon, Jeffrey S., Permutation group algorithms based on partitions, I: theory and algorithms, J. Symbolic Comput., 12, 4, 533-583, (1991) · Zbl 0807.20001
[10] Linton, Steve, Finding the smallest image of a set, (Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation. Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, ISSAC ’04, (2004), ACM: ACM New York, NY, USA), 229-234 · Zbl 1134.05302
[11] McKay, Brendan D., Practical graph isomorphism, Congr. Numer., 30, 45-87, (1980)
[12] McKay, Brendan D.; Piperno, Adolfo, Practical graph isomorphism, II, J. Symbolic Comput., 60, 94-112, (2014) · Zbl 1394.05079
[13] Pech, Christian; Reichard, Sven, Enumerating Set Orbits, 137-150, (2009), Springer: Springer Berlin, Heidelberg · Zbl 1183.20001
[14] Soicher, Leonard H., On the structure and classification of somas: generalizations of mutually orthogonal latin squares, Electron. J. Combin., 6, (1999) · Zbl 0922.05010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.