?
Проверка эквивалентности программ при помощи двухленточных автоматов
Cybernetics and Systems Analysis. 2010. № 4. С. 39-48.
Zakharov V.
This paper shows how two-tape automata can be employed to design efficient equivalence checking procedures for sequential programs. The semantics of sequential programs is defined in terms of dynamic logic structures. If a dynamic frame is acyclic (i.e., all program statements are irreversible), it can be specified by means of a two-tape deterministic automaton. Then the equivalence checking problem for sequential programs operating on the dynamic frame can be reduced to the emptiness problem for two-tape automata (compound machine).
Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2014 Т. 26 № 2 С. 245-268
It is generally accepted that to unify a pair of substitutions θ_1 and θ_2 means to find out a pair of substitutions η' and η'' such that the compositions θ_1 η' and θ_2 η'' are the same. Actually, unification is the problem of solving linear equations of the form θ_1 X=θ_2 Y in the semigroup ...
Added: September 30, 2015
Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 22 С. 435-455
Strong (logic&term) equivalence of programs is the weakest decidable equivalence relation which approximates the functional equivalence of programs. In this paper we develop a new variant of the algorithm for checking strong equivalence of programs. A distinguished feature of our algorithm is that it relies completely on the algebra of finite substitutions which includes the ...
Added: September 30, 2015
Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 23 С. 455-476
Унифицировать два алгебраических выражения и означает отыскать такую подстановку термов вместо переменных этих выражений, чтобы оба терма и имели одинаковое значение. Задачу унификации можно распространить и на программы. Унифицировать две программы и означает отыскать такие цепочки присваиваний и ...
Added: September 30, 2015
Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2011 Т. 21 С. 141-166
Many problems in software engineering such as program refactoring, deobfuscation, vulnerability detection, require an efficient toolset for detecting pieces of code that have similar behavior. Current state of art in software clone detection makes it possible to find out only those pieces of code which have the same syntactic structure since. A more profound analysis ...
Added: September 30, 2015
Zakharov V., Жайлауова Ш. Р., В кн. : Проблемы теоретической кибернетики: XVIII международная конференция (Пенза, 19-23 июня 2017 г.). : М. : МГУ, МАКС Пресс, 2017. С. 84-87.
Эффективная разрешимость проблемы л-т эквивалентности дает возможность приступить к решению задачи минимизации - построения схемы программ наименьшего размера, л-т эквивалентной заданной схеме. Чтобы отыскать ее решение, заметим, что модель вычислений стандартных схем программ сходна модели вычислений автоматов-преобразователей, работающих над полугруппами. Ранее был предложен метод минимизации автоматов-преобра\-зо\-вателей, работающих над упорядоченными левосократимыми полугруппами. В данной заметке мы ...
Added: October 22, 2017
Babash A. V., Кудияров Д. С., Проблемы информационной безопасности. Компьютерные системы 2013 № 3 С. 49-54
Даны достаточные условия, при которых периоды последовательностей отображений генератора IA кратны числу 2 в степени n. ...
Added: March 8, 2014
Sergei Valentinovich Fedorenko, IEEE Access 2021 Vol. 9 P. 38673-38686
A novel method for finding roots of polynomials over finite fields has been proposed.
This method is based on the cyclotomic discrete Fourier transform algorithm.
The improvement is achieved by using the normalized cyclic convolutions,
which have a small complexity and allow matrix decomposition,
as well as methods of adapting the truncated normalized cyclic convolutions calculation.
For small values of ...
Added: April 15, 2021
Salibekyan S. M., Прикладная информатика 2017 Т. 12 № 2 С. 5-16
The article describes implementation (hardware and software) of computing system in automatic paradigm based on object-attribute (OA) computer system belonging to the class of dataflow machines. OA-computer is the system of functional unit (FU) collaborating each other. FU is hardware of software unit. The system named OA-automation emulate behavior of automation. It is discussion of ...
Added: September 14, 2019
Zakharov V., Жайлауова Ш. Р., Моделирование и анализ информационных систем 2017 Т. 24 № 4 С. 415-433
rst-order program schemata is one of the simplest models of sequential imperative
programs intended for solving verication and optimization problems. We consider the decidable rela tion of logical-thermal equivalence of these schemata and the problem of their size minimization while
preserving logical-thermal equivalence. We prove that this problem is decidable. Further we show that
the rst-order program schemata supplied ...
Added: October 12, 2017
Zakharov V., Труды Института системного программирования РАН 2015 Т. 27 № 2 С. 221-250
Finite state transducers extend the finite state automata to model functions on strings or lists. They may be used also as simple models of sequential reactive programs. These programs operate in the interaction with the environment permanently receiving data (requests) from it. At receiving a piece of data such program performs a sequence of actions. ...
Added: September 30, 2015
Babash A. V., М. : ФГБОУ ВО "РЭУ им. Г.В. Плеханова", 2016
В сборнике трудов представлены статьи по математическим ьетодам в экономике и информационной безопасности ...
Added: February 26, 2017
Zakharov V., Подымов В. В., Труды Института системного программирования РАН 2015 Т. 27 № 4
Equivalence checking algorithms found vast applications in system programming; they are used in software refactoring, security checking, malware detection, program integration, regression verification, compiler verification and validation. In this paper we show that equivalence checking procedures can be utilized for the development of global optimization transformation of programs. We consider minimization problem for two formal ...
Added: October 13, 2015
Vyalyi M., Гимадеев Р. А., Дискретный анализ и исследование операций 2014 Т. 21 № 1 С. 3-14
Получены нижние оценки сложности различения слов кратностями вхождений подслов с учётом позиции подслова в слове. Доказано, что в случае подслов длины 1 оценка оптимальна с точностью до мультипликативного множителя. Рассмотрена связь задачи различения слов вхождениями подслов с задачей различения слов автоматами. ...
Added: October 18, 2014
Babash A. V., М. : МЭСИ, 2014
Монография знакомит читателя с теоретико-автоматными методами синтеза криптографической защиты информации ...
Added: March 8, 2015
М. : МГУ, МАКС Пресс, 2017
Книга представляет собой сборник статей, написанных на основе докладов, представленных на 18-ой Международной конференции "Теоретические проблемы кибернетики" в Пензенском государственном университете, 19-23 июня 2017 г. ...
Added: October 12, 2017
Babash A. V., Кудияров Д. С., Проблемы информационной безопасности. Компьютерные системы 2013 № 3 С. 49-54
Даны достаточные условия, при которых периоды последовательностей отображений генератора IA кратны числу 2 в степени n. ...
Added: March 7, 2014
Zakharov V.A., Lecture Notes in Computer Science 2015 Vol. 9270 P. 208-221
Finite state transducers over semigroups can be regarded as a formal model of sequential reactive programs. In this paper we introduce a uniform tech- nique for checking eectively functionality, k-valuedness, equivalence and inclusion for this model of computation in the case when a semigroup these transducers op- erate over is embeddable in a decidable group. ...
Added: September 30, 2015
М. : Издательский центр «Российский государственный гуманитарный университет», 2019
Сборник включает 27 докладов международной конференции по компьютерной лингвистике и интеллектуальным технологиям «Диалог 2019», не вошедшие в ежегодник «Компьютерная лингвистика и интеллектуальные технологии», но рекомендованные Программным Комитетом к представлению на конференции. Для специалистов в области теоретической и прикладной лингвистики и интеллектуальных технологий. ...
Added: December 10, 2019
Karpov V. E., Karpova I. P., Procedia Engineering 2015 Vol. 100 P. 1459-1468
Work solutions are proposed for problems of leader definition and role distribution in homogeneous groups of robots. It is shown that transition from a swarm to a collective of robots with hierarchical organization is possible using exclusively local interaction. The local revoting algorithm is central to the procedure for choice of leader while redistribution of roles can ...
Added: March 14, 2015
Chernyshev S. V., Cherepanov E. A., Pankratiev E. V. et al., Journal of Mathematical Sciences 2005 Vol. 128 No. 6 P. 3487-3495
Added: January 27, 2014
Chuprikov P., Nikolenko S. I., Davydow A. et al., IEEE Transactions on Networking 2018 Vol. 26 No. 1 P. 342-355
Modern network elements are increasingly required to deal with heterogeneous traffic. Recent works consider processing policies for buffers that hold packets with different processing requirements (number of processing cycles needed before a packet can be transmitted out) but uniform value, aiming to maximize the throughput, i.e., the number of transmitted packets. Other developments deal with ...
Added: March 14, 2018
Goncharov R., Сапанов П. М., Яшунский А. Д., Социология власти 2013 № 3 С. 57-72
В статье представлена технология, позволяющая собирать в полевых исследованиях пространственно локализованные данные об объектах городской среды. Технология основана на автоматической привязке фотографий к пространственным координатам. Приведен план полевых и камеральных мероприятий, предложены варианты ГИС-обработки собираемых таким образом данных. В качестве примера приведены данные об использовании белорусского языка в общественном пространстве городов Белоруссии. ...
Added: April 12, 2015
Sotnikova S., Динамика сложных систем 2012 № 3 С. 84-87
In article is described designed programme complex of the physical processes modeling, which also allows to conduct the identification printed node parameters (the physical model). On printed node designed the on-board secondary power supply source is realized. For it are designed relationship interfaces of controlling program with the known program of modeling and optimization. ...
Added: December 5, 2014
Skoptsov K. A., Sheshenin S., Galatenko V. V. et al., International Journal of Applied Mechanics 2016 Vol. 8 No. 2 P. 1650016-01-1650016-18
We present a method for evaluating elastic properties of a composite material produced by molding a resin filled with short elastic fibers. A flow of the filled resin is simulated numerically using a mesh-free method. After that, assuming that spatial distribution and orientation of fibers are not significantly changed during polymerization, effective elastic moduli of ...
Added: May 22, 2016