• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 114
Sort:
by name
by year
Article
Davydova K. V., Shershakov S. A. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 3. P. 85-102.

In this paper, we consider an approach to reverse engineering of UML sequence  diagrams from event logs of information systems with a service-oriented architecture (SOA).  UML sequence diagrams are graphical models quite suitable for representing interactions in  heterogeneous component systems; in particular, the latter include increasingly popular SOA- based  information  systems.  The  approach  deals  with  execution  traces  of  SOA  systems,  represented  in  the  form  of  event  logs.  Event  logs  are  created  by  almost  all  modern  information  systems  primarily  for  debug  purposes.  In  contrast  with  conventional  reverse  engineering techniques that require source code for analysis, our approach for inferring UML  sequence diagrams deals only with available logs and some heuristic knowledge. Our method  consists  of  several  stages  of  building  UML  sequence  diagrams  according  to  different  perspectives  set by  the analyst.  They include mapping  log attributes  to diagram  elements,  thereby determining a level of abstraction, grouping several components of a diagram and  building hierarchical diagrams. We propose to group some of diagram components (messages  and  lifelines)  based  on  regular  expressions  and  build  hierarchical  diagrams  using  nested  fragments. The approach is evaluated in a software prototype implemented as a Microsoft  Visio add-in. The add-in builds a UML sequence diagram from a given event log according  to a set of customizable settings.

Added: Nov 18, 2016
Article
K. Davydova, S. Shershakov. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 155-174.

In the paper we consider a method for mining so-called “hybrid” UML models, that refers to software process mining. Models are built from execution traces of information systems with service-oriented architecture (SOA), given in the form of event logs. While common reverse engineering techniques usually require the source code, which is often unavailable, our approach deals with event logs which are produced by a lot of information systems, and some heuristic parameters. Since an individual type of UML diagrams shows only one perspective of a system’s model, we propose to mine a combination of various types of UML diagrams (namely, sequence and activity), which are considered together with communication diagrams. This allows us to increase the expressive power of the individual diagram. Each type of diagram correlates with one of three levels of abstraction (workflow, interaction and operation), which are commonly used while considering web-service interaction. The proposed algorithm consists of four tasks. They include splitting an event log into several parts and building UML sequence, activity and communication diagrams. We also propose to encapsulate some insignificant or low-level implementation details (such as internal service operations) into activity diagrams and connect them with a more general sequence diagram by using interaction use semantics. To cope with a problem of immense size of synthesized UML sequence diagrams, we propose an abstraction technique based on regular expressions. The approach is evaluated by using a developed software tool as a Windows-application in C#. It produces UML models in the form of XML-files. The latter are compatible with well-known Sparx Enterprise Architect and can be further visualized and utilized by that tool.

Added: Oct 18, 2017
Article
Salibekyan S. M., Oleynik P. P. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 3. P. 35-50.

The article describes two approaches for control access rights based on role approach (RBAC) and the use of tables (lists) access rights (ACL). At first, an overview of modern approaches to information security and control user access rights of applications with different architectures is provided. After that, two author's methods of data protection is described. The first approach was developed for the protection of object-oriented applications, the second approach was developed for object-attribute applications used to operating network (graph) databases and knowledge bases. The focus of attention is the first author's approach based on the description of access rights for classes, attributes of classes and objects that has a certain criterion. The approach is implemented by the use of a class hierarchy, composition and structure describing in detail in the article. The article gives examples of specific information systems developed by the first author: information system for scientific conferences that was repeatedly used at the conference "Object systems" (objectsystems.ru) and information system of the beauty salon. Further focus is on the second approach required development of new technique to the information security of network (graph) information structures. The approach developed by second author fully duplicates the functionality of the first approach. In particular, it provides permissions copy when copying of the network data structure, just as in the object-oriented paradigm is a transfer of the properties of parent to child class; the article gives a detailed description of such mechanism. For access control, the method involves the use of a special virtual device. Information about access rights is linked to the node network (graph) if restrict access is needed.

Added: Sep 16, 2016
Article
Горшков И. А., Долгалева И. И. Труды Института системного программирования РАН. 2018. Т. 29. № 4. С. 325-336.

