Математическая логика, алгебра, теория чисел и дискретная математика

О разрешимых и неразрешимых теориях языков

Б. Н. Карлов

Тверской государственный университет, г. Тверь

Аннотация: В работе исследованы некоторые теории языков с различными операциями. Доказана разрешимость теорий языков с операциями дополнения, обращения, циклического сдвига, а также некоторых фрагментов теории конкатенации, когда один из языков фиксирован. Установлена неразрешимость теории ортогональной конкатенации.

Ключевые слова: формальный язык, теория, разрешимость, унар, ортогональная конкатенация.

УДК: 510.65

Поступила в редакцию: 01.12.2024
Исправленный вариант: 16.12.2024

DOI: 10.26456/vtpmk725

Реферативные базы данных:

•