?
О полиномиальной разрешимости проблемы эквивалентности программ в перегородчатых моделях над прогрессивными полугруппами
С. 174–176.
Подымов В. В., Молчанов А. Э.
Language:
Russian
In book
М.: МАКС Пресс, 2017.
Malbin D., Вестник арбитражной практики 2023 № 2 С. 20–27
The current legislation establishes the institution of protection of a good faith purchaser where the compensatory nature of the property acquisition by such purchaser is one of the preconditions for protecting. Currently, in judicial practice, an approach has been adopted, according to which property is considered to be acquired for a fee if the alienator ...
Added: July 18, 2023
Kantonistova E., Родионов И. В., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2022 Т. 507 № 1 С. 36–39
We propose a method for testing the hypothesis about the equivalence of the distribution tail of
observed data and a certain distribution tail, which is the analogue of the goodness-of-fit hypothesis for statistics
of extremes. The method is based on a new data transformation moving k largest order statistics of a
sample from the standard uniform distribution U[0,1] ...
Added: July 9, 2023
The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups
Birget J., Talambutsa A., International Journal of Algebra and Computation 2022 Vol. 32 No. 6 P. 1261–1274
In this paper, we define the symmetric Post Correspondence Problem (PCP) and prove that it is undecidable. As an application, we show that the original proof of undecidability of the freeness problem for 3×3 integer matrix semigroups works for the symmetric PCP, but not for the PCP in general. ...
Added: December 9, 2022
Blank M., Advances in Mathematics 2022 Vol. 406 Article 108529
We study measure-theoretical aspects of torus piecewise isometries.
Not much is known about this type of dynamical systems, except for
the special case of one-dimensional interval exchange mappings. The
last case is fundamentally different from the general situation
in the presence of an invariant measure (Lebesgue measure), which
helps a lot in the analysis. Due to the absence of good ...
Added: June 26, 2022
Sosnin A., Balakina Y. V., Кащихин А. Н., Вестник Санкт-Петербургского университета. Язык и литература 2022 Т. 19 № 1 С. 125–148
The article evaluates the quality of translation; we consider the applied and pragmatic aspects
of such evaluation in the conditions of the current rapid increase in the number of texts to be
translated. The article summarizes a plethora of assessment principles, each having its merits
and drawbacks, and examines the correlation between the categories of adequacy and equivalence
as ...
Added: May 31, 2022
V. Kruglov, O. Pochinka, G. Talanova, Proceedings of the International Geometry Center 2020 Vol. 13 No. 1 P. 49–60
Currently, a complete topological classification has been obtained with respect to the topological equivalence of Morse-Smale flows, [9,7], as well as their generalizations of Ω-stable flows on closed surfaces, [4]. Some results on topological conjugacy classification for such systems are also known. In particular, the coincidence of the classes of topological equivalence and conjugacy of ...
Added: June 28, 2020
Zakharov V., В кн.: Дискретные модели в теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды.: МГУ, МАКС Пресс, 2018. С. 128–130.
It is shown how the verification of the equivalence of two-tape deterministic automata can be reduced to the problem of checking the equivalence of weakly nondeterministic finite automata-transformers working on the semigroup of prefix regular languages with the concatenation operation. ...
Added: June 14, 2018
Petrenko A. K., Khoroshilov A. V., В кн.: Actual Problems of System and Software Engineering 2017. Proceedings of the 5th International Conference on Actual Problems of System and Software Engineering Supported by Russian Foundation for Basic Research. Project #17-07-20565 Moscow, Russia, November 14-16, 2017, 408 P.Vol. 1989.: Aachen: CEUR Workshop Proceedings, 2017. С. 202–208.
The paper examines the functional requirements and the basic architecture of the tools supporting model-oriented techniques for design of safety critical software/hardware systems. The best practices of development such systems are described in international standards like ARP-4754, ARP-4761, and DO-178. The proposed approach is built around architecture models expressed in AADL language and its extensions. ...
Added: March 22, 2018
Zakharov V., Жайлауова Ш. Р., В кн.: Проблемы теоретической кибернетики: XVIII международная конференция (Пенза, 19-23 июня 2017 г.).: М.: МГУ, МАКС Пресс, 2017. С. 84–87.
Эффективная разрешимость проблемы л-т эквивалентности дает возможность приступить к решению задачи минимизации - построения схемы программ наименьшего размера, л-т эквивалентной заданной схеме. Чтобы отыскать ее решение, заметим, что модель вычислений стандартных схем программ сходна модели вычислений автоматов-преобразователей, работающих над полугруппами. Ранее был предложен метод минимизации автоматов-преобра\-зо\-вателей, работающих над упорядоченными левосократимыми полугруппами. В данной заметке мы ...
Added: October 22, 2017
Zakharov V., Жайлауова Ш. Р., Моделирование и анализ информационных систем 2017 Т. 24 № 4 С. 415–433
rst-order program schemata is one of the simplest models of sequential imperative
programs intended for solving veri cation 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., Темербекова Г. Г., Моделирование и анализ информационных систем 2016 Т. 23 № 6 С. 741–753
Finite state transducers over semigroups are regarded as a formal model of sequential reactive programs that operate in the interaction with the environment. At receiving a piece of data a program performs a sequence of actions and displays the current result. Such programs usually arise at implementation of computer drivers, on-line algorithms, control procedures. In ...
Added: October 13, 2016
Zakharov V., Джусупекова З., В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.).: М.: Изд-во механико-математического факультета МГУ, 2016. С. 190–192.
Автоматы-преобразователи в качестве модели последовательных реагирующих программы используются в системном программировании, в компьютерной лингвистике, в криптографии, при проектировании микроэлектронных схем и др. Преобразователь принимает на входе последовательность сигналов и выполняет некоторую последовательность действий, преобразуя тем самым конечные слова входного алфавита в полугрупповое выражение, значения которых и являются результатами вычислений.
Мы рассматриваем автоматы-преобразователи над произвольной полугруппой $S$, ...
Added: October 13, 2016
Zakharov V., Темербекова Г. Г., В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.).: М.: Изд-во механико-математического факультета МГУ, 2016. С. 232–234.
Потоковые алгоритмы возникают при решении многих прикладных задач. В статье предложена модель потоковых программ- автоматов-преобразователей над полугруппами- и для нее была исследована проблема эквивалентности. В настоящей работе описан метод оптимизации потоковых программ. Этот метод является обобщением ранее известного подхода, предложенного в статье для минимизации автоматов-преобразователей. Решение задачи минимизации потоковых программ над группами представлено в статье ...
Added: October 13, 2016
Zakharov V., Temerbekova G., Системная информатика 2016 No. 7 P. 33–44
Finite state transducers over semigroups can be regarded as a formal model of sequential reactive programs. In some cases verification of such programs can be reduced to minimization and equivalence checking problems for this model of computation. To solve efficiently these problems certain requirements are imposed on a semigroup these transducers operate on. Minimization of ...
Added: October 13, 2016
Avdoshin S. M., Набебин А. А., М.: ДМК Пресс, 2017.
The textbook contains necessary information about universal and classical algebras, systems of axioms for the basic algebraic structures (groupoid, monoid, semi-groups, groups, partial orders, rings, fields). The basic cryptographic algorithms are described. Error-correcting codes - linear, cyclic, BCH are considered. Algorithms for designing of such codes are given. Many examples are shown. It is put ...
Added: August 19, 2016
Zakharov V., В кн.: Материалы XVII международной конференции "Проблемы теоретической кибернетики".: Каз.: Отечество, 2014. С. 100–102.
Показано, что задача проверки k-значности конечного автомата-преобразователя, работающего над полугруппой, вложимой в разрешимую группу, может быть решена за время, полиномиальное относительно размера автомата. ...
Added: October 13, 2015
Zakharov V., Новикова Т. А., В кн.: Дискретные модели в теории управляющих систем : IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г.: Труды.: М.: МАКС Пресс, 2015. С. 173–176.
В статье предложена новая модель последовательных императивных программ, использующих средства работы с динамической памятью (указателями, списками и пр.) ...
Added: October 12, 2015
Zakharov V., Cybernetics and Systems Analysis 2010 № 4 С. 39–48
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 ...
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., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 23 С. 455–476
Унифицировать два алгебраических выражения и означает отыскать такую подстановку термов вместо переменных этих выражений, чтобы оба терма и имели одинаковое значение. Задачу унификации можно распространить и на программы. Унифицировать две программы и означает отыскать такие цепочки присваиваний и ...
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., Новикова Т. А., Труды Института системного программирования РАН 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