АЛГОРИТМИЧЕСКИЕ СВОЙСТВА БАЗОВЫХ КАТЕГОРИАЛЬНЫХ ГРАММАТИК С ОДНОЗНАЧНЫМ ПРИСВОЕНИЕМ КАТЕГОРИЙ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Работа посвящена базовым категориальным грамматикам с однозначным присвоением типов (БКГОПТ). Для данного класса рассмотрен ряд алгоритмических свойств. Доказано, что проверка для произвольного контекстно-свободного языка L того, порождается ли он некоторой грамматикой из класса БКГОПТ, является алгоритмически неразрешимой. Кроме того, доказано, что для произвольных двух БКГОПТ задача определения пустоты пересечения языков, порождаемых этими грамматиками, также алгоритмически неразрешима.

Об авторах

М. Е Вишникин

Московский государственный университет имени М.В. Ломоносова

Email: maksim.vishnikin@math.msu.ru
Москва, Россия

Список литературы

  1. Ajdukiewicz K. Die syntaktische konnexitat // Studia philosophica. 1935. P. 1-27.
  2. Bar-Hillel Y. A quasi-arithmetical notation for syntactic description // Language. 1953. V. 29. № 1. P. 47-58.
  3. Bar-Hillel Y., Gaijman H., Shamir E. On categorial and phrase structure grammars // Bulletin of the Research Council of Israel. 1960. 9F. P. 155-166.
  4. Вишникин М.Е. Базовые категориальные грамматики с однозначным присвоением типов // Вестник Московского университета. Серия 1. Математика. Механика. 2022. № 2. C. 64-67.
  5. Post E. A variant of a recursively unsolvable problem // Bull. Amer. Math. Soc. 1946. V. 52. № 4. P. 264-269.
  6. Пентус А.Е., Пентус М.Р. Теория формальных языков: Учебное пособие. Москва: Изд-во ЦПИ при механико-математическом ф-те МГУ. 2004. 80 стр.
  7. Neary T. Undecidability in binary tag systems and the Post correspondence problem for five pairs of words // Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science. 2015. V. 30. P. 649-661.
  8. Foret A. The emptiness of intersection problem for languages of k-valued categorial grammars (classical and Lambek) is undecidable // Electronic Notes in Theoretical Computer Science. 2004. V. 53. P. 81-93.
  9. Kanazawa M. Identification in the limit of categorial grammars // Journal of Logic, Language and Information. 1996. V. 5. P. 115-155.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Примечание

В печатной версии статья выходила под DOI: 10.31857/S2686954325030044


© Российская академия наук, 2025

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).