Перевод названия: POLYNOMIAL GRAMMARS GENERATING AN INFINITE SET OF LANGUAGES
Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: Решетневские чтения; Красноярск; Красноярск
Год издания: 2022
Ключевые слова: polynomial grammars, non-commutative variables, formal power series, commutative image, jacobian, полиномиальные грамматики, некоммутативные переменные, формальный степенной ряд, коммутативный образ, якобиан
Аннотация: В работе продолжается исследование формальных грамматик, под которыми подразумеваются системы полиномиальных уравнений относительно некоммутативных переменных, которые решаются в виде формальных степенных рядов, выражающих нетерминальные символы алфавита через терминальные символы алфавита; первая компонента решения является формалПоказать полностьюьным языком. Рассмотрено определение грамматики, имеющей бесконечно много решений (порождающей бесконечное множество языков). Такие грамматики могут возникать в ситуации, когда якобиан коммутативного образа грамматики тождественно равен нулю. Показано, что в случае якобиана, тождественно равного нулю, описание множества решений грамматики сложнее, чем для аналогичных полиномиальных систем с вещественными или комплексными переменными, поскольку могут реализовываться все возможные ситуации: такая грамматика может иметь бесконечно много решений, любое конечное число решений, либо не иметь решений вовсе. The paper continues the study of formal grammars, which mean systems of polynomial equations with respect to noncommutative variables, which are solved in the form of formal power series expressing nonterminal alphabet symbols through terminal alphabet symbols; the first component of the solution is a formal language. A definition of a grammar having infinitely many solutions (generating an infinite number of languages) is considered. Such grammars can arise in a situation where the Jacobian of the commutative image of the grammar is identically zero. It is shown that in the case of a Jacobian identically equal to zero, describing the set of grammar solutions is more difficult than for similar polynomial systems with real or complex variables, since all possible situations can be realized: such a grammar can have infinitely many solutions, any finite number of solutions, or have no solutions at all.
Журнал: Решетневские чтения
Выпуск журнала: Часть 2
Номера страниц: 14-16
Место издания: Красноярск
Издатель: Федеральное государственное бюджетное образовательное учреждение высшего образования "Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнева"