RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Матем. сб., 1977, том 103(145), номер 2(6), страницы 147–236 (Mi msb2805)  

Эта публикация цитируется в 116 научных статьях (всего в 117 статьях)

Проблема разрешимости уравнений в свободной полугруппе

Г. С. Маканин


Аннотация: В работе построен алгоритм, распознающий разрешимость произвольных уравнений в свободной полугруппе.
Библиография: 4 названия.

Полный текст: PDF файл (7361 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Mathematics of the USSR-Sbornik, 1977, 32:2, 129–198

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.4
MSC: Primary 20M05; Secondary 02E10
Поступила в редакцию: 13.02.1977

Образец цитирования: Г. С. Маканин, “Проблема разрешимости уравнений в свободной полугруппе”, Матем. сб., 103(145):2(6) (1977), 147–236; G. S. Makanin, “The problem of solvability of equations in a free semigroup”, Math. USSR-Sb., 32:2 (1977), 129–198

Цитирование в формате AMSBIB
\RBibitem{Mak77}
\by Г.~С.~Маканин
\paper Проблема разрешимости уравнений в~свободной полугруппе
\jour Матем. сб.
\yr 1977
\vol 103(145)
\issue 2(6)
\pages 147--236
\mathnet{http://mi.mathnet.ru/msb2805}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=470107}
\zmath{https://zbmath.org/?q=an:0371.20047|0396.20037}
\transl
\by G.~S.~Makanin
\paper The problem of solvability of equations in a~free semigroup
\jour Math. USSR-Sb.
\yr 1977
\vol 32
\issue 2
\pages 129--198
\crossref{https://doi.org/10.1070/SM1977v032n02ABEH002376}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1977GH22400001}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/msb2805
  • http://mi.mathnet.ru/rus/msb/v145/i2/p147

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Г. С. Маканин, “Распознавание ранга уравнений в свободной полугруппе”, Изв. АН СССР. Сер. матем., 43:3 (1979), 547–602  mathnet  mathscinet  zmath; G. S. Makanin, “Recognition of the rank of equations in a free semigroup”, Math. USSR-Izv., 14:3 (1980), 499–545  crossref  isi
    2. Wegner L., “On Parsing 2-Level Grammars”, Acta Inform., 14:2 (1980), 175–193  crossref  mathscinet  zmath  isi
    3. Ю. М. Важенин, Б. В. Розенблат, “Разрешимость позитивной теории свободной счетнопорожденной полугруппы”, Матем. сб., 116(158):1(9) (1981), 120–127  mathnet  mathscinet  zmath; Yu. M. Vazhenin, B. V. Rozenblat, “Decidability of the positive theory of a free countably generated semigroup”, Math. USSR-Sb., 44:1 (1983), 109–116  crossref
    4. Г. С. Маканин, “Уравнения в свободной группе”, Изв. АН СССР. Сер. матем., 46:6 (1982), 1199–1273  mathnet  mathscinet  zmath; G. S. Makanin, “Equations in a free group”, Math. USSR-Izv., 21:3 (1983), 483–546  crossref
    5. K.N. Venkataraman, Ann Yasuhara, Frank M. Hawrusik, “A view of computability on term algebras”, Journal of Computer and System Sciences, 26:3 (1983), 410  crossref
    6. А. А. Разборов, “О системах уравнений в свободной группе”, Изв. АН СССР. Сер. матем., 48:4 (1984), 779–832  mathnet  mathscinet  zmath; A. A. Razborov, “On systems of equations in a free group”, Math. USSR-Izv., 25:1 (1985), 115–162  crossref
    7. J.P Pecuchet, “Solutions principales et rang d'un système d'équations avec constantes dans le monoïde libre”, Discrete Mathematics, 48:2-3 (1984), 253  crossref
    8. Rybakov V., “Equations in Free Closure Algebra and the Substitution Problem”, 287, no. 3, 1986, 554–557  mathscinet  zmath  isi
    9. Jon Barwise, Solomon Feferman, David Israel, “Meeting of the Association for Symbolic Logic, Stanford, California, 1985”, J. symb. log, 51:03 (1986), 832  crossref
    10. J. Richard Büchi, Steven Senger, “Coding in the existential theory of concatenation”, Arch math Logik, 26:1 (1987), 101  crossref  mathscinet
    11. Culik K., Karhumaki J., “The Equivalence Problem for Single-Valued 2-Way Transducers (on Npdtol Languages) Is Decidable”, SIAM J. Comput., 16:2 (1987), 221–230  crossref  mathscinet  zmath  isi
    12. Orevkov V., “Lower Bounds of the Length of Deductions in the Arithmetic Through the Complexity of Terms Participating in Them”, 294, no. 4, 1987, 784–787  mathscinet  zmath  isi
    13. Orevkov V., “Reconstruction of a Proof by its Analysis”, 293, no. 2, 1987, 313–316  mathscinet  zmath  isi
    14. Karhumaki J., “The Equivalence of Mappings on Languages”, Lect. Notes Comput. Sci., 281 (1987), 26–38  crossref  mathscinet  isi
    15. J. Richard Büchi†, Steven Senger, “Definability in the Existential Theory of Concatenation and Undecidable Extensions of this Theory”, Z Math Logik Grundlagen Math, 34:4 (1988), 337  crossref  mathscinet  zmath
    16. William M. Farmer, “A unification algorithm for second-order monadic terms”, Annals of Pure and Applied Logic, 39:2 (1988), 131  crossref
    17. Abdulrab H., Pecuchet J., “Solving Word Equations”, J. Symbolic Comput., 8:5 (1989), 499–521  crossref  mathscinet  zmath  isi
    18. Abdulrab H., “Equations in Words”, Lect. Notes Comput. Sci., 358 (1989), 508–520  crossref  mathscinet  isi
    19. Abdulrab H., Pecuchet J., “Solving Systems of Linear Diophantine Equations and Word Equations”, Lect. Notes Comput. Sci., 355 (1989), 530–532  isi
    20. Abdulrab H., Pecuchet J., “On Word Equations and Makanin Algorithm”, Lect. Notes Comput. Sci., 380 (1989), 1–12  crossref  mathscinet  zmath  isi
    21. Jean-François Romeuf, “A polynomial algorithm for solving systems of two linear diophantine equations”, Theoretical Computer Science, 74:3 (1990), 329  crossref
    22. Taimanov A., Taimanov V., “On the Representation of the Solution of Equation in Free Semigroup Without Unit”, 312, no. 2, 1990, 274–276  mathscinet  isi
    23. Orevkov V., “Correctness of Short Proofs in Theory with Notions of Feasibility”, Lect. Notes Comput. Sci., 417 (1990), 242–245  crossref  mathscinet  zmath  isi
    24. Abdulrab H., “Solving Word Equations”, Rairo-Inform. Theor. Appl.-Theor. Inform. Appl., 24:2 (1990), 109–130  mathscinet  zmath  isi
    25. Neraud J., “On the Deficit of a Finite-Set of Words”, Semigr. Forum, 41:1 (1990), 1–21  crossref  mathscinet  zmath  isi
    26. William M. Farmer, “Simple second-order languages for which unification is undecidable”, Theoretical Computer Science, 87:1 (1991), 25  crossref
    27. Narjes Doggaz, Claude Kirchner, “Completion for unification”, Theoretical Computer Science, 85:2 (1991), 231  crossref
    28. Abdulrab H., “Implementation of Makanin Algorithm”, Lect. Notes Comput. Sci., 572 (1992), 61–84  crossref  mathscinet  isi
    29. Klaus U. Schulz, “Word unification and transformation of generalized equations”, J Automated Reasoning, 11:2 (1993), 149  crossref  mathscinet  zmath
    30. J. Karhumäki, “Equations over finite sets of words and equivalence problems in automata theory”, Theoretical Computer Science, 108:1 (1993), 103  crossref
    31. J JAFFAR, “Constraint logic programming: a survey”, The Journal of Logic Programming, 19-20 (1994), 503  crossref
    32. Friedrich Otto, “Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general”, Information Processing Letters, 53:5 (1995), 237  crossref
    33. Koscielski A., Pacholski L., “Complexity of Makanin's Algorithm”, J. ACM, 43:4 (1996), 670–684  crossref  mathscinet  zmath  isi
    34. SchmidtSchauss M., “An Algorithm for Distributive Unification”, Rewriting Techniques and Applications, Lecture Notes in Computer Science, 1103, ed. Ganzinger H., Springer-Verlag Berlin, 1996, 287–301  crossref  mathscinet  isi
    35. Otten J., Kreitz C., “T-String Unification: Unifying Prefixes in Non-Classical Proof Methods”, Theorem Proving with Analytic Tableaux and Related Methods, Lecture Notes in Artificial Intelligence, 1071, eds. Miglioli P., Moscato U., Mundici D., Ornaghi M., Springer-Verlag Berlin, 1996, 244–260  mathscinet  isi
    36. Kryvyi S., “Unification Problem in Equational Theories”, Cybern. Syst. Anal., 33:6 (1997), 874–899  crossref  mathscinet  zmath  isi
    37. Karhumaki J., Plandowski W., Mignosi F., “The Expressibility of Languages and Relations by Word Equations”, Automata, Languages and Programming, Lecture Notes in Computer Science, 1256, eds. Degano P., Gorrieri R., MarchettiSpaccamela A., Springer-Verlag Berlin, 1997, 98–109  crossref  mathscinet  isi
    38. Diekert V., Matiyasevich Y., Muscholl A., “Solving Trace Equations Using Lexicographical Normal Forms”, Automata, Languages and Programming, Lecture Notes in Computer Science, 1256, eds. Degano P., Gorrieri R., MarchettiSpaccamela A., Springer-Verlag Berlin, 1997, 336–346  crossref  mathscinet  isi
    39. Narendran P., Otto F., “The Word Matching Problem Is Undecidable for Finite Special String-Rewriting Systems That Are Confluent”, Automata, Languages and Programming, Lecture Notes in Computer Science, 1256, eds. Degano P., Gorrieri R., MarchettiSpaccamela A., Springer-Verlag Berlin, 1997, 638–648  crossref  mathscinet  isi
    40. Antoni Kościelski, Leszek Pacholski, “Makanin's algorithm is not primitive recursive”, Theoretical Computer Science, 191:1-2 (1998), 145  crossref
    41. Friedrich Otto, Paliath Narendran, Daniel J. Dougherty, “Equational unification, word unification, and 2nd-order equational unification”, Theoretical Computer Science, 198:1-2 (1998), 1  crossref
    42. Manfred Schmidt-Schauβ, “A decision algorithm for distributive unification”, Theoretical Computer Science, 208:1-2 (1998), 111  crossref
    43. O. Kharlampovich, A. Myasnikov, “Irreducible Affine Varieties over a Free Group”, Journal of Algebra, 200:2 (1998), 517  crossref
    44. Plandowski W., Rytter W., “Application of Lempel-Ziv Encodings to the Solution of Word Equations”, Automata, Languages and Programming, Lecture Notes in Computer Science, 1443, eds. Larsen K., Skyum S., Winskel G., Springer-Verlag Berlin, 1998, 731–742  crossref  mathscinet  zmath  isi
    45. Volker Diekert, Yuri Matiyasevich, Anca Muscholl, “Solving word equations modulo partial commutations”, Theoretical Computer Science, 224:1-2 (1999), 215  crossref
    46. Noriko Sugimoto, Hiroki Ishizaka, “Generating languages by a derivation procedure for elementary formal systems”, Information Processing Letters, 69:4 (1999), 161  crossref
    47. Gurevich Y., Voronkov A., “Monadic Simultaneous Rigid E-Unification”, Theor. Comput. Sci., 222:1-2 (1999), 133–152  crossref  mathscinet  zmath  isi
    48. Beauquier J., Berard B., Fribourg L., “A New Rewrite Method for Proving Convergence of Self-Stabilizing Systems”, Distributed Computing, Lecture Notes in Computer Science, 1693, ed. Jayanti P., Springer-Verlag Berlin, 1999, 240–253  crossref  isi
    49. Rytter W., “Algorithms on Compressed Strings and Arrays”, Sofsem'99: Theory and Practice of Informatics, Lecture Notes in Computer Science, 1725, eds. Pavelka J., Tel G., Bartosek M., Springer-Verlag Berlin, 1999, 48–65  crossref  mathscinet  zmath  isi
    50. Robson J., Diekert V., “On Quadratic Word Equations”, Stacs'99 - 16th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, 1563, eds. Meinel C., Tison S., Springer-Verlag Berlin, 1999, 217–226  crossref  mathscinet  zmath  isi
    51. В. Г. Дурнев, “Неразрешимость простого фрагмента позитивной теории с одной константой свободной полугруппы ранга 2”, Матем. заметки, 67:2 (2000), 191–200  mathnet  crossref  mathscinet  zmath; V. G. Durnev, “Undecidability of a simple fragment of a positive theory with a single constant for a free semigroup of rank two”, Math. Notes, 67:2 (2000), 152–159  crossref  isi
    52. Jordi Levy, Margus Veanes, “On the Undecidability of Second-Order Unification”, Information and Computation, 159:1-2 (2000), 125  crossref
    53. Rytter W., “Compressed and Fully Compressed Pattern Matching in One and Two Dimensions”, Proc. IEEE, 88:11, SI (2000), 1769–1778  crossref  isi
    54. Ilie L., Plandowski W., “Two-Variable Word Equations”, Rairo-Inform. Theor. Appl.-Theor. Inform. Appl., 34:6 (2000), 467–501  crossref  mathscinet  zmath  isi
    55. Degtyarev A., Gurevich Y., Narendran P., Veanes M., Voronkov A., “Decidability and Complexity of Simultaneous Rigid E-Unification with One Variable and Related Results”, Theor. Comput. Sci., 243:1-2 (2000), 167–184  crossref  mathscinet  zmath  isi
    56. Karhumaki J., Mignosi F., Plandowski W., “The Expressibility of Languages and Relations by Word Equations”, J. ACM, 47:3 (2000), 483–505  crossref  mathscinet  isi
    57. Gutierrez C., “Equations in Free Semigroups with Anti-Involution and their Relation to Equations in Free Groups”, Latin 2000: Theoretical Informatics, Lecture Notes in Computer Science, 1776, eds. Gonnet G., Panario D., Viola A., Springer-Verlag Berlin, 2000, 387–396  crossref  zmath  isi
    58. Ilie L., Plandowski W., “Two-Variable Word Equations”, Stacs 2000: 17th Annual Symposium on Theoretical Aspect of Computer Science, Lecture Notes in Computer Science, 1770, eds. Reichel H., Tison S., Springer-Verlag Berlin, 2000, 122–132  crossref  mathscinet  zmath  isi
    59. Sabrina Mantaci, Antonio Restivo, “Codes and equations on trees”, Theoretical Computer Science, 255:1-2 (2001), 483  crossref
    60. Karhumaki J., Mignosi F., Plandowski W., “On the Expressibility of Languages by Word Equations with a Bounded Number of Variables”, Bull. Belg. Math. Soc.-Simon Steven, 8:2 (2001), 293–305  mathscinet  isi
    61. Beauquier J., Berard B., Fribourg L., Magniette F., “Proving Convergence of Self-Stabilizing Systems Using First-Order Rewriting and Regular Languages”, Distrib. Comput., 14:2 (2001), 83–95  crossref  isi
    62. Diekert V., Muscholl A., “Solvability of Equations in Free Partially Commutative Groups Is Decidable”, Automata Languages and Programming, Proceeding, Lecture Notes in Computer Science, 2076, eds. Orejas F., Spirakis P., VanLeeuwen J., Springer-Verlag Berlin, 2001, 543–554  crossref  mathscinet  zmath  isi
    63. Baader F., Schulz K., “Combining Constraint Solving”, Constraints in Computational Logics: Theory and Applications, Lecture Notes in Computer Science, 2002, eds. Comon H., Marche C., Treinen R., Springer-Verlag Berlin, 2001, 104–158  crossref  mathscinet  zmath  isi
    64. В. Ю. Попов, “О позитивных теориях многообразий и псевдомногообразий полугрупп”, Фундамент. и прикл. матем., 8:2 (2002), 631–635  mathnet  mathscinet  zmath
    65. Sergei Vorobyov, “∀∃5-equational theory of context unification is undecidable”, Theoretical Computer Science, 275:1-2 (2002), 463  crossref
    66. Manfred Schmidt-Schauß, Klaus U. Schulz, “Solvability of Context Equations with Two Context Variables is Decidable”, Journal of Symbolic Computation, 33:1 (2002), 77  crossref
    67. Temur Kutsia, “Pattern Unification with Sequence Variables and Flexible Arity Symbols”, Electronic Notes in Theoretical Computer Science, 66:5 (2002), 52  crossref
    68. Diekert V., Lohrey M., “A Note on the Existential Theory of Equations in Plain Groups”, Int. J. Algebr. Comput., 12:1-2 (2002), 1–7  crossref  mathscinet  zmath  isi
    69. Karhumaki J., Lisovik L., “The Equivalence Problem of Finite Substitutions on Abc, with Applications”, Automata, Languages and Programming, Lecture Notes in Computer Science, 2380, eds. Widmayer P., Triguero F., Morales R., Hennessy M., Eidenbenz S., Conejo R., Springer-Verlag Berlin, 2002, 812–820  crossref  mathscinet  isi
    70. Gutierrez C., “Equations in Free Semigroups with Involution and their Relation to Equations in Free Groups”, Theor. Comput. Sci., 297:1-3 (2003), 271–280  crossref  mathscinet  zmath  isi
    71. Erk K., Niehren J., “Well-Nested Parallelism Constraints for Ellipsis Resolution”, Eacl 2003: 10th Conference of the European Chapter of the Association for Computational Linguistics, Proceedings of the Conference, Association Computational Linguistics, 2003, 115–122  isi
    72. Diekert V., Lohrey M., “Word Equations Over Graph Products”, Fst Tcs 2003: Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, 2914, eds. Pandya P., Radhakrishnan J., Springer-Verlag Berlin, 2003, 156–167  crossref  mathscinet  zmath  isi
    73. Baba K., Tsuruta S., Shinohara A., Takeda M., “On the Length of the Minimum Solution of Word Equations in One Variable”, Mathematical Foundations of Computer Science 2003, Proceedings, Lecture Notes in Computer Science, 2747, eds. Rovan B., Vojtas P., Springer-Verlag Berlin, 2003, 189–197  crossref  mathscinet  zmath  isi
    74. Kuske D., Lohrey M., “Decidable Theories of Cayley-Graphs”, Stacs 2003, Proceedings, Lecture Notes in Computer Science, 2607, eds. Alt H., Habib M., Springer-Verlag Berlin, 2003, 463–474  crossref  mathscinet  zmath  isi
    75. Manfred Schmidt-Schauß, “Decidability of bounded second order unification”, Information and Computation, 188:2 (2004), 143  crossref
    76. Plandowski W., “Satisfiability of Word Equations with Constants Is in Pspace”, J. ACM, 51:3 (2004), 483–496  crossref  mathscinet  zmath  isi
    77. Rytter W., “Grammar Compression, Lz-Encodings, and String Algorithms with Implicit Input”, Automata , Languages and Programming, Proceedings, Lecture Notes in Computer Science, 3142, eds. Diaz J., Karhumaki J., Lepisto A., Sannella D., Springer-Verlag Berlin, 2004, 15–27  crossref  mathscinet  zmath  isi
    78. Zhang T., Sipma H., Manna Z., “Decision Procedures for Recursive Data Structures with Integer Constraints”, Automated Reasoning, Proceedings, Lecture Notes in Artificial Intelligence, 3097, eds. Basin D., Rusinowitch M., Springer-Verlag Berlin, 2004, 152–167  mathscinet  zmath  isi
    79. Coelho J., Florido M., “Clp(Flex): Constraint Logic Programming Applied to Xml Processing”, On the Move to Meaningful Internet Systems 2004: Coopls, Doa, and Odbase, Pt 2, Proceedings, Lecture Notes in Computer Science, 3291, ed. Meersman R., Springer-Verlag Berlin, 2004, 1098–1112  crossref  isi
    80. Elena Czeizler, “The non-parametrizability of the word equation : A short proof”, Theoretical Computer Science, 345:2-3 (2005), 296  crossref
    81. Manfred Schmidt-Schauß, Klaus U. Schulz, “Decidability of bounded higher-order unification”, Journal of Symbolic Computation, 40:2 (2005), 905  crossref
    82. Diekert V., Gutierrez C., Hagenah C., “The Existential Theory of Equations with Rational Constraints in Free Groups Is Pspace-Complete”, Inf. Comput., 202:2 (2005), 105–140  crossref  mathscinet  zmath  isi  elib
    83. Diekert V., Muscholl A., “Solvability of Equations in Graph Groups Is Decidable”, Int. J. Algebr. Comput., 16:6 (2006), 1047–1069  crossref  mathscinet  zmath  isi
    84. Zhang T., Sipma H.B., Manna Z., “Decision Procedures for Term Algebras with Integer Constraints”, Inf. Comput., 204:10 (2006), 1526–1574  crossref  mathscinet  zmath  isi
    85. Kuske D., Lohrey M., “Logical Aspects of Cayley-Graphs: the Monoid Case”, Int. J. Algebr. Comput., 16:2 (2006), 307–340  crossref  mathscinet  zmath  isi
    86. Kuske D., “Theories of Orders on the Set of Words”, Rairo-Theor. Inform. Appl., 40:1 (2006), 53–74  crossref  mathscinet  zmath  isi
    87. Temur Kutsia, “Solving equations with sequence variables and sequence functions”, Journal of Symbolic Computation, 42:3 (2007), 352  crossref
    88. ELENA CZEIZLER, JUHANI KARHUMÄKI, “ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS”, Int. J. Found. Comput. Sci, 18:04 (2007), 873  crossref
    89. Deis T., Meakin J., Senizergues G., “Equations in Free Inverse Monoids”, Int. J. Algebr. Comput., 17:4 (2007), 761–795  crossref  mathscinet  zmath  isi
    90. Kunc M., “What Do We Know About Language Equations?”, Developments in Language Theory, Proceedings, Lecture Notes in Computer Science, 4588, eds. Harju T., Karhumaki J., Lepisto A., Springer-Verlag Berlin, 2007, 23–27  crossref  isi
    91. Kunc M., “The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable”, Fundamentals of Computation Theory, Proceedings, Lecture Notes in Computer Science, 4639, eds. CsuhajVarju E., Esik Z., Springer-Verlag Berlin, 2007, 365–375  crossref  zmath  isi
    92. Jordi Levy, Manfred Schmidt-Schauß, Mateu Villaret, “The Complexity of Monadic Second-Order Unification”, SIAM J Comput, 38:3 (2008), 1113  crossref  mathscinet  isi
    93. В. Г. Дурнев, О. В. Зеткина, “Об уравнениях с ограничениями на решения в свободных полугруппах”, Исследования по конструктивной математике и математической логике. XI, Зап. научн. сем. ПОМИ, 358, ПОМИ, СПб., 2008, 120–129  mathnet  elib; V. G. Durnev, O. V. Zetkina, “On equations in free semigroups with certain constraints on their solutions”, J. Math. Sci. (N. Y.), 158:5 (2009), 671–676  crossref  elib
    94. S. Cavagnetto, “The Lengths of Proofs: Kreisel's conjecture and Gödel's speed-up theorem”, Исследования по конструктивной математике и математической логике. XI, Зап. научн. сем. ПОМИ, 358, ПОМИ, СПб., 2008, 153–188  mathnet; J. Math. Sci. (N. Y.), 158:5 (2009), 689–707  crossref
    95. Baaz M., Wojtylak P., “Generalizing Proofs in Monadic Languages”, Ann. Pure Appl. Log., 154:2 (2008), 71–138  crossref  mathscinet  zmath  isi
    96. Francine Blanchet-Sadri, D. Dakota Blair, Rebeca V. Lewis, “Equations on partial words”, Theoret Informatics Appl, 43:1 (2009), 23  crossref  mathscinet  zmath  isi
    97. Jordi Levy, Mateu Villaret, “Simplifying the signature in second-order unification”, AAECC, 2009  crossref  isi
    98. Kudinov O.V., Selivanov V.L., “Definability in the Infix Order on Words”, Developments in Language Theory, Proceedings, Lecture Notes in Computer Science, 5583, eds. Diekert V., Nowotka D., Springer-Verlag Berlin, 2009, 454–465  crossref  mathscinet  zmath  isi
    99. J. Levy, M. Schmidt-Schauss, M. Villaret, “On the complexity of Bounded Second-Order Unification and Stratified Context Unification”, Logic Journal of the IGPL, 2010  crossref
    100. Temur Kutsia, Jordi Levy, Mateu Villaret, “On the relation between Context and Sequence Unification”, Journal of Symbolic Computation, 45:1 (2010), 74  crossref
    101. Adrià Gascón, Guillem Godoy, Manfred Schmidt-Schauß, Ashish Tiwari, “Context unification with one context variable”, Journal of Symbolic Computation, 45:2 (2010), 173  crossref
    102. Horatiu Cirstea, Claude Kirchner, Radu Kopetz, Pierre-Etienne Moreau, “Anti-patterns for rule-based languages”, Journal of Symbolic Computation, 45:5 (2010), 523  crossref
    103. В. Г. Дурнев, О. В. Зеткина, “Об уравнениях с подполугрупповыми ограничениями на решения в свободных полугруппах”, Чебышевский сб., 11:3 (2010), 78–87  mathnet  zmath
    104. Juhani Karhumäki, Aleksi Saarela, “On maximal chains of systems of word equations”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 130–136  mathnet  mathscinet; Proc. Steklov Inst. Math., 274 (2011), 116–123  crossref  isi
    105. Casals-Ruiz M., Kazachkov I., “On Systems of Equations Over Free Partially Commutative Groups”, Mem. Am. Math. Soc., 212:999 (2011), 1+  crossref  mathscinet  isi  elib
    106. Casals-Ruiz M., Kazachkov I.V., “On Systems of Equations Over Free Products of Groups”, J. Algebra, 333:1 (2011), 368–426  crossref  mathscinet  zmath  isi  elib
    107. Klima O., Polak L., “Identity Problems, Solvability of Equations and Unification in Varieties of Semigroups Related to Varieties of Groups”, Algebraic Foundations in Computer Science: Essays Dedicated to Symeon Bozapalidis on the Occasion of His Retirement, Lecture Notes in Computer Science, 7020, eds. Kuich W., Rahonis G., Springer-Verlag Berlin, 2011, 214–227  crossref  mathscinet  zmath  isi
    108. Xiang Fu, Michael C. Powell, Michael Bantegui, Chung-Chih Li, “Simple linear string constraints”, Form Asp Comp, 2012  crossref
    109. Kiezun A., Ganesh V., Artzi Sh., Guo Ph.J., Hooimeijer P., Ernst M.D., “Hampi: a Solver for Word Equations Over Strings, Regular Expressions, and Context-Free Grammars”, ACM Trans. Softw. Eng. Methodol., 21:4 (2012), 25  crossref  isi
    110. Baader F., Okhotin A., “On Language Equations with One-Sided Concatenation”, Fundam. Inform., 126:1 (2013), 1–35  crossref  isi
    111. Ferte J., Marin N., Senizergues G., “Word-Mappings of Level 2”, Theor. Comput. Syst., 54:1 (2014), 111–148  crossref  isi
    112. Temur Kutsia, Mircea Marin, “Regular expression order-sorted unification and matching”, Journal of Symbolic Computation, 2014  crossref
    113. В. Г. Дурнев, О. В. Зеткина, “Некоторые результаты, полученные в Ярославском отделении алгебраической школы М. Д. Гриндлингера”, Чебышевский сб., 15:4 (2014), 5–31  mathnet
    114. В. Г. Дурнев, О. В. Зеткина, А. И. Зеткина, “Об уравнениях и неравенствах в словах и длинах”, Чебышевский сб., 17:2 (2016), 137–145  mathnet  elib
    115. Szabo P., Siekmann J., Hoche M., “What Is Essential Unification?”, Martin Davis on Computability, Computational Logic, and Mathematical Foundations, Outstanding Contributions to Logic, 10, eds. Omodeo E., Policriti A., Springer International Publishing Ag, 2016, 285–314  crossref  isi
    116. А. Н. Непейвода, “Заметка об автоматическом решении квадратичных уравнений в словах”, Программные системы: теория и приложения, 9:2 (2018), 3–21  mathnet  crossref
    117. С. И. Адян, “Об исследованиях Геннадия Семëновича Маканина по алгоритмическим вопросам теории групп и полугрупп”, УМН, 73:3(441) (2018), 183–196  mathnet  crossref  adsnasa  elib; S. I. Adian, “On the studies of Gennadii Semënovich Makanin on algorithmic questions of the theory of groups and semigroups”, Russian Math. Surveys, 73:3 (2018), 553–568  crossref  isi
  • Математический сборник (новая серия) - 1964–1988 Sbornik: Mathematics (from 1967)
    Просмотров:
    Эта страница:871
    Полный текст:250
    Литература:46

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018