From monomials to words to graphs
Copyright policy )From monomials to words to graphs
Given a finite alphabet X and an ordering on the letters, the map ��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 generated by ��(I) in the free monoid is finitely generated. Whether there exists an ordering such that is finitely generated turns out to be NP-complete. The latter problem is closely related to the recognition problem for comparability graphs.
27 pages, 2 postscript figures, uses gastex.sty
Free semigroups, generators and relations, word problems, polynomials, Analysis of algorithms and problem complexity, 68R15, Group Theory (math.GR), 16Z05, Commutative Algebra (math.AC), Polynomials, Theoretical Computer Science, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Comparability graphs, 13P10, NP-complete, 13P10;68R15;05C17;16Z05;68Q25, 68Q25, Mathematics - Commutative Algebra, blocking polyhedra, 05C17, Computational Theory and Mathematics, Graph theory (including graph drawing) in computer science, comparability graphs, Gröbner bases, Combinatorics (math.CO), NP-complete problems, Mathematics - Group Theory, Blocking polyhedron
Free semigroups, generators and relations, word problems, polynomials, Analysis of algorithms and problem complexity, 68R15, Group Theory (math.GR), 16Z05, Commutative Algebra (math.AC), Polynomials, Theoretical Computer Science, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Comparability graphs, 13P10, NP-complete, 13P10;68R15;05C17;16Z05;68Q25, 68Q25, Mathematics - Commutative Algebra, blocking polyhedra, 05C17, Computational Theory and Mathematics, Graph theory (including graph drawing) in computer science, comparability graphs, Gröbner bases, Combinatorics (math.CO), NP-complete problems, Mathematics - Group Theory, Blocking polyhedron
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!