• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 12
Sort:
by name
by year
Article
Lomazova I. A., Romanov I. V. Fundamenta Informaticae. 2013. Vol. 128. No. 1-2. P. 129-141.

In this work we consider modeling of services with workflow modules, which form a Petri net subclass. The service compatibility problem is to answer the question, whether two services fit together, i.e. whether the composed system is correct. We study complementarity of resources, produced/consumed by two services—a necessary condition for the service compatibility. Resources, which are produced/consumed by a service, are represented as a multiset language. We define an algebra of multiset languages and present algorithms for checking conformance of resources for two given well-structured workflow modules.

Added: Nov 18, 2013
Article
Vladislav Podymov. Fundamenta Informaticae. 2016. Vol. 147. No. 2-3. P. 315-336.
For many program analysis problems it is useful to have means to efficiently prove that given programs have similar (equivalent) behaviors. Unfortunately, in most cases to prove the behavioral equivalence is an undecidable problem. A common way to overcome such undecidability is to consider a model of programs with an abstract semantics based on the real one, in which only some simple properties are captured, and to provide an efficient equivalence-checking algorithm for the model. We focus on two kinds of properties of data-modifying statements of imperative programs. Statements a and b are commutative, if the execution of sequences ab and ba lead to the same result. A statement b is (left-)absorptive for a statement a, if the execution of sequences ab and b lead to the same result. We consider propositional program models in which commutativity and absorption properties are caprtured (CA-models). Formally, data states for a CA-model are elements of a monoid over the set of statement symbols, defined by an arbitrary set of relations of the form ab = ba (for commutativity) and ab = b (for absorption). We propose an equivalence-checking algorithm for CA-models based on (what we call) progressive monoids. The algorithm terminates in time polynomial in size of programs. As a consequence, we prove a polynomial-time decidability for the equivalence problem in such CA-models.
Added: Oct 9, 2016
Article
Revenko A., Kuznetsov S. Fundamenta Informaticae. 2012. Vol. 4. No. 115. P. 377-394.

An approach for studying relations between properties of functions on sets is proposed. The approach is based on Attribute Exploration. 16 properties of functions are considered, among them monotonicity, idempotency, path independence, exchange properties, convexity, etc. Example functions are partially computer generated on the powersets of sets with 2, 3 and 4 elements. Attribute Exploration is run on contexts where objects are functions and attributes are 16 function properties. Minimal implication bases are presented. The list of proved implications is presented and discussed.

Added: Dec 31, 2012
Article
Vladimir A. Bashkin, Lomazova I. A. Fundamenta Informaticae. 2012. Vol. 120. No. 3-4. P. 243-257.

Resource-driven automata (RDA) are finite automata, sitting in the nodes of a finite system net and asynchronously consuming/producing shared resources through input/output system ports (arcs of the system net). RDAs themselves may be resources for each other, thus allowing the highly flexible structure of the model. It was proved earlier, that RDA-nets are expressively equivalent to Petri nets. In this paper the new formalism of cellular RDAs is introduced. Cellular RDAs are RDA-nets with an infinite regularly structured system net. We build a hierarchy of cellular RDA classes on the basis of restrictions on the underlying grid. The expressive power of several major classes of 1-dimensional grids is studied.

Added: Nov 28, 2012
Article
Lomazova I. A., Sidorova N., Serebrenik A. et al. Fundamenta Informaticae. 2007. Vol. 79. No. 3-4. P. 347-362.
Added: Mar 13, 2010
Article
Kryszkiewicz M., Obiedkov Sergei, Ras Z. W. Fundamenta Informaticae. 2012. Vol. 115. No. 4. P. i-ii.

The paper is the preface to the special issue of the Fundamenta Informaticae journal on concept lattices and their applications. It is focused on recent developments in Formal Concept Analysis (FCA), as well as on applications in closely related areas such as data mining, information retrieval, knowledge management, data and knowledge engineering, and lattice theory.

Added: Jan 25, 2013
Article
Lomazova I. A., Popova-Zeugmann L. Fundamenta Informaticae. 2016. Vol. 143. No. 1-2. P. 101-112.

