Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
Построение каскадной параллельной композиции временных автоматов с использованием BALM-II
Get PDFIn this paper, we consider the problem of deriving a cascade parallel composition of timed finite state machines (TFSMs). In order to build such a composition we can derive the corresponding binary parallel compositions step-by-step. It is known that if each component of a binary parallel composition is TFSM with output delays that are natural numbers or zero, the result of the composition can be TFSM with output delays that are sets of linear functions. So, the problem of deriving a cascade composition of TFSMs with constant output delays is reduced to the problem of deriving several binary parallel compositions of TFSMs with output delays that are sets of constants or linear functions. In this work, we refine the definition of TFSM and pay special attention to the description of an output delay function. As a tool for deriving the composition we consider balm-ii, and in consequence we study the ways of constructing the corresponding automaton for TFSM with output delays as a set of linear functions. We suggest a new procedure for constructing such an automaton, and unlike the known procedure our procedure does not require further determinization of the derived automaton. Moreover, we describe step by step how to build the composition of the derived automaton by using balm-ii, and discuss a procedure of reverse transformation from the global automaton to TFSM in case when the components are TFSMs with output delays that are sets of linear functions. We use an application example in order to illustrate derivation of the cascade parallel composition of TFSMs.В данной работе мы рассмотрели задачу построения каскадной параллельной композиции временных автоматов. Построение такой композиции можно свести к поэтапному построению бинарной параллельной композиции. Известно, что если каждая из компонент бинарной параллельной композиции есть временной автомат с константными задержками выходов, то результатом композиции может быть временной автомат, множество задержек выходных символов которого бесконечно и задано при помощи конечного множества линейных функций. Поэтому задача построения каскадной композиции временных автоматов с константными задержками выходов сводится к построению ряда бинарных параллельных композиций временных автоматов, задержки выходов которых заданы либо в виде констант, либо в виде множества линейных функций. В данной работе мы уточняем определение временного автомата, обращая особое внимание на описание задержки выходного символа. В качестве инструмента для построения композиции мы используем balm-ii, и поэтому рассматриваем переход от временного автомата с задержками выходов в виде множества линейных функций к соответствующему полуавтомату. Мы предлагаем свою процедуру построения полуавтомата, которая, в отличие от известной процедуры, не требует последующей детерминизации полученного полуавтомата. Кроме того, мы пошагово описываем, каким образом построить композицию соответствующих полуавтоматов при помощи balm-ii, а также обсуждаем процедуру обратного преобразования от полуавтомата композиции к временному автомату, отмечая некоторые нюансы, связанные с композицией временных автоматов с задержками выходов в виде множества линейных функций. В работе приведён пример, иллюстрирующий построение каскадной параллельной композиции временных автоматов
Существование и устойчивость периодических решений уравнения реакция-диффузия в двумерном случае
No full textParabolic singularly perturbed problems have been actively studied in recent years in connection with a large number of practical applications: chemical kinetics, synergetics, astrophysics, biology, and so on. In this work a singularly perturbed periodic problem for a parabolic reaction-diffusion equation is studied in the two-dimensional case. The case when there is an internal transition layer under unbalanced nonlinearity is considered. The internal layer is localised near the so called transitional curve. An asymptotic expansion of the solution is constructed and an asymptotics for the transitional curve is determined. The asymptotical expansion consists of a regular part, an interior layer part and a boundary part. In this work we focus on the interior layer part. In order to describe it in the neighborhood of the transition curve the local coordinate system is introduced and the stretched variables are used. To substantiate the asymptotics thus constructed, the asymptotic method of differential inequalities is used. The upper and lower solutions are constructed by sufficiently complicated modification of the asymptotic expansion of the solution. The Lyapunov asymptotical stability of the solution was proved by using the method of contracting barriers. This method is based on the asymptotic comparison principle and uses the upper and lower solutions which are exponentially tending to the solution to the problem. As a result, the solution is locally unique.The article is published in the authors’ wording.Параболические сингулярно возмущенные задачи активно исследуются в последние годы в связи с большим количеством практических применений: химическая кинетика, синергетика, астрофизика, биология и т.д. В этой работе исследуется сингулярно возмущенная периодическая задача для параболического уравнения реакция-диффузия в двумерном случае. Рассматривается случай существования внутреннего переходного слоя при несбалансированной нелинейности. Внутренний слой локализован вблизи так называемой кривой переходного слоя. Cтроится асимптотическое разложение решения и определяется асимптотика для кривой переходного слоя. Асимптотическое разложение состоит из регулярной части, внутреннего слоя и части пограничного слоя. В этой работе мы сфокусируем внимание на части внутреннего переходного слоя. С целью его описания вводится локальная система координат в окрестности кривой перехода и используются растянутые переменные. Чтобы обосновать таким образом построенную асимптотику, используется асимптотический метод дифференциальных неравенств. Верхнее и нижнее решения строятся путем достаточно сложной модификации асимптотического разложения решения. Асимптотическая устойчивость решения по Ляпунову доказывается с помощью метода сужающихся барьеров. Этот метод базируется на принципе дифференциальных неравенств, и в нем используются верхнее и нижнее решения, которые экспоненциально стремятся к решению задачи. Как результат, решение является локально единственным.Статья публикуется в авторской редакции
Полилогарифмы и асимптотика моментов сингулярной функции Лебега
Get PDFRecall the Lebesgue's singular function. We define a Lebesgue's singular function as the unique continuous solution of the functional equationwhere p,q>0, , .The moments of Lebesque' singular function are defined asThe main result of this paper iswhereThe proof is based on analytic techniques such as the poissonization and the Mellin transform.Напомним, что сингулярная функция Лебега определяется как единственное решение уравнениягде p,q>0, q=1-p, p\ne q.Моментами функции будем называть величиныОсновной результат настоящей работыгде функция является периодической от с периодом 1 и задается какДоказательство основано на применении пуассонизации и преобразования Меллина
Реконфигурирование компонентно-ориентированных систем на базе графовых грамматик
Get PDFDynamic reconfigurations can modify the architecture of component-based systems without incurring any system downtime. In this context, the main contribution of the present article is the establishment of correctness results proving component-based systems reconfigurations using graph grammars. New guarded reconfigurations allow us to build reconfigurations based on primitive reconfiguration operations using sequences of reconfigurations and the alternative and the repetitive constructs, while preserving configuration consistency. A practical contribution consists of the implementation of a component-based model using the GROOVE graph transformation tool. Then, after enriching the model with interpreted configurations and reconfigurations in a consistency compatible manner, a simulation relation is exploited to validate component systems’ implementations. This sound implementation is illustrated on a cloud-based multitier application hosting environment managed as a component-based system.Динамические реконфигурирования могут изменять архитектуру компонентно-ориентированных систем, не подвергаясь никакому системному простою. В этом контексте основной вклад данной статьи – доказательство результатов корректности реконфигурирования систем, используя графовые грамматики. В этой статье предложены новые охраняемые реконфигурирования на базе логики Хоара, которые построены на основе примитивных операций по реконфигурированию и включают последовательности реконфигурирований, альтернативные и повторяющиеся конструкции, сохраняя при этом непротиворечивость конфигураций. Практический вклад состоит в описании имплементации компонентно-ориентированной модели, используя программный инструмент GROOVE для преобразования графов. После обогащения модели интерпретированными конфигурациями и реконфигурированиями, совместимого с непротиворечивостью, отношение симуляции используется для доказательства корректности имплементации, выполненной под GROOVE. Эта имплементация иллюстрирована на примере многоуровневого облачно-ориентированного приложения
Аналитико-численный подход для решения сигулярно возмущенных параболиче- ских уравнений с использованием динамически адаптированных сеток
No full textThe main objective of the paper is to present a new analytic-numerical approach to singularly perturbed reaction-diffusion-advection models with solutions containing moving interior layers (fronts). We describe some methods to generate the dynamic adapted meshes for an efficient numerical solution of such problems. It is based on a priori information about the moving front properties provided by the asymptotic analysis. In particular, for the mesh construction we take into account a priori asymptotic evaluation of the location and speed of the moving front, its width and structure. Our algorithms significantly reduce the CPU time and enhance the stability of the numerical process compared with classical approaches.The article is published in the authors’ wording.Основной целью данной работы является представление нового аналитико-численного подхода к исследованию сингулярно возмущенных моделей типа реакция-диффузия-адвекция, решения которых содержат движущиеся внутренние переходные слои (фронты). В работе описаны некоторые методы построения динамически адаптированных сеток для эффективного численного решения задач указанного типа. Эти методы основаны на использовании априорной информации о свойствах движущегося фронта, полученной в результате асимптотического анализа. В частности, при построении сетки учитываются априорные асимптотические оценки локализации и скорости фронта, его ширина и структура. Предложенные алгоритмы позволяют существенно снизить затраты вычислительных ресурсов и повысить стабильность численного счета по сравнению с известными классическими подходами. Статья публикуется в авторской редакции
Применение метода дифференциальных неравенств для обоснования решения системы параболических уравнений в виде движущегося фронта
Get PDFInvestigations of initial boundary value problems for parabolic equations solutions are an important component of mathematical modeling. In this regard of special interest for mathematical modeling are the boundary value problem solutions that undergo sharp changes in any area of space. Such areas are called internal transitional layers. In case when the position of a transitional layer changes over time, the solution of a parabolic equation behaves as a moving front. For the purpose of proving the existence of such initial boundary value problem solutions, the method of differential inequalities is very effective. According to this method the so-called upper and lower solutions are to be constructed for the initial boundary value problem. The essence of an asymptotic method of differential inequalities is in receiving the upper and lower solutions as modifications of asymptotic submissions of the solutions of boundary value problems. The existence of the upper and lower solutions is a sufficient condition of existence of a solution of a boundary value problem. While proving the differential inequalities the so-called ”quasimonotony” condition is essential. In the present work it is considered how to construct the upper and lower solutions for the system of the parabolic equations under various conditions of quasimonotony.Исследование решений начально-краевых задач для параболических уравнений является важной составляющей математического моделирования. Особый интерес для математического моделирования представляют краевые задачи, решения которых претерпевают резкое изменение в какой-либо области пространства. Такие области называются внутренними переходными слоями. В том случае, если положение переходного слоя изменяется со временем, решение параболической задачи имеет вид движущегося фронта. При доказательстве существования у начально-краевых задач решений такого вида весьма эффективным оказывается метод дифференциальных неравенств, согласно которому для данной краевой задачи строятся так называемые верхнее и нижнее решения. Суть асимптотического метода дифференциальных неравенств заключается в том, чтобы получать верхнее и нижнее решения как модификации асимптотических представлений решений краевых задач. Существование верхнего и нижнего решений является достаточным условием существования решения краевой задачи. В ходе проверки выполнения дифференциальных неравенств существенным оказывается так называемое условие квазимонотонностии. В настоящей работе рассмотрено, каким образом можно построить верхнее и нижнее решения для системы параболических уравнений при различных условиях квазимонотонности
О минимизации конечных автоматов-преобразователей над полугруппами
Get PDFFinite 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 many cases verification of such programs can be reduced to minimization and equivalence checking problems for finite state transducers. Minimization of a transducer over a semigroup is performed in three stages. At first the greatest common left-divisors are computed for all states of the transducer, next the transducer is brought to a reduced form by pulling all such divisors ”upstream”, and finally a minimization algorithm for finite state automata is applied to the reduced transducer.Автоматы-преобразователи над полугруппами можно использовать в качестве модели последовательных реагирующих программ, работающих в постоянном взаимодействии со своим окружением. Получив очередную порцию данных, реагирующая программа выполняет некоторую последовательность действий и предъявляет результат. Такие программы возникают при проектировании компьютерных драйверов, алгоритмов, работающих в оперативном режиме, сетевых коммутаторов. Во многих случаях проблема верификации программ такого рода может быть сведена к задачам минимизации и проверки эквивалентности конечных автоматовпреобразователей. Минимизация преобразователей над полугруппами проводится в три этапа. Вначале для всех состояний преобразователя вычисляются наибольшие общие левые делители. Затем все вычисленные делители ”поднимаются вверх” по переходам преобразователя, и в результате образуется приведенный преобразователь. Наконец, для минимизации приведенных преобразователей применяются методы минимизации классических конечных автоматов-распознавателей
Методические аспекты выделения семантических отношений для автоматической генерации специализированных тезаурусов и их оценки
Get PDFThe paper is devoted to analysis of methods for automatic generation of a specialized thesaurus. The main algorithm of generation consists of three stages: selection and preprocessing of a text corpus, recognition of thesaurus terms, and extraction of relations among terms. Our work is focused on exploring methods for semantic relation extraction. We developed a test bench that allow to test well-known algorithms for extraction of synonyms and hypernyms. These algorithms are based on different relation extraction techniques: lexico-syntactic patterns, morpho-syntactic rules, measurement of term information quantity, general-purpose thesaurus WordNet, and Levenstein distance. For analysis of the result thesaurus we proposed a complex assessment that includes the following metrics: precision of extracted terms, precision and recall of hierarchical and synonym relations, and characteristics of the thesaurus graph (the number of extracted terms and semantic relationships of different types, the number of connected components, and the number of vertices in the largest component). The proposed set of metrics allows to evaluate the quality of the thesaurus as a whole, reveal some drawbacks of standard relation extraction methods, and create more efficient hybrid methods that can generate thesauri with better characteristics than thesauri generated by using separate methods. In order to illustrate this fact, one of such hybrid methods is considered in the paper. It combines the best standard algorithms for hypernym and synonym extraction and generates a specialized medical thesaurus. The hybrid method leaves the thesaurus quality on the same level and finds more relations between terms than well-known algorithms.Работа посвящена анализу методов автоматической генерации специализированного тезауруса. Основной алгоритм генерации состоит из трех шагов: отбор и предварительная обработка корпуса текстов, формирование множества терминов для включения в тезаурус и выделение связей между терминами тезауруса. Данное исследование сфокусировано на изучении методов выделения семантических связей, для чего авторами был разработан программный стенд, который позволяет протестировать распространенные алгоритмы выделения гиперонимов и синонимов, использующие в своей работе лексико-синтаксические шаблоны, морфо-синтаксические правила, количество информации терминов, тезаурус общего назначения WordNet и расстояние Левенштейна. Для анализа результирующего тезауруса, созданного на стенде, авторами была разработана комплексная оценка, содержащая следующие характеристики качества: точность выделения терминов, точность и полнота выделения синонимических и гиперонимических связей, а также метрики графа тезауруса (количество выделенных терминов, количество семантических связей различных типов, число компонент связности и число вершин в наибольшей компоненте). Предлагаемый набор метрик позволяет оценить качество тезауруса в целом, выявить отдельные недостатки стандартных методов выделения связей и построить более эффективные гибридные методы, генерирующие тезаурус с лучшими характеристиками по сравнению с тезаурусами, генерируемыми при использовании отдельных методов. Для иллюстрации данного факта в статье рассмотрен один из таких гибридных методов. Он комбинирует лучшие стандартные алгоритмы построения гиперонимических и синонимических связей и строит специализированный тезаурус в области медицины с тем же уровнем качества, что и другие методы, но с большим количеством связей между терминами
Вероятностный анализ систем организации турниров
Get PDFIn this paper a criteria of comparison of different tournament organization systems in sporting contests is offered; the criteria uses the probability of winning the fairly strongest player. Two probabilistic models have been analyzed. Calculating formulas for estimating the probability and probability density of score points gained by one or another player were obtained. Some really used tournament systems were analyzed with the stochastic modeling method. The available results also provide an order of objects presenting to experts while organizating the examination by paired comparison. An analytical estimation of probability of tournament results (or pared comparison) was obtained. In many cases it allows to avoid a time-consuming procedure of sorting out possible variants. В работе предложен критерий для сравнения структуры организации турниров в спортивных соревнованиях по вероятности победы в турнире объективно сильнейшего участника. Проанализированы две вероятностные модели результатов парной игры. Получены расчетные формулы для оценки такой вероятности и для плотности распределения вероятности числа очков, набранных в турнире тем или иным игроком. С использованием метода стохастического моделирования проанализированы некоторые реально использующиеся структуры турниров. Полученные результаты определяют и порядок предъявления экспертам объектов при организации экспертизы посредством серии парных сравнений. Получена аналитическая оценка вероятности результатов турнира или серии парных сравнений, позволяющая во многих случаях избежать трудоемкую процедуру перебора допустимых вариантов.
Эквивалентность обычной и модифицированной сети обобщенных нейронных элементов
Get PDFThe article is devoted to the analysis of neural networks consisting of generalized neural elements. The first part of the article proposes a new neural network model — a modified network of generalized neural elements (MGNE-network). This network developes the model of generalized neural element, whose formal description contains some flaws. In the model of the MGNE-network these drawbacks are overcome. A neural network is introduced all at once, without preliminary description of the model of a single neural element and method of such elements interaction. The description of neural network mathematical model is simplified and makes it relatively easy to construct on its basis a simulation model to conduct numerical experiments. The model of the MGNE-network is universal, uniting properties of networks consisting of neurons-oscillators and neurons-detectors. In the second part of the article we prove the equivalence of the dynamics of the two considered neural networks: the network, consisting of classical generalized neural elements, and MGNE-network. We introduce the definition of equivalence in the functioning of the generalized neural element and the MGNE-network consisting of a single element. Then we introduce the definition of the equivalence of the dynamics of the two neural networks in general. It is determined the correlation of different parameters of the two considered neural network models. We discuss the issue of matching the initial conditions of the two considered neural network models. We prove the theorem about the equivalence of the dynamics of the two considered neural networks. This theorem allows us to apply all previously obtained results for the networks, consisting of classical generalized neural elements, to the MGNE-network.Статья посвящена анализу сетей, состоящих из обобщенных нейронных элементов. В первой части статьи предлагается новая нейросетевая модель — модифицированная сеть обобщенных нейронных элементов (МОНЭ-сеть). Данная сеть является развитием модели отдельного нейрона — обобщенного нейронного элемента, формальное описание которого содержит некоторые недостатки. В модели МОНЭ-сети эти недостатки преодолеваются. Нейронная сеть вводится сразу целиком, без предварительного описания модели одного нейронного элемента и способа взаимодействия таких элементов между собой. Описание нейросетевой математической модели упрощено и позволяет сравнительно легко построить на ее основе имитационную модель для проведения численных экспериментов. Модель МОНЭ-сети носит универсальный характер, объединяя свойства сетей, состоящих из нейронов-автогенераторов и нейронов-детекторов. Во второй части статьи доказывается эквивалентность функционирования двух рассмотренных нейронных сетей: сети, состоящей из классических обобщенных нейронных элементов, и МОНЭ-сети. Вводится определение эквивалентности функционирования обобщенного нейронного элемента и МОНЭ-сети, состоящей из одного элемента. Затем вводится определение эквивалентности функционирования двух нейронных сетей в целом. Устанавливается соответствие различных параметров двух рассматриваемых нейросетевых моделей. Обсуждается вопрос согласования начальных условий двух рассматриваемых нейросетевых моделей. Доказывается теорема об эквивалентном функционировании этих моделей. Данная теорема позволяет перенести все полученные ранее результаты для сетей обобщенных нейронных элементов на класс модифицированных сетей