Гиперграфовое исчисление Ламбека. Тихон Пшеницын (03.12.2020)

Исчисление Ламбека — это логический формализм, введенный в 1958 году И. Ламбеком для описания синтаксиса естественных языков. Для математиков интересны как собственно логические свойства этого исчисления (устранимость сечения, логические эквивалентности, модели и др.), так и свойства категориальных грамматик, в основу которых оно положено (один из основных результатов в данной области — эквивалентность контекстно-свободным грамматикам).

Помимо этого, известно, что контекстно-свободные грамматики можно обобщить на гиперграфы — получатся так называемые гиперграфовые грамматики — им был посвящен предыдущий доклад:

Возникает вопрос: возможно ли аналогичным способом обобщить на гиперграфы исчисление Ламбека? Оказывается, возможно. В данном докладе мы представим такое обобщение (введенное докладчиком), называемое гиперграфовым исчислением Ламбека. Будет показано, что в него вкладывается исчисление Ламбека, а также многие его разновидности: исчисление Ламбека с единицей, с модальностями, с правилом перестановки, с операцией обращения (reversal operation). Будет представлена теорема об устранимости сечения в данном гиперграфовом исчислении и дана сложностная характеристика проблемы выводимости секвенции.

В будущих докладах мы надеемся осветить и другие аспекты гиперграфового исчисления Ламбека: структурные свойства, категориальные грамматики и их распознающую силу, модели.

Докладчик: Пшеницын Тихон Григорьевич, мехмат, 4 курс.
Науч. руководитель: проф. М. Р. Пентус.

______________________________

Совместные заседания научных семинаров
«Логические проблемы информатики»
(руководители: проф. С.Н.Артёмов, акад. РАН Л.Д.Беклемишев,
доц. В.Н.Крупский, проф. М.Р.Пентус, доц. Т.Л.Яворская) и
«Модальная и алгебраическая логика»
(руководители: проф. М.Р.Пентус,
проф. В.Б.Шехтман, к.ф.-м.н. И.Б.Шапировский)
проходят по четвергам в 18 : 30.

Веб-страница (слайды, ссылка zoom):