Modeling and Analysis of Information Systems

Journal Information
ISSN / EISSN : 1818-1015 / 2313-5417
Current Publisher: P.G. Demidov Yaroslavl State University (10.18255)
Total articles ≅ 503
Current Coverage
DOAJ
Archived in
SHERPA/ROMEO
Filter:

Latest articles in this journal

Vladimir A. Zakharov
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-3-260-303

Abstract:
Конечные преобразователи, двухленточные автоматы и биавтоматы — взаимосвязанные вычислительные модели, ведущие свое происхождение от концепции конечного автомата. В вычислениях этих машин проявляется много общих черт, и удивительно, что методы анализа, разработанные для одной из указанных моделей, не находят подходящего применения в других моделях. Целью данной статьи является разработка единой методики построения быстрых алгоритмов проверки эквивалентности для некоторых классов автоматов (конечных преобразователей, двухленточных автоматов, биавтоматов, магазинных автоматов), которые демонстрируют определенные черты детерминированного или однозначное поведение. Этот новый метод сводит проверку эквивалентности автоматов к проверке разрешимости систем уравнений над полукольцами языков или бинарных отношений. Как оказалось, такую проверку достаточно просто провести методом исключения переменных, используя некоторые комбинаторные и алгебраические свойства регулярных префиксных языков. Основные результаты, полученные в этой статье, таковы.1. При помощи алгебраического метода построен новый алгоритм проверки эквивалентности детерминированных конечных автоматов, имеющий сложность по времени O(n log n).2. Выделен новый класс префиксных конечных трансдьюсеров и показано, что проверка эквивалентности трансдьюсеров из этого класса может быть осуществлена новым методом за время, квадратичное (для префиксных трансдьюсеров реального времени) и кубическое (для префиксных трансдьюсеров с ɛ-переходами) относительно размеров анализируемых автоматов.3. Показано, что проблема эквивалентности для детерминированных двухленточных конечных автоматов сводится к задаче проверки эквивалентности префиксных конечных трансдьюсеров и может быть решена за время, кубическое относительно их размеров.4. Аналогичным образом установлена разрешимость проблемы эквивалентности для детерминированных конечных биавтоматов за время, кубическое относительно их размеров.5. При помощи нового метода построен алгоритм проверки эквивалентности для простых грамматик, соответствующих детерминированным магазинным автоматам с одним состоянием.
Егор Владимирович Кузьмин, Олег Евгеньевич Горбунов, Петр Олегович Плотников, Vadim A. Tyukin, Владимир Анатольевич Башкин
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-3-316-329

Abstract:
Для обеспечения безопасности движения на железнодорожном транспорте регулярно проводится неразрушающий контроль рельсов с применением различных подходов и методов, включая методы вихретоковой дефектоскопии. Актуальной задачей является автоматический анализ больших массивов данных (дефектограмм), которые поступают от соответствующего оборудования. Под анализом понимается процесс определения по дефектограммам наличия дефектных участков наряду с выявлением конструктивных элементов рельсового пути. Данная статья посвящена задаче распознавания образов длинных конструктивных элементов железнодорожных рельсов по дефектограммам многоканальных вихретоковых дефектоскопов. Рассматриваются два класса конструктивных элементов рельсового пути: 1) счётчики осей подвижного состава, 2) пересечения рельсовых путей. Длинные отметки, которые не могут быть отнесены к этим двум классам, условно считаются дефектами и выносятся в отдельный третий класс. Для распознавания образов конструктивных элементов на дефектограммах применяется свёрточная нейронная сеть, реализованная в рамках открытой библиотеки TensorFlow. С этой целью каждая выделенная для анализа область дефектограммы преобразуется в графический образ в градации серого цвета размером 30 на 140 точек.
Сергей Владимирович Зыкин
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-3-356-365

