Wyniki wyszukiwania - BazTech

1

Towards a universal model of action

Winkowski J.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2016

|

Nr 1035

1--32

EN

In the paper a model of action is described that is universal in the sense that it may serve to represent actions of any kind: discrete, continuous, or partially discrete and partially continuous. The model is founded on the assumption that an action is executed in a universe of objects. It describes how the possible executions change the situation of involved objects. It exploits the fact that executions are represented such that fragments of executions are represented such that their closed segments admit only trivial automorphisms. The model has an algebraic strucure and it is a directed complete partial order.

PL

Praca zawiera opis pewnego modelu akcji, który jest uniwersalny w tym sensie, że może służyć do reprezentowania akcji dowolnego rodzaju: dyskretnych, ciągłych, lub częściowo dyskretnych i częściowo ciągłych. Model ten opiera się na za lożeniu, że akcja jest wykonywana w pewnym środowisku obiektów. Opisuje jak możliwe wykonania akcji zmieniają sytuacje zaangażowanych obiektów. Wykorzystuje fakt, że fragmenty wykonań akcji są reprezentowane tak, że ich ograniczone segmenty mają jedynie trywialne automorfizmy. Model ma pewną strukturę algebraiczną i częściowy porządek przy którym podzbiory skierowane mają kresy górne.

2

On the Completion of Rough Sets System Determined by Arbitrary Binary Relations

Umadevi D.

Fundamenta Informaticae

|

2015

|

Vol. 137, nr 3

413--424

EN

In this paper, a solution is given to the problem proposed by J¨arvinen in [8]. A smallest completion of the rough sets system determined by an arbitrary binary relation is given. This completion, in the case of a quasi order, coincides with the rough sets system which is a Nelson algebra. Further, the algebraic properties of this completion has been studied.

3

On Algorithmic Study of Non-negative Posets of Corank at Most Two and their Coxeter-Dynkin Types

Gąsiorek M., Zając K.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 4

347--367

EN

Here we study the connected posets I that are non-negative of corank one or two, in the sense that the symmetric Gram matrix 1/2 (CI + Citr) ∊ Mn(Q) is positive semi-definite of corank one or two, where CII ∊ Mn(Z) is the incidence matrix of I. We study such posets I by means of the Dynkin type DynI and the Coxeter polynomial coxI (t) := det(t.E - CoxI) ∊ Z[t], where CoxI := CI + CItr ∊ Mn(Z) is the Coxeter matrix of I. Among other results, we develop an algorithmic technique that allows us to compute a complete list of such posets I, with |I| ≤ 16, their Dynkin types DynI, and the Coxeter polynomials coxI(t) ∊Z[t]. We prove that, given a pair of such connected posets I and J, the incidence matrices CI and CJ are Z-congruent if and only if coxI (t) = coxJ (t) and DynI = DynJ

4

Algorithms for Isotropy Groups of Cox-regular Edge-bipartite Graphs

Kasjan S., Simson D.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 3

249--275

EN

This paper can be viewed as a third part of our paper [Fund. Inform. 2015, in press]. Following our Coxeter spectral study in [Fund. Inform. 123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827-854] of the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study a larger category RBigrn of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual Z-congruences ~Z and ≈Z. The positive graphs Δ in RBigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ ⊂ C, the irreduciblemesh root systems of Dynkin types Bn, n ≥ 2, Cn, n ≥ 3, F4, G2, the isotropy group G1(n, Z)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure Appl. Algebra 215(2011), 13-24]. Here we present combinatorial algorithms for constructing the isotropy groups G1(n,Z)Δ. One of the aims of our three paper series is to develop computational tools for the study of the Zcongruence ~Z and the following Coxeter spectral analysis question: "Does the congruence Δ ≈Z Δ' holds, for any pair of connected positive graphsΔ,Δ' ∈ RBigrn such that speccΔ = speccΔ' and the numbers of loops in Δ and Δ' coincide?". For this purpose, we construct in this paper a extended inflation algorithm Δ → DΔ, with DΔ ~Z Δ, that allows a reduction of the question to the Coxeter spectral study of the G1(n,Z)D-orbits in the set MorD ⊂ Mn(Z) of matrix morsifications of the associated edge-bipartite Dynkin graph D = DΔ ∈ RBigrn. We also outline a construction of a numeric algorithm for computing the isotropy group G1(n,Z)Δ of any connected positive edge-bipartite graph Δ in RBigrn. Finally, we compute the finite isotropy group G1(n,Z)D, for each of the Cox-regular edge-bipartite Dynkin graphs D.

5

Relatively orthocomplemented skew nearlattices in Rickart rings

Cırulis J.

Demonstratio Mathematica

|

2015

|

Vol. 48, nr 4

493--508

EN

A class of (right) Rickart rings, called strong, is isolated. In particular, every Rickart *-ring is strong. It is shown in the paper that every strong Rickart ring R admits a binary operation which turns R into a right normal band having an upper bound property with respect to its natural order ≤; such bands are known as right normal skew nearlattices. The poset (R, ≤) is relatively orthocomplemented; in particular, every initial segment in it is orthomodular. The order ≤ is actually a version of the so called right-star order. The one-sided star orders are well-investigated for matrices and recently have been generalized to bounded linear Hilbert space operators and to abstract Rickart *-rings. The paper demonstrates that they can successfully be treated also in Rickart rings without involution.

6

Lattices of annihilators in commutative algebras over fields

Jastrzębska M., Krempa J.

Demonstratio Mathematica

|

2015

|

Vol. 48, nr 4

546--553

EN

Let K be any field and L be any lattice. In this note we show that L is a sublattice of annihilators in an associative and commutative K-algebra. If L is finite, then our algebra will be finite dimensional over K.

