Free Term Algebras

Grzegorz Bancerek

Formalized Mathematics (2012)

  • Volume: 20, Issue: 3, page 239-256
  • ISSN: 1426-2630

Abstract

top
We interoduce a new characterization of algebras of normal forms of term rewriting systems [35] as algerbras of term free in itself (any function from free generators into the algebra generates endomorphism of the algebra). Introduced algebras are free in classes of algebras satisfying some sets of equalities. Their universes are subsets of all terms and the denotations of operation symbols are partially identical with the operations of construction of terms. These algebras are compiler algebras requiring some equalities of terms, e.g., associativity of addition.

How to cite

top

Grzegorz Bancerek. "Free Term Algebras." Formalized Mathematics 20.3 (2012): 239-256. <http://eudml.org/doc/268221>.

@article{GrzegorzBancerek2012,
abstract = {We interoduce a new characterization of algebras of normal forms of term rewriting systems [35] as algerbras of term free in itself (any function from free generators into the algebra generates endomorphism of the algebra). Introduced algebras are free in classes of algebras satisfying some sets of equalities. Their universes are subsets of all terms and the denotations of operation symbols are partially identical with the operations of construction of terms. These algebras are compiler algebras requiring some equalities of terms, e.g., associativity of addition.},
author = {Grzegorz Bancerek},
journal = {Formalized Mathematics},
language = {eng},
number = {3},
pages = {239-256},
title = {Free Term Algebras},
url = {http://eudml.org/doc/268221},
volume = {20},
year = {2012},
}

TY - JOUR
AU - Grzegorz Bancerek
TI - Free Term Algebras
JO - Formalized Mathematics
PY - 2012
VL - 20
IS - 3
SP - 239
EP - 256
AB - We interoduce a new characterization of algebras of normal forms of term rewriting systems [35] as algerbras of term free in itself (any function from free generators into the algebra generates endomorphism of the algebra). Introduced algebras are free in classes of algebras satisfying some sets of equalities. Their universes are subsets of all terms and the denotations of operation symbols are partially identical with the operations of construction of terms. These algebras are compiler algebras requiring some equalities of terms, e.g., associativity of addition.
LA - eng
UR - http://eudml.org/doc/268221
ER -

References

top
  1. [1] Grzegorz Bancerek. Cardinal numbers. Formalized Mathematics, 1(2):377-382, 1990. 
  2. [2] Grzegorz Bancerek. Introduction to trees. Formalized Mathematics, 1(2):421-427, 1990. 
  3. [3] Grzegorz Bancerek. K¨onig’s theorem. Formalized Mathematics, 1(3):589-593, 1990. 
  4. [4] Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990. 
  5. [5] Grzegorz Bancerek. Cartesian product of functions. Formalized Mathematics, 2(4):547-552, 1991. 
  6. [6] Grzegorz Bancerek. K¨onig’s lemma. Formalized Mathematics, 2(3):397-402, 1991. 
  7. [7] Grzegorz Bancerek. Sets and functions of trees and joining operations of trees. FormalizedMathematics, 3(2):195-204, 1992. 
  8. [8] Grzegorz Bancerek. Joining of decorated trees. Formalized Mathematics, 4(1):77-82, 1993. 
  9. [9] Grzegorz Bancerek. Reduction relations. Formalized Mathematics, 5(4):469-478, 1996. 
  10. [10] Grzegorz Bancerek. Subtrees. Formalized Mathematics, 5(2):185-190, 1996. 
  11. [11] Grzegorz Bancerek. Terms over many sorted universal algebra. Formalized Mathematics, 5(2):191-198, 1996. 
  12. [12] Grzegorz Bancerek. Translations, endomorphisms, and stable equational theories. FormalizedMathematics, 5(4):553-564, 1996. 
  13. [13] Grzegorz Bancerek. Algebra of morphisms. Formalized Mathematics, 6(2):303-310, 1997. 
  14. [14] Grzegorz Bancerek. Institution of many sorted algebras. Part I: Signature reduct of an algebra. Formalized Mathematics, 6(2):279-287, 1997. 
  15. [15] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Formalized Mathematics, 1(1):107-114, 1990.[16] Grzegorz Bancerek and Artur Korniłowicz. Yet another construction of free algebra. Formalized Mathematics, 9(4):779-785, 2001. 
  16. [17] Grzegorz Bancerek and Piotr Rudnicki. On defining functions on trees. Formalized Mathematics, 4(1):91-101, 1993. 
  17. [18] Grzegorz Bancerek and Piotr Rudnicki. The set of primitive recursive functions. FormalizedMathematics, 9(4):705-720, 2001. 
  18. [19] Grzegorz Bancerek and Andrzej Trybulec. Miscellaneous facts about functions. FormalizedMathematics, 5(4):485-492, 1996. 
  19. [20] Ewa Burakowska. Subalgebras of many sorted algebra. Lattice of subalgebras. FormalizedMathematics, 5(1):47-54, 1996. 
  20. [21] Czesław Bylinski. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990. 
  21. [22] Czesław Bylinski. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990. 
  22. [23] Czesław Bylinski. Partial functions. Formalized Mathematics, 1(2):357-367, 1990. 
  23. [24] Czesław Bylinski. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990. 
  24. [25] Agata Darmochwał. Finite sets. Formalized Mathematics, 1(1):165-167, 1990. 
  25. [26] Artur Korniłowicz. Some basic properties of many sorted sets. Formalized Mathematics, 5(3):395-399, 1996. 
  26. [27] Artur Korniłowicz. Equations in many sorted algebras. Formalized Mathematics, 6(3):363-369, 1997. 
  27. [28] Małgorzata Korolkiewicz. Homomorphisms of many sorted algebras. Formalized Mathematics, 5(1):61-65, 1996. 
  28. [29] Małgorzata Korolkiewicz. Many sorted quotient algebra. Formalized Mathematics, 5(1):79-84, 1996. 
  29. [30] Jarosław Kotowicz. Functions and finite sequences of real numbers. Formalized Mathematics, 3(2):275-278, 1992. 
  30. [31] Adam Naumowicz. On Segre’s product of partial line spaces. Formalized Mathematics, 9(2):383-390, 2001. Zbl1019.51003
  31. [32] Andrzej Nedzusiak. Probability. Formalized Mathematics, 1(4):745-749, 1990. 
  32. [33] Beata Padlewska. Families of sets. Formalized Mathematics, 1(1):147-152, 1990. 
  33. [34] Beata Perkowska. Free many sorted universal algebra. Formalized Mathematics, 5(1):67-74, 1996. 
  34. [35] D.M. Gabbay S. Abramsky and T.S.E. Maibaum, editors. Handbook of Logic inComputer Science, chapter Term Rewriting Systems, pages 1-116. Oxford University Press, New York, 1992. http://www.informatik.uni-bremen.de/agbkb/lehre/-rbs/texte/Klop-TR.pdf. 
  35. [36] Andrzej Trybulec. Binary operations applied to functions. Formalized Mathematics, 1(2):329-334, 1990. 
  36. [37] Andrzej Trybulec. Many sorted sets. Formalized Mathematics, 4(1):15-22, 1993. 
  37. [38] Andrzej Trybulec. Many sorted algebras. Formalized Mathematics, 5(1):37-42, 1996. 
  38. [39] Andrzej Trybulec. A scheme for extensions of homomorphisms of many sorted algebras. Formalized Mathematics, 5(2):205-209, 1996. 
  39. [40] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990. 
  40. [41] Edmund Woronowicz. Many argument relations. Formalized Mathematics, 1(4):733-737, 1990. 
  41. [42] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990. 
  42. [43] Edmund Woronowicz and Anna Zalewska. Properties of binary relations. FormalizedMathematics, 1(1):85-89, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.