A Complete Finite Axiomatisation of the Equational Theory of Common Meadows

被引:1
|
作者
Bergstra, Jan A. [1 ]
Tucker, John v [2 ]
机构
[1] Univ Amsterdam, Informat Inst, Amsterdam, Netherlands
[2] Swansea Univ, Dept Comp Sci, Swansea, Wales
关键词
arithmetical data type; division by zero; error value; common meadow; fracterm; fracterm calculus; equational theory; FRACTIONS;
D O I
10.1145/3689211
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We analyse abstract data types that model numerical structures with a concept of error. Specifically, we focus on arithmetic data types that contain an error value perpendicular to whose main purpose is to always return a value for division. To rings and fields, we add a division operator x/y and study a class of algebras called common meadows wherein x/0 = perpendicular to. The set of equations true in all common meadows is named the equational theory of common meadows. We give a finite equational axiomatisation of the equational theory of common meadows and prove that it is complete and that the equational theory is decidable.
引用
收藏
页数:28
相关论文
共 31 条
  • [1] Meadows and the equational specification of division
    Bergstra, J. A.
    Hirshfeld, Y.
    Tucker, J. V.
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (12-13) : 1261 - 1271
  • [3] ON THE EQUATIONAL THEORY OF PROJECTION LATTICES OF FINITE VON NEUMANN FACTORS
    Herrmann, Christian
    JOURNAL OF SYMBOLIC LOGIC, 2010, 75 (03) : 1102 - 1110
  • [4] On The Axioms Of Common Meadows: Fracterm Calculus, Flattening And Incompleteness
    Bergstra, Jan A.
    Tucker, John, V
    COMPUTER JOURNAL, 2023, 66 (07) : 1565 - 1572
  • [5] An equational theory for trilattices
    Biedermann, K
    ALGEBRA UNIVERSALIS, 1999, 42 (04) : 253 - 268
  • [6] An equational theory for trilattices
    K. Biedermann
    algebra universalis, 1999, 42 : 253 - 268
  • [7] The structure of finite meadows
    Bethke, Inge
    Rodenburg, Piet
    Sevenster, Arjen
    JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING, 2015, 84 (02) : 276 - 282
  • [8] The equational theory of Kleene lattices
    Andreka, Hajnal
    Mikulas, Szabolcs
    Nemeti, Istvan
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (52) : 7099 - 7108
  • [9] On equational theories of classes of finite rings
    V. Y. Popov
    Siberian Mathematical Journal, 1999, 40 : 556 - 564
  • [10] The equational theory of regular words
    Bloom, SL
    Ésik, Z
    INFORMATION AND COMPUTATION, 2005, 197 (1-2) : 55 - 89