Abstracts

Hypercube communication structures analysis via parametric Petri nets // Proceedings of 24th UK Performance Engineering Workshop (UKPEW 2008), 3-4 July 2008, Department of Computing, Imperial College London, p. 358-371 (with Shmeleva T.R.).

A model of a hypercube communication structure of an arbitrary size with an arbitrary number of dimensions in the form of parametric Petri net was constructed. A technique of the linear invariants calculation for parametric Petri nets was developed which allowed the analysis of transmissions involving an arbitrary number of communicating devices (routers) in hypercube. The compulsory buffering of the packets inevitably leads to possible blockings of communicating devices. The structure of complex deadlocks involving an arbitrary number of communicating devices caused by both the chain (cycle) of blockings and the isolation was studied. In real-life networks, described deadlocks lead to considerable decrease of performance and can be inflicted by the ill-intended traffic of a peculiar form.

Keywords: router, switch, hypercube communication structure, parametric Petri net, deadlock

Effectiveness of Bluetooth Address Space Usage // Proceedings of 20th International Conference, Software & Systems Engineering and their Applications (ICSSEA 2007), Paris 4-6 December 2007 (with Bereznyuk M.V., Gupta K.K.).

In this paper, we have constructed the Colored Petri Net models of master and slave devices of the Bluetooth protocol. On the series of examples of piconets models with various numbers of slave devices, the effectiveness of protocol address space usage has been estimated. For the construction and investigation of models, well-known simulation system CPN Tools has been used. The possibility of information exchange slipping at the growth of the number of slave devices attached to piconet has also been discovered.

Keywords: Bluetooth, colored Petri net, simulation, address space, slipping effect

World-wide network Ethernet? // Zviazok (Communications), no. 5, 2007. - p. 14-19. (with Vorobiyenko P.P., Nechiporuk O.L.) In Russ.

New addressing schemes of world-wide networks (Е6/Е6-4/Е4Р) were developed. Networks are built completely on the base of Ethernet technology with annulment of network-transport protocols of TCP/IP stack and complete preservation of application interfaces. Sketch design of protocols Е6/Е6-4/Е4Р stack and corresponding switching routers E6 was implemented provided with examples of networks construction. The advantages of the proposed approach is the reduction of packets overhead information, increase of network performance especoally at the transmission of voice traffic, extension of address space.

Keywords: Ethernet, address Е6, stack of protocols, switching router

Evaluation of Ethernet networks characteristics using parametric Petri nets // Zviazok (Communications), no. 4, 2007. - p. 62-67. (with Shmeleva T.R.) In Russ.

Modified parametric model of switched Ethernet was presented which is invariant regarding network topology and numbers of attached network and terminal devices. Models measuring fragments were developed which provide the evaluation of throughput, frames delivery time and sizes of internal buffers of switches during the simulation. The adequacy of the model was acknowledged by the results of real-life networks measuring. The analysis was implemented for various types of applied network hardware. The area of the results application is the development of Ethernet networks and devices close to optimal.

Keywords: Ethernet, switch, parametric Petri net, throughput, delivery time

Performance evaluation of label switching networks with simulation system ns // Transactions of Odessa National Academy of Telecommunication, no. 1, 2007. - p. 25-31. (with Litvin D.A.) In Russ.

The technique of MPLS backbones' models construction into simulation system NS on the example of European Internet backbone's fragment was presented. For the dynamic performance evaluation of the backbone, a procedure was developed, that estimates periodically the network's performance during the simulation process. The procedure might be used for the revealing of short duration overloads into backbones. The adequacy of early presented models in the form of Colored Petri nets was acknowledged.

Keywords: label switching, MPLS, performance evaluation, simulation

Modeling telecommunication networks with system ns // Transactions of Odessa National Academy of Telecommunication, no. 2, 2006. - p. 35-43. (with Shinkarchuk T.N.) In Russ.

