By this author

ALGORITHMIC PROPERTIES OF BASIC CATEGORIAL GRAMMARS WITH UNIQUE CATEGORY ASSIGNMENT

Issue number 1 from 23.05.2025

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

11 0