?
Об эквивалентности ограниченно недетерминированных автоматов-преобразователей над полугруппами
С. 100–102.
Zakharov V.
Language:
Russian
In book
Каз.: Отечество, 2014.
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
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
Gnatenko A., Zakharov V., Automatic Control and Computer Sciences 2021 Vol. 55 No. 7 P. 776–785
Sequential reactive systems include programs and devices that work with two streams of
data and convert input streams of data into output streams. Such information processing systems
include controllers, device drivers, computer interpreters. The results of operation of such computing
systems are infinite sequences of pairs of events of the request-response type, and, therefore, finite
transducers are most often ...
Added: January 17, 2022
Zakharov V., Automatic Control and Computer Sciences (AC&CS), Switzerland 2021 Vol. 55 No. 7 P. 670–701
Finite transducers, two-tape automata, and biautomata are related computational models
descended from the concept of finite-state automaton. In these models an automaton controls two
heads that read or write symbols on the tapes in the one-way mode. The computations of these three
types of automata show many common features, and it is surprising that the methods for analyzing ...
Added: January 17, 2022
Gnatenko A., Zakharov V., Моделирование и анализ информационных систем 2021 Т. 28 № 4 С. 356–371
Sequential reactive systems are computer programs or hardware devices which process the flows of input data or control signals and output the streams of instructions or responses. When designing such systems one needs formal specification languages capable of expressing the relationships between the input and output flows. Previously, we introduced a family of such specification ...
Added: January 17, 2022
Gnatenko A., Zakharov V., Моделирование и анализ информационных систем 2020 Т. 27 № 4 С. 428–441
Sequential reactive systems include programs and devices that work with two streams of data and convert input streams ofdata into output streams. Such information processing systems include controllers, device drivers, computer interpreters.e result of the operation of such computing systems are innite sequences of pairs of events of the request–responsetype, and, therefore, nite transducers are ...
Added: January 31, 2021
Gnatenko A., Zakharov V., Системная информатика 2020 Vol. 17 P. 21–32
Sequential reactive systems such as controllers, device drivers, computer interpreters operate with two data streams and transform input streams of data (control signals, instructions) into output streams of control signals (instructions, data). Finite state transducers are widely used as an adequate formal model for information processing systems of this kind. Since runs of transducers develop ...
Added: November 9, 2020
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., Жайлауова Ш. Р., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 272–274.
В данной статье мы продолжаем поиск и исследование новых классов недетерминированных автоматов-преобразователей с разрешимой проблемой эквивалентности. Цель исследования~--- провести как можно более точную и подробную демаркацию границы между разрешимыми и неразрешимыми случаями проблемы эквивалентности для рассматриваемой модели вычислений. Мы рассматриваем один класс недетерминированных автоматов, работающих над выходным алфавитом из одной буквы. Характерная особенность рассматриваемых автоматов-преобразователей ...
Added: October 17, 2019
Gnatenko A., Zakharov V., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 263–266.
Описаны синтаксис и семантика нового расширения Reg-CTL* темпоральной логики деревьев вычислений CTL*, предназначенного для спецификации и верификации вычислений последовательных реагирующих систем. Поеказано, что задача верификации моделей автоматов-преобразователей относительно выполнимости формул логики CTL* является PSPACE-полной. ...
Added: October 17, 2019
Gnatenko A., Zakharov V., Proceedings of the Institute for System Programming of the RAS 2018 Vol. 30 No. 3 P. 303–324
The syntax and semantics of the new temporal logic LP-CTL * designed for the formal specification of the behavior of sequential responsive programs, modeled by automata-transducers (transducers) over semigroups, are developed. An algorithm is developed for verifying the feasibility of the formulas of the proposed temporal logic on models represented by finite transducers working on ...
Added: June 14, 2018
Гнатенко А. Р., Zakharov V., В кн.: Дискретные модели в теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды.: МГУ, МАКС Пресс, 2018. С. 131–133.
The expressive power of a new variant of temporal logic LP-CTL * is studied. In this logic, two classes of LP-1-LTL and LP-n-LTL formulas were distinguished and it was shown that the LP-1-LTL fragment more expressive than the known temporal logic of linear time LTL, and the LP-n-LTL fragment has the same expressive possibilities as ...
Added: June 14, 2018
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
Подымов В. В., Молчанов А. Э., В кн.: Материалы XVIII международной конференции "Проблемы теоретической кибернетики" (Пенза, 19-23 июня 2017 г.).: М.: МАКС Пресс, 2017. С. 174–176.
Проблема эквивалентности программ формулируется так: выяснить, имеют ли две программы схожие (эквивалентные) поведения. Известен алгоритм полиномиального сведения проблемы эквивалентности в перегородчатых моделях программ с процедурами к двум проблемам в моделях программ без процедур с той же семантикой программных операторов: эквивалентности и совместного останова. Проблема совместного останова формулируется так: выяснить, существует ли общий контекст работы программ, ...
Added: October 22, 2017
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., Kozlova D., , in: Proceedings of the 25th International Workshop on Concurrency, Specification and Programming, Rostock, Germany, September 28-30, 2016.Vol. 1698.: Humboldt-Universität zu Berlin, 2016. P. 233–244.
By sequential reactive system we mean a program which operates in the interaction with the environment permanently receiving data (requests) from it. At receiving a piece of data a program performs a sequence of actions (response) and displays the current result. Such programs usually arise at implementation of computer drivers, online algorithms, control procedures. Basic ...
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., Козлова Д. Г., В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.).: М.: Изд-во механико-математического факультета МГУ, 2016. С. 204–206.
Характерная особенность моделей Крипке и большинства темпоральных логик (PLTL, CTL, PDL, mu-исчисление и др.), используемых в качестве формальных языков спецификации, состоит в том, что элементарные свойства вычислений зависят только от состояний модели, но не от вычислений, которыми достигаются состояния. Однако для стороннего наблюдателя поведение реагирующей системы проявляется в соответствии между последовательностями стимулов (сигналов), которыми внешняя ...
Added: October 13, 2016