Nowadays, news portals are forced to seek new methods of engaging the audience due to the increasing competition in today’s mass media. The growth in the loyalty of news service consumers may further a rise of popularity and, as a result, additional advertising revenue. Therefore, we propose the tool that is intended for stylish presenting of facts from a news feed. Its outputs are little poems that contain key facts from different news sources, based on the texts of Russian classics. The main idea of our algorithm is to use a collection of classical literature or poetry as a dictionary of style. The facts are extracted from news texts through Tomita Parser and then presented in the form similar to a sample from the collection. During our work, we tested several approaches for text generating, such as machine learning (including neural networks) and template-base method. The last method gave us the best performance, while the texts generated by the neural network are still needed to be improved. In this article, we present the current state of Narrabat, a prototype system rephrasing news we are currently working on, give examples of generated poems, and discuss some ideas for future performance improvement.

Added: Oct 31, 2018
Article
Zelenova S. A., Zelenov S. V. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 6. P. 183-202.

In the paper, we address mission critical systems, such as automobile, avionic, mobile robotic, telecommunication, etc. Such systems must meet hard real-time constraints in order to avoid catastrophic consequences. To meet the real-time constraints, strict periodicity is used (i.e. for any periodic task, time between release points is constant). Sensors, actuators and feedback control functions are typical examples of strict periodic tasks. We study a monoprocessor preemptive scheduling problem for arbitrary number of strict periodic tasks. In this context, we focus on the following problem: how to find non-conflict set of task release points (i.e. sequences of instance release points for different tasks must not intersect). First, as a preliminaries, we introduce some fundamental definitions and prove several elementary schedulability conditions. Next, we investigate the correlation between the scheduling problem and a graph coloring problem for graphs of some special kinds. The graphs under consideration are built on the basis of the tasks' period values. We introduce a notion of divisibility graph for tasks' periods, and study compatibility of graphs' coloring with respect to the schedulability problem. At last, we prove a theorem that provides necessary and sufficient graph coloring conditions for schedulability of given strict periodic tasks. This theorem allows either to find non-conflict set of task release points directly, or to determine quickly that scheduling is impossible.  

Added: Aug 11, 2018
Article
Gnatenko A. R., 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 free semigroups. The correctness of the developed algorithm is proved and an upper bound of its complexity is obtained.

Added: Jun 14, 2018
Article
Carrasquel Gamez J. C., Morales A., Villapol M. E. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 4. P. 127-128.

This paper presents Prosega/CPN (Protocol Sequence Generator and Analyzer), an extension of CPN Tools for supporting automata-based analysis and verification. The tool implements several operations such as the  generation of a minimized deterministic finite-state automaton (FSA) from a CPN’s occurrence graph, language generation, and FSA comparison. The solution is supported by the Simulator Extensions feature whose development has been driven by the need of integrating CPN with other formal methods.

Added: Nov 19, 2018
Article
Nesterov R.A., Mitsyuk A.A., Lomazova I.A. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 3. P. 285-302.

In this paper, we present an approach to model and simulate models of multi-agent systems (MAS) using Petri nets. A MAS is modeled as a set of workflow nets. The agent-toagent interactions are described by means of an interface. It is a logical formula over atomic interaction constraints specifying the order of inner agent actions. Our study considers positive and negative interaction rules. In this work, we study interfaces describing acyclic agent interactions. We propose an algorithm for simulating the MAS with respect to a given interface. The algorithm is implemented as a ProM 6 plug-in that allows one to generate a set of event logs. We suggest our approach to be used for evaluating process discovery techniques against the quality of obtained models since this research area is on the rise. The proposed approach can be used for process discovery algorithms concerning internal agent interactions of the MAS.

Added: Jul 10, 2018
Article
Гудошникова А. А., Литвинов Ю. В. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 2. P. 97-110.

The theme of code reuse in software development is still important. Sometimes it is hard to find out what exactly we need to reuse in isolation of context. However, there is an opportunity to narrow the context problem, if applications in one given domain are considered. Same features in different applications in one domain have the same context respectively so the common part must be reused. Hence, the problem of domain analysis arises. On the other hand, there is metaCASE-techonology that allows to generate code of an application using diagrams, which describe this application. The main objective of this article is to present the technology for application family creation which connects the metaCASE-techonology and results of domain analysis activity. We propose to use some ideas of FODA (feature-oriented domain analysis) approach for domain analysis and use feature diagrams for describing of variability in a domain. Then we suggest to generate metamodel of the domain-specific visual language, based on feature diagram. After that based on generated metamodel domain-specific visual language editor is generated with the aid of metaCASE-tool. With this language user can connect and configure existing feature implementations thus producing an application. This technology supposed to be especially useful for software product lines.

Added: Oct 30, 2018
Article
Денис Турдаков, Астраханцев Н. А., Недумов Я. Р. и др. Труды Института системного программирования РАН. 2014. Т. 26. С. 421-438.

he paper presents a framework for fast text analytics developed during the Texterra project. Texterra is a technology for multilingual text mining based on novel text processing methods that exploit knowledge extracted from user-generated content. It delivers a fast scalable solution for text mining without the expensive customization. Depending on use-cases Texterra could be utilized as a library, extendable framework or scalable cloudbased service. This paper describes details of the project, use-cases and results of evaluation for all developed tools. Texterra utilizes Wikipedia as a primary knowledge source to facilitate text mining in arbitrary documents (news, blogs, etc). We mine the graph of Wikipedia’s links to compute semantic relatedness between all concepts described in Wikipedia. As a result, we build a semantic graph with more than 5 million concepts. This graph is exploited to interpret meanings and relationships of terms in text documents. In spite of large size, Wikipedia doesn’t contain information about many domain-specific concepts. In order to increase applicability of the technology we developed several automatic knowledge extraction tools. These tools include systems for knowledge extraction from MediaWiki resources and Linked Data resources, as well as system for knowledge base extension with concepts described in arbitrary text documents using original information extraction techniques. In addition, utilization of information from Wikipedia allows easily extend Texterra for support of new Natural languages. The paper presents evaluation of Texterra applied for different text processing tasks (part-of-speech tagging, word sense disambiguation, keyword extraction and sentiment analysis) for English and Russian.

Added: Nov 6, 2017
Article
Денис Турдаков, Недумов Я., Астраханцев Н. и др. Труды Института системного программирования РАН. 2014. Т. 26. № 1. С. 421-438.
Added: Sep 13, 2016
Article
Glukhoded E., Smetanin S. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 3. P. 7-20.

The concept of Z-numbers introduced by Zade in 2011 is discussed topically nowadays due to it aptitude to deal with nonlinearities and uncertainties whose are common in real life. It was a large step of representing fuzzy logic, however that numbers created much larger problems of how to calculate them or aggregate multiple numbers of that type. Z-numbers have a significant potential in the describing of the uncertainty of the human knowledge because both the expert assessment and the Z-number consists of restraint and reliability of the measured value. In this paper, a method of converting an expert opinion to Z-number is proposed according to set of specific questions. In addition, the approach to Z-numbers aggregation is introduced. Finally, submitted methods are demonstrated on a real example. The topicality of the research is developing a new algorithm and software (based on that development) which could help people make decision in a messy uncertainty with many parameters and factors that are also defined imprecisely. In this work, we present the research that is aimed to find the most efficient methods to operate them (aggregate, add, divide). Firstly, it is important to identify all existing methods of aggregating Z-numbers. Secondly, it is needed to invent new methods of how work with them. The most interesting techniques should be detailed and summarized. There is also a program that is developed to model the real-word task of decision-making.

Added: Nov 23, 2018
Article
S.M. Avdoshin, E.N. Beresneva. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 123-138.

