Wyniki wyszukiwania - BazTech

1

Resource Bisimilarity in Petri Nets is Decidable

Lomazova Irina, Bashkin Vladimir, Jančar Petr

Fundamenta Informaticae

|

2022

|

Vol. 186, nr 1-4

175--194

EN

Petri nets are a popular formalism for modeling and analyzing distributed systems. Tokens in Petri net models can represent the control flow state or resources produced/consumed by transition firings. We define a resource as a part (a submultiset) of Petri net markings and call two resources equivalent when replacing one of them with another in any marking does not change the observable Petri net behavior. We consider resource similarity and resource bisimilarity, two congruent restrictions of bisimulation equivalence on Petri net markings. Previously it was proved that resource similarity (the largest congruence included in bisimulation equivalence) is undecidable. Here we present an algorithm for checking resource bisimilarity, thereby proving that this relation (the largest congruence included in bisimulation equivalence that is a bisimulation) is decidable. We also give an example of two resources in a Petri net that are similar but not bisimilar.

2

A note on Browkin’s and Cao’s cancellation algorithm

Tomski A., Zakarczemny M.

Technical Transactions

|

2018

|

Vol. 115, iss. 7

153--165

EN

In this paper, we follow our generalisation of the cancellation algorithm described in our previous paper [A. Tomski, M. Zakarczemny, On some cancellation algorithms, NNTDM. 23, 2017, p. 101–114]. For f being a natural-valued function defined on ℕs , s ≥1 we remove the divisors of all possible values of ƒ in the points in which the sum of coordinates is less than or equal to n. The least non-cancelled number is called the discriminator Dƒ(n). We find formulas, or at least an estimation for this discriminator, in the case of a broad class of sequences.

PL

Kontynuujemy badania nad generalizacją algorytmu sitowego Browkina i Cao, [A. Tomski, M. Zakarczemny, On some cancellation algorithms, NNTDM. 23, 2017, p. 101–114]. Niech f będzie funkcją o wartościach w zbiorze liczb naturalnych, określoną na ℕs , s ≥1. Usuwamy dzielniki wszystkich możliwych wartości funkcji ƒ, w punktach, w których suma współrzędnych nie przekracza n. Najmniejszą niewykreśloną liczbę naturalną nazywamy dyskryminatorem Dƒ(n). W artykule uogólniamy pojęcie dyskryminatora. Znajdujemy jawne wzory lub oszacowania na dyskryminator dla szerokiej klasy ciągów.

3

Infinite families of congruences modulo 5 and 9 for overpartitions

Gu C., Hirschhorn M. D., Sellers J. A., Xia E. X. W.

Bulletin of the Polish Academy of Sciences. Mathematics

|

2018

|

Vol. 66, no. 1

31--44

EN

Let p͞(n) denote the number of overpartitions of n. Recently, a number of congruences modulo 5 and powers of 3 for p͞(n) were established by a number of authors. In particular, Treneer proved that the generating function for p͞(5n) modulo 5 is ∑∞n=0 p͞(5n)qn ≡ (q;q)6∞/(q2; q2)3∞ (mod 5). In this paper, employing elementary methods, we establish the generating function of p͞(5n) which yields the congruence due to Treneer. Furthermore, we prove some new congruences modulo 5 and 9 for p͞(n) by utilizing the fact that the generating functions for p͞(5n) modulo 5 and for p͞(3n) modulo 9 are eigenforms for half-integral weight Hecke operators.

4

Sparingly glued tolerances

Górnicka A., Grygiel J., Tyrala I.

Scientific Issues of Jan Długosz University in Częstochowa. Mathematics

|

2015

|

Vol. 20

49--54

EN

We introduce the notion of sparingly glued tolerances for lattices and then count their numbers in case of finite chains. We also estimate the density of sparingly glued tolerances among all glued tolerances on finite chains.

5

On monoids of injective partial selfmaps almost everywhere the identity

Chuchman I., Gutik O.

Demonstratio Mathematica

|

2011

|

Vol. 44, nr 4

699-722

EN

In this paper we study the semigroup (…) of injective partial selfmaps almost everywhere the identity of a set of infinite cardinality (…). We describe the Green relations on (…), all (two-sided) ideals and all congruences of the semigroup (…). We prove that every Hausdorff hereditary Baire topology (…) such that (…) is a semitopological semigroup is discrete and describe the closure of the discrete semigroup (…) in a topological semigroup. Also we show that for an infinite cardinal (…) the discrete semigroup (…) does not embed into a compact topological semigroup and construct two non-discrete Hausdorff topologies turning (…) into a topological inverse semigroup.

6

Monounary algebras with same quasiorders or retracts

Jakubíková-Studenovská D., Petrejčíková M., Pócs J.

Demonstratio Mathematica

