On constructive nilpotent groups. (English) Zbl 1485.03114
Day, Adam (ed.) et al., Computability and complexity. Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 10010, 324-353 (2017).
Summary: The purpose of this paper to review the results on the constructive nilpotent groups, not claiming to be complete. We consider both the fundamental questions, which are general in the computable algebra, such as the problems of existence, uniqueness, and extension of constructivizations (computable copies), and the questions that arise from the study of the effectiveness of the basic theorems, constructions and structural properties within the class of nilpotent groups.
For the entire collection see [Zbl 1352.03004].
For the entire collection see [Zbl 1352.03004].
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 03D45 | Theory of numerations, effectively presented structures |
| 20F18 | Nilpotent groups |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20K15 | Torsion-free groups, finite rank |
| 20K25 | Direct sums, direct products, etc. for abelian groups |
References:
| [1] | Ash, CJ; Knight, J., Computable Structures and the Hyperarithmetical Hierarchy, 2000, Amsterdam: North-Holland Publishing Co., Amsterdam · Zbl 0960.03001 |
| [2] | Baumslag, G.; Dyer, E.; Miller, C., On the integral homology of finitely presented groups, Topology, 22, 27-46, 1983 · Zbl 0503.20018 · doi:10.1016/0040-9383(83)90044-7 |
| [3] | Chandler, B.; Magnus, W., The History of Combinatorial Group Theory: A Case Study in the History of Ideas, 1982, Berlin, Heidelberg, New York: Springer, Berlin, Heidelberg, New York · Zbl 0498.20001 · doi:10.1007/978-1-4613-9487-7 |
| [4] | Csima, BF; Solomon, R., The complexity of central series, Ann. Pure Appl. Logic, 162, 667-678, 2011 · Zbl 1247.03091 · doi:10.1016/j.apal.2011.01.011 |
| [5] | Dobritsa, VP, Computability of certain classes of construktive algebras (Russian), Sibirsk. Math. Zh., 18, 570-579, 1977 · Zbl 0361.02065 |
| [6] | Dobritsa, VP, On construktivizable abelian groups (Russian), Sibirsk. Math. Zh., 22, 208-213, 239, 1981 · Zbl 0473.03037 |
| [7] | Dobritsa, VP, Some construktivizations of abelian groups (Russian), Sibirsk. Math. Zh., 24, 18-25, 1983 · Zbl 0528.20038 |
| [8] | Dobritsa, VP; Ershov Yu, L.; Goncharov, SS; Nerode, A.; Remmel, JB, Computable classes of constructive models, Handbook of Recursive Mathematics, vol. 1, 183-233, 1998, New York: Elsevier, New York · Zbl 0976.03039 · doi:10.1016/S0049-237X(98)80005-0 |
| [9] | Dobritsa, VP; Khisamiev, NG; Nurtazin, AT, Construktive periodic abelian groups (Russian), Sibirsk. Math. Zh., 19, 1260-1265, 1978 · Zbl 0421.20021 |
| [10] | Downey, RG; Fellows, MR, Parameterized Complexity, 1999, New York: Springer, New York · doi:10.1007/978-1-4612-0515-9 |
| [11] | Downey, RG; Goncharov, SS; Kach, AM; Knight, JF; Kudinov, OV; Melnikov, AG; Turetsky, D., Decidability and computability of certain torsion-free abelian groups, Notre Dame J. Formal Logic, 51, 1, 85-96, 2010 · Zbl 1211.03063 · doi:10.1215/00294527-2010-006 |
| [12] | Downey, RG; Kurtz, SA, Recursion theory and ordered groups, Ann. Pure Appl. Logic, 32, 137-151, 1986 · Zbl 0629.03020 · doi:10.1016/0168-0072(86)90049-7 |
| [13] | Downey, RG; Montalbàn, A., The isomorphism problem for torsion-free abelian groups is analytic complete, J. Algebra, 320, 2291-2300, 2008 · Zbl 1156.03042 · doi:10.1016/j.jalgebra.2008.06.007 |
| [14] | Dzgoev, VD, Constructivizations of direct products of algebraic systems (Russian), Algebra i Logika, 21, 138-148, 1982 · Zbl 0507.03013 · doi:10.1007/BF01980749 |
| [15] | Ershov, Y., Existence of constructivizations (Russian), Dokl. Akad. Nauk SSSR, 204, 1041-1044, 1972 |
| [16] | Ershov, Y.L.: Constructive models (Russian). Izbr. Vopr. Alg. i Log. [Selected Questions in Algebra and Logic], Sbornik posvjascen. pamjati A. I. Malceva, [A collection dedicated to the memory of A. I. Malceva], Izdat. Nauk Sibirsk. Otdel., Novosibirsk, pp. 111-130 (1973) · Zbl 0293.02038 |
| [17] | Ershov, YL, Theory of Numerations (Russian), 1977, Moscow: Nauka, Moscow |
| [18] | Ershov, YL, Theorie der Numerierungen, III. Z. Math. Logik Grundlag. Math., 23, 289-371, 1977 · Zbl 0374.02028 · doi:10.1002/malq.19770231902 |
| [19] | Ershov, YL, Decision Problems and Constructivizable Models (Russian), 1980, Moskva: Nauka, Moskva · Zbl 0495.03009 |
| [20] | Ershov, Y.L., Goncharov, S.S.: Constructive Models, Siberian School of Algebra and Logic.(Russian). Nauch. Kniga, Novosibirsk (1996). [translated in: Consultants Bureau, New York, 2000] |
| [21] | Ershov, YL; Goncharov, SS; Nerode, A.; Remmel, JB; Marek, VW, Handbook of Recursive Mathematics, vol. 1 Recursive Model Theory, 1998, Amsterdam: North-Holland, Amsterdam · Zbl 0905.03001 |
| [22] | Ershov, YL; Goncharov, SS; Nerode, A.; Remmel, JB; Marek, VW, Handbook of Recursive Mathematics, vol. 2, Recursive Algebra, Analysis and Combinatorics, 1998, Amsterdam: North Holland, Amsterdam · Zbl 0905.03002 |
| [23] | Ershov, YL; Palutin, EA, Mathematical Logic (Russian), 1987, Moscow: Nauka, Moscow |
| [24] | Faermark, DS, Algorithm to determine the identity of words in the nilpotent products of groups defined by a finite number of generators, defining relations (Russian), Dokl. Akad. Nauk SSSR, 137, 291-294, 1961 · Zbl 0156.01302 |
| [25] | Fröhlich, A.; Shepherdson, JC, Effective procedures in field theory, Philos. Trans. R. Soc. London Ser. A, 248, 407-432, 1956 · Zbl 0070.03502 · doi:10.1098/rsta.1956.0003 |
| [26] | Fuchs, L., Innite Abelian Groups, 1973, New York: Academic Press, New York · Zbl 0257.20035 |
| [27] | Goncharov, SS, Autostability of models, abelian groups (Russian), Algebra i Logika, 19, 23-44, 1980 · Zbl 0468.03022 |
| [28] | Goncharov, SS, Groups with a finite number of constructivizations (Russian), Dokl. Akad. Nauk SSSR, 256, 269-272, 1981 |
| [29] | Goncharov, SS; Drobotun, BN, On the algorithmic dimention of nilpotent groups (Russian), Sibirsk. Math. Zh., 30, 52-60, 225, 1989 · Zbl 0682.20025 |
| [30] | Goncharov, SS; Lempp, S.; Solomon, R., The computable dimension of ordered abelian groups, Adv. Math., 175, 1, 102-143, 2003 · Zbl 1031.03058 · doi:10.1016/S0001-8708(02)00042-7 |
| [31] | Goncharov, SS; Molokov, AV; Romanovskiĭ, NS, Nilpotent groups of finite algorithmic dimention, Sibirsk. Math. Zh., 30, 82-88, 1989 · Zbl 0677.20024 |
| [32] | Griffor, ER, Handbook of Computability Theory, 1999, Amsterdam: North- Holland Publishing Co., Amsterdam |
| [33] | Gödel, K., Über formal unentscheibare Sätze der Principia mathematica und verwandter Systeme I, Monatsh. Math. Phys., 38, 173-198, 1931 · JFM 57.0054.02 · doi:10.1007/BF01700692 |
| [34] | Hall, M., The Theory of Groups, 1959, New York: Macmillan, New York · Zbl 0084.02202 |
| [35] | Hall, P.: Nilpotent Groups, Queen Mary College Math. Notes, Queen Mary Coll. (Univ. London), London (1969) · Zbl 0211.34201 |
| [36] | Hilbert, D.: Mathematische probleme. Archiv. f. Math. und Phys. Ser. 3, 1, 44-63, 213-237 (1901) · JFM 32.0084.05 |
| [37] | Hirschfeldt, DR; Khoussainov, B.; Shore, RA; Slinko, AM, Degree spectra and computable dimensions in algebraic structures, Ann. Pure Appl. Logic, 115, 71-113, 2002 · Zbl 1016.03034 · doi:10.1016/S0168-0072(01)00087-2 |
| [38] | Hjorth, G., The isomorphism relation on countable torsion free abelian groups, Fundamenta Math., 175, 241-257, 2002 · Zbl 1021.03042 · doi:10.4064/fm175-3-2 |
| [39] | Kargapolov, MI; Merzljakov, YI, Fundamentals of the Theory of Groups, Translations of Osnovy Theorii Grupp, 1977, Moscow: Nauka, Moscow |
| [40] | Kharlampovich, O.; Baumslag, G.; Miller, CF III, The word problem for solvable groups and lie algebras, Algorithms and Classification in Combinatorial Group Theory, 61-67, 1992, Hampton: Mathematical Sciences Research Institute Publications, Hampton · Zbl 0818.20036 · doi:10.1007/978-1-4613-9730-4_2 |
| [41] | Khisamiev, N.G.: Construktive periodic abelian groups (Russian). In: Proceedings of 5th Kazakhstan Conference on Mathematics and Mechanics, Alma-Ata, Extended Abstracts, part 2, vol. 253 (1974) |
| [42] | Khisamiev, NG, The periodic part of a strongly construktivizable abelian group (Russian), Teor. I Priklad. Zad. Mat. I Mech. Alma-Ata, Nauka Kazakh. SSR, 318, 299-303, 1977 · Zbl 0431.20043 |
| [43] | Khisamiev, NG, Criterion for construktivizable of a direct sum of cyclic p-groups (Russian), Izv. Akad. Nauk. Kazakh. SSR, Ser. Fiz.-Mat., 86, 51-55, 1981 · Zbl 0457.20001 |
| [44] | Khisamiev, ZG; Khisamiev, NG, Nonconstruktivizability of the reduced part of a strongly constructive torsion-free abelian group (Russian), Algebra I Logika, 24, 108-118, 123, 1985 · Zbl 0601.20051 · doi:10.1007/BF01978707 |
| [45] | Khisamiev, NG, Theory of abelian groups with constructive models (Russian), Sibirsk. Math. Zh., 27, 128-143, 1986 · Zbl 0625.03015 |
| [46] | Khisamiev, NG, Hierarchies of torsion-free Abelian groups (Russian), Algebra i Logika, 25, 2, 205-226, 244, 1986 · Zbl 0625.03026 · doi:10.1007/BF01978886 |
| [47] | Khisamiev, NG, Non construktivizability of certain ordered fields of real numbers (Russian), Sibirsk. Math. Zh., 28, 193-195, 1987 · Zbl 0647.03038 |
| [48] | Khisamiev, NG, The arithmetic hierarchy of Abelian Groups (Russian), Sibirsk. Math. Zh., 29, 144-159, 1988 · Zbl 0675.20043 |
| [49] | Khisamiev, NG; Ershov, YL; Goncharov, SS; Nerode, A.; Remmel, JB; Marek, VM, Constructive abelian groups, Handbook of Recursive Mathematics, vol. 2, 1177-1231, 1998, New York: Elsevier, New York · Zbl 0940.03044 |
| [50] | Khisamiev, NG, Constructivizability criterion for an abelian group (russian), Algebra i Logika, 38, 743-760, 1999 · Zbl 0937.03053 · doi:10.1007/BF02671737 |
| [51] | Khisamiev, NG, On a class of strongly decomposable abelian groups, Algebra i Logika, 41, 4, 493-509, 511, 512, 2002 · Zbl 1018.03031 · doi:10.1023/A:1020112806274 |
| [52] | Khisamiev, NG, On positive, constructive groups (Russian), Sibirsk. Mat. Zh., 53, 5, 1133-1146, 2012 · Zbl 1260.03084 |
| [53] | Khisamiev, NG; Krykpaeva, AA, Effectively completely decomposable abelian groups, Sibersk. Mat. Zh., 38, 6, 1413-1426, 1997 |
| [54] | Khisamiev, N.G., Latkin, I.V.: Computability of nilpotent product of computable torsion free Abelian groups (Russian), Abstracts of the International Conference “Actual problems of mathematics and mathematical modeling”, dedicated to the 50th anniversary of the Institute of Mathematics and Mechanics, Almaty, 1-5 June, pp. 185-186 (2015) |
| [55] | Khisamiev, NG; Nurizinov, MK; Tyulyubergenev, RK, Computable torsion-free nilpotent groups of finite dimension, Sibersk. Mat. Zh., 55, 3, 580-591, 2014 · Zbl 1304.20052 |
| [56] | Khisamiev, NG; Nurizinov, MK; Tyulyubergenev, RK, On constructive nilpotent groups, KazNU Bull. Math. Mech. Comput. Sci. Ser., 2, 82, 94-106, 2015 |
| [57] | Latkin, I.V.: Constructivizable group, nilpotent product which does not constructivizable (Russian). In: 8-Union Conference on Mathematical Logic - Moscou, p. 101 (1986) |
| [58] | Latkin, IV, Algorithmic complexity of the problem of occurrence in commutants, the members of the lower central series (Russian), Sibirsk. Math. Zh., 28, 5, 102-110, 1987 · Zbl 0638.03038 |
| [59] | Latkin, IV, Arithmetic hierarchy of torsion-free nilpotent groups, Algebra i Logika, 35, 3, 308-313, 1996 · Zbl 0976.20027 · doi:10.1007/BF02367215 |
| [60] | Latkin, I.V.: Thesis for the degree of Candidate of Physico-Mathematical Sciences. Novosibirsk State University, Russian (2001) |
| [61] | Latkin, IV, On constructivizability of the tensor product of modules (Russian), Siberian Math. J., 43, 2, 414-418, 2002 · Zbl 1011.03025 · doi:10.1023/A:1014701306542 |
| [62] | Latkin, IV, Constructive nilpotent groups with a non-constructivizable center (Russian), Bull. East Kazak. State Techn. Univ., 23, 1, 82-84, 2004 |
| [63] | Logic notebook (Russian), Novosibirsk, Inst. Math. SB USSR Acad. Sci. (1986) |
| [64] | Lyndon, RC; Schupp, PE, Combinatorial Group Theory, 1977, Berlin, Heidelberg, New York: Springer, Berlin, Heidelberg, New York · Zbl 0368.20023 |
| [65] | MacHenry, T., The tensor product and the 2-nd nilpotent product of groups, Math. J., 73, 1, 134-145, 1960 · Zbl 0121.27002 · doi:10.1007/BF01162474 |
| [66] | Magnus, W.; Karrass, A.; Solitar, D., Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations, 1966, New York, London, Sydney: Interscience Publishers, A division of Wiley & Sons Inc, Interscience, New York, London, Sydney · Zbl 0138.25604 |
| [67] | Maltsev, AI, Torsion-free abelian groups of finite rank (Russian), Math. Sb. (N.S.), 4, 67-68, 1938 · Zbl 0021.29803 |
| [68] | Maltsev, AI, On homomorphisms onto finite groups (Russian), Uchen. Zapiski Ivanovsk Ped. instituta, 18, 5, 49-60, 1958 |
| [69] | Maltsev, AI, Constructive algebras I (Russian), Uspekhi Mat. Nauk, 16, 3-60, 1961 |
| [70] | Maltsev, AI, On recursive abelian groups (Russian), Dokl. Akad. Nauk SSSR, 146, 1009-1012, 1962 · Zbl 0156.01105 |
| [71] | Maltsev, AI, Algorithms and Recursive Functions (Russian) Izdat, 1965, Moscow: Nauka, Moscow |
| [72] | Maltsev, AI; Smirnov, VD; Taiclin, M., Algebraic Systems (Russian), Izdat, 1970, Moscow: Nauka, Moscow |
| [73] | Miller, CF III; Baumslag, G.; Miller, CF III, Decision problems for groups survey and reflections, Algorithms and Classification in Combinatorial Group Theory, 1-59, 1992, Heidelberg: Springer, Heidelberg · Zbl 0752.20014 · doi:10.1007/978-1-4613-9730-4_1 |
| [74] | Neumann, H., Varieties of Groups, 1967, Berlin: Springer, Berlin · Zbl 0251.20001 · doi:10.1007/978-3-642-88599-0 |
| [75] | Novikov, PS, On the algorithmic unsolvability of the word problem in group theory (Russian), Trudy Math. Inst. Steklov., 44, 3-143, 1955 |
| [76] | Nurtazin, A.T.: Computable classes and algebraic criteria of autostability, summary of scientific thesis (Russian), Math. Inst. Siberian Branch of SSSR Acad. Sci. Novosibirsk (1974) |
| [77] | Nurtazin, A.T.: On constructive groups (Russian). In: Proceedings of 4th All-Union Conference on Mathematical Logic (Kishinev), vol. 106 (1976) |
| [78] | Rabin, MO, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc., 95, 2, 341-360, 1960 · Zbl 0156.01201 |
| [79] | Rogers Jr., H.: Theory of Recursive Functions and Effective Computability, Ist. edn. McGraw-Hill, New York, Toronto, Ontario, London (1967), 2nd edn. MIT Press, Cambridge, London (1987) · Zbl 0183.01401 |
| [80] | Roman’kov, V., Khisamiev, N.: On constructible matrix or ordered groups. In: Proceedings of Workshop Computability and Models, Kazakhstan University, Almaty, pp. 44-47(2002) |
| [81] | Roman’kov, VA; Khisamiev, NG, Constructive matrix, orderable groups, Algebra i Logika, 43, 3, 353-363, 2004 · Zbl 1080.20044 |
| [82] | Roman’kov, VA; Khisamiev, NG, Constructible matrix groups, Algebra i Logika, 43, 5, 603-613, 2004 · Zbl 1080.20045 |
| [83] | Soare, RI, Recursively Enumerable Sets and Degrees, 1987, Heidelberg: Springer, Heidelberg · Zbl 0667.03030 · doi:10.1007/978-3-662-02460-7 |
| [84] | Smith, RL; Lerman, M.; Soar, RI, Two theorems on autostability in p-groups, in Logic Year 1979-1980, Proceedings of Seminars and Conference on Mathematics and Logic University Connecticut, Storrs, CT, 1979/80, 302-311, 1981, Heidelberg: Springer, Heidelberg · Zbl 0488.03024 |
| [85] | Solomon, VA, \(Pi^0_1\) classes and orderable groups, Ann. Pure Appl. Logic, 115, 279-302, 2002 · Zbl 0998.03036 · doi:10.1016/S0168-0072(01)00097-5 |
| [86] | Uspenskiĭ, VA, The systems of enumeramerable sets and their enumerations (Russian), Docl. Akad. Nauk SSSR., 105, 6, 1155-1158, 1955 · Zbl 0067.00302 |
| [87] | van der Waerden, BL, Eine Bemerkung ber die Unzerlegbarkeit von Polynomen, Mathematische Annalen, 102, 738-739, 1930 · JFM 56.0825.05 · doi:10.1007/BF01782374 |
| [88] | Wussing, H., Die Genesis des Abstrakten Gruppenbegriff, 1969, Berlin: VEB Deutcher Verlag Wiss, Berlin · Zbl 0199.29101 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
