Fundamenta Informaticae - Volume 184, issue 2

Authors: Fajardo, William

Article Type: Research Article

Abstract: In this paper we present a right version of the Buchberger algorithm over skew Poincaré-Birkhoff-Witt extensions (skew PBW extensions for short) defined by Gallego and Lezama [5]. This algorithm is an adaptation of the left case given in [3]. In particular, we developed a right version of the division algorithm and from this we built the right Grbner bases theory over bijective skew PBW extensions. The algorithms were implemented in the SPBWE library developed in Maple, this paper includes an application of these to the membership problem. The theory developed here is fundamental to complete the SPBWE library …and thus be able to implement various homological applications that arise as result of obtaining the right Grbner bases over skew PBW extensions. Show more

Keywords: Non-commutative computational algebra, skew PBW extensions, Buchberger algorithm, Grbner bases, SPBWE library, Maple, Mathematics Subject Classification. 2021: Primary: 16Z05. Secondary: 16D40, 15A21

DOI: 10.3233/FI-2021-2093

Citation: Fundamenta Informaticae, vol. 184, no. 2, pp. 83-105, 2021

Authors: Wroński, Michał | Kijko, Tomasz | Dryło, Robert

Article Type: Research Article

Abstract: This paper presents method for obtaining high-degree compression functions using natural symmetries in a given model of an elliptic curve. Such symmetries may be found using symmetry of involution [–1] and symmetry of translation morphism τ T = P + T , where T is the n -torsion point which naturally belongs to the E (𝕂) for a given elliptic curve model. We will study alternative models of elliptic curves with points of order 2 and 4, and specifically Huff’s curves and the Hessian family of elliptic curves (like Hessian, twisted Hessian and generalized Hessian curves) …with a point of order 3. We bring up some known compression functions on those models and present new ones as well. For (almost) every presented compression function, differential addition and point doubling formulas are shown. As in the case of high-degree compression functions manual investigation of differential addition and doubling formulas is very difficult, we came up with a Magma program which relies on the Gröbner basis. We prove that if for a model E of an elliptic curve exists an isomorphism φ : E → E M , where E M is the Montgomery curve and for any P ∈ E (𝕂) holds that φ (P ) = (φ x (P ), φ y (P )), then for a model E one may find compression function of degree 2. Moreover, one may find, defined for this compression function, differential addition and doubling formulas of the same efficiency as Montgomery’s. However, it seems that for the family of elliptic curves having a natural point of order 3, compression functions of the same efficiency do not exist. Show more

Keywords: alternative models of elliptic curves, compression on elliptic curves

DOI: 10.3233/FI-2021-2094

Citation: Fundamenta Informaticae, vol. 184, no. 2, pp. 107-139, 2021

Authors: Zieliński, Bartosz

Article Type: Research Article

Abstract: We develop a multiset query and update language executable in a term rewriting system. Its most remarkable feature, besides non-standard approach to quantification and introduction of fresh values, is non-determinism — a query result is not uniquely determined by the database. We argue that this feature is very useful, e.g., in modelling user choices during simulation or reachability analysis of a data-centric business process — the intended application of our work. Query evaluation is implemented by converting the query into a terminating term rewriting system and normalizing the initial term which encapsulates the current database. A normal form encapsulates a …query result. We prove that our language can express any relational algebra query. Finally, we present a simple business process specification framework (and an example specification). Both syntax and semantics of our query language is implemented in Maude. Show more

Keywords: term rewriting, query languages, business process modelling

DOI: 10.3233/FI-2021-2095

Citation: Fundamenta Informaticae, vol. 184, no. 2, pp. 141-180, 2021