The Metric Travelling Salesman Problem is a subcase of the Travelling Salesman Problem (TSP), where the triangle inequality holds. It is a key problem in combinatorial optimization. Solutions of the Metric TSP are generally used for costs minimization tasks in logistics, manufacturing, genetics and other fields. Since this problem is NP-hard, heuristic algorithms providing near optimal solutions in polynomial time will be considered instead of the exact ones. The aim of this article is to experimentally find Pareto optimal heuristics for Metric TSP under criteria of error rate and run time efficiency. Two real-life kinds of inputs are intercompared - VLSI Data Sets based on very large scale integration schemes and National TSPs that use geographic coordinates of cities. This paper provides an overview and prior estimates of seventeen heuristic algorithms implemented in C++ and tested on both data sets. The details of the research methodology are provided, the computational scenario is presented. In the course of computational experiments, the comparative figures are obtained and on their basis multi-objective optimization is provided. Overall, the group of Pareto-optimal algorithms for different  consists of some of the MC, SC, NN, DENN, CI, GRD, CI + 2-Opt,  GRD + 2-Opt, CHR and LKH heuristics.

Added: Sep 27, 2017
Article
M.K. Gordenko, S.M. Avdoshin. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 107-122.

The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which defined on mixed multigraph) using the reduction of the original problem into General Travelling Salesman Problem (GTSP). The variants of CPP are pointed out. The mathematical formulations of some problems are presented. The algorithm for reduction the MCPP in multigraph into GTSP is shown. The experimental results of solving MCPP in multigraph through the reduction into GTSP are presented. 

Added: Sep 27, 2017
Article
Pozin B. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 1. P. 103-114.

The set of outline and guidelines as well as tools for automation to ensure continuity of business-continuity in the lifecycle of mission critical systems are considered. This complex is called the Life Cycle Supporting System (LCSS). The aim of the system is to reduce the risk level of the realization of critical errors in the system and application software throughout the life cycle of mission critical system, reducing operational risks and total cost of ownership of mission critical system. LCSS in the ISO / IEC / IEEE 15288 terms is enabling system. LCSS is created for life cycle of mission critical system support in the organization-owner.

Added: Oct 31, 2018
Article
Smetanin S. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 315-324.

With the popularization of social media, a vast amount of textual content with additional geo-located and time-stamped information is directly generated by human every day. Both tweet meaning and extended message information can be analyzed in a purpose of exploration of public mood variations within a certain time periods.  This paper aims at describing the development of the program for public mood monitoring based on sentiment analysis of Twitter content in Russian. Machine learning (naive Bayes classifier) and natural language processing techniques were used for the program implementation. As a result, the client-server program was implemented, where the server-side application collects tweets via Twitter API and analyses tweets using naive Bayes classifier, and the client-side web application visualizes the public mood using Google Charts libraries.  The mood visualization consists of the Russian mood geo chart, the mood changes plot through the day, and the mood changes plot through the week. Cloud computing services were used in this program in two cases. Firstly, the program was deployed on Google App Engine, which allows completely abstracts away infrastructure, so the server administration is not required.  Secondly, the data is stored in Google Cloud Datastore, that is, the highly-scalable NoSQL document database, which is fully integrated with Google App Engine.

Added: Nov 23, 2018
Article
Gordenko M., Avdoshin S. M. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 3. P. 221-232.

In this article, the routing problems are described. It is shown, that almost all routing problem can be transformed into each other. An example of the Mixed Chinese Postman problem is discussed. The article gives an overview of various variants of Chinese Postman Problem. For all problems the mathematical formulation is given. Moreover, the useful real-life application is presented, too. Then, the article provides a table of possible Chinese Postman problems and identifies parameters that can be varied for obtaining new problems. Five parameters have been identified, such as: presence of set of edges; presence of set of arcs; presence of edges with cost, depending on traversing; the presence of set of required edges; the presence of set of required arcs. It was shown that by varying these parameters one can obtain tasks that were not described earlier but can be used in real life. Four new tasks were identified. Then it is shown that the Chinese Postman problem can be solved as another routing tasks through graph transformations. The method for transforming Chinese Postman problem into the Generalized Travelling Salesman problem is given. Then the results of solving the above problem are presented by simple algorithms, and their effectiveness is shown. The research is not over yet. The testing of other algorithms is planned.

Added: Sep 2, 2018
Article
Dworzanski L. W., Михайлов В. Е. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 175-190.