|

2011

|

Vol. 44, nr 3

481-496

EN

Let (A, f) be a monounary algebra. We describe all monounary algebras (A, g) having the same set of quasiorders, Quord (A, f) = Quord (A, g). It is proved that if Quord (A, f) does not coincide with the set of all reflexive and transitive relations on the set A and (A, f) contains no cycle with more than two elements, then f is uniquely determined by means of Quord (A, f). In the opposite case, Quord (A, f) = Quord (A, g) if and only if Con (A, f) = Con (A, g). Further, we show that, except the case when Quord (A, f) coincides with the set of all reflexive and transitive relations, if the monounary algebras (A, f) and (A, g) have the same quasiorders, then they have the same retracts. Next we characterize monounary algebras which are determined by their sets of retracts and connected monounary algebras which are determined by their sets of quasiorders.

7

Concept Lattices of Subcontexts of a Context

Wang X., Zhang W.

Fundamenta Informaticae

|

2009

|

Vol. 90, nr 1-2

157-169

EN

As an effective tool for data analysis and knowledge processing, the theory of concept lattices has been studied extensively and applied to various fields. In order to discover useful knowledge, one often ignores some attributes according to a particular purpose and merely considers the subcontexts of a rather complex context. In this paper, we make a deep investigation on the theory of concept lattices of subcontexts. An approach to construct the concept lattice of a context is first presented by means of the concept lattices of its subcontexts. Then the concept lattices induced by all subcontexts of the context are considered as a set, and an order relation is introduced into the set. It is proved that the set together with the order relation is a complete lattice. Finally, the top element and the bottom element of the complete lattice are also obtained.

8

Implications and equivalences in orthomodular lattices

Hyčko M.

Demonstratio Mathematica

|

2005

|

Vol. 38, nr 4

777--792

EN

The present article describes a method for checking the validity of implications or equivalences in the free orthomodular lattice on two generators and in the F(a, b, c1,..., cn), which is the free orthomodular lattice generated by the elements a, 6, ci,... Cn, where the elements ci, i = 1,..., n are central in it. The structure of the previous lattices is described in [3] and [1]. The method presented is based on comparing the elements that are assigned to each expression on both sides of an implication or an equivalence. It gives a necessary condition for the implication or equivalence of arbitrary positive statements (a combination of identities and logical connectives AND and OR) to hold. When the conclusion part is an identity or a conjunction of identities, these conditions become also sufficient.

9

On (weakly) local approximation spaces of information systems

Kou H., Luo M.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 2

139--150

EN

A dependence space is an ordered pair consisting of a nonempty finite set and a congruence on its boolean lattice, and is viewed as a general model to deal with the indiscernibility-type incompleteness of information in rough set analysis. In this paper we consider the question when a dependence space can be locally approximated by a approximation space. We introduce a concept of (weakly) local approximation spaces and establish several important relationships among equivalences, reducts, and sub-reducts with respect to (weakly) local approximation spaces. It is shown that a dependence space is a local approximation space if and only if it is locally reducible if and only if the closure lattice generated by the dependence space is an atomic lattice. This result also gives a partial solution to an open problem posed by M. Novotny.

10

Σ-genomorphism of algebraic structures

Emanovský P.

Demonstratio Mathematica

|

2003

|

Vol. 36, nr 4

785--792

EN

For an algebraic structure A = (A, F, R) of type τ and a set Σ of open formulas of the first order language L(τ), the concept of Σ-closed subset of A was introduced in [3]. The set C Σ(A) of all Σ-closed subsets of A forms a complete lattice whose properties were studied in [3], [4] and [5]. Algebraic structures A, B of type τ are called CΣ-isomorphic (or Σ-isomorphic in [3]) if the lattices CΣ(A) and CΣ(B) are isomorphic. The CΣ-isomorphisms are investigated for so-called Σ-separable algebraic structures in [3]. The study of the Σ-isomorphisms of algebraic structures is continued in this paper. We introduce the concepts of Σ-genomorphism and Σ-isogenomorphism of algebraic structures and we formulate a sufficient condition under which two structures are isomorphic. We show that for Σ-separable structures the condition is also necessary. Further, we introduce the concepts of Σ-morphism, congruential E -morphism and congruence induced by a congruential Σ-morphism. We also prove Theorem on Σ-genomorphism and Theorem on Σ-morphism.

11

Standard QBCC-algebras

Halaš R., Ort J.

Demonstratio Mathematica

|

2003

|

Vol. 36, nr 1

1--10

EN

The class of QBBC-algebras was introduced and studied by the authors in ioj. These algebras model properties of the logical connective implication "=>" in which tin- validity of formulas x => y and y => x does not imply the equivalence of x and y. In ihe paper the properties of standard QBCC-algebras derived from qosets are studied.