The development of model for a fragment of European Internet backbone in the environment of simulation system NS was implemented. For the estimation of backbone's throughput, packet's delivery time and delivered packets percentage the corresponding scripts of OS Unix, using the analysis of complete simulation trace, were written. The adequacy of earlier represented models in the form of colored Petri nets was confirmed.

Keywords: backbone network, IP, performance, packet delivery time, simulation

Switched Ethernet Response Time Evaluation via Colored Petri Net Model // Proc. of International Middle Eastern Multiconference on Simulation and Modelling, August 28-30, 2006. - Alexandria (Egypt). - 2006. - P. 68-77 (with Shmeleva T.R. ).

The enterprise class model of switched LAN in the form of a colored Petri net is represented. The components of the model are submodels of switch, server and workstation. For the evaluation of network response time a special measuring workstation model is proposed. It counts response times for each request and calculates the average response time. For the simulation of network behavior and accumulation of statistical information, CPN Tools was applied. Hierarchical nets usage allows the convenient representation of an arbitrary given structure of LAN. The influence of such features as limitations of switch's buffer size and dynamic maintenance of switching table were estimated.

Keywords: Ethernet, Switch, Response time, Colored Petri net, Evaluation

Studying the efficacy of MPLS technology via Colored Petri nets // Zviazok (Communications), 2006, Vol. 65, no. 5. - P. 49-55 (with Sakun A.L.). In Russ.

Models of backbone Internet routers implementing classical IP routing and label switching MPLS were constructed in the form of colored Petri nets. On the example of European Internet backbone's model the comparative evaluation of IP and MPLS efficacy. For models construction and studying the enterprise-class simulation system CPN Tools was used. Usage of MPLS technology allows the traffic increase in 1,7 times on average.

Keywords: backbone networks, MPLS, colored Petri net, simulation, evaluation of efficacy

Verification of protocol TCP in the process of sequential composition of Petri net models // Zviazok (Communications), 2006, Vol. 64, no. 4. - P. 49-58. In Russ.

The correctness of connection establishment and disconnection procedures of protocol TCP has been proven. Model constructed on standard specifications of the protocol is represented by Petri net. The peculiarity of the model is a distinct representation of TCP header flags used in connection establishment and disconnection procedures. For protocol's verification, linear invariants of Petri nets were applied. The calculation of invariants was implemented in the process of sequential model's composition out of its functional subnets that gives us considerable speed-up of computations.

Keywords: TCP, Petri net, linear invariant, functional subnet, sequential composition

On realization of compositional algorithms of linear systems solution // Control systems and machines. - 2006, no. 3. - P. 32-41. In Russ.

Compositional algorithms allowing the speed-up of linear systems solution were constructed. Algorithms are founded on the decomposition of systems into clans and may be applied at systems' solution over rings and fields. The invariance in regard to a region of values and a chosen algorithm of a linear system solution was provided. Exponential speed-up of computations has been obtained at solution of the Diophantine systems in the nonnegative region. The description of program realization Adriana peculiarities was implemented.

Keywords: linear Diaphantine system, clan, composition, algorithm, speed-up

Sequential composition of linear systems' clans // Systems Research and Information Technologies, 2006, no. 2. - P. 121-137. In Russ.

For obtaining of an additional speed-up of computations at the solution of linear systems, it was proposed to organize a sequential process of composition of its clans. Speed-up of computations was obtained due to the solution of a sequence of clans' composition systems with essentially lesser dimension. Graph of decomposition of system into clans was used. A comparative analysis of sequential composition for subgraphs and edges (pairwise) was implemented. The task of construction of systems' sequence with the least dimension was named by a collapse of weighted graph. Estimations of upper and lower bounds of collapse width, which corresponds to dimension of systems, were obtained. A heuristic algorithm of optimal collapse was constructed and statistically grounded.

Keywords: linear Diaphantine system, clan, sequential composition, collapse of weighted graph, speed-up

Verification of Ethernet protocols via parametric composition of Petri net // INCOM'2006: 12th IFAC/IFIP/IFORS/IEEE/IMS Symposium Information Control Problems in Manufacturing, May 17-19 2006, Saint-Etienne, France, p. 261-267 (with Zaitsev I.D.).

