Gröbner Representations of Binary Matroids | SpringerLink
Skip to main content
Springer Nature Link
Log in

Gröbner Representations of Binary Matroids

  • Conference paper
Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5527))

  • 875 Accesses

Abstract

Several constructions in binary linear block codes are also related to matroid theory topics. These constructions rely on a given order in the ground set of the matroid. In this paper we define the Gröbner representation of a binary matroid and we show how it can be used for studying different sets bases, cycles, activity intervals, etc.

Partially funded by “Agencia Española de Cooperación Internacional”, Project A/016959/08.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Borges-Quintana, M., Borges-Trenard, M.A., Fitzpatrick, P., Martínez-Moro, E.: On a Gröbner bases and combinatorics for binary codes. Appl. Algebra Engrg. Comm. Comput. 19-5, 393–411 (2008)

    Article  MATH  Google Scholar 

  2. Borges-Quintana, M., Borges-Trenard, M.A., Martínez-Moro, E.: A general framework for applying FGLM techniques to linear codes. In: Fossorier, M.P.C., Imai, H., Lin, S., Poli, A. (eds.) AAECC 2006. LNCS, vol. 3857, pp. 76–86. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  3. Borges-Quintana, M., Borges-Trenard, M.A., Martínez-Moro, E.: On a Gröbner bases structure associated to linear codes. J. Discrete Math. Sci. Cryptogr. 10-2, 151–191 (2007)

    Article  MATH  Google Scholar 

  4. Borges-Quintana, M., Borges-Trenard, M.A., Martínez-Moro, E.: A Gröbner representation of linear codes. In: Advances in Coding Theory and Cryptography, pp. 17–32. World Scientific, Singapore (2007)

    Chapter  Google Scholar 

  5. Borges-Quintana, M., Borges-Trenard, M.A., Mora, T.: Computing Gröbner Bases by FGLM Techniques in a Noncommutative Settings. J. Symb.Comp. 30, 429–449 (2000)

    Article  MATH  Google Scholar 

  6. Cameron, P.: Codes, matroids and trellises, citeseerx.ist.psu.edu/343758.html

  7. Cox, D., Little, J., O’Shea, D.: Ideals, varieties, and algorithms (1992)

    Google Scholar 

  8. Esmaeili, M., Gulliver, T., Secord, N.: Trellis complexity of linear block codes via atomic codewords. In: Chouinard, J.-Y., Fortier, P., Gulliver, T.A. (eds.) Information Theory 1995. LNCS, vol. 1133, pp. 130–148. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  9. Faugère, J., Gianni, P., Lazard, D., Mora, T.: Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering. J. Symb. Comp. 16(4), 329–344 (1993)

    Article  MATH  Google Scholar 

  10. Kschischang, F.R., Sorokine, V.: On the trellis structure of block codes. IEEE Trans. Inform. Theory 41, 1924–1937 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  11. Mora, T.: Solving Polynomial Equation Systems II: Macaulay’s Paradigm and Gröbner Technology. Cambridge Univ. Press, Cambridge (2005)

    Book  MATH  Google Scholar 

  12. Mora, T.: The FGLM Problem and Möller’s Algorithm on Zero-dimensional Ideals. In: [15]

    Google Scholar 

  13. Muder, D.J.: Minimal trellises for block codes. IEEE Trans. Inform. Theory 34(5, part 1), 1049–1053 (1988)

    Google Scholar 

  14. Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)

    MATH  Google Scholar 

  15. Sala, M., Mora, T., Perret, L., Sakata, S., Traverso, C. (eds.): Gröbner Bases, Coding, and Cryptography. Springer, Heidelberg (2009) (to appear)

    MATH  Google Scholar 

  16. Reinert, B., Madlener, K., Mora, T.: A Note on Nielsen Reduction and Coset Enumeration. In: Proc. ISSAC 1998, pp. 171–178. ACM, New York (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dpto. de Matemática, FCMC, U. de Oriente, Santiago de Cuba, Cuba

    M. Borges-Quintana & M. A. Borges-Trenard

  2. Dpto. de Matemática Aplicada, U. de Valladolid, Castilla, Spain

    E. Martínez-Moro

Authors
  1. M. Borges-Quintana
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. A. Borges-Trenard
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. E. Martínez-Moro
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Avinguda Països Catalans, 26, 43007, Tarragona, Spain

    Maria Bras-Amorós

  2. Department of Mathematics, The Technical University of Denmark, Building 303, 2800, Lyngby, Denmark

    Tom Høholdt

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Borges-Quintana, M., Borges-Trenard, M.A., Martínez-Moro, E. (2009). Gröbner Representations of Binary Matroids. In: Bras-Amorós, M., Høholdt, T. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 2009. Lecture Notes in Computer Science, vol 5527. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02181-7_26

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02181-7_26

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02180-0

  • Online ISBN: 978-3-642-02181-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics