Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
К синтезу синхронизирующих и установочных последовательностей для входо-выходных полуавтоматов
Get PDFIn this paper, we study the problem of existence check and derivation of synchronizing and homing sequences for finite input/output automata. Corresponding sequences can be effectively used for the current state identification of a system under test / verification, after the input sequence is applied. In the model considered in the paper, the alphabet of actions is divided into disjoint sets of inputs and outputs; however, no sets of possible initial or final states are defined. We introduce the notions of homing and synchronizing sequences for a specific class of such machines for which at each state the transitions only under inputs or under outputs are defined, and the machine transition diagram does not contain cycles labeled by outputs, i.e. the language of the machine does not contain traces with infinite postfix of outputs. For such a class of input/output automata, we establish necessary and sufficient conditions for the existence of synchronizing and homing sequences and discuss the length of such sequences. We also define some subclasses of automata for which the worst-case upper bounds (normally, exponential) are not reachable. В работе рассматриваются задачи проверки существования и синтеза синхронизирующих и установочных последовательностей для конечных входо-выходных полуавтоматов. Соответствующие последовательности могут быть использованы при идентификации состояния проверяемой системы после подачи подходящей входной последовательности. В модели, исследуемой в работе, действия разделены на входные и выходные, однако отсутствуют выделенные явно семейства начальных и финальных состояний. В статье определяются понятия синхронизирующей и установочной последовательностей и предлагаются методы их синтеза для специального класса входо-выходных полуавтоматов, у которых в каждом состоянии определены переходы или только по входным, или только по выходным действиям; кроме того, в соответствующем графе переходов отсутствуют циклы по выходным символам. Для описанного класса входо-выходных полуавтоматов устанавливаются необходимые и достаточные условия существования синхронизирующих и установочных последовательностей и оценивается длина таких последовательностей. Выделяются подклассы полуавтоматов, для которых худшие (в основном экспоненциальные) оценки сложности не являются достижимыми.
Задачи оптимизации с усреднением по части переменных и условия их оптимальности в форме принципа максимума
Get PDFThe problems of nonlinear programming, criteria and limitations depend on the variables averaged. It is shown that if these problems have solutions, the Lagrangian reaches the maximum for the variables, which are averaged. The functions defining the problem can not be differentiable and continuous on these variables, the set of possible values may contain isolated points. In variational problems there can be no solution in the class of piecewise continuous functions of the variables, but there can be a generalized solution in which these variables change in the sliding mode, and the optimality criterion tends to its upper edge. If in such problems the solution in the class of piecewise - continuous functions exists, the conditions of optimality of this solution are in the form of the Hamiltonian function of the maximum principle. The relationship between the average over time and across multiple variables is considered.Рассмотрены задачи нелинейного программирования, критерий и ограничения которых усредненно зависят от части переменных. Показано, что если в этих задачах существует решение, то функция Лагранжа на нем достигает максимума по тем переменным, по которым происходит усреднение. При этом функции, определяющие задачу, могут быть не дифференцируемыми, а непрерывными по этим переменным, множество их допустимых значений может содержать и изолированные точки. В вариационных задачах может отсутствовать решение в классе кусочно-непрерывных функций по части переменных, но существовать обобщенное решение, на котором эти переменные изменяются в скользящем режиме, а критерий оптимальности стремится к своей верхней грани. Если же в таких задачах решение в классе кусочно – непрерывных функций существует, то условия оптимальности этого решения имеют форму принципа максимума функции Гамильтона. Рассмотрена связь усреднения по времени и по множеству значений переменных
О локально выпуклых кривых
Get PDFWe introduce the definition of locally convex curves and establish some properties of such curves. In the section 1, we consider the curve allowing the parametric representation , where , are continuously differentiable on functions such that |u'(t)| + |v'(t)| > 0 \,\forall t \in [a,b]. A continuous on function is called it the angle function of the curve if the following conditions hold: . The curve is called it locally convex if its angle function is strictly monotonous on . For a closed curve the number is whole. This number is equal to the number of rotations that the speed vector performs around the origin. The main result of the first section is the statement: if the curve is locally convex, then for any straight line the number of intersections of and is finite and the estimate holds. We discuss versions of this estimate for closed and non-closed curves. In the sections 2 and 3, we consider curves arising in the investigation of a linear homogeneous differential equation of the form with locally summable coefficients .We demonstrate how conditions of disconjugacy of the differential operator that were established in works of G.A. Bessmertnyh and A.Yu.Levin, can be applied.Вводится понятие и устанавливаются свойства локально выпуклых кривых. В первом пункте рассматривается кривая , допускающая параметрическое представление где -- непрерывно дифференцируемые на отрезке функции, причём |u'(t)| + |v'(t)| > 0 \,\forall t \in [a,b]. Угловая функция кривой -- это непрерывная на отрезке функция, удовлетворяющая соотношениямКривая называется локально выпуклой, если её угловая функция строго монотонна на отрезке . Для замкнутой кривой число целое; оно равно числу оборотов, которое вектор скорости совершает вокруг начала координат. Основной результат пункта: если кривая локально выпукла и замкнута, то для любой прямой число точек пересечения с конечно и верна оценка . Обсуждаются варианты этой оценки для незамкнутых и негладких кривых. В пунктах 2, 3 основное внимание уделяется кривым, возникающим при исследовании линейного однородного дифференциального уравнения вида с локально суммируемыми коэффициентами . Существенную роль начинают играть признаки неосцилляции дифференциального оператора , установленные в работах Г.А. Бессмертных и А.Ю. Левина
Семейство негрубых циклов в системе двух связанных генераторов с запаздыванием
Get PDFIn this paper, we consider the nonlocal dynamics of the model of two coupled oscillators with delayed feedback. This model has the form of a system of two differential equations with delay. The feedback function is non-linear, finite and smooth. The main assumption in the problem is that the coupling between the generators is sufficiently small. With the help of asymptotic methods we investigate the existence of relaxation periodic solutions of a given system. For this purpose, a special set is constructed in the phase space of the original system. Then we build an asymptotics of the solutions of the given system with initial conditions from this set. Using this asymptotics, a special mapping is constructed. Dynamics of this map describes the dynamics of the original problem in general. It is proved that all solutions of this mapping are non-rough cycles of period two. As a result, we formulate conditions for the coupling parameter such that the initial system has a two-parameter family of nonrough inhomogeneous relaxation periodic asymptotic (with respect to the residual) solutions. В данной работе рассматривается нелокальная динамика модели двух связанных генераторов с запаздывающей обратной связью. Эта модель имеет вид системы двух дифференциальных уравнений с запаздыванием. Функция обратной связи является нелинейной, финитной и гладкой. Главным предположением в задаче является то, что связь между генераторами достаточно малая. Асимптотическими методами исследуется существование релаксационных периодических решений данной системы. Для этого в фазовом пространстве исходной системы выделяется специальное множество. Затем находится асимптотика решений данной системы с начальными условиями из этого множества. С помощью этой асимптотики строится специальное отображение, описывающее в главном динамику исходной задачи. Доказывается, что все решения данного отображения являются негрубыми циклами периода два. В результате удается сформулировать условия на параметр связи, при выполнении которых исходная система имеет двупараметрическое семейство негрубых неоднородных релаксационных периодических асимптотических по невязке решений.
Релаксационные циклы в модели синаптически взаимодействующих осцилляторов
Get PDFIn this paper the mathematical model of a neural network with a ring synaptic interaction elements is considered. The model is a system of scalar nonlinear differential-difference equations, the right parts of which depend on a large parameter. The unknown functions included in the system characterize the membrane potentials of the neurons. The search of relaxation cycles within the system of equations is interested. To this end solutions of the task are finded in the form of discrete traveling waves. It allows to research a scalar nonlinear differential-difference equations with two delays instead of system. Further, a limit a object that represents a relay equation with two delays is defined by large parameter tends to infinity. There are six cases of restrictions on the parameters. In every case exist alone periodic solution of relay equation started from initial function from suitable function class. It is structurally proved by using the step method. Next, the existence of a relaxation periodic solutions of a singularly perturbed equation with two delays is proved by using Poincare operator and Schauder principle. The asymptotics of this solution is constructed, and then it is proved that the solution is close to decision of the relay equation. Because of the exponential estimate Frechet derivative of the Poincare operator implies the uniqueness and stability of solutions of differential-difference equation with two delays.В настоящей работе рассматривается математическая модель кольцевой нейронной сети с синаптическим взаимодействием элементов. Модель представляет собой систему скалярных нелинейных дифференциально-разностных уравнений, правые части которых зависят от большого параметра. Неизвестные функции, входящие в систему, характеризуют мембранные потенциалы нейронов. Представляет интерес поиск в рамках данной системы уравнений релаксационных циклов, а именно периодических решений с асимптотически большим всплеском на периоде. С этой целью ставится задача отыскания решений в виде дискретных бегущих волн, что позволяет перейти от исследования системы к изучению одного скалярного нелинейного дифференциально-разностного уравнения с двумя запаздываниями. Далее, при стремлении большого параметра к бесконечности определяется предельный объект, представляющий собой релейное уравнение с двумя запаздываниями. Конструктивно, с использованием метода шагов, доказывается, что можно выделить шесть случаев ограничений на параметры, в каждом из которых решение релейного уравнения с начальной функцией из подходящего класса совпадает с одной и той же периодической функцией с требуемыми свойствами. Затем определяется оператор последований Пуанкаре и с использованием принципа Шаудера доказывается существование релаксационного периодического решения сингулярно возмущенного уравнения с двумя запаздываниями. Для этого строится асимптотика этого решения, а затем доказывается его близость к решению релейного уравнения. Из экспоненциальной оценки производной Фреше оператора Пуанкаре следует единственность в построенном классе функций решения дифференциально-разностного уравнения с двумя запаздываниями, а также обосновывается его экспоненциальная орбитальная устойчивость
Существование несмещенной оценки энтропии для специальной меры Бернулли
Get PDFLet be a space of right-sided infinite sequences drawn from a finite alphabet , , \label{rho} \rho(\boldsymbol{x},\boldsymbol{y}) = \sum_{k=1}^{\infty}|x_{k} - y_{k}|2^{-k} a metric on , and is a probability measure on . Let be independent identically distributed points on . We study the estimator of the reciprocal of the entropy that are defined as \label{etan} \eta_n^{(k)}(\gamma) = k \left(r_{n}^{(k)}(\gamma) - r_{n}^{(k+1)}(\gamma)\right), where \label{def_r} r_n^{(k)}(\gamma) = \frac{1}{n+1}\sum_{j=0}^{n} \gamma\left(\min_{i:i \neq j} {^{(k)}} \rho(\boldsymbol{\xi_{i}}, \boldsymbol{\xi_{j}})\right), , if . The number and the function are auxiliary parameters.The main result of this paper isTheorem. Let be the Bernoulli measure with probabilities p_0,p_1>0, , . There exists a function such that Пусть - пространство правосторонних бесконечных последовательностей символов из алфавита , , \label{rho} \rho(\boldsymbol{x},\boldsymbol{y}) = \sum_{k=1}^{\infty}|x_{k} - y_{k}|2^{-k} - метрика на и - вероятностная мера на . Пусть - независимые случайные точки на , распределенные по мере . Будем изучать оценку величины обратной к энтропии , которая определяется следующим образом: \label{etan} \eta_n^{(k)}(\gamma) = k \left(r_{n}^{(k)}(\gamma) - r_{n}^{(k+1)}(\gamma)\right), где \label{def_r} r_n^{(k)}(\gamma) = \frac{1}{n+1}\sum_{j=0}^{n} \gamma\left(\min_{i:i \neq j} {^{(k)}} \rho(\boldsymbol{\xi_{i}}, \boldsymbol{\xi_{j}})\right), , if . Число и функция - вспомогательные параметры. Основной результат работы: Теорема. Пусть - мера Бернулли с вероятностями p_0,p_1>0, , , тогда существует функция такая, что \[E\eta_n^{(k)}(\gamma) = \frac1h.\
Варианты метода коллокации и наименьших невязок для решения задач математической физики в выпуклых четырехугольных областях
Get PDFThe new versions of the collocations and least residuals (CLR) method of high-order accuracy are proposed and implemented for the numerical solution of the boundary value problems for PDE in the convex quadrangular domains. Their implementation and numerical experiments are performed by the examples of solving the biharmonic and Poisson equations. The solution of the biharmonic equation is used for simulation of the stress-strain state of an isotropic plate under the action of the transverse load. Differential problems are projected into the space of fourth-degree polynomials by the CLR method. The boundary conditions for the approximate solution are put down exactly on the boundary of the computational domain. The versions of the CLR method are implemented on the grids, which are constructed by two different ways. In the first version, a “quasiregular” grid is constructed in the domain, the extreme lines of this grid coincide with the boundaries of the domain. In the second version, the domain is initially covered by a regular grid with rectangular cells. Herewith, the collocation and matching points that are situated outside the domain are used for approximation of the differential equations in the boundary cells that had been crossed by the boundary. In addition the “small” irregular triangular cells that had been cut off by the domain boundary from rectangular cells of the initial regular grid are joined to adjacent quadrangular cells. This technique allowed to essentially reduce the conditionality of the system of linear algebraic equations of the approximate problem in comparison with the case when small irregular cells together with other cells were used as independent ones for constructing an approximate solution of the problem. It is shown that the approximate solution of problems converges with high order and matches with high accuracy with the analytical solution of the test problems in the case of the known solution in numerical experiments on the convergence of the solution of various problems on a sequence of grids. Предложены и реализованы новые варианты метода коллокации и наименьших невязок (КНН) для численного решения краевых задач для уравнений с частными производными в выпуклых четырехугольных областях. Их реализация и численные эксперименты выполнены на примерах решения уравнений Пуассона и бигармонического. Решение второго уравнения использовано для моделирования напряженно–деформированного состояния изотропной пластины, находящейся под действием поперечной нагрузки. Дифференциальные задачи методом КНН проектировались в пространство полиномов четвертой степени. Граничные условия для приближенного решения задач выписывались точно на границе расчетной области. Реализованы варианты метода КНН на сетках, построенных двумя различными способами. В первом варианте в области строится некоторая “квазирегулярная” сетка, крайние линии которой совпадают с границами области. Во втором — область сначала накрывается регулярной сеткой с прямоугольными ячейками. При этом в граничных ячейках, которые пересекла граница, для аппроксимации дифференциальных уравнений использованы “законтурные” (расположенные вне расчетной области) точки коллокации и точки согласования решения задачи. Кроме этого, “малые” нерегулярные треугольные ячейки, отсеченные границей области от прямоугольных ячеек начальной регулярной сетки, присоединялись к соседним четырехугольным ячейкам. Этот прием позволил существенно уменьшить обусловленность системы линейных алгебраических уравнений приближенной задачи по сравнению со случаем, когда малые ячейки наряду с другими ячейками использовались как самостоятельные для построения приближенного решения задачи. В численных экспериментах по сходимости приближенного решения различных задач на последовательности сеток установлено, что оно сходится с повышенным порядком и с высокой точностью совпадает с аналитическим решением задачи в случае, когда оно известно.
О бифуркациях при малых возмущениях в логистическом уравнении с запаздыванием
Get PDFThe article considers bifurcation problems for a logistic equation with delay at small perturbations. The most interesting results are for the case when small perturbations contain a large delay. The main results are special nonlinear equations of evolution in the normal form. Their nonlocal dynamics defines the behaviour of the solutions of the original equation in a small neigbourhood of the balance state or the cycle. It turns out that the order of large delay magnitude is principal. For the simplest case, when this order is congruent with the magnitude inverse to the small parameter appearing in the equation, the normal form is a complex equation with delay. In the case when the order of the delay coefficient is even higher, the normal form is presented by a multiparameter family of special boundary-value problems of degenerate-parabolic type. All these things allow to make a conclusion about the fact that in the considered problems with large delay the multistability is typical.В статье рассматриваются бифуркационные задачи для логистического уравнения с запаздыванием при наличии малых возмущений. Наиболее интересны результаты для случая, когда малые возмущения содержат большое запаздывание. В качестве основных результатов получены специальные нелинейные эволюционные нормальной формы уравнения, нелокальная динамика которых определяет поведение решений исходного уравнения в малой окрестности состояния равновесия или цикла. Как оказывается, принципиальное значение имеет порядок величины большого запаздывания. Для наиболее простого случая, когда этот порядок совпадает с величиной, обратной к фигурирующему в уравнении малому параметру, нормальная форма представляет собой комплексное уравнение с запаздыванием. В том случае, когда порядок коэффициента запаздывания еще выше, в качестве нормальной формы выступает многопараметрическое семейство специальных краевых задач вырожденно-параболического типа. Все это позволяет сделать вывод о том, что в рассматриваемых задачах с большим запаздыванием характерно явление мультистабильности
Построение высокоуровневой модели процесса по журналу событий
No full textProcess mining is a relatively new field of computer science, which deals with process discovery and analysis based on event logs. In this paper we consider the problem of discovering a high-level business process model from a low-level event log, i.e. automatic synthesis of process models based on the information stored in event logs of information systems. Events in a high-level model are abstract events, which can be refined to low-level subprocesses, whose behavior is recorded in event logs. Models synthesis is intensively studied in the frame of process mining research, but only models and event logs of the same granularity are mainly considered in the literature. Here we present an algorithm for discovering high-level acyclic process models from event logs and some specified partition of low-level events into subsets associated with abstract events in a high-level model.Извлечение и анализ процессов (process mining) - это достаточно новая область компьютерных наук, изучающая синтез и анализ процессов на основе журналов событий. В работе рассматривается задача извлечения высокоуровневой модели по низкоуровневому журналу событий, т.е. задача автоматического синтеза модели процесса на основе информации, хранящейся в журналах событий информационной системы. События в высокоуровневой модели это абстрактные события, которые могут быть детализированы в виде низкоуровневых подпроцессов, поведение которых представлено в журналах событий. Синтез моделей интенсивно изучается в рамках исследований по майнингу процессов, но в основном в литературе рассматриваются только логи и модели одного и того же уровня детализации. Здесь мы представляем алгоритм для извлечения высокоуровневых ациклических моделей процессов на основании журналов событий и заранее определенного разбиения низкоуровневых событий на подмножества, ассоциированные с абстрактными событиями в высокоуровневой модели
Семантические средства обеспечения безопасности в программно-конфигурируемых сетях
Get PDFSoftware-defined networking is a promising technology for constructing communication networks where the network management is the software that configures network devices. This contrasts with the traditional point of view where the network behaviour is updated by manual configuration uploading to devices under control. The software controller allows dynamic routing configuration inside the net depending on the quality of service. However, there must be a proof that ensures that every network flow is secure, for example, we can define security policy as follows: confidential nodes can not send data to the public segment of the network. The paper shows how this problem can be solved by using a semantic security model. We propose a method that allows us to construct semantics that captures necessary security properties the network must follow. This involves the specification that states allowed and forbidden network flows. The specification is then modeled as a decision tree that may be reduced. We use the decision tree for semantic construction that captures security requirements. The semantic can be implemented as a module of the controller software so the correctness of the control plane of the network can be ensured on-the-fly. Программно-конфигурируемые сети являются многообещающей технологией построения коммуникационных сетей, в которой управление сетью в отличие от традиционного подхода, основанного на конфигурировании отдельных устройств, представляет собой программу, автоматически задающую конфигурацию сети. Это управляющее программное обеспечение позволяет динамически настраивать маршрутизацию информационных потоков внутри сети в зависимости от требований к качеству обслуживания. Однако при этом возникает задача обеспечения безопасности передачи данных [2,3], например, чтобы потоки от конфиденциальных узлов не могли достигать открытого сегмента сети. В статье показано, как эта задача может быть решена с использованием семантических средств.