电邮这篇文章 ALGORITHMIC PROPERTIES OF BASIC CATEGORIAL GRAMMARS WITH UNIQUE CATEGORY ASSIGNMENT
- 作者: Vishnikin M.E1
-
隶属关系:
- Lomonosov Moscow State University
- 期: 卷 523, 编号 1 (2025)
- 页面: 21-26
- 栏目: MATHEMATICS
- URL: https://ogarev-online.ru/2686-9543/article/view/305340
- DOI: https://doi.org/10.7868/S3034504925030044
- EDN: https://elibrary.ru/JSKCMQ
- ID: 305340
如何引用文章
开放存取
##reader.subscriptionAccessGranted##
订阅存取
详细
The work is devoted to basic categorial grammars with unique type assignment (BCGUTA). For this class, a number of algorithmic properties are examined. It is proven that, for an arbitrary context-free language L, the problem of verifying whether is generated by a grammar from the BCGUTA class is algorithmically undecidable. Furthermore, it is proven that for any two BCGUTA grammars, the problem of determining the emptiness of the intersection of the languages generated by these grammars is also algorithmically undecidable.
作者简介
M. Vishnikin
Lomonosov Moscow State University
Email: maksim.vishnikin@math.msu.ru
Moscow, Russia
参考
- Ajdukiewicz K. Die syntaktische konnexitat // Studia philosophica. 1935. P. 1-27.
- Bar-Hillel Y. A quasi-arithmetical notation for syntactic description // Language. 1953. V. 29. № 1. P. 47-58.
- 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.
- Вишникин М.Е. Базовые категориальные грамматики с однозначным присвоением типов // Вестник Московского университета. Серия 1. Математика. Механика. 2022. № 2. C. 64-67.
- Post E. A variant of a recursively unsolvable problem // Bull. Amer. Math. Soc. 1946. V. 52. № 4. P. 264-269.
- Пентус А.Е., Пентус М.Р. Теория формальных языков: Учебное пособие. Москва: Изд-во ЦПИ при механико-математическом ф-те МГУ. 2004. 80 стр.
- 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.
- 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.
- Kanazawa M. Identification in the limit of categorial grammars // Journal of Logic, Language and Information. 1996. V. 5. P. 115-155.
补充文件
注意
In the print version, the article was published under the DOI: 10.31857/S2686954325030044