Well-structured transition systems (WSTS) became a well-known tool in the study of concurrency systems for proving decidability of properties based on coverability and boundedness. Each year brings new formalisms proven to be WSTS systems. Despite the large body of theoretical work on the WSTS theory, there has been a notable gap of empirical research of well-structured transition systems. In this paper, the tool for behavioural analysis of such systems is presented. We suggest the extension of SETL language to describe WSTS systems (WSTSL). It makes the description of new formalisms very close to the formal definition. Therefore, it is easy to introduce and modify new formalisms as well as conduct analysis of the behavioural properties without much programming efforts. It is highly convenient when a new formalism is still under active development. Two most studied algorithms for analysis of well-structured transition systems behavior (backward reachability and the Finite Reachability Tree analyses) have been implemented; and, their performance was measured through the runs on such models as Petri Nets and Lossy Channel Systems. The developed tool can be useful for incorporating and testing analysis methods to formalisms that occur to be well-structuredness transition systems.

Added: Oct 1, 2017
Article
Гималетдинова А. Р., Degtiarev K.Y. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 87-106.

In the last few years there has been a growing interest in route building oriented mobile applications with the following features of navigation and sending timely notifications about arrival. Despite the large body of existing knowledge on navigational services, there has been an important issue relative to positioning accuracy. The paper discusses a possible solution to comparison problem, which is linked to the determination of the closeness to destination metro station through finding a difference between user’s current coordinates and fixed-point coordinates. With this end in view, fuzzy logic approach is used to develop Routes Recommender System (RRS) that utilizes linguistic variables to express the vague and uncertain term ‘closeness to…’. The paper provides detailed explanation of each variable considered in the fuzzy inference system (FIS), set of fuzzy rules in line with graphical representation of system’s output. Based on Mamdani model, we propose a set of test cases to check maintainability of the model and provide a description about received results. At a later time, an Android-based mobile application aimed at public transport route building will be developed whose notification system will be based on our model`s implementation presented. It should be emphasized that the paper examines potentials of the modeling approach based on interval type-2 fuzzy sets (IT2FS) that attract much attention these days in various research studies and conventional Mamdani fuzzy inference system (MFIS) as applied to real and rather topical problem. The significance of developing such models may be of a high demand for appropriate representation of factors that are inherently vague and uncertain. Hence, this study may also contribute to future research on similar topics.

Added: Sep 12, 2017
Article
R.A. Nesterov, I.A. Lomazova. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 21-38.

Process mining offers various tools for studying process-aware information systems. They mainly involve several participants (or agents) managing and executing operations on the basis of process models. To reveal the actual behavior of agents, we can use process discovery. However, for large-scale processes, it does not yield models, which help understand how agents interact since they are independent and their concurrent implementation can lead to a very sophisticated behavior. To overcome this problem, we propose interface patterns, which allow getting models of multi-agent processes with a clearly identified agent behavior and interaction scheme as well. The correctness of patterns is provided via morphisms. We also conduct a preliminary experiment, results of which are highly competitive compared to the process discovery without interface patterns.

Added: Sep 6, 2017
Article
Mallachiev K. A., Pakulin N. V., Khoroshilov A. V. et al. Proceedings of the Institute for System Programming of the RAS. 2017. Vol. 29. No. 4. P. 283-294.

Modern embedded OS are designed to be used in control solutions in various hardware contexts. Control computers may differ in the architecture of the CPU, the structure of communication channels, supported communication protocols, etc. Embedded OS are often statically configured to create an OS image, which intended to be executed on some specific control computer. System integrator usually performs this configuration. Embedded OS are often developed by many companies. Joint development and integration is very complex if OS doesn’t support modularity. Support of modularity and component assembly reduces the need of communication among companies during development and integration. This allows customers to create minimal solutions that are optimally adapted to the particular task and hardware platform. Furthermore, customers may be interested in adding their own low level components without OS modification. In this article, we present an approach to building modular embedded solutions from heterogeneous components based on the RTOS JetOS. The mechanism of components binding developed by us allows uniting heterogeneous components from different manufacturers within the same section of the address space. This mechanism allows component developer to independently develop their components. And system integrator can independently from developers configure what component he likes to see in OS image and how components should interact.

Added: Aug 11, 2018