- Код статьи
- S2686954325030044-1
- DOI
- 10.31857/S2686954325030044
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 523 / Номер выпуска 1
- Страницы
- 21-26
- Аннотация
- Работа посвящена базовым категориальным грамматикам с однозначным присвоением типов (БКГОПТ). Для данного класса рассмотрен ряд алгоритмических свойств. Доказано, что проверка для произвольного контекстно-свободного языка L того, порождается ли он некоторой грамматикой из класса БКГОПТ, является алгоритмически неразрешимой. Кроме того, доказано, что для произвольных двух БКГОПТ задача определения пустоты пересечения языков, порождаемых этими грамматиками, также алгоритмически неразрешима.
- Ключевые слова
- формальные грамматики категориальные грамматики единственность назначения категорий
- Дата публикации
- 23.05.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 12
Библиография
- 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.
