From monomials to words to graphs.

DOI10.1016/J.JCTA.2003.11.001zbMATH Open1060.20046arXivmath/0302252OpenAlexW2061565212MaRDI QIDQ598451FDOQ598451

Arnaldo Mandel, Cristina G. Fernandes, E. L. Green

Publication date: 6 August 2004

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Given a finite alphabet X and an ordering on the letters, the map sigma sends each monomial on X to the word that is the ordered product of the letter powers in the monomial. Motivated by a question on Groebner bases, we characterize ideals I in the free commutative monoid (in terms of a generating set) such that the ideal <sigma(I)> generated by sigma(I) in the free monoid is finitely generated. Whether there exists an ordering such that <sigma(I)> is finitely generated turns out to be NP-complete. The latter problem is closely related to the recognition problem for comparability graphs.

Full work available at URL: https://arxiv.org/abs/math/0302252

Recommendations

• Monomial orderings, rewriting systems, and Gröbner bases for the commutator ideal of a free algebra
• scientific article; zbMATH DE number 1892892
• scientific article; zbMATH DE number 3972221
• Graphs and free partially commutative monoids
• A decision procedure on partially commutative free monoids

zbMATH Keywords

polynomialsNP-complete problemscomparability graphsblocking polyhedraGröbner bases

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Free semigroups, generators and relations, word problems (20M05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An introduction to commutative and noncommutative Gröbner bases
• On the Homology of Associative Algebras
• The complexity of satisfiability problems
• Title not available (Why is that?)
• Automata and forbidden words
• Title not available (Why is that?)
• Title not available (Why is that?)
• Forbidden words in symbolic dynamics
• Ordering by Divisibility in Abstract Algebras
• Title not available (Why is that?)
• How to shell a monoid
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'
• Projective resolutions of straightening closed algebras generated by minors
• Higher-order syzygies for the bracket algebra and for the ring of coordinates of the Grassmanian.
• Non-commutative Gröbner bases for commutative algebras

Cited In (1)

• Word-Representable Graphs: a Survey

This page was built for publication: From monomials to words to graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598451)