String rewriting and Grobner bases -- a general ap

UNIVERSITATKAISERSLAUTERNZentrumfurComputeralgebraREPORTSONCOMPUTERALGEBRANO.16StringRewritingandGrobnerBases{AGeneralApproachtoMonoidandGroupRingsbyK.MadlenerandB.ReinertOctober1997TheZentrumfurComputeralgebra(CentreforComputerAlgebra)attheUniversityofKaiserslauternwasfoundedinJune1993bytheMinisteriumfurWissenschaftundWeiter-bildunginRheinland-Pfalz(MinistryofScienceandEducationofthestateofRheinland-Pfalz).ThecentreisascienticinstitutionofthedepartmentsofMathematics,Com-puterScience,andElectricalEngineeringattheUniversityofKaiserslautern.ThegoalsofthecentrearetoadvanceandtosupporttheuseofComputerAlgebrainindustry,research,andteaching.Moreconcretegoalsofthecentreincludethedevelopment,integration,anduseofsoftwareforComputerAlgebrathedevelopmentofcurriculainComputerAlgebraunderspecialconsiderationofinterdisciplinaryaspectstherealisationofseminarsaboutComputerAlgebrathecooperationwithothercentresandinstitutionswhichhavesimilargoalsThepresentcoordinatoroftheReportsonComputerAlgebrais:OlafBachmann(email:[e-mail])ZentrumfurComputeralgebrac/oProf.Dr.G.-M.Greuel,FBMathematikErwin-Schrodinger-StrasseD-67663Kaiserslautern;GermanyPhone:49-631/205-2850Fax:[phone]email:[e-mail]:~zca/StringRewritingandGrobnerBases{AGeneralApproachtoMonoidandGroupRingsKlausMadlener,BirgitReinertUniversitatKaiserslautern67663Kaiserslauternfmadlener,[e-mail]onSymbolicRewritingSystemsMonteVerita,May1995October,1997AbstractTheconceptofalgebraicsimplicationisofgreatimportancefortheeldofsym-boliccomputationincomputeralgebra.InthispaperwereviewsomefundamentalconceptsconcerningreductionringsinthespiritofBuchberger.Themostimportantpropertiesofreductionringsarepresented.Thetechniquesforpresentingmonoidsorgroupsbystringrewritingsystemsareusedtodeneseveraltypesofreductioninmonoidandgrouprings.Grobnerbasesinthissettingarisenaturallyasgener-alizationsofthecorrespondingknownnotionsinthecommutativeandsomenon-commutativecases.Severalresultsontheconnectionofthewordproblemandthecongruenceproblemareproven.Theconceptsofsaturationandcompletionarein-troducedformonoidringshavinganiteconvergentpresentationbyasemi-Thuesystem.Forcertainpresentations,includingfreegroupsandcontext-freegroups,theexistenceofniteGrobnerbasesfornitelygeneratedrightidealsisshownandaproceduretocomputethemisgiven.1IntroductionOneoftheamazingfeaturesofcomputersistheabilitytodiscovernewmathematicalresultsduetoextensivecomputationsimpossibletobedonebyhand.Besidesincrediblenumeri-calcalculations,symbolicalmathematicalmanipulationsaresubstantialtomanyeldsinmathematicsandphysics.Hencetheideaofusingacomputertodosuchmanipulationsledtoopenupwholenewareasofmathematicsandcomputerscience.Oneimportantcontribu-tiontotheeldofcomputeralgebraisBuchberger’salgorithmformanipulatingsystemsofpolynomialequations.In1965BuchbergerintroducedthetheoryofGrobnerbases1forpoly-nomialidealsincommutativepolynomialringsoverelds[Bu65].Itestablishedarewritingapproachtothetheoryofpolynomialideals.Polynomialscanbeusedasrulesbygivinganadmissible2orderingonthetermsandusingthelargestmonomialaccordingtothisorderingasalefthandsideofarule.\ReductionasdenedbyBuchbergerthencanbecomparedtodivisionofonepolynomialbyasetofnitelymanypolynomials.AGrobnerbasisGisasetofpolynomialssuchthateverypolynomialinthepolynomialringhasauniquenormalformwithrespecttoreductionusingthepolynomialsinGasrules(especiallythepolynomialsintheidealgeneratedbyGreducetozerousingG).BuchbergerdevelopedaterminatingproceduretotransformanitegeneratingsetofapolynomialidealintoaniteGrobnerbasisofthesameideal.ThemethodofGrobnerbasesallowstosolvemanyproblemsrelatedtopolynomialidealsinacomputationalfashion.ItwasshownbyHilbert(compareHilbert’sbasistheorem)thateveryidealinapolynomialringhasanitegeneratingset.However,anarbitrarynitegeneratingsetneednotprovidemuchinsightintothenatureoftheideal.Letf1=X21+X2andf2=X21+X3betwopolynomialsinthepolynomialring3Q[X1;X2;X3].Then{=ff1g1+f2g2jg1;g22Q[X1;X2;X3]gistheidealtheygenerateanditisnothardtoseethatthepolynomialX2X3belongsto{sinceX2X3=f1f2.Butwhatcanbesaidaboutthepolynomialf=X33+X1+X3?Doesitbelongto{ornot?Theproblemtodecidewhetheragivenpolynomialliesinagivenidealiscalledthemember-shipproblemforideals.IncasethegeneratingsetisaGrobnerbasisthisproblembecomesimmediatelysolvable,asthemembershipproblemthenreducestocheckingwhetherthepolynomialreducestozero.InourexamplethesetfX21+X3;X2X3gisageneratingsetof{whichisinfactaGrobnerbasis.Nowreturningtothepolynomialf=X33+X1+X3wendthatitcannotbelongto{sinceneitherX21norX2isadivisorofaterminfandhencefcannotbereducedtozerobythepolynomialsintheGrobnerbasis.FurtherapplicationsofGrobnerbasestoalgebraicquestionscanbefounde.g.intheworkofBuchberger[Bu87],BeckerandWeispfenning[BeWe92]andinthebookofCox,LittleandO’Shea[CoLiOS92].Inthelastyears,themethodofGrobnerbasesanditsapplicationshavebeenextendedfromcommutativepolynomialringsovereldstova