{"entities":{"Q598451":{"pageid":600227,"ns":120,"title":"Item:Q598451","lastrevid":77829611,"modified":"2026-05-06T10:09:08Z","type":"item","id":"Q598451","labels":{"en":{"language":"en","value":"From monomials to words to graphs."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2083268"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$3957DC6D-3916-442E-9779-497CFD153576","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7eceffd1bd6eae56df8c57d501c299d41837eb11","datavalue":{"value":{"text":"From monomials to words to graphs.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q598451$1F1B97C5-0A3E-45C7-9B8C-78475BAA9874","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9d6e5fcd550cb2af3f13bfc32933ada9c730f35c","datavalue":{"value":"1060.20046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q598451$9E6D049F-60CD-4D05-8E60-1389B4A6B165","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"71bdaae01673fd4746ec8b438e9fb124ceb0698c","datavalue":{"value":{"entity-type":"item","numeric-id":299052,"id":"Q299052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$B4A237A3-946E-4CED-A4A0-8C00D672BEFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"18e29d2282fde6aaf0145adfdb5813986b83f616","datavalue":{"value":{"entity-type":"item","numeric-id":598450,"id":"Q598450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$6284C362-2680-4F37-9FA2-D3CD1428AB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"405bb47a41e958d1b1851884e917a0596ba1893e","datavalue":{"value":{"entity-type":"item","numeric-id":1013760,"id":"Q1013760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$F132D9CE-0094-4F31-85CF-9D3577D985BE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$37DEA739-968D-4666-B701-E13EF8183028","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fdf3003d3f6dc4bd36d0ddd91ae69d1d9d4864ff","datavalue":{"value":{"time":"+2004-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q598451$1894C1DA-8EEF-46B8-B4BD-AFD111D61508","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"786e5127e5b74551b146f26b9faa2ef874a5146c","datavalue":{"value":"https://arxiv.org/abs/math/0302252","type":"string"},"datatype":"url"},"type":"statement","id":"Q598451$3A964298-4060-46CE-9897-4576CEFEA49C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d22bc2784fc11e7dfd3ec8407750bcb94273b9f7","datavalue":{"value":"Starting from a finite alphabet \\(X\\), let \\([X]\\) be the free commutative monoid on \\(X\\), and let \\(X^*\\) be the free monoid on \\(X\\). The members of \\(X\\) are called `letters', the members of \\([X]\\) `monomials', and the ones of \\(X^*\\) `words'. For each ordering \\(\\prec\\) of the letters, let \\(\\sigma\\colon[X]\\to X^*\\) be the function that maps a monomial to the word that is the ordered product of the letter powers in the monomial.   In this paper, the authors consider problems that were motivated by the study of noncommutative presentations of affine algebras and their Gr\u00f6bner bases. Given an ideal \\(I\\) in \\([X]\\) and an ordering \\(\\prec\\) of \\(X\\), the authors describe in particular a polynomial-time algorithm to decide whether the ideal \\(\\langle\\sigma_\\prec(I)\\rangle\\) generated by \\(\\sigma_\\prec(I)\\) in the free monoid is finitely generated. Also, given an ideal \\(I\\) in \\([X]\\), they show that whether there exists an ordering \\(\\prec\\) such that \\(\\langle\\sigma_\\prec(I)\\rangle\\) is finitely generated is an NP-complete problem closely related to the recognition problem for comparability graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q598451$C87DDCD4-3EAA-4B2D-93DD-44B517065D13","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3f9e311a53969bed982204d1446a9d77dda26ac9","datavalue":{"value":{"entity-type":"item","numeric-id":591667,"id":"Q591667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$771BA0C9-4378-4395-81CE-5C878FAC3FF2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q598451$A0A3961D-9EB4-44E8-BBF0-44ACC0AF0F58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q598451$277E62CA-37A2-4445-9117-10C76A1B935C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q598451$2CDAB71D-2CBE-44E6-99BA-B7F62AA705CF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9efceaaf5e6c1105955c99944d6d621ec43e6db6","datavalue":{"value":"2083268","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q598451$5EBA1D48-C84D-43AF-9C0E-07681B99141B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99c239dc77a316f7da47f9d2d7c645993f6cd8d7","datavalue":{"value":"Gr\u00f6bner bases","type":"string"},"datatype":"string"},"type":"statement","id":"Q598451$0DF6710B-4B2F-4278-A2C3-EF9C1D86CD52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7a609ae2c21271342f267522dda74375687f014","datavalue":{"value":"polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q598451$CA463F7F-9EC1-4D48-AE51-04E9FAA06390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"329e1c13daa8aa98a20a699b2b1edca88d38cf5a","datavalue":{"value":"comparability graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q598451$D32FEC9E-9524-48DB-812B-1EDB13449257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q598451$440D59D3-480D-47E0-900C-C4A195C8E6CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"778c8e475cd871631b331b830d65836286b93a3f","datavalue":{"value":"blocking polyhedra","type":"string"},"datatype":"string"},"type":"statement","id":"Q598451$FDF9E992-DA39-4138-BB07-65C0D4FE5665","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$AAA1CE89-7556-4BC7-9DC2-7860B7C5A89F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3dea384fa5032b6195839a8c3292e4d68bf95223","datavalue":{"value":"W2061565212","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q598451$31517E01-335C-4339-99A1-95D57099BB67","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"95a838651d29e96f94d985ef4668bfed9c3f9ca1","datavalue":{"value":{"entity-type":"item","numeric-id":3731815,"id":"Q3731815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$58148805-3C97-486F-960F-72A186A763C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c7aa0b727e30c23c399b44772628492aa32ac6d","datavalue":{"value":{"entity-type":"item","numeric-id":4021798,"id":"Q4021798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$89B5EEB5-6130-4FFB-B16A-5331C3FB93B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc033019b58a79faf71c4b699c919f0077ee1349","datavalue":{"value":{"entity-type":"item","numeric-id":1585506,"id":"Q1585506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$D768F9BF-6E3F-4D3C-8435-B75DB96F38BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"590f321285074e3ca978723231274a99cd379395","datavalue":{"value":{"entity-type":"item","numeric-id":293331,"id":"Q293331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$2FC78B6F-3FAE-47CB-AA94-B0DEEE33A9DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"284c6ec54e850e1af06348b6938daee9f90a6826","datavalue":{"value":{"entity-type":"item","numeric-id":4383047,"id":"Q4383047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$4114CF2F-DA3D-4AB7-83B5-E129C0384551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1f4712fe0e4365ae43e7804a03e54faf57f0513","datavalue":{"value":{"entity-type":"item","numeric-id":5341588,"id":"Q5341588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$7FAA1359-E0C2-4D42-B362-B313538AA6EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$9B857480-E349-45FF-AF76-13389D8ECAEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97629a956f437ce60853cad390a73c8c525cdc4e","datavalue":{"value":{"entity-type":"item","numeric-id":3221420,"id":"Q3221420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$0102D1F9-733B-4B95-82B2-7ED15B2E78E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31e6b779c2c88295baba59a44a4504017a34c589","datavalue":{"value":{"entity-type":"item","numeric-id":4270306,"id":"Q4270306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$AD794C4E-08AA-4FF4-960E-FEAE5EE2F7A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d46d7bd1b51ecaed7885bc5913cbc5ddcfe3bff","datavalue":{"value":{"entity-type":"item","numeric-id":1842230,"id":"Q1842230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$BCE34796-AB7B-4C69-8D1B-ED39954E8D1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58709679cfff7718457ae5dbfaa34a4e9b17219c","datavalue":{"value":{"entity-type":"item","numeric-id":5812263,"id":"Q5812263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$29377FFB-4DB4-4C29-9B53-1B9287EBC811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8b3b3f02a231ad62f03bd6202a3de0a5b762f86","datavalue":{"value":{"entity-type":"item","numeric-id":1341746,"id":"Q1341746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$8EAA4C7F-BBCA-4833-9D92-75896CB7D08D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a625364a9d29262349e3e4cbdfce9e9220f15f3","datavalue":{"value":{"entity-type":"item","numeric-id":2758332,"id":"Q2758332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$99441C6E-4810-4C38-97A8-D60EC9FA26DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16df57742b2c5cec867dc4432d0b040e9f291c36","datavalue":{"value":{"entity-type":"item","numeric-id":1384634,"id":"Q1384634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$932D607C-B918-4F6C-9DE2-671B615FBD66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14173c09d5dea76d63edf8f58dba8cfee05a9d9d","datavalue":{"value":{"entity-type":"item","numeric-id":4484907,"id":"Q4484907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$A1B851AE-11AF-49FB-896B-78FFDA0B0897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$2B89BEC8-2EC1-4E7F-9868-019FC3BBD992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q598451$83FBAC7C-2A41-4F3D-967A-DBE25DB774F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cc6c28bdb19fbfa0bb82f3b225b968fb45845586","datavalue":{"value":"10.1016/J.JCTA.2003.11.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q598451$A070A33B-6D25-4785-82D8-A0386C464E48","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a064c0d11d51845b03b1414f3a3d4f70efadf9d2","datavalue":{"value":{"entity-type":"item","numeric-id":1284278,"id":"Q1284278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38655a26ad667e8569e172d828250759489136d9","datavalue":{"value":{"amount":"+0.7677035927772522","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q598451$9BD34752-D125-488B-8E9A-B1AF6C380858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cda5399746fdc096f14d21dd1d9502242f075090","datavalue":{"value":{"entity-type":"item","numeric-id":4800828,"id":"Q4800828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38655a26ad667e8569e172d828250759489136d9","datavalue":{"value":{"amount":"+0.7677035927772522","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q598451$6D3F025F-74BE-4B47-8D08-EC0FC250E069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"408fe2eda89ec0a525c0ded565dfa1012bcd400f","datavalue":{"value":{"entity-type":"item","numeric-id":3738586,"id":"Q3738586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ed0c21fbf6dd6e35dec08e5f171e2aa69792815","datavalue":{"value":{"amount":"+0.7654418349266052","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q598451$ADEF6FDC-19E0-4E3E-A658-2138C3BD88FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3e39580aa622594aec77123518bd1268c6ee3fb","datavalue":{"value":{"entity-type":"item","numeric-id":803150,"id":"Q803150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09aa859e035a554bc64f6555d9c6ca1eea29e8fb","datavalue":{"value":{"amount":"+0.7460086941719055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q598451$21D87E43-2DCA-4927-89DA-7C8BD1422D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db522d13b6a457586f78f2e4d1ce2d536dcadfaa","datavalue":{"value":{"entity-type":"item","numeric-id":1086682,"id":"Q1086682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4671cd7fae8376bf85125c46e81b8d214f63659d","datavalue":{"value":{"amount":"+0.7445059418678284","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q598451$3F73E109-B387-419D-BD6E-84CF91754AB3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"From monomials to words to graphs.","badges":[]}}}}}