The verification of Ethernet protocols represented by Petri net models is implemented. A model consisting of an arbitrary number of workstations on bus is composed out of model of a single workstation via the fusion of contact places. The invariance of the model with an arbitrary number of workstations is proved on the base of the invariance of separate workstation's model, which is the functional subnet. Parametric equations and invariants are used.

Keywords: Ethernet, Petri net, invariant, composition, functional subnet

Studying the efficacy of protocol Bluetooth address space utilization // Radioelectronics. Informatics. Control. 2006, no. 1. - P. 57-63 (with Bereznyuk M.V.). In Russ.

In the present work the Petri net models of master and slave devices implementing protocol Bluetooth were built. On the examples of piconets' models with various number of slave devices the evaluation of address space usage efficiency was implemented. For models' construction and investigation the enterprise-level simulation system CPN Tools was used. It was found the possibility of information exchange slipping at the growth of number of attached to piconet slave devices.

Keywords: colored Petri net, Bluetooth piconet, address space, evaluation

Synthesis of Petri net model and verification of electronic commerce protocol IOTP // Raditekhnika: All-Ukr. Sci. Interdep. Mag., 2006, Вып. 144. - С. 28-35 (with Chornogala E.Y.). In Russ.

Early presented technique of Petri net models of telecommunication protocols synthesis was applied to the synthesis of model for well-known protocol of electronic commerce IOTP. Model was constructed for typical purchase transaction and consists of about hundred of Petri net elements. Verification of the protocol was implemented in the process of sequential composition of functional Petri nets, since the invariance analysis by traditional methods is practically impossible.

Keywords: electronic commerce, protocol, Petri net, verification, synthesis

Transmission function of Petri net // Artificial Intelligence, 2006, no. 1, p. 23-30. In Russ.

An algebraic representation of transfer function for an arbitrary timed Petri net was obtained. Weak types of fictional equivalence were introduced and investigated, additional rules of nets' transformations for weal types of equivalence leading to considerable decrease of net's size were studied.

Keywords: functional Petri net, state equation, transfer function, equivalence

Sequential composition of telecommunication protocols Petri net models // Zviazok (Communications), 2006, no. 1 (61), p. 45-50. In Russ.

The technique of telecommunication protocols verification in the process of sequential composition of Petri net model out of its minimal functional subnets was presented. The sequential organization of the composition process allows the obtaining an additional speed-up of computations in the comparison with early considered simultaneous composition. At exponential complexity of Petri nets invariance analysis, the obtained speed-up of computations is rather considerable. Presented technique is meticulously studied on the example of sequential composition of the wide-know protocol BGP used in backbone Internet routing.

Keywords: telecommunication protocol, verification, Petri net, linear invariant, sequential composition, functional subnet

Compositional analysis of Petri nets // Cybernetics and Systems Analysis, 2006, no. 1, p. 143-154.

Foundations of Petri nets compositional analysis are represented, that consists in given Petri net properties obtaining on the base of properties of its functional subnets. At that a composition of Petri net out of subnets may be either given at model development or obtained in the result of decomposition. Compositional analysis involves in investigation of behavioral and structural properties of Petri nets with matrix methods using fundamental equation and invariants. Acceleration of computations obtained is exponential with the respect to dimension of net.

Keywords: Petri net, functional subnet, composition, linear invariant, speed-up

Synthesis of telecommunication protocols Petri net models // Transactions of Odessa National Academy of Telecommunication, 2005, no. 2, p. 36-42. In Russ.

A technique for Petri net models of telecommunication protocols synthesis was presented. A survey of telecommunication protocols' standards was implemented. As an intermediate language of specifications Hoare's communicating sequential processes were used. The methods of finite automata synthesis on formulae of sequential processes and methods of labeled Petri net synthesis on formulae of communicating sequential processes were developed. The task of unlabeled Petri net synthesis given by finite automata was formalized.

