- PII
- S3034504925030044-1
- DOI
- 10.7868/S3034504925030044
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume 523 / Issue number 1
- Pages
- 21-26
- 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.
- Keywords
- формальные грамматики категориальные грамматики единственность назначения категорий
- Date of publication
- 02.06.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 72
References
- 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.