Abstract:
В работе рассматривается обобщение правил вывода зависимостей соединения, которые используются при проектировании схемы базы данных, удовлетворяющей требованиям пятой нормальной формы. В предшествующих работах, посвященных данной проблематике, делаются попытки построить системы аксиом таких зависимостей, основанных на правилах вывода. Однако, если обоснование непротиворечивости (надежности) полученных аксиом не вызывает затруднений, то доказательство полноты в общем случае не получило удовлетворительного решения. Прежде всего, это связано с ограниченностью самих правил вывода. В данной работе акцентировано внимание на двух оригинальных системах аксиом, представленных в работах Sciore и Malvestuto. Для зависимостей включения получена система правил, которая обобщает существующие системы и при этом имеет меньше ограничений. В работе представлено доказательство выводимости известных систем аксиом из представленных правил вывода. Кроме того, приводится доказательство непротиворечивости (надежности) этих правил. Вопрос о полноте формальной системы, основанной на представленных правилах, не нашел положительного решения. В заключение отмечена теоретическая и практическая значимость правил вывода для зависимостей соединения.
Валерий Анатольевич Соколов
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-3-304-315

Abstract:
Рафаэль Робинсон показал, что все примитивно рекурсивные функции, зависящие от одного аргумента, и только они могут быть получены из двух функций s(x) = х +1 и q(x) = x - [√x]²с помощью операций сложения +, суперпозиции ∗ и итерации i. Джулия Робинсон доказала, что из этих же двух функций с помощью операций сложения +, суперпозиции ∗ и операции ¯¹ обращения функций можно получить все общерекурсивные (при определённом условии на операцию обращения) и все частично рекурсивные функции. На основании этих результатов А. И. Мальцев ввёл в рассмотрение алгебру Рафаэля Робинсона всех одноместных примитивно рекурсивных функций и две алгебры Джулии Робинсон: частичную алгебру всех одноместных общерекурсивных функций и алгебру всех одноместных частично рекурсивных функций, и предложил исследовать свойства этих алгебр, в том числе, выяснить, существуют ли в этих алгебрах конечные базисы тождеств. В этой статье мы показываем, что конечного базиса тождеств ни в одной из указанных алгебр не существует.
Ксения Владимировна Лагутина, Alla M. Manakhova
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-3-330-343

Abstract:
Статья посвящена сравнению стилометрических характеристик нескольких уровней, являющихся маркерами стиля прозаического текста, и анализу стилистических изменений русской и британской прозы 19-21 веков. Стилометрические характеристики включают в себя низкоуровневые характеристики, основанные на словах и символах, и высокоуровневые — ритмические. Подобные характеристики моделируют стиль текста и являются индикаторами времени его создания.Вычисление всех характеристик происходит полностью автоматически, что позволяет проводить крупные эксперименты с художественными произведениями большого объёма и ускоряет работу эксперта-лингвиста. Для подсчёта стилометрических характеристик, в том числе основанных на результатах поиска ритмических средств, используется программа ProseRhythmDetector. В результате её работы каждый текст представляется в виде набора одних и тех же характеристик трёх уровней: символов, слов, ритма. Тексты объединяются по десятилетиям, для каждого десятилетия находятся средние значения стилометрических характеристик. Полученные модели десятилетий сравниваются при помощи стандартных метрик близости, результаты сравнения визуализируются в виде тепловых карт и дендрограмм. Эксперименты с двумя корпусами русских и британских текстов показывают, что в течение 19-21 веков появляются как общие тенденции изменения стиля для обоих корпусов, например, уменьшение количества ритмических средств в расчёте на одно предложение, так и собственные для каждого языка, например, динамика изменения длин слов и предложений. Стилометрические характеристики всех уровней выявляют схожесть стиля текстов, опубликованных в одном веке. Также характеристики трёх уровней в комплексе лучше демонстрируют уникальность каждого десятилетия, чем характеристики конкретного уровня. Это исследование показывает значимость стилометрических характеристик как маркеров стиля различных эпох и позволяет выявить тенденции изменения стиля на протяжении нескольких веков.
Сергей Дмитриевич Глызин, Sergey A. Kashchenko, Anna O. Tolbey
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-3-344-355

Abstract:
Логистическое уравнение с запаздыванием или уравнение Хатчинсона представляет собой одно из фундаментальных уравнений популяционной динамики и находит широкое применение в задачах математической экологии. В работе рассматривается семейство отображений, построеннное для этого уравнения на основе центральных разделенных разностей. Такие разностные схемы обычно используются при численном моделировании данной задачи. Представленные отображения сами по себе могут служить моделями динамики популяций, поэтому их изучение представляет значительный интерес. В работе сопоставляются свойства траекторий данных отображений и исходного уравнения с запаздыванием. Показано, что поведение решений отображений, построенных на основе центральных разделенных разностей, не сохраняет, даже при достаточно малой величине шага по времени, основных динамических свойств логистического уравнения с запаздыванием. В частности, у этого отображения при колебательной потере устойчивости ненулевого состояния равновесия не бифурцирует устойчивая инвариантная кривая. Эта кривая соответствует в таких отображениях устойчивому предельному циклу исходного непрерывного уравнения. Тем самым показано, что такая разностная схема не может быть использована для численного моделирования логистического уравнения с запаздыванием.
Mark G. Gonopolskiy, Алевтина Борисовна Глонина
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-2-218-233