Keywords: Petri net, synthesis, finite automaton, CSP, linear system

Principes of parametric Petri net models construction for switched networks // Simulation and Computer Graphics: Proceedings of 1-st International Scientific-Technic Conference, October 4-7 2005, Donetsk, DonNTU, 2005, p.207-215 (with Shmeleva T.R.). In Russ.

The technique of construction of parametric models of switched telecommunication networks in the form of colored Petri nets was presented. The standard model is invariant with respect to network's topology and consists of a fixed number of elements. The components of the modeled network are workstations, servers, switches and hubs. The topology of a network is the parameter of the model.

Keywords: colored Petri net, switched network, parametric model

A measurement of characteristics for a single-level switched network using parametric Petri net model // Raditekhnika: All-Ukr. Sci. Interdep. Mag. 2005, no. 142, p. 40-47 (with Shmeleva T.R.). In Russ.

A parametric model Petri of a single-level switched local-area network is represented. A model allows the buffers' sizes and processors' numbers limitation as well as discipline FIFO realization for queues. An automatic measurement of the network response time is provided during imitation of model's behavior. For these purposes special measuring fragments of Petri nets are used. Questions of state-stable mode existence for local-area network dynamics as well as the dependence of network response time on characteristics of hardware and software used are investigated. Results are represented in the form of diagrams, graphs, and tables.

Keywords: colored Petri net; switched network; parametric model; measurement

Parametric Petri net model of single-level switched network // Proceedings of Odessa National Telecommunication Academy, no. 1, 2005, p. 33-40 (with Shmeleva T.R.). In Russ.

A model of a single-level switched network invariant with respect to topology was constructed. The model is represented with colored Petri net. Basic parameters of the model are packed matrix of topology, table of workstations' requests to servers, times of frames' transmission and requests processing. For model debug and collection of statistical information CPN Tools system was applied.

Keywords: colored Petri net; switched network; parametric model

Software for decomposition of bipartite directed graphs // Proceedings of Donetsk State Technical University, series "Informatics, Cybernetics and Computer Science", Vol. 93, 2005, p. 60-70. In Russ.

Software for decomposition of bipartite directed graphs (Petri nets) into functional subnets was represented. Decomposition is aimed to speed-up of large-scale Petri net models analysis. Basic operations of decomposition algorithm were defined, the optimization of data structures for effective implementation of basic operations was executed, detailed algorithm of decomposition was represented. Variants of decomposition software module integration into automated systems of Petri net models analysis and synthesis were studied. Results of decomposition a host of nets allow the conclusion about good enough partibility of real-life objects' models.

Keywords: bipartite digraph, Petri net, decomposition, functional subnet

Functional Petri Nets, Universite Paris-Dauphine, Cahier du Lamsade 224 Avril 2005, 62p (www.lamsade.dauphine.fr/cahiers.html).

Functional Petri nets and subnets are introduced and studied for the purpose of speed-up of Petri nets analysis with algebraic methods. We show that any functional subnet may be generated by a composition of minimal functional subnets. We propose two ways to decompose a Petri net: via logical equations solution and with an ad-hoc algorithm, whose complexity is polynomial. Then properties of functional subnets are studied. We show that linear invariants of Petri net may be computed from invariants of its functional subnets; similar results also hold for the fundamental equation of Petri nets. A technique for Petri net analysis using composition of functional subnets is also introduced and studied. We show that composition-based calculation of invariants and solutions of fundamental equation provides a significant speed-up of computations. For an additional speed-up we propose a sequential composition of functional subnets. Sequential composition is formalized in the terms of graph theory and was named the optimal collapse of a weighted graph. At last, we apply the introduced technique to the analysis of Petri net models of such well-known telecommunication protocols as ECMA, TCP, BGP.

Keywords: Petri net, functional net, functional subnet, composition

Solving linear systems using decomposition // Systems Investigations and Information Technilogies, 2005, no. 2, 2005, p. 131-143. In Russ.