In this paper we examine how it is possible to control Petri net behavior with the help of transition priorities. Controlling here means forcing a process to behave in a stable way by ascribing priorities to transitions and hence transforming a classic Petri net into a Priority Petri net. For Petri net models stability is often ensured by liveness and boundedness. These properties are crucial in many application areas, e.g. workflow modeling, embedded systems design, and bioinformatics. In this paper we study the problem of transforming a given live, but unbounded Petri net into a live and bounded one by adding priority constraints. We specify necessary conditions for the solvability of this problem and present an algorithm for ascribing priorities to net transitions in such a way that the resulting net becomes bounded while staying live.

Added: Oct 12, 2015
Article
Kalenkova A. A., Lomazova I. A. Fundamenta Informaticae. 2014. Vol. 133. No. 2-3. P. 197-209.

Process mining is a relatively new field of computer science which deals with process discovery and analysis based on event logs. In this work we consider the problem of discovering workflow nets with cancellation regions from event logs. Cancellations occur in the majority of real-life event logs. In spite of huge amount of process mining techniques little has been done on cancellation regions discovery. We show that the state-based region algorithm gives labeled Petri nets with overcomplicated control flow structure for logs with cancellations. We propose a novel method to discover cancellation regions from the transition systems built on event logs and show the way to construct equivalent workflow net with reset arcs to simplify the control flow structure.

Added: Sep 30, 2014
Article
Lomazova I. A. Fundamenta Informaticae. 2010. Vol. 101. No. 1-2. P. 59-70.

In this work we consider modeling of workflow systems with Petri nets. To increase flexibility and give tools for workflow models re-engineering we extend the formalism of workflow nets by considering systems of interacting nets. Then we study soundness - the main correctness property of workflow processes - and show, that for a special class of structured workflow system soundness can be proved in compositional way.

 

 

Added: Nov 19, 2012
Article
Dworzanski L. W., Lomazova I. A. Fundamenta Informaticae. 2012. Vol. 120. No. 3-4. P. 275-293.

Nested Petri nets (NP-nets) are Petri nets with net tokens. The liveness and boundedness problems are undecidable for two-level NP-nets. Boundedness is in EXPSPACE and liveness is in EXPSPACE or worse for plain Petri nets. However, for some restricted classes, e.g. for plain free-choice Petri nets, problems become more amenable to analysis. There is a polynomial time algorithm to check if a free-choice Petri net is live and bounded.

In this paper we prove, that for NP-nets boundedness can be checked in a compositional way, and define restrictions, under which liveness is also compositional. These results give a base to establish boundedness and liveness for NP-nets by checking these properties for separate plain components, which can belong to tractable Petri net subclasses, or be small enough for model checking.

Added: Nov 28, 2012
Article
Панкратьева В. В., Kuznetsov S. Fundamenta Informaticae. 2012. Vol. 115. No. 4. P. 265-277.

Relationships between proto-fuzzy concepts, crisply generated fuzzy concepts, and pattern structures are considered. It is shown that proto-fuzzy concepts are closely related to crisply generated fuzzy concepts in the sense that the mappings involved in the definitions coincide for crisp subsets of attributes. Moreover, a proto-fuzzy concept determines a crisp subset of attributes, which generates a (crisply generated) fuzzy concept. However, the reverse is true only in part: given a crisp subset of attributes, one can find a proto-fuzzy concept whose intent includes (but not necessarily coincides with) the given subset of attributes. Interval pattern concepts are shown to be related to crisply generated formal concepts. In particular, every crisply closed subset of objects is an extent of an interval pattern concept. Also, we establish some properties of the collection of formal concepts for a given fuzzy context.

Added: Jan 29, 2013
Article
Vladimir A. Bashkin, Lomazova I. A. Fundamenta Informaticae. 2011. Vol. 109. No. 3. P. 223-236.

A new formalism of Resource Driven Automata Nets (RDA-nets) is presented. A RDAnet has two levels: a system level is represented by a net of active resources, describing distribution of agents/resources and their interactions; agents in an object level are finite automata, communicating via ports and shared resources of a system level. RDA-nets are assigned for modeling mobility in multi-agent systems from the resource dependence perspective. We prove that RDA-nets have the same expressive power as Petri nets and give examples of modeling agent communications, dynamics and mobility.

Added: Feb 2, 2013