Abstract:
The paper presents an algorithm for the worst case response time (WCRT) estimation for multiprocessor systems with fixed-priority preemptive schedulers and the interval uncertainty of tasks execution times. Each task has a unique priority within its processor, a period, an execution time interval [BCET, WCET] and can have data dependency on other tasks. If a decrease in the execution time of the task A can lead to an increase in the response time of the another task B, then task A is called an anomalous task for task B. According to the chosen approach, in order to estimate a task’s WCRT, two steps should be performed. The first one is to construct a set of anomalous tasks using the proposed algorithm for the given task. The paper provides the algorithm and the proof of its correctness. The second one is to find the WCRT estimation using a genetic algorithm. The proposed approach has been implemented software as a program in Python3. A set of experiments have been carried out in order to compare the proposed method in terms of precision and speed with two well-known WCRT estimating methods: the method that does not take into account interval uncertainty (assuming that the execution time of a given task is equal to WCET) and the brute force method. The results of the experiments have shown that, in contrast to the brute force method, the proposed method is applicable to the analysis of the real scale computing systems and also allows to achieve greater precision than the method that does not take into account interval uncertainty.
Владимир Анатольевич Башкин
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-2-234-253

Abstract:
Two resources (submarkings) are called similar if in any marking any one of them can be replaced by another one without affecting the observable behavior of the net (regarding marking bisimulation). It is known that resource similarity is undecidable for general labelled Petri nets. In this paper we study the properties of the resource similarity and resource bisimulation (a subset of complete similarity relation closed under transition firing) in Petri nets with invisible transitions (where some transitions may be labelled with an invisible label (τ) that makes their firings unobservable for an external observer). It is shown that for a proper subclass (p-saturated nets) the resource bisimlation can be effectively checked. For a general class of Petri net with invisible transitions it is possible to construct a sequence of so-called (n, m)-equivalences approximating the largest τ-bisimulation of resources.
Евгений Павлович Кубышкин, Владимир Александрович Куликов
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-2-152-163

Abstract:
Spatially inhomogeneous structures of light waves are used as a mechanism of compacting information in optical and fiber-optic communication systems. In this paper, we consider a mathematical model of an optical radiation generator with a nonlinear delayed feedback loop and a stretching (compression) operator of the spatial coordinates of the light wave in a plane orthogonal to the radiation direction. It is shown that the presence of a delay in the feedback loop can lead to the generation of stable periodic spatially inhomogeneous oscillations. In the space of the main parameters of the generator, the spaces of generation of stable spatially non-uniform oscillations are constructed, the mechanism of their occurrence is studied, and approximate asymptotic formulas are constructed.
Сергей Андреевич Шершаков
Modeling and Analysis of Information Systems, Volume 27; doi:10.18255/1818-1015-2020-2-194-217

Abstract:
Process-Aware Information Systems (PAIS) is a special class of the IS intended for the support the tasks of initialization, end-to-end management and completion of business processes. During the operation such systems accumulate a large number of data that are recorded in the form of the event logs. Event logs are a valuable source of knowledge about the actual behavior of a system. For example, there can be found information about the discrepancy between the real and the prescribed behavior of the system; to identify bottlenecks and performance issues; to detect anti-patterns of building a business system. These problems are studied by the discipline called “Process Mining”.The practical application of the process mining methods and practices is carried out using the specialized software for data analysts. The subject area of the process analysis involves the work of an analyst with a large number of graphical models. Such work will be more efficient with a convenient graphical modeling tool. The paper discusses the principles of building a graphical tool “VTMine for Visio” for the process modeling, based on the widespread application for business intelligence Microsoft Visio. There are presented features of the architecture design of the software extension for application in the process mining domain and integration with the existing libraries and tools for working with data. The application of the developed tool for solving various types of tasks for modeling and analysis of processes is demonstrated on a set of experimental schemes.
Back to Top Top