Email this article 
ALGORITHMIC PROPERTIES OF BASIC CATEGORIAL GRAMMARS WITH UNIQUE CATEGORY ASSIGNMENT
- Authors: Vishnikin M.E1
-
Affiliations:
- Lomonosov Moscow State University
- Issue: Vol 523, No 1 (2025)
- Pages: 21-26
- Section: 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
Cite item
Open Access
Access granted
Subscription Access
Abstract
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.
About the authors
M. E Vishnikin
Lomonosov Moscow State University
Email: maksim.vishnikin@math.msu.ru
Moscow, Russia
References
- 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.
Supplementary files
Note
In the print version, the article was published under the DOI: 10.31857/S2686954325030044