From monomials to words to graphs.

DOI10.1016/J.JCTA.2003.11.001MaRDI QIDQ598451zbMATH OpenOpenAlexFDO

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

Publication date 6 August 2004

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

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

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)

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.

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

Cites work

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

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)