Special subsets of equations of linear system named by clans were introduced and studied. It was proposed to use the decomposition into clans for the acceleration of solving of linear system. Complexity of decomposition equals cube depending on size of system. Therefore, acceleration of computations was obtained for methods with complexity exceeding cube. For solving of integer systems in nonnegative integer numbers acceleration of computations obtained is exponential.

Keywords: linear system, clan, decomposition, speed-up of computations

Verification of Protocol BGP via Decomposition of Petri Net Model into Functional Subnets // Proceedings of the Design, Analysis, and Simulation of Distributed Systems Symposium, April 2-8, 2005, San Diego, USA, p. 72-78.

Petri net model of the widely known protocol BGP of Internet backbone routing was constructed. The decomposition of Petri net model of communication protocol BGP into functional subnets was implemented. Invariance of the source model was proved on the base of established invariance of its functional subnets. The speed-up of computations obtained is exponential with respect to dimension of Petri net.

Keywords: Petri net, BGP, Invariance, Decomposition, Functional subnet

The measuring fragments in Petri net models of telecommunication networks // Zviazok (Communications), no. 2(54), 2005, p. 65-71. In Russ.

The technique for measuring of characteristics of switched networks' Petri net models with the aid of ad-hoc measuring fragments of coloured Petri nets is presented. The peculiarities of measuring fragments application were studied at the example of network's response time evaluation in the model of switched local area network. For the automated construction of the model in the form of hierarchical coloured Petri net and simulation CPN Tools was used. The model reflects such features of Ethernet as CSMA access procedures, full-duplex mode of data transmission and also provides an easy scalability at modelling of concrete LANs.

Keywords: LAN; switch; measuring fragment; response time; coloured Petri net

Verification of telecommunication protocols using decomposition of Petri nets // Zviazok (Communications), no. 1(53), 2005, p. 41-47. In Russ.

The technique for verification of telecommunication protocols with the aid of decomposition of Petri net models is presented. Detailed Petri net models of telecommunication protocols contain hundreds and sometimes thousands of nodes. Such a dimension makes their analysis by the formal methods based on application of fundamental equation and linear invariants practically unfeasible. Decomposition of Petri net model into functional subnets allows the obtaining the exponential speed-up of computations. Presented technique was studied in details on the example of verification for wide-known protocol BGP of Internet backbone routing.

Keywords: telecommunication protocol; verification; Petri net; invariant; decomposition; functional subnet

Solving the fundamental equation of Petri net in the process of composition of functional subnets // Artificial Intelligence, no. 1, 2005, p. 59-68. In Russ.

The technique of solution of the fundamental equation of Petri net based on decomposition into functional subnets is proposed. Solutions of the fundamental equation of the entire Petri net are calculated out of solutions of the fundamental equations of functional subnets for dual Petri net. Acceleration of computations obtained is exponential with the respect to dimension of Petri net.

Keywords: Petri net, Fundamental equation, Functional subnet, Composition

Stepwise composition of functional subnets // Proceedings of Odessa National Telecommunication Academy, no. 3, 2004, p. 33-40. In Russ.

Stepwise composition allows the additional speed-up of computations at the expense of solution the sequence of systems with lesser dimension for subsets of contact places. For formal representation of decomposition into functional subnets weighted graph was used. Since stepwise composition compress graph into single vertex, the task was named a collapse of weighted graph. The width of collapse corresponds to dimension of solving system. Properties of collapse were studied; upper and lower bounds for width of collapse were obtained. Simple and effective heuristic algorithm of collapse was suggested. Results of arbitrary graphs collapse with this algorithm have shown that it provides a width of collapse close to optimal.

Keywords: Petri net, Composition, Functional Subnet, Stepwise, Collapse of graph

Decomposition of Petri Nets // Cybernetics and Systems Analysis, no. 5, 2004, p. 131-140.

The problem of splitting of any given Petri net into its functional subnets is considered. Properties of functional subnets and their inducing sets are investigated. Graph of decomposition into functional subnets is introduced. Two ways of decomposition are considered: with the aid of logical equations and an algorithmic. The algorithm of net decomposition possessing a polinomial complexity is constructed.

