Tree adjunct grammar inference as a tool for automatic generalization of algorithms
Keywords:
tree adjunct grammar, grammar inference, automatic programming, AND-OR treeAbstract
The article considers the problem of automatic generalization of algorithms in procedural programming languages. A unique way of combining the semantics of algorithms is proposed by representing the program as a recurrent function in reverse Polish notation and deriving a tree adjunct grammar (TAG) with the formation of an AND-OR tree using the algorithm of set-theoretic operations on formal grammars. A description of the AND-OR graph of the internal representation of the algorithm and the main stages of program generalization are given. At present, the algorithm has not been tested.
References
Поляков, В. И. Основы теории алгорит-мов / В. И. Поляков, В. И. Скорубский. – СПб : СПб НИУ ИТМО, 2012.
Лаздин, А. В. Формальные языки, грам-матики, автоматы. / А. В. Лаздин. – СПб : Университет ИТМО, 2019.
de la Higuera C. Grammatical Inference: Learning Automata and Grammars. / C. de la Higuera. – Cambridge : Cambridge University Press, 2010.
Wojciech, W. Grammatical Inference. Т. 673 / W. Wojciech. – 2017.
Вандевурд, Д. Шаблоны С++. Справочник разработчика. / Д. Вандевурд, Н. М. Джонаттис, Д. Грегор. – Изд. 2. – СПб. : ООО «Альфа-книга», 2018. – 848 c.
Helmuth, T. Improving generalization of evolved programs through automatic simplification / T. Helmuth, N. Mcphee, E. Pantridge, L. Spector. – 2017. – С. 937-944.
Xu D. Neural Task Programming: Learning to Generalize Across Hierarchical Tasks / D. Xu, S. Nair, Y. Zhu [и др.]. – 2017.
Elleuch, S. From Metaheuristics to Automatic Programming / S. Elleuch, B. Jarboui, P. Siarry. – 2022. – С. 3-38.
O’Neill, M. Automatic programming: The open issue? / M. O’Neill, L. Spector // Genetic Programming and Evolvable Machines. – 2020. – Т. 21.
Грачев, П. Г. Генерация автоматов на основе рекуррентных нейросетей и автоматического выбора кластеризации [Текст: электронный] / П. Г. Грачев, С. Б. Муравьев, А. А. Фильченков, А. А. Шалыто// Информационно-управляющие системы, 2020. – № 1 (104). – URL: https://cyberleninka.ru/article/n/generatsiya-avtomatov-na-osnove-rekurrentnyh-neyrosetey-i-avtomaticheskogo-vybora-klasterizatsii
Григорьев, А. В. Алгоритм выполне-ния теоретико-множественных операций над грамматиками в среде специализированной оболочки для создания интеллектуальных САПР / А. В. Григорьев // Наукові праці Донецького національного технічного університету : Проблеми моделювання та автоматизації проектування. – Донецьк : ДонНТУ, 2002. – С. 83-93.
Abbass, H. AntTAG: a new method to compose computer programs using colonies of ants / H. Abbass, N. Hoai, R. McKay. – 2002. – Т. 2. – С. 1654-1659.
Григорьев, А. В. Комплекс средств и методов работы с формальными грамматиками в семиотической концептуальной модели предметной области интеллектуальных САПР / А. В. Григорьев // Информатика и кибернетика. – Донецк: ДонНТУ, 2017. – № 1(7). – С. 46-72.
Крицкий, С. П. Реализация оптимизи-рующих преобразований программ с помощью структурных предикативных грамматик / С. П. Крицкий, Б. Ю. Тапкинов. – Текст: электронный // Известия вузов. Северо-Кавказский регион. Серия: Естественные науки. – 2006. – № S1. – URL: https://cyberleninka.ru/article/n/realizatsiya-optimiziruyuschih-preobrazovaniy-programm-s-pomoschyu-strukturnyh-predikativnyh-grammatik
