Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-12T08:06:09.405Z Has data issue: false hasContentIssue false
  • English
  • Français

On the algorithmic complexity of crystals

Published online by Cambridge University Press:  05 July 2018

S. V. Krivovichev
S. V. Krivovichev*
Affiliation:
Department of Crystallography, Faculty of Geology, St. Petersburg State University, University Emb. 7/9, 199034 St. Petersburg, RussiaNanomaterials Research Centre, Kola Science Centre, Russian Academy of Sciences, Apatity, Russia
*
E-mail: skrivovi@mail.ru
Get accessRights & Permissions [Opens in a new window]

Abstract

The concept of the algorithmic complexity of crystals is developed for a particular class of minerals and inorganic materials based on orthogonal networks, which are defined as networks derived from the primitive cubic net (pcu) by the removal of some vertices and/or edges. Orthogonal networks are an important class of networks that dominate topologies of inorganic oxysalts, framework silicates and aluminosilicate minerals, zeolites and coordination polymers. The growth of periodic orthogonal networks may be modelled using structural automata, which are finite automata with states corresponding to vertex configurations and transition symbols corresponding to the edges linking the respective vertices. The model proposed describes possible relations between theoretical crystallography and theoretical computer science through the theory of networks and the theory of deterministic finite automata.

Keywords

crystal structuretopologyalgorithmic complexityorthogonal networksfinite state automatazeolitesinorganic oxysaltsformal languages

Information

Type
Research Article
Information
Mineralogical Magazine , Volume 78 , Issue 2 , April 2014, pp. 415 - 435
Copyright
Copyright © The Mineralogical Society of Great Britain and Ireland 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Alexandrov, E.V., Blatov, V.A., Kochetkov, A.V. and Proserpio, D.M. (2011) Underlying nets in threeperiodic coordination polymers: topology, taxonomy and prediction from a computer-aided analysis of the Cambridge Structural Database. CrystEngComm, 13, 3947–3958.CrossRefGoogle Scholar
Baerlocher, Ch., McCusker, L.B., and Olson, D.H. (2007) Atlas of Zeolite Framework Types, 6th revised edition. Elsevier, Amsterdam.Google Scholar
Baur, W.H., Tillmanns, E.T. and Hofmeister, W. (1983) Topological analysis of crystal structures. Acta Crystallographica, B39, 669–674.CrossRefGoogle Scholar
Bulakh, A.G., Krivovichev, V.G. and Zolotarev, A.A. (2008) General Mineralogy. Academia, Moscow [in Russian].Google Scholar
Crutchfield, J.P. (2012) Between order and chaos. Nature Physics, 8, 17–24.CrossRefGoogle Scholar
Delgado Friedrichs, O., O’Keeffe, M. and Yaghi, O.M. (2003) Three-periodic nets and tilings: regular and quasiregular nets. Acta Crystallographica, A59, 22–27.CrossRefGoogle Scholar
Depmeier, W. (2005) The sodalite family – a simple but versatile framework structure. Pp 203–240 in: Micro- and Mesoporous Mineral Phases (G. Ferraris and S. Merlino, editors). Reviews in Mineralogy & Geochemistry, 57. Mineralogical Society of America, and the Geochemical Society, Washington DC.CrossRefGoogle Scholar
Estevez-Rams, E. and González-Férez, R. (2009) On the concept of long-range order in solids: the use of algorithmic complexity. Zeitschrif t für Kristallographie, 224, 179–184.Google Scholar
Goldsmith, J.R. (1953) A "simplexity principle" and its relation to "ease" of crystallization. Journal of Geology, 61, 439–451.CrossRefGoogle Scholar
Hawthorne, F.C. (1983) Graphical enumeration of polyhedral clusters. Acta Crystallographica, A39, 724–736.CrossRefGoogle Scholar
Hawthorne, F.C. (2012) A bond-topological approach to theoretical mineralogy: crystal structure, chemical composition and chemical reactions. Physics and Chemistry of Minerals, 39, 841–874.CrossRefGoogle Scholar
Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2001) Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston, USA.Google Scholar
Ilachinski, A. (2001) Cellular Automata. A Discrete Universe. World Scientific Publishing Co., Singapore.CrossRefGoogle Scholar
Klee, W.E. (2004) Crystallographic nets and their quotient graphs. Crystal Research and Technology, 39, 959–968.CrossRefGoogle Scholar
Krivovichev, S.V. (2004a) Crystal structures and cellular automata. Acta Crystallographica, A60, 257–262.CrossRefGoogle Scholar
Krivovichev, S.V. (2004b) Combinatorial topology of inorganic oxysalts: 0-, 1- and 2-dimensional units with corner-sharing between coordination polyhedra. Crystallography Reviews, 10, 185–232.CrossRefGoogle Scholar
Krivovichev, S.V. (2008) Structural Crystallography of Inorganic Oxysalts. Oxford University Press, Oxford, UK.Google Scholar
Krivovichev, S.V. (2010) Actinyl compounds with hexavalent elements (S, Cr, Se, Mo) – Structural diversity, nanoscale chemistry, and cellular automata modeling. European Journal of Inorganic Chemistry, 2010, 2594–2603.CrossRefGoogle Scholar
Krivovichev, S.V. (2012a) Topological complexity of crystal structures: quantitative approach. Acta Crystallographica, A68, 393–398.CrossRefGoogle Scholar
Krivovichev, S.V. (2012b) Information-based measures of structural complexity: application to fluoriterelated structures. Structural Chemistry, 23, 1045–1052.CrossRefGoogle Scholar
Krivovichev, S.V. (2012c) Algorithmic crystal chemistry: a cellular automata approach. Crystallography Reports, 57, 10–17.CrossRefGoogle Scholar
Krivovichev, S.V. (2013a) Structural complexity of minerals: information storage and processing in the mineral world. Mineralogical Magazine, 77, 275–326.CrossRefGoogle Scholar
Krivovichev, S.V. (2013b) Crystal chemistry of uranium oxides and minerals. Pp. 611–640 in: Comprehensive Inorganic Chemistry II, Volume 2. (J. Reedijk, and K. Poeppelmeier, editors). Elsevier, Amsterdam.Google Scholar
Krivovichev, S.V. and Plášil, J. (2013) Mineralogy and crystallography of uranium. Pp. 15–120 in: Uranium: Cradle to Grave (P.C. Burns and G.E. Sigmon, editors). Mineralogical Association of Canada Short Course Series, 43. Quebec, Canada.Google Scholar
Krivovichev, S.V., Kahlenberg, V., Kaindl, R., Mersdorf, E., Tananaev, I.G. and Myasoedov, B.F. (2005) Nanoscale tubules in uranyl selenates. Angewandte Chemie International Edition, 44, 1134–1136.CrossRefGoogle ScholarPubMed
Krivovichev, S.V., Shcherbakova, E.P. and Nishanbaev, T.P. (2012) Crystal structure of svyatoslavite and evolution of complexity during crystallization of the CaAl2Si2O8 melt: a structural automata description. The Canadian Mineralogist, 50, 585–592.CrossRefGoogle Scholar
Mackay, A.L. (1976) Crystal symmetry. Physics Bulletin, 1976, 495–496.CrossRefGoogle Scholar
Mayfield, J.E. (2013) Evolution as Computation. The Engine of Complexity. Columbia University Press, New York.Google Scholar
Mitchell, M. (2011) Complexity. A Guided Tour. Oxford University Press, USA, New York.Google Scholar
Morey, J., Sedig, K., Mercer, R.E. and Wilson, W. (2002) Crystal lattice automata. Pp. 214–220 in: Conference on Implementation and Application of Automata, 2001, LNCS 2494, (B.W. Watson and D. Wood, editors). Springer-Verlag, Berlin-Heidelberg, Germany.Google Scholar
Morse, J.W. and Casey, W.H. (1988) Ostwald processes and mineral paragenesis in sediments. American Journal of Science, 288, 537–560.CrossRefGoogle Scholar
Pushcharovsky, D.Yu. and Pushcharovsky, Yu.M. (2012) The mineralogy and the origin of the deep geospheres: a review. Earth-Science Reviews, 113, 94–109.CrossRefGoogle Scholar
Oberhagemann, U., Bayat, P., Marler, B., Gies, H. and Rius, J. (1996) A layer silicate: synthesis and structure of the zeolite precursor RUB-15 - [N(CH3)4]8[Si24O52(OH)4]·20H2O. Angewandte Chemie International Edition, 35, 2869–2871.CrossRefGoogle Scholar
Shevchenko, V.Ya. and Krivovichev, S.V. (2008) Where are genes in paulingite? Mathematical principles of formation of inorganic materials on the atomic level. Structural Chemistry, 19, 571–577.CrossRefGoogle Scholar
Shevchenko, V.Ya, Krivovichev, S.V. and Mackay, A. (2010) Cellular automata and local order in the structural chemistry of the lovozerite group minerals. Glass Physics and Chemistry, 36, 1–9.CrossRefGoogle Scholar