Applying term rewriting to partial algebra theory

• Autorzy: Dojer N.
• Języki publikacji: EN

Abstrakty

EN

In our paper we apply term rewriting to decidability of equations in classes of partial algebras, as well as to embeddability of partial algebras into classes of total ones. We follow the approach to partial algebras introduced by H.-J. Kreowski in [13], in which (classes of) partial algebras are described by means of (classes of) total ones.

Słowa kluczowe

EN

partial algebras; term rewriting; based specification; embeddability problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 63, nr 4
• Strony: 375--384
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Dojer N.

• Faculty of Mathematics, Informatics and Mechanics, Warsaw University, ul. Banacha 2, 02-097 Warszawa, Poland,

Bibliografia

• [1] Andréka, H., Németi, I.: Generalization of the concept of variety and quasivariety to partial algebras through category theory, Dissertationes Math. (Rozprawy Mat.), 204, 1983, 51.
• [2] Baader, F., Nipkow, T.: Term rewriting and all that, Cambridge University Press, Cambridge, 1998.
• [3] Bachmair, L.: Proof by consistency in equational theories, Proceedings 3rd IEEE Symposium on Logic in Computer Science, Edinburgh (UK), 1988.
• [4] Bartol, W., Rosselló, F.: On the class of weak subalgebras of a variety, Manuscript.
• [5] Broy, M., Wirsing, M.: Partial abstract types, Acta Inform., 18(1), 1982/83, 47-64.
• [6] Burmeister, P.: An embedding theorem for partial algebras and the free completion of a free partial algebra within a primitive class, Algebra Universalis, 3, 1973, 271-279.
• [7] Burmeister, P.: A model theoretic oriented approach to partial algebras, vol. 32 of Mathematical Research, Akademie-Verlag, Berlin, 1986, Introduction to theory and application of partial algebras. Part I.
• [8] Dojer, N.: A new presentation of existential varieties, in: Contributions to general algebra. 14, Heyn, Klagenfurt, 2004, 53-57.
• [9] Evans, T.: The word problem for abstract algebras, J. London Math. Soc., 26, 1951, 64-71.
• [10] Evans, T.: Embeddability and the word problem, J. London Math. Soc., 28, 1953, 76-80.
• [11] Kirchner, C., Kirchner, H.: Rewriting Solving Proving, http://www.loria.fr/˜ckirchne.
• [12] Kounalis, E.: Testing for inductive (co)-reducibility, in: CAAP ’90 (Copenhagen, 1990), vol. 431 of Lecture Notes in Comput. Sci., Springer, Berlin, 1990, 221-238.
• [13] Kreowski, H.-J.: Partial algebras flow from algebraic specifications, in: Automata, languages and programming (Karlsruhe, 1987), vol. 267 of Lecture Notes in Comput. Sci., Springer, Berlin, 1987, 521-530.
• [14] Reddy, U. S.: Term rewriting induction, in: 10th International Conference on Automated Deduction (Kaiserslautern, 1990), vol. 449 of Lecture Notes in Comput. Sci., Springer, Berlin, 1990, 162-177.
• [15] Reichel, H.: Structural induction on partial algebras, vol. 18 of Mathematical Research, Akademie-Verlag, Berlin, 1984, Introduction to theory and application of partial algebras. Part II.
• [16] Schmidt, J.: A general existence theorem on partial algebras and its special cases, Colloq. Math., 14, 1966, 73-87.
• [17] Słomiński, J.: A theory of extensions of quasi-algebras to algebras, Rozprawy Mat., 40, 1964, 63.
• [18] Słomiński, J.: Peano-algebras and quasi-algebras, Dissertationes Math. Rozprawy Mat., 57, 1968, 60.
• [19] Wirsing, M.: Algebraic specification, in: Handbook of theoretical computer science, Vol. B, Elsevier, Amsterdam, 1990, 675-788.