Publications of IIS researchers

The Russian-English and English-Russian dictionary contains about 5000 terms on graph-theory and its applications in informatics and programming. For convenience of readers the single book includes the both parts: Russian-English and English-Russian.

This dictionary is intended for the wide area of specialists which use the graph theory techniques for solving their problems; first of all it is intended for the programmers and specialists in AID, the creators of VLSI and other.

A.P. Ershov Institute of Informatis Systems was formed 20 years ago on the basis of several departments of the Computing Center of SB AS USSR. The booklet outlines major achievements of these teams, in particular, the Department of programming created by A.P. Ershov in 1958. You can also find information about the structure of our Institute, its principal research subjects, and main results of research and teaching activities of our staff.

The book contains more than 2500 graph-related terms with their clear and succinct definitions. In addition to the base graph theory terminology, terms and definitions from computing are included. Every term is presented in English and Russian, and its description is given.

The book will be useful for students and teachers of computing, and everyone who uses computers at home, lab, or in business.

The book is devoted to the development of adaptive methods and tools for support of distance education in programming in the framework of the problembased approach. It is the fourteenth volume in a series of books published by A.P. Ershov Institute of Informatics Systems SB RAS on problems of program construction and optimization. The problems of distance and problem-based education are considered, as well as the methods and tools of its adaptation and intellectualization. The adaptive environment WAPE for support of distance education in programming in the framework of the problem-based approach is described. An introductory course of programming on the base of a new language Zonnon is presented.

The book is intended for system programmers, students and post-graduates working in the field of system and theoretical programming. It will be of particular interest for those connected with the development of methodological and program tools for support of distance education.

In the monograph, a wide range of behavioral equivalences has been proposed and investigated on the well-known models for concurrent systems specification and analysis such as Petri nets and process algebras. The equivalence relations have been explored on subclasses and extensions of the models: time and stochastic Petri nets and stochastic process algebras. On Petri nets both with and without silent transitions and their subclasses a wide set of basic, back-forth and place behavioural equivalences were proposed and investigated in the semantics ranged from interleaving to true concurrent as well as from linear to branching time ones. On time Petri nets both with and without silent transitions and their subclasses a number of time, untime and regional equivalences were proposed and investigated in interleaving and step semantics as well as in trace and bisimulation ones. Semantic equivalences of standard and stochastic process algebras are investigated, and a coherence between them and the net equivalence relations is clarified. An algorithm of automatic formula comparison for the semantic equivalence is designed and implemented. For graduate and post-graduate students and researchers interested in theoretical computer science, in particular, formal modeling and analysis of behavioural properties of concurrent systems and processes.

Keywords: standard, time and stochastic Petri nets, subclasses, standard and stochastic process algebras, invisible transitions and actions, behavioural and semantic equivalences, bisimulation, temporal and probabilistic logics, reduction, refinement and composition, congruence, axiomatization, term rewrite systems, implementation.

The book can be purchased in the internet shop of SB RAS Publisher or in the Akademkniga bookshop (22, Morskoj pr., 630090 Novosibirsk, Russia. Phone: +7 383 330 09 22).

This volume presents an overview of program slicing, including various approaches and algorithms used to compute slices, as well as an overview of applications of program slicing, which include debugging, program integration, dataflow testing, reengineering and software maintenance. It is the eights among books published in A. P. Ershov Institute of Informatics Systems on problems of program construction and optimization.

The volume is of interest for system programmers, students and postgraduate students working in the field of system and theoretical programming.

This work is devoted to research dealing with automated constructing net models of Estelle specifications and developing verification tools of the models. We consider Estelle specifications with delay-clauses and priorities, but without dynamic constructions. The specifications allows to represent a considerable class of communication protocols. We use coloured Petri nets extended by priorities and Merlin's time concepts as the net models. This work describes a method of translating the Estelle specification into the net models, its implementation and the system NetCalc for editing and simulating the models. We present experimental results of net modeling and simulation for versions of the following well-known protocols: sliding window, ring, connection and InRes.