A semantic construction of two-ary integers

Gabriele Ricci

Discussiones Mathematicae - General Algebra and Applications (2005)

  • Volume: 25, Issue: 2, page 165-219
  • ISSN: 1509-9415

Abstract

top
To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex. We use a semantic construction to get this extension. This method differs from the algebraic ones, mainly because it is able to find equational features of the extended objects. Two-ary integers turn out to form the free algebra corresponding to the Jónsson-Tarski's "paradoxical" equations. This entails that they have a "sum" operation as well as other operations of higher dimensions. Two-ary integers can provide LISP memories with convenient direct access jumps and the above low complexity hints at feasible hardware implementations.

How to cite

top

Gabriele Ricci. "A semantic construction of two-ary integers." Discussiones Mathematicae - General Algebra and Applications 25.2 (2005): 165-219. <http://eudml.org/doc/287734>.

@article{GabrieleRicci2005,
abstract = {To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex. We use a semantic construction to get this extension. This method differs from the algebraic ones, mainly because it is able to find equational features of the extended objects. Two-ary integers turn out to form the free algebra corresponding to the Jónsson-Tarski's "paradoxical" equations. This entails that they have a "sum" operation as well as other operations of higher dimensions. Two-ary integers can provide LISP memories with convenient direct access jumps and the above low complexity hints at feasible hardware implementations.},
author = {Gabriele Ricci},
journal = {Discussiones Mathematicae - General Algebra and Applications},
keywords = {universal matrix; analytic monoid; LISP; semantics; jump; free algebra},
language = {eng},
number = {2},
pages = {165-219},
title = {A semantic construction of two-ary integers},
url = {http://eudml.org/doc/287734},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Gabriele Ricci
TI - A semantic construction of two-ary integers
JO - Discussiones Mathematicae - General Algebra and Applications
PY - 2005
VL - 25
IS - 2
SP - 165
EP - 219
AB - To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex. We use a semantic construction to get this extension. This method differs from the algebraic ones, mainly because it is able to find equational features of the extended objects. Two-ary integers turn out to form the free algebra corresponding to the Jónsson-Tarski's "paradoxical" equations. This entails that they have a "sum" operation as well as other operations of higher dimensions. Two-ary integers can provide LISP memories with convenient direct access jumps and the above low complexity hints at feasible hardware implementations.
LA - eng
KW - universal matrix; analytic monoid; LISP; semantics; jump; free algebra
UR - http://eudml.org/doc/287734
ER -

References

top
  1. [1] G.J. Chaitin, Algorithmic Information Theory, IBM J. Res. Develop. 21 (1977), 350-359, 496. Zbl0362.94035
  2. [2] G.J. Chaitin, Information-Thoretic Incompleteness (World Scientific, Singapore 1992). 
  3. [3] R. Chuaqui, Axiomatic Set Theory (Nort-Holland, Mathematics Studies, Amsterdam 1981). Zbl0471.03049
  4. [4] H.B. Curry, R. Feys and W. Craig, Combinatory Logic, 1, (North-Holland, Amsterdam 1959). Zbl0175.27601
  5. [5] A. Goetz and C. Ryll-Nardzewski, On bases of abstract algebras, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 157-161. Zbl0123.00603
  6. [6] G. Grätzer, Universal Algebra, 2th ed., (Springer-Verlag, New York 1979). 
  7. [7] J.R. Hindley and J.P. Seldin, Introduction to Combinators and l-Calculus (Cambridge University Press, London 1986). Zbl0614.03014
  8. [8] B. Jónsson and A. Tarski, Two general theorems concerning free algebras, Bull. Amer. Math. Soc. 62 (1956), 554. 
  9. [9] E.G. Manes, Algebraic theories (Springer-Verlag, Berlin 1976). 
  10. [10] E. Marczewski, Independence and homomorphisms in abstract algebras, Fund. Math. 50 (1961-62), 45-61. Zbl0104.25501
  11. [11] I. Mason and C. Talcott, Inferring the equivalence of functional program that mutate data, Theoretical Computer Science 105 (1992), 167-215. Zbl0768.68092
  12. [12] M.L. Minsky, Problems of formulation for Artificial IntelligenceR.E. Bellman, Mathematical Problems in the Biological Sciences, Proceedings of Symposia in Applied Mathematics XIV, American Mathematical Society, Providence, R.I. 1962, 35. Zbl0116.11803
  13. [13] J.D. Monk, Introduction to Set Theory (McGraw-Hill, New York 1969). Zbl0200.00066
  14. [14] G. Ricci, Universal eigenvalue equations, Pure Math.and Appl. Ser. B, 3, 2-3-4 (1992), 231-288. (Most of the misprints appear in ERRATA to Universal eigenvalue equations, Pure Math.and Appl. Ser. B, 5, 2 (1994), 241-243.). 
  15. [15] G. Ricci, A Whitehead generator, Quaderni del Dipartimento di Matematica 86, (Universitá di Parma, Parma 1993). 
  16. [16] G. Ricci, Two isotropy properties of 'universal eigenspaces' (and a problem for DT0L rewriting systems), G. Pilz, Contributions to General Algebra 9 (Verlag Hölder-Pichler-Tempsky, Wien 1995 - Verlag B.G. Teubner), 281-290. Zbl0884.08001
  17. [17] G. Ricci, New characterizations of universal matrices show that neural networks cannot be made algebraic, D. Dorninger, G. Eigenthaler, H.K. Kaiser, H. Kautschitsch, W. Moren and W.B. Müller, Contributions to General Algebra 10 (J. Hein Verlag, Klagenfurt 1998), 269-291. 
  18. [18] G. Ricci, Boolean matrices ... neither Boolean nor matrices, Discuss. Math. General Algebra and Applications 20 (2000), 141-151. Zbl0964.08003
  19. [19] G. Ricci, Isomorphisms between analytic monoids, The Eighth International Workshop in Mathematics Gronów 2000, Institute of Mathematics, Technical University of Zielona Góra', September 25-29, 2000, 33. 
  20. [20] G. Ricci, Some analytic features of algebraic data, Discrete Appl. Math. 122/1-3 (2002), 235-249. Zbl1002.68031
  21. [21] G. Ricci, Analytic monoids versus abstract monoids, Italian Journal of pure and Applied Mathematics, 16 (2004), 125-136. Zbl1177.08002
  22. [22] M. Servi, Classificazione dei Clan binari, Quaderni del Dipartimento di Matematica 113, (Universitá di Parma, Parma 1995). 
  23. [23] M. Servi, Definizione dei clan binari e loro classificazione, Rend. Mat. Acc. Lincei (9) 9 (1998). 
  24. [24] M. Servi, Due parole sui Clan di Ordine, Quaderni del Dipartimento di Matematica 186, (Universitá di Parma, Parma 1998). 
  25. [25] M. Servi, I clan binari di ordine, Riv. Mat. Univ. Parma (6) 1 (1998), 207-214. 
  26. [26] S. Świerckowski, Algebras independently generated by every n elements, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 7 (1959), 501-502. Zbl0091.03003
  27. [27] S. Świerckowski, Algebras which are independently generated by every n elements, Fund. Math. 49 (1960-61), 93-104. 
  28. [28] D.S. Touretzky, Common LISP: a Gentle Introduction to Symbolic Computation (The Benjamin/Cummings Publishing Co. Inc, Redwood City 1990). Zbl0548.68005
  29. [29] C. Weissman, LISP 1.5 Primer (Dickenson, Belmont, Ca., 1967). 
  30. [30] A.N. Whitehead, A treatise on Universal Algebra with Applications, 1, (Cambridge University Press, Cambridge 1898). Zbl29.0066.03

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.