Keywords: Petri net, Functional Subnet, Decomposition

An Evaluation of Network Response Time using a Coloured Petri Net Model of Switched LAN // Proceedings of Fifth Workshop and Tutorial on Practical Use of Coloured Petri Nets and the CPN Tools, October 8-11, Aarhus, Denmark, p. 157-167.

The enterprise class model of switched LAN in the form of a coloured Petri net is represented. The components of the model are switches, servers and workstations. For the evaluation of network response time a special measuring workstation model is proposed. It counts response times for each request and calculates the average response time. For the simulation of network behaviour and accumulation of statistical information, CPN Tools was applied. Hierarchical nets usage allows the convenient representation of an arbitrary given structure of LAN.

Keywords: LAN; Switch; Response time; Colored Petri net; Evaluation

Verification of protocol TCP via decomposition of Petri net model into functional subnets // Proceedings of the Poster session of 12th Annual Meeting of the IEEE / ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, October 5-7, 2004, Volendam, Netherlands, p. 73-75.

Proof of the invariance of Petri net model for connection and disconnection phases of TCP protocol was implemented. Decomposition of Petri net model into functional subnets was realized. Calculation of invariants was implemented in the process of sequential composition, which allows the essential acceleration of computations.

Keywords: TCP, verification, Petri net, invariant, decomposition, functional subnet

Solving the fundamental equation of Petri net using the decomposition into functional subnets // 11th Workshop on Algorithms and Tools for Petri Nets, September 30 - October 1, 2004, University of Paderborn, Germany, p. 75-81

The technique of solution of the fundamental equation of Petri net based on decomposition into functional subnets is proposed. Solutions of the fundamental equation of the entire Petri net are calculated out of solutions of the fundamental equations of functional subnets for dual Petri net. Acceleration of computations obtained is exponential with the respect to dimension of Petri net.

Keywords: Petri net, Fundamental equation, Decomposition, Functional subnet

Speed-up of solution of linear systems with the aid of decomposition into clans // Artificial Intelligence. Intelligent and multiprocessor systems-2004, Proceedings of international conference, Vol. 1, Taganrog, TRTU, 2004, p. 259-264. In Russ.

Special subsets of equations of linear system named by clans were introduced and studied. It was proposed to use the decomposition into clans for the acceleration of solving of linear system. Complexity of decomposition equals cube depending on size of system. Therefore, acceleration of computations was obtained for methods with complexity exceeding cube. For solving of integer systems in nonnegative integer numbers speed-up of computations obtained is exponential.

Keywords: Linear System, Clan, Decomposition, Speed-up of Computations

Verification of Protocol ECMA with Decomposition of Petri Net Model // Proceedings of The International Conference on Cybernetics and Information Technologies, Systems and Applications, Orlando, Florida, USA, July 21-25, 2004.

Decomposition of Petri net model of ECMA communication protocol into minimal functional subnets, left and right communicating systems, subsystems of connection establishing and disconnecting is implemented. A correct protocol ought to be invariant one. Invariance of source model is proved on the base of established invariance of functional subnets. Isomorphism of subnets has allowed the calculation of invariants in the process of consecutive composition of net. Acceleration of computations for decomposition technique was estimated. It is exponential with the respect to net dimension.

Keywords: Protocol, Petri net, Invariant, Functional subnet, Decomposition.

Decomposition-based calculation of Petri net invariants // Proceedings of Workshop on Token based computing of the 25-th International conference on application and theory of Petri nets, Bologna, Italy, June 21-25, 2004, p. 79-83.

The decomposition-based technique for calculation of Petri net invariants is presented. It was proved that invariants of the entire Petri net might be constructed of invariants of its functional subnets. The acceleration of calculations obtained is exponential with respect to the number of Petri net nodes.

Keywords: Petri net, Invariant, Decomposition, Functional subnet

Switched LAN simulation by colored Petri nets // Mathematics and Computers in Simulation, vol. 65, no. 3, 2004, p. 245-249.