7

Free algebras over a poset in varieties of Łukasiewicz-Moisil algebras

Figallo Orellano A., Gallardo C.

Demonstratio Mathematica

|

2015

|

Vol. 48, nr 3

348--356

EN

A general construction of the free algebra over a poset in varieties finitely generated is given in [8]. In this paper, we apply this to the varieties of Łukasiewicz–Moisil algebras, giving a detailed description of the free algebra over a finite poset (X, ≤), Free n ((X, ≤)). As a consequence of this description, the cardinality of Free n ((X, ≤)) is computed for special posets.

8

Mesh Algorithms for Solving Principal Diophantine Equations, Sand-glass Tubes and Tori of Roots

Simson D.

Fundamenta Informaticae

|

2011

|

Vol. 109, nr 4

425-462

EN

We study integral solutions of diophantine equations q(x) = d, where x = (x1, . . . , xn), n ≥1, d .∈Z is an integer and q : Z^n →Z is a non-negative homogeneous quadratic form. Contrary to the negative solution of the Hilbert’s tenth problem, for any such a form q(x), we give efficient algorithms describing the set Rq(d) of all integral solutions of the equation q(x) = d in a Φ_A-mesh translation quiver form. We show in Section 5 that usually the set Rq(d) has a shape of a Φ_A-mesh sand-glass tube or of a A-mesh torus, see 5.8, 5.10, and 5.13. If, in addition, the subgroup Ker q = {v ∈Z^n; q(v) = 0} of Zn is infinite cyclic, we study the solutions of the equations q(x) = 1 by applying a defect δ_A : Z^n → Z and a reduced Coxeter number čA ∈ N defined by means of a morsification b_A : Zn × Zn → Z of q, see Section 4. On this way we get a simple graphical algorithm that constructs all integral solutions in the shape of a mesh translation oriented graph consisting of Coxeter A-orbits. It turns out that usually the graph has at most three infinite connected components and each of them has an infinite band shape, or an infinite horizontal tube shape, or has a sand-glass tube shape. The results have important applications in representation theory of groups, algebras, quivers and partially ordered sets, as well as in the study of derived categories (in the sense of Verdier) of module categories and categories of coherent sheaves over algebraic varieties.

9

Extended-order algebras as a generalization of posets

Solovyov S. A.

Demonstratio Mathematica

|

2011

|

Vol. 44, nr 3

589-614

EN

Motivated by the recent study of several researchers on extended-order algebras introduced by C.Guido and P.Toto as a possible common framework for the majority of algebraic structures used in many valued mathematics,the paper focuses on the properties of homomorphisms of the new structures,considering extended order algebras as a generalization of partially ordered sets.The manuscript also introduces the notion of extended-relation algebra providing a new framework for developing the theory of rough sets.

10

An Algorithmic Solution of a Birkhoff Type Problem

Simson D., Wojewódzki M.

Fundamenta Informaticae

|

2008

|

Vol. 83, nr 4

389-410

EN

We give an algorithmic solution in a simple combinatorial data of Birkhoff?s type problem studied in [22] and [25], for the category repft(I, K[t]/(tm)) of filtered I-chains of modules over the K-algebra K[t]/(tm) of K-dimension m < ?, where m ^(3) 2, I is a finite poset with a unique maximal element, and K is an algebraically closed field. The problem is to decide when the indecomposable objects of the category repft(I, K[t]/(tm)) admit a classification by means of a suitable parametrisation. A complete solution of this important problem of the modern representation theory is contained in Theorems 2.4 and 2.5. We show that repft(I, K[t]/(tm)) admits such a classification if and only if (I, m) is one of the pairs of the finite list presented in Theorem 2.4, and such a classification does not exist for repft(I, K[t]/(tm)) if and only if the pair (I, m) is bigger than or equal to one of the minimal pairs of the finite list presented in Theorem 2.5. The finite lists are constructed by producing computer accessible algorithms and computational programs written in MAPLE and involving essentially the package CREP (see Section 4). On this way the lists are obtained as an effect of computer computations. In particular, the solution we get shows an importance of the computer algebra technique and computer computations in solving difficult and important problems of modern algebra.

11

Exploiting the Lattice of Ideals Representation of a Poset

De Loof K., De Meyer H., De Baets B.

Fundamenta Informaticae

|

2006

|

Vol. 71, nr 2,3

309-321

EN

In this paper, we demonstrate how some simple graph counting operations on the ideal lattice representation of a partially ordered set (poset) P allow for the counting of the number of linear extensions of P, for the random generation of a linear extension of P, for the calculation of the rank probabilities for every x Î P, and, finally, for the calculation of the mutual rank probabilities Prob(x > y) for every (x,y) Î P2. We show that all linear extensions can be counted and a first random linear extension can be generated in O(|I(P)|źw(P) ) time, while every subsequent random linear extension can be obtained in O( |P|źw(P)) time, where |I(P)| denotes the number of ideals of the poset P and w(P) the width of the poset P. Furthermore, we show that all rank probability distributions can be computed in O( |I(P)|źw(P)) time, while the computation of all mutual rank probabilities requires O(|I(P)|ź|P|źw(P)) time, to our knowledge the fastest exact algorithms currently known. It is well known that each of the four problems described above resides in the class of #P-complete counting problems, the counterpart of the NP-complete class for decision problems. Since recent research has indicated that the ideal lattice representation of a poset can be obtained in constant amortized time, the stated time complexity expressions also cover the time needed to construct the ideal lattice representation itself, clearly favouring the use of our approach over the standard approach consisting of the exhaustive enumeration of all linear extensions.