The rational numbers as an abstract data type

被引:46
作者
Bergstra, J. A.
Tucker, J. V.
机构
[1] Univ Amsterdam, Inst Informat, NL-1098 SJ Amsterdam, Netherlands
[2] Univ Coll Swansea, Dept Comp Sci, Swansea SA2 8PP, W Glam, Wales
关键词
verification; languages; rational numbers; field; meadow; division-by-zero; total versus partial functions; abstract data types; algebraic specification; equations; initial algebra; computable algebras;
D O I
10.1145/1219092.1219095
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We give an equational specification of the field operations on the rational numbers under initial algebra semantics using just total field operations and 12 equations. A consequence of this specification is that 0(-1) = 0, an interesting equation consistent with the ring axioms and many properties of division. The existence of an equational specification of the rationals without hidden functions was an open question. We also give an axiomatic examination of the divisibility operator, from which some interesting new axioms emerge along with equational specifications of algebras of rationals, including one with the modulus function. Finally, we state some open problems, including: Does there exist an equational specification of the field operations on the rationals without hidden functions that is a complete term rewriting system?
引用
收藏
页数:25
相关论文
共 36 条
[1]   On abstract data types presented by multiequations [J].
Adámek, J ;
Hébert, M ;
Rosicky, J .
THEORETICAL COMPUTER SCIENCE, 2002, 275 (1-2) :427-462
[2]  
[Anonymous], 1978, CURRENT TRENDS PROGR
[3]  
[Anonymous], HDB LOGIC COMPUTER S
[4]  
[Anonymous], 1998, THEOREM PROVING REAL
[5]  
[Anonymous], 1993, ENCY MATH APPL, DOI DOI 10.1017/CBO9780511551574
[6]   Elementary algebraic specifications of the rational function field [J].
Bergstra, J. A. .
LOGICAL APPROACHES TO COMPUTATIONAL BARRIERS, PROCEEDINGS, 2006, 3988 :40-54
[7]   THE COMPLETENESS OF THE ALGEBRAIC SPECIFICATION METHODS FOR COMPUTABLE DATA-TYPES [J].
BERGSTRA, JA ;
TUCKER, JV .
INFORMATION AND CONTROL, 1982, 54 (03) :186-200
[8]   Equational specifications, complete term rewriting systems, and computable and semicomputable algebras [J].
Bergstra, JA ;
Tucker, JV .
JOURNAL OF THE ACM, 1995, 42 (06) :1194-1230
[9]   INITIAL AND FINAL ALGEBRA-SEMANTICS FOR DATA TYPE SPECIFICATIONS - 2 CHARACTERIZATION THEOREMS [J].
BERGSTRA, JA ;
TUCKER, JV .
SIAM JOURNAL ON COMPUTING, 1983, 12 (02) :366-387
[10]   ALGEBRAIC SPECIFICATIONS OF COMPUTABLE AND SEMICOMPUTABLE DATA-TYPES [J].
BERGSTRA, JA ;
TUCKER, JV .
THEORETICAL COMPUTER SCIENCE, 1987, 50 (02) :137-181