The methodology of switched LAN models construction in the form of colored Petri net is introduced. For the simulation and analysis of the model the Design / CPN tool is used. The tasks of estimation of LAN switch's buffer size and network response time were solved. The components of the model are switches, servers and workstations.

Keywords: Computer networks; Switch; Petri net; Estimation

Invariants of timed Petri nets // Cybernetics and Systems Analysis, no. 2, 2004, p. 92-106.

A linear fundamental equation of timed Petri net is constructed. Full and partial invariants of state and behavior of timed Petri net are introduced. Properties of the invariant nets are investigated. Interrelations of the full and partial invariants are explained. Examples of analysis for net models of production systems and processes are described.

Keywords: timed Petri net; fundamental equation; partial invariant; full invariant

Modelling of switched networks with colored Petri nets // Zviazok (Communications), no. 2(46), 2004, p. 56-60. In Russ. (with Shmeleva T.R.)

It was shown the way colored Petri nets may be applied to communication devices modelling. Models of Ethernet switch as well as server and workstation were constructed. Moreover, algorithms of dynamic maintaining of switching table were represented by colored Petri nets. For the simulation and analysis of the model the Design / CPN tool was used. Results were illustrated with model of concrete given LAN.

Keywords: Computer networks; Switch; Petri net; Estimation; Dynamic switching table

Invariance of TCP protocol Petri net model // Proceedings of Odessa National Telecommunication Academy, no. 2, 2004, p. 19-27. In Russ.

Proof of the invariance of Petri net model for connection and disconnection phases of TCP protocol was implemented. Decomposition of Petri net model into functional subnets was realized. Calculation of invariants was implemented in the process of sequential composition, which allows the essential acceleration of computations.

Keywords: TCP, Petri net, invariant, functional subnet

On question of calculation complexity of Toudic's method // Artificial Intelligence, no. 1, 2004, p. 29-37. In Russ.

Estimation of time and space complexity of Toudic method aimed to solution of homogeneous linear Diophantine systems of equations in nonnegative integer numbers is implemented. Conditions of polynomial complexity of method are obtained. It was shown that in the worst case calculation complexity of the method is double exponential with respect to dimension of a system. It was found that for sparse matrixes there is a flood effect resulting in estimations of complexity in the worst case.

Keywords: Petri net; invariant; Toudic method; double exponent; flood effect

Theoretical grounding of Toudic's method // Proceedings of Donetsk State Technical University, series "Informatics, Cybernetics and Computer Science", Vol. 74, 2004. p. 286-293. In Russ.

Paper gives a theoretical grounding of know heuristic Toudic method for the solution of linear diophantine homogeneous systems of equations in nonnegative integer numbers. In particular nonnegative solutions are required for calculation of the invariants for Petri nets. At first we construct the solution for one equation. Then the solution is expanded to whole system of equations. To generate all solutions via the Toudic's basis a linear combination was extended by special operation of reduction in common measure of vectors' components.

Keywords: Diophantine equation; Linear system; Nonnegative solution; Petri net; Invariant

Decomposition of protocol ECMA // Raditekhnika: All-Ukr. Sci. Interdep. Mag. 2004, no. 138, p. 130-137. In Russ.

Decomposition of Petri net model of ECMA protocol into minimal functional subnets, left and right interconnecting systems, subnets of connection establishing and disconnecting is implemented. Invariance of source model is proved on the base of established invariance of functional subnets. Isomorphism of subnets has allowed calculate invariants in the process of consequent composition of net. Acceleration of computations with compositional methods of invariants construction was estimated.

Keywords: Telecommunication protocol; Petri net; Invariant; Decomposition; Functional subnet

Verification of Ethernet protocols // Proceedings of Odessa National Telecommunication Academy, no. 1, 2004. In Russ.

Verification of Ethernet protocols represented with Petri nets is implemented. Natural decomposition of Petri net into functional subnets defined by model construction rules is used. Invariance of models with an arbitrary number of workstations is proved on the base of invariance of separate workstation model that is functional subnet.

