{"entities":{"Q6987054":{"pageid":21425334,"ns":120,"title":"Item:Q6987054","lastrevid":84014975,"modified":"2026-05-07T23:20:53Z","type":"item","id":"Q6987054","labels":{"en":{"language":"en","value":"Commutative semigroups with a context-free word problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8037083"}},"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":"Q6987054$6918B55D-97C1-4949-8B3D-FBCE634BC063","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bd9ef89f40627553d7d79ffbc07280592e2db8c2","datavalue":{"value":{"text":"Commutative semigroups with a context-free word problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6987054$D60A488B-7422-4E4A-8908-2AD2F4B96A92","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5c5221f5e74784ca7567f1753d5a2c340cc66d68","datavalue":{"value":"1571.20072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6987054$25425992-36BC-4131-8DAC-350A07817CE6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"47b6be5a54191bdbd7cfd5be495d99d864e5ab74","datavalue":{"value":"10.1142/S0218196725500092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6987054$A1A75105-BD01-43FE-8153-1E1A6CE31719","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5bc9308f7965b39c12d76bef83967100a21dfaa4","datavalue":{"value":{"entity-type":"item","numeric-id":782589,"id":"Q782589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$825BA490-BF45-42E2-8DBE-4E55401244B9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7f4e75461d95037e69d585d3faf5530e0368f039","datavalue":{"value":{"entity-type":"item","numeric-id":2703070,"id":"Q2703070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$E56D1DCC-8DB2-4F62-BCE7-E2FA37B7261D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"66f16df79848c88a7e372b53160ab8402dffc7b0","datavalue":{"value":{"time":"+2025-05-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6987054$62129FDC-AF2F-4238-BE3C-167EDFFB543A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1271dce71ddc7b226c79e9e4baf0aa5035ab73f3","datavalue":{"value":"Let \\(M\\) be a commutative monoid generated by a finite set \\(A\\) that does not contain \\(\\#\\). Consider a language \\(L\\), consisting of all words of form \\(u\\#v^R ,\\) where \\(u,v\\) are non-empty words in the alphabet \\(A\\cup\\{\\#\\}\\) such that \\(u=v\\) in \\(M,\\) and \\(v^R\\) is the word \\(v\\) written in the opposite order.\\N\\NThe main result is that \\(L\\) is context-free if and only if \\(M\\) does not contain a free commutative monoid on two generators as a submonoid. A similar result is obtained for the semigroups.\\N\\NThe article contains many other interesting results about such monoids, e.g. that for any \\(a,b\\in M\\) there exists a non-negative \\(q\\) such that at least one of the following equalities holds in M:\\N\\begin{itemize}\\N\\item[(1)] \\((a^qb^q)a^s=a^qb^q\\) for some positive integer \\(s;\\)\\N\\item[(2)] \\((a^qb^q)b^s=a^qb^q\\) for some positive integer \\(s;\\)\\N\\item[(3)] \\((a^qb^q)a^s=(a^qb^q)b^t\\) for some positive integers \\(s,t\\);\\N\\item[(4)] \\((a^qb^q)a^sb^t=(a^qb^q)\\) for some positive integers \\(s,t\\).\\N\\end{itemize}","type":"string"},"datatype":"string"},"type":"statement","id":"Q6987054$7AF4AB5F-1713-46DB-B4C4-E5683D40451C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6539d9ac55fea0baad65d4fd89c707d6265cecc8","datavalue":{"value":{"entity-type":"item","numeric-id":509115,"id":"Q509115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$23FB7DB6-B582-4949-80DA-15248498436F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6987054$883494DB-DB9B-4FD0-8964-3D862F6B33D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eadae2eb6bbadf82bbbb96425466d50c2adfbaee","datavalue":{"value":"20M14","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6987054$527A27A8-2B02-4722-8563-34C61D69F671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6987054$06206EB1-E7D5-4A31-80E7-32C212E29D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6987054$CCAF29E3-4023-4E72-A33A-276C7BC34DAA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"25934d2a5b2908ef5ac171604ae4c3f64cc3c7bb","datavalue":{"value":"8037083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6987054$6016D765-DB9D-416D-B00E-F3677042C03B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q6987054$32FD4B0A-C880-4AB4-AAFF-00EEB87C2D68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c0d1e92fea6d7db131a4694ca9d8654f02d8eab","datavalue":{"value":"commutative semigroup","type":"string"},"datatype":"string"},"type":"statement","id":"Q6987054$CB77CB01-6319-40D1-B01A-6D6049792DA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3cce6d341d819e09322510961aab563a2fb1bcf8","datavalue":{"value":"commutative monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q6987054$2E8C10C2-35D7-49AC-979E-3AA2B212E2DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d75d448735778f46c4e9667e177539a844422b26","datavalue":{"value":"context-free language","type":"string"},"datatype":"string"},"type":"statement","id":"Q6987054$0A1C445F-A262-45B7-93BC-F97869F1F54F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f84741d92afe8fc80c594aed6b861040ad27899a","datavalue":{"value":"pushdown automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q6987054$9EB9B7BC-D56D-4708-9B4A-D51D8D07A391","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":"Q6987054$CAEF461B-27AC-418E-BC7E-41936752D5C0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ea830727e9b6bedf20862785e40529682d300fc","datavalue":{"value":{"entity-type":"item","numeric-id":5652216,"id":"Q5652216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$2F47AC42-78A0-4B4F-B8BF-8C6C4175404E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b5ff0e3ff688ac86fd949e1651f59ec122badd0","datavalue":{"value":{"entity-type":"item","numeric-id":2884691,"id":"Q2884691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$A4D7B316-19F0-471A-A889-7EE9EB3D24DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64039618e0aff9f6aae2f13ad6e493c7dc5b7140","datavalue":{"value":{"entity-type":"item","numeric-id":2249563,"id":"Q2249563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$83ACF491-251F-48F6-A6EA-6E2A310F0A6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5459d4cd20f6f5f008c751afcafb0a2fff5d100","datavalue":{"value":{"entity-type":"item","numeric-id":777984,"id":"Q777984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$8AD40D1C-83BA-4A5C-9F2A-B1258793EAC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1fefb8a777f6215db51179cd8cc8468a21eea3","datavalue":{"value":{"entity-type":"item","numeric-id":2216121,"id":"Q2216121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$303D7581-A8DA-4B9D-8312-395B98708EAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8db6678d7992b729c1a9f4c5b7bc6188ec8aa15e","datavalue":{"value":{"entity-type":"item","numeric-id":2327563,"id":"Q2327563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$ABEAAB93-9F41-465C-B659-68422B3230C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc7417d82ea2cf12ee67afae7d15c1427412deef","datavalue":{"value":{"entity-type":"item","numeric-id":4923204,"id":"Q4923204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$B3A79062-72DA-43B3-BB02-E8DD4DECDC1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5994671d89e47ea44ac9328c9d9ef55506434a87","datavalue":{"value":{"entity-type":"item","numeric-id":3295796,"id":"Q3295796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$F5718365-159B-4FD2-9B76-5620BBC33172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77efcc08159cf43aed748fe4663d47c81bd2d9d6","datavalue":{"value":{"entity-type":"item","numeric-id":4819118,"id":"Q4819118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$F8DC0F1C-F9FE-40AE-A0C5-62AED710EF44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64eaadb5fe90b853b5422ea4979121c326763206","datavalue":{"value":{"entity-type":"item","numeric-id":1062144,"id":"Q1062144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$917D1FD6-6C2E-4654-BD2B-601AD1FE7A2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9051f3f6f25a0879f4f9d21a6e909b73210fbd9e","datavalue":{"value":{"entity-type":"item","numeric-id":3601328,"id":"Q3601328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$AC607142-14C9-459F-9BBD-3E35C2AF4071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1225b7155b520f2225ef93da5de76078306c69ff","datavalue":{"value":{"entity-type":"item","numeric-id":1206793,"id":"Q1206793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$4906CE4F-0026-4ED0-BE79-C3802BAF8174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"324808556a2d03907b1134e7d63e855c3c630b1d","datavalue":{"value":{"entity-type":"item","numeric-id":3978768,"id":"Q3978768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$F20F3BE2-5797-4260-85A8-5354D93A0233","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8897dc9267303c84537b081d98d0f6feeed68d86","datavalue":{"value":{"entity-type":"item","numeric-id":3167487,"id":"Q3167487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$9D19A779-D2EF-4DA1-A65C-3778772EBAA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2aa19e984556b3c6f76b0b22b1535ecc343434fc","datavalue":{"value":{"entity-type":"item","numeric-id":5322915,"id":"Q5322915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$21BB8AB1-6201-4A58-84E8-2F8BA8607700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b44f98db0325e4c97d4f3a4b55a1214d521ae021","datavalue":{"value":{"entity-type":"item","numeric-id":2965530,"id":"Q2965530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$E0B8AFC0-E58A-48A5-BBF6-F1D7DD7FF5F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$CFCAB9EA-FF11-4DEE-BBCC-E343915DE722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3015882132c1055eea025e4c02df3f03ae6d0a79","datavalue":{"value":{"entity-type":"item","numeric-id":4003737,"id":"Q4003737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$FC299DE0-489E-4DDA-8DBF-FF643BA6409A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24ef9589468dbd4884aa4ae69a654376ced13d2e","datavalue":{"value":{"entity-type":"item","numeric-id":2508978,"id":"Q2508978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$7BD4345F-C4F9-4763-90F4-A1A4E9A36E50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb53b69a005134b7aae07b4949b21bc26d9d6bca","datavalue":{"value":{"entity-type":"item","numeric-id":4344149,"id":"Q4344149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$974DD776-4DD1-4E34-AC0D-86C32D02C8DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b749b18150d5ddb0e428c4da605d553da2d262cb","datavalue":{"value":{"entity-type":"item","numeric-id":2304867,"id":"Q2304867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$16F14F15-F87E-4FF0-BBC7-ABDB4FEA8E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ef16dd25e8a5a711d3d257a91badb994fac452d","datavalue":{"value":{"entity-type":"item","numeric-id":705541,"id":"Q705541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$6EA93C20-F843-4339-845F-1E408BB1D39A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9627e1b476acf2205bbc762d64a97a5279e8b61","datavalue":{"value":{"entity-type":"item","numeric-id":5711963,"id":"Q5711963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$FBB863D6-7D46-4756-AFE6-EAA180FA104C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"437751fb8bd09529f6c874dab3c8069e5e081dd3","datavalue":{"value":{"entity-type":"item","numeric-id":5189807,"id":"Q5189807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$730505B7-8257-4360-A8C8-FD6AF4E9869F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2af188522ee36dfbc40e8063345c06265fc901ae","datavalue":{"value":{"entity-type":"item","numeric-id":792454,"id":"Q792454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$732A545A-F201-4628-AF84-C58073F9AEE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66c7bb34f2462146976a5b1478a5542587fc852a","datavalue":{"value":{"entity-type":"item","numeric-id":2163877,"id":"Q2163877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$34F14F94-DE2D-49AC-8C94-3695FEE65B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b80dd5d66473ce1656c4cf140ed2efc85d70e8f7","datavalue":{"value":{"entity-type":"item","numeric-id":2099288,"id":"Q2099288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$0BFBD19C-8310-4696-9762-C2584780C869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd948e5dda6176805a4d5e4ac5c23f21776d7079","datavalue":{"value":{"entity-type":"item","numeric-id":2693366,"id":"Q2693366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$25B5F8A3-A9A4-43DA-A8CD-A1FB1B92E976","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d46d53aaa78e4e1f3286eef514e163c5ea4ffb6","datavalue":{"value":{"entity-type":"item","numeric-id":5534924,"id":"Q5534924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$B4E42FEC-5337-40A2-B18C-25CA384D5D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6814ef78453770263be7153847467267beb6722","datavalue":{"value":{"entity-type":"item","numeric-id":5343411,"id":"Q5343411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$185AEB46-48AE-4C80-BFB5-C5FE34A1545B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9984a92fad53ca3e5aaaa139c87fddf25ff435d8","datavalue":{"value":{"entity-type":"item","numeric-id":4951130,"id":"Q4951130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$EDAEA3EA-6BFF-4E59-A7D0-8388E6AFA7B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9546227c998113fa65a80f5fc04e89469c43615","datavalue":{"value":{"entity-type":"item","numeric-id":2353402,"id":"Q2353402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6987054$867150D6-276E-46A5-AE74-CE062F480693","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Commutative semigroups with a context-free word problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Commutative_semigroups_with_a_context-free_word_problem"}}}}}