用户名： 密码： 验证码：
Minsky Machines and Algorithmic Problems
详细信息    查看全文
  • 关键词：Minsky machines ; Word problem ; Uniform word problem ; Semigroup ; Group ; Identity ; Variety
  • 刊名：Lecture Notes in Computer Science
  • 出版年：2015
  • 出版时间：2015
  • 年：2015
  • 卷：9300
  • 期：1
  • 页码：273-292
  • 全文大小：278 KB
  • 参考文献：1.Bou-Rabee, K.: Quantifying residual finiteness. J. Algebra 323, 729–737 (2010)MathSciNet CrossRef MATH
    2.Bridson, M.R., Wilton, H.: The isomorphism problem for profinite completions of finitely presented, residually finite groups. (English Summary) Groups Geom. Dyn. 8(3), 733–745 (2014)MathSciNet CrossRef MATH
    3.Bridson, M.R., Wilton, H.: The triviality problem for profinite completions. arXiv:​1401.​2273
    4.Clifford, A.H., Preston, G.B.: The Algebraic Theory of Semigroups, Math. Surveys 7, Vol. 1, 2, Amer. Math. Soc, Providence, RI (1961) (1967)
    5.Conway, J.H.: Unpredictable iterations. In: Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972), pp. 49–52. Univ. Colorado, Boulder, Colo. (1972)
    6.Davis, M.: A note on universal Turing machines. Automata studies. Annals of mathematics studies, no. 34, pp. 167–175. Princeton University Press, Princeton, N. J. (1956)
    7.Davis, M., Putnam, H., Robinson, J.: The decision problem for exponential diophantine equations. Ann. Math. 74(2), 425–436 (1961)MathSciNet CrossRef MATH
    8.Evans, T.: Some connections between residual finiteness, finite embeddability and the word problem. J. London Math. Soc. 1(2), 399–403 (1969)MathSciNet CrossRef MATH
    9.Gersten, S.M.: Isoperimetric and isodiametric functions of finite presentations. Geometric group theory, Vol. 1 (Sussex, 1991), 79–96, London Math. Soc. Lecture Note Ser., 181, Cambridge Univ. Press, Cambridge (1993)
    10.Gersten, S.M., Riley, T.R.: Some duality conjectures for finite graphs and their group theoretic consequences. Proc. Edin. Math. Soc. 48(2), 389–421 (2005)MathSciNet CrossRef MATH
    11.Gurevich, JuSh: The problem of equality of words for certain classes of semigroups. Algebra i Logika 5(5), 25–35 (1966)MathSciNet
    12.Hall, T.E., Kublanovskii, S., Margolis, S., Sapir, M., Trotter, P.G.: Algorithmic problems for finite groups and finite 0-simple semigroups. J. Pure Appl. Algebra 119(1), 75–96 (1997)MathSciNet CrossRef MATH
    13.Hall, T.E., Putcha, M.S.: The potential \(J\) -relation and amalgamation bases for finite semigroups. Proc. AMS 3, 361–364 (1985)MathSciNet MATH
    14.Jackson, M.: The embeddability of ring and semigroup amalgams is undecidable. J. Austral. Math. Soc. Ser. A 69(2), 272–286 (2000)MathSciNet CrossRef MATH
    15.Karrass, A., Pietrowski, A., Solitar, D.: Finite and infinite cyclic extensions of free groups. J. Austr. Math. Soc. 16, 458–466 (1973)MathSciNet CrossRef MATH
    16.Kharlampovich, O.: The universal theory of the class of finite nilpotent groups is undecidable. Mat. Zametki 33(4), 499–516 (1983)MathSciNet MATH
    17.Kharlampovich, O.: The word problem for groups and Lie algebras, Doctor’s Thesis (Russian), Moscow Steklov Mathematical Institute (1990)
    18.Kharlampovich, O., Sapir, M.: Algorithmic problem in varieties. Int. J. Algebra Comput. 5(4–5), 379–602 (1995)MathSciNet CrossRef MATH
    19.Kharlampovich, O., Myasnikov, A., Sapir, M.: Residually finite finitely presented solvable groups. arXiv:​1204.​6506
    20.Kublanovsky, S., Sapir, M.: Potential divisibility in finite semigroups is undecidable. Internat. J. Algebra Comput. 8(6), 671–679 (1998)MathSciNet CrossRef MATH
    21.Lipton, R.J., Zalcstein, Y.: Word problems solvable in logspace. J. Assoc. Comput. Mach. 24, 522–526 (1977)MathSciNet CrossRef MATH
    22.Lyapin, E.S.: Semigroups. Gos. Izd. Fiz.-Mat. Lit, Moscow (1960)MATH
    23.Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Springer-Verlag, Berlin (1977)CrossRef MATH
    24.Malcev, A.I.: Algorithms and Recursive Functions. Nauka, Moscow (1965)
    25.Malcev, A.I.: On homomorphisms onto finite groups. Uchen. Zap. Ivanovskogo Gos. Ped. Inst. 18, 49–60 (1958). English translation. In: Amer. Math. Soc. Transl. Ser. 2(119), 67–79 (1983)
    26.Minsky, M.L.: Recursive unsolvability of post’s problem of “Tag” and other topics in theory of turing machines. Annals Math. Second Ser. 74(3), 437–455 (1961)MathSciNet CrossRef MATH
    27.Sapir, M.: Residually finite semigroups, Diploma Thesis, Ural State University, Russian (1978)
    28.Sapir, M.: Problems of Burnside type and the finite basis property in varieties of semigroups. Izv. Akad. Nauk. SSSR. Ser. Mat. 51(2), 319–340 (1987). transl. in Math USSR-Izv, 30(2):295–314: (1988)MathSciNet
    29.Sapir, M.: Algorithmic problems in varieties of semigroups. Algebra i Logika 27(4), 440–463 (1988)MathSciNet CrossRef MATH
    30.Sapir, M.: Weak word problem for finite semigroups. Monoids and semigroups with applications (Berkeley, CA, : 206–219. World Sci. Publ, River Edge, NJ (1989) (1991)
    31.Sapir, M.: The restricted Burnside problem for varieties of semigroups. Izv. Akad. Nauk SSSR Ser. Mat. 55(3), 670–679 (1991). translation in Math. USSR-Izv. 38(3), 659–667 (1992)MathSciNet MATH
    32.Sapir, M.: Algorithmic problems for amalgams of finite semigroups. J. Algebra 229(2), 514–531 (2000)MathSciNet CrossRef MATH
    33.Sapir, M.: Combinatorial algebra: syntax and semantics, Springer Monographs in Mathematics (2014)
    34.Slobodskoi, A.: Undecidability of the universal theory of finite groups. Algebra Logic 20(2), 207–230 (1981)MathSciNet CrossRef
    35.Zel’manov, E.: The solution of the restricted Burnside problem for groups of odd exponent. Izv. Akad. Nauk. SSSR. Ser. Mat. 54(1), 42–59 (1990). transl. in Math. USSR-Izv. 36 (1991), no.1, 41–60MathSciNet MATH
    36.Zel’manov, E.: The solution of the restricted Burnside problem for 2-groups. Mat. Sb. 182(4), 568–592 (1991)MATH
  • 作者单位：Mark Sapir (18)

    18. Department of Mathematics, Vanderbilt University, Nashville, U.S.A
  • 丛书名：Fields of Logic and Computation II
  • ISBN：978-3-319-23534-9
  • 刊物类别：Computer Science
  • 刊物主题：Artificial Intelligence and Robotics
    Computer Communication Networks
    Software Engineering
    Data Encryption
    Database Management
    Computation by Abstract Devices
    Algorithm Analysis and Problem Complexity
  • 出版者：Springer Berlin / Heidelberg
  • ISSN：1611-3349
文摘
This is a survey of using Minsky machines to study algorithmic problems in semigroups, groups and other algebraic systems.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址：北京市海淀区学院路29号 邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700