Keywords: Telecommunication protocol; Petri net; Invariant; Composition; Functional subnet

Invariants of functional subnets // Proceedings of Odessa National Telecommunication Academy, no. 4, 2003, с. 57-63. In Russ.

Method of Petri nets invariants calculation based on decomposition of a given net into functional subnets is represented. Method consists in calculation of invariants for functional subnets and subsequent recovery of invariants for source net. Exponential acceleration of computations was obtained. The results are explained with example.

Keywords: Petri net; Invariant; Composition; Functional subnet

Switched LAN Simulation by Colored Petri Nets // Proceedings of European Simulation and Modelling Conference, Naples, Italy, October 27-29, 2003, p. 485-489.

The methodology of switched LAN models construction in the form of colored Petri net is introduced. For the simulation and analysis of the model the Design / CPN tool is used. The tasks of estimation of LAN switch buffer size and network response time were solved. The components of the model are switches, servers and workstations.

Keywords: Computer networks; Switch; Petri net; Estimation

Formal Grounding of Toudic Method // Proceedings of the 10th Workshop "Algorithms and Tools for Petri Nets".- Eichstaett, Germany, September 26-27, 2003, p. 184-190.

Paper gives a formal grounding of know heuristic Toudic method for the solution of linear diophantine homogeneous systems of equations in nonnegative integer numbers. In particular nonnegative solutions are required for calculation of the invariants for Petri nets. At first we construct the solution for one equation. Then the solution is expanded to whole system of equations. To generate all solutions via the Toudic’s basis a linear combination was extended by special operation of reduction in common measure of vectors’ components.

Keywords: Diophantine equation; Linear system; Nonnegative solution; Petri net; Invariant

Subnets with Input and Output Places // Petri Net Newsletter, Vol. 64, April 2003, p. 3-6, Cover Picture Story.

The aim of this paper is to introduce a concept of subnet with input and output places, especially, the specific class of the functional subnet and to construct a formal methods for the decomposition of an arbitrary Petri net into subnets. The generating family of subnets is presented and grounded. An efficient polynomial algorithm of the decomposition of an arbitrary Petri net is constructed.

Keywords: Petri net; Functional subnet; Decomposition; Algorithm

Synthesis of Continuous Logic Function Given by Table // Cybernetics And Systems Analysis, no. 2, 1998, p. 46-53. (with Sarbej V.G., Sleptsov A.I.)

Polynomial algorithm for synthesis of continuous (fuzzy) logic function on given table of choice was constructed. An arbitrary function of continuous logic may be given by table of choice. The conditions under which a table of choice defines any function of continuous logic are found.

Keywords: Continuous logic; Fuzzy logic; Table of choice; Constituent of maximum

State Equations and Equivalent Transformations of Timed Petri Nets // Cybernetics And Systems Analysis, Vol. 33, no. 5, 1997, p. 659-672. (with Sleptsov A.I.)

Generalized class of timed Petri nets with multi-channel transitions was introduced. It allows not only repetitive firing of an active transition but simultaneous firing of few copies of the same transition. State equation that is complete formal description of net behaviour was constructed. New type of functional equivalence was introduced and studied. Transmission function of net with input and output places was investigated. For structural conflict-free net explicit description of transmission function was obtained. It was suggested the usage of laws of algebra with logic, arithmetic, timed operations to implement the equivalent transformations of nets.

Keywords: Timed Petri net; Multi-channel transition; State equation; Transmission function; Functional equivalence

Visualization of production processes in software tools of dispatcher at machine-building enterprise // Avtometriya, 1990, p. 90-93. (with Sleptsov A.I.)

Approach to development of software tools of dispatcher for machine-building enterprise based on visualization of production processes with special timed Petri nets was suggested. Features of implemented tools system "Opera-Topaz" were described. It provides the effective man-computer solution of tasks in the field of enterprise planning, management and control.

Keywords: Management; Petri net; Timetable; Jobs; Resources