Skip to main content
SpringerLink
Log in

Arithmetic and k-maximality of the cyclic free magma

  • Published:
Algebra universalis Aims and scope Submit manuscript

Abstract

We survey free magmas and we explore the structure of their submagmas. By equipping the cyclic free magma with a second distributive operation we obtain a ringoid-like structure with some primitive arithmetical properties. A submagma is k-maximal when there are only \(k-1\) submagmas between it and the free magma itself. These two tools, arithmetic and maximality, allow us to study the lattice of the submagmas of a free magma.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Amerlynck, B.: Itérées d’exponentielles: aspects combinatoires et arithmétiques. Univ. Libre de Bruxelles, Mémoire de licence (1998)

    Google Scholar 

  2. Blondel, V.: Structured numbers. Technical report TRITA/MAT-94-31, Department of mathematics, Royal institute of Technology, 10044, Stockholm (1994)

  3. Blondel, V.: Operations on structured numbers. Research report 2464, INRIA BP 105, 78153, Le Chesnay Cedex (1995)

  4. Blondel, V.: Une famille d’opérations sur les arbres binaires. C. R. Acad. Sci. Paris 321, 491–494 (1995)

    MathSciNet  MATH  Google Scholar 

  5. Blondel, V.: Structured numbers, properties of a hierarchy of operations on binary trees. Acta Inform. 35, 1–15 (1998)

    Article  MathSciNet  Google Scholar 

  6. Bourbaki, N.: Algebra I, Chapters 1–3. Springer, Berlin (1989)

    MATH  Google Scholar 

  7. Brown, R.: From groups to groupoids: a brief survey. Bull. Lond. Math. Soc. 19, 113–134 (1987)

    Article  MathSciNet  Google Scholar 

  8. Burris, S., Sankappanavar, H.P.: A course in Universal Algebra. The Millenium Edition (2012). http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html. Accessed 01 Aug 2019

  9. Crepinšek, M., Mernik, L.: An efficient representation for solving Catalan number related problems. Int. J. Pure Appl. Math. 56, 598–604 (2009)

    MathSciNet  MATH  Google Scholar 

  10. Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order. Cambridge University Press, New York (2002)

    Book  Google Scholar 

  11. Duchon, Ph: Right-cancellability of a family of operations on binary trees. Discr. Math. Theor. Comput. Sci. 2, 27–33 (1998)

    MathSciNet  MATH  Google Scholar 

  12. Dutton, R.D., Brigham, R.C.: Computationally efficient bounds for the Catalan numbers. Eur. J. Combin. 7, 211–213 (1986)

    Article  MathSciNet  Google Scholar 

  13. Flajolet, P., Raoult, J.C., Vuillemin, J.: The number of registers required for evaluating arithmetic expressions. Theor. Comput. Sci. 9, 99–125 (1979)

    Article  MathSciNet  Google Scholar 

  14. Gabow, H.N., Galil, Z., Spencer, T., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6, 109–122 (1986)

    Article  MathSciNet  Google Scholar 

  15. Grätzer, G.: Universal Algebra. The university series in higher mathematics. D. Van Nostrand Co., Princeton (1968)

    MATH  Google Scholar 

  16. Hopcroft, J.E., Raajeev, M., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Pearson Education. Addison Wesley, Reading (2001)

  17. Knuth, D.E.: The art of Computer Programming, vol. I and II, 3rd edn. Addison Wesley, Reading (1997)

  18. Knuth, D.E., Graham, R.L., Patashnik, O.: Concrete Mathematics, 2nd edn. Addison Wesley, Reading (1994)

  19. Lallement, G.: Semigroups and Combinatorial Applications. Wiley, New York (1979)

    MATH  Google Scholar 

  20. Levi, F.W.: On semigroups. Bull. Calc. Math. Soc. 36, 141–146 (1944)

    MATH  Google Scholar 

  21. Reutenauer, C.: Free Lie Algebras. Clarendon Press, Oxford (1993)

    MATH  Google Scholar 

  22. Rosenfeld, A.: An Introduction to Algebraic Structures. Holden-Day, San Francisco (1968)

    MATH  Google Scholar 

  23. Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Cambridge (1989)

    MATH  Google Scholar 

  24. Sedgewick, R., Flajolet, Ph: An Introduction to the Analysis of Algorithms. Addison Wesley, Upper Saddle River (1995)

    MATH  Google Scholar 

  25. Sloane, N.J.A.: The on-line Encyclopedia of Integer Sequences. A035010. https://oeis.org/A035010. Accessed 01 Aug 2019

  26. Stillwell, J.: Classical Topology and Combinatorial Group Theory, 2nd edn. Springer, New York (1995)

    MATH  Google Scholar 

  27. Zwick U.: Directed minimum spanning trees. Lecture notes, School of Computer Science, Tel Aviv University. http://www.cs.tau.ac.il/~zwick/grad-algo-13/directed-mst.pdf. Accessed 01 Aug 2019

Download references

Acknowledgements

Thanks to Algebra Universalis reviewing, and, specially, many thanks to Professor Josep Maria Font for his valuable advice.

Author information

Authors and Affiliations

  1. Departament de Ciències de la Computació, Campus Nord, Edifici Omega, Jordi Girona Salgado 1-3, Universitat Politècnica de Catalunya, 08034, Barcelona, Catalonia, Spain

    Carles Cardó

Authors
  1. Carles Cardó
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carles Cardó.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This research was supported the recognition 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cardó, C. Arithmetic and k-maximality of the cyclic free magma. Algebra Univers. 80, 35 (2019). https://doi.org/10.1007/s00012-019-0608-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00012-019-0608-2

Keywords

Mathematics Subject Classification

Search

Navigation