EQUATIONAL SPECIFICATIONS, COMPLETE TERM REWRITING-SYSTEMS, AND COMPUTABLE AND SEMICOMPUTABLE ALGEBRAS

Authors
BERGSTRA JA TUCKER JV
Citation
Ja. Bergstra et Jv. Tucker, EQUATIONAL SPECIFICATIONS, COMPLETE TERM REWRITING-SYSTEMS, AND COMPUTABLE AND SEMICOMPUTABLE ALGEBRAS, Journal of the Association for Computing Machinery, 42(6), 1995, pp. 1194-1230
Citations number
23
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
Journal of the Association for Computing Machinery
ISSN journal
00045411 → ACNP
Volume
42
Issue
6
Year of publication
1995
Pages
1194 - 1230
Database
ISI
SICI code
Abstract
We classify the computable and semicomputable algebras in terms of fin ite equational initial algebra specifications and their properties as term term rewriting systems, such as completeness. Further results on properties of these specifications, such as on their size and orthogon ality, are provided which show that our main results are the best poss ible.