{"entities":{"Q2502268":{"pageid":2513011,"ns":120,"title":"Item:Q2502268","lastrevid":49913803,"modified":"2026-01-12T00:11:28Z","type":"item","id":"Q2502268","labels":{"en":{"language":"en","value":"On graph products of automatic and biautomatic monoids."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5053094"}},"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":"Q2502268$8EF1D9C9-5F28-4E9E-8A25-B5DF392E5B04","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"afe9a64f53c4ef9519a5ed4f2a0c760ea7f79c70","datavalue":{"value":{"text":"On graph products of automatic and biautomatic monoids.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2502268$0A8A9DE9-B2D6-48E3-B4C0-6EFEA28A683F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"88137967c0140048d5c733b6ff16c586363bbe1e","datavalue":{"value":"1124.20040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2502268$9CFEDEDA-CA89-4262-8BC2-3B9948F03F5E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5543e91eef155ab4b916a068c63e327c976eda02","datavalue":{"value":{"entity-type":"item","numeric-id":2502267,"id":"Q2502267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2502268$82AE21BE-CC41-4B4B-957C-8279ABA6D1B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a8f9028ed4d5274f77df4d4f9e07b117d4309ffd","datavalue":{"value":{"entity-type":"item","numeric-id":420855,"id":"Q420855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2502268$53551443-128F-4246-9031-037B4D6423A1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"28dbf90a09492d81530507fd711b9336815e58a3","datavalue":{"value":{"entity-type":"item","numeric-id":172569,"id":"Q172569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2502268$8E49E486-F828-46F1-BC10-19132AF48D82","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7fd47b58f27435239dc8447da9ea0a760e50b459","datavalue":{"value":{"time":"+2006-09-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2502268$EFB6410D-F99D-48D6-88C9-62D21B9FA486","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ac23bf713cfef79a5a19b2bbf51a7d39f70ebc4","datavalue":{"value":"Let \\(A\\) be any non-empty finite set and \\(A^*\\) denotes the set of all words over \\(A\\) including the empty word \\(\\varepsilon\\). Let \\(\\emptyset\\not\\in A\\) be a symbol and \\(A(2,\\emptyset)=(A\\cup\\{\\emptyset\\})\\times (A\\cup\\{\\emptyset\\})\\setminus\\{(\\emptyset,\\emptyset)\\}\\). The convolution is defined as a special map \\(\\otimes\\colon A^*\\times A^*\\to A(2,\\emptyset)^*\\). Let \\(M\\) be a monoid, \\(A\\) a finite set, \\(\\theta_A\\colon A^*\\to M\\) a homomorphism, and \\(L\\subseteq A^*\\). Then \\((A,\\theta_A,L)\\) is an `automatic structure' for \\(M\\) if \\(L\\) and all the sets \\(L_a=\\{v\\otimes w\\mid v,w\\in L\\), \\(\\theta_A(va)=\\theta_A(w)\\}\\subseteq A(2,\\emptyset)^*\\) for \\(a\\in A\\) are regular in \\(A(2,\\emptyset)^*\\) and if \\(\\theta_A\\) maps \\(L\\) bijectively onto \\(M\\). An automatic structure \\((A,\\theta_A,L)\\) for \\(M\\) is `biautomatic' if, in addition, the sets \\(_aL=\\{v\\otimes w\\mid v,w\\in L\\), \\(\\theta_A(av)=\\theta_A(w)\\}\\subseteq A(2,\\emptyset)^*\\) for \\(a\\in A\\) are regular. A monoid \\(M\\) is `(bi)automatic' if there is exists a (bi)automatic structure for \\(M\\). Suppose that \\(M_1,\\dots,M_n\\) are monoids presented by \\((A_1,R_1),\\dots,(A_n,R_n)\\) (we assume that the sets \\(A_1,\\dots,A_n\\) are mutually disjoint), \\([n]=\\{1,\\dots,n\\}\\) and \\(\\Gamma=([n],E)\\) is an undirected and loop free graph. The `graph product' \\(\\Gamma(M_1,\\dots,M_n)\\) is the monoid presented by \\((A,R)\\), where \\(A=\\bigcup_{i\\in [n]}A_i\\), \\(R=\\bigcup_{i\\in[n]}R_i\\cup\\bigcup_{(i,j)\\in E}\\{ab=ba\\mid a\\in A_i\\), \\(b\\in A_j\\}\\).   The main results of the paper are the following. The graph product \\(\\Gamma(M_1,\\dots,M_n)\\) of monoids is always automatic thereby improving on a result by \\textit{A. Veloso da Costa} who showed this result provided the factors have finite geometric type [Theor. Inform. Appl. 35, No. 5, 403-417 (2001; Zbl 1019.20028) and Semigroup Forum 63, No. 2, 247-277 (2001; Zbl 0992.20042)]. Secondly, it is shown that, in general, the free product (and therefore the graph product) of biautomatic monoids need not be biautomatic. If for all \\(i\\in[n]\\), the monoid \\(M_i\\) is biautomatic and the equation \\(px=q\\) has only finitely many solutions for any \\(p,q\\in M_i\\), then the graph product \\(\\Gamma(M_1,\\dots,M_n)\\) is biautomatic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2502268$3F93BEE7-E1B0-49CF-A3B4-1D60338DD0DE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2502268$1ACC1967-A64B-4F6F-9B28-DC026886CA90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2502268$0A49C211-0930-4ABF-AE2A-14DB3F858E56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2502268$0CFD05A3-79D2-43FF-90AD-26338F785FFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2502268$E799F274-403C-4C47-9675-A43FDA64DD8B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5a9d15d27d621da3ea0f27a74ff6977218bfdb36","datavalue":{"value":"5053094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2502268$E1BB298F-67C5-4902-8622-80B2E2D479EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb0093911622d56aba5330f559f7451ce091a17a","datavalue":{"value":"automatic monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q2502268$9FB3BA5B-DA41-4E08-BBBE-650B72971BEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34faf0d31849a2546987d7c6e80089393f911bc1","datavalue":{"value":"biautomatic monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q2502268$D4E1CA53-4437-4D75-9BA9-87DBFAE31180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87358badf78ee8b81015673c24e405dcd5968853","datavalue":{"value":"graph products","type":"string"},"datatype":"string"},"type":"statement","id":"Q2502268$24427957-F4C9-4E95-94D4-E2802715FEB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4629110a5c382916c4a4f2be5f39d848eb7f7f32","datavalue":{"value":"free products of monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q2502268$707DEB9E-09C9-4075-BFBA-0108750E65AB","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":"Q2502268$0BCF6904-AEA0-4601-A255-9D6A5F8AF430","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dce770d14e5358f42bfa449dea9b3c153d66c199","datavalue":{"value":"https://doi.org/10.1007/s00233-006-0602-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q2502268$D4748E49-9183-4124-9F72-FB24DEE35997","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2dc1a6055a9e3dbbf4f35a5321d057b20c45622f","datavalue":{"value":"W2063022977","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2502268$581CCD22-70A0-4D70-8D50-CD4E99086B7C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"354a6aac7f1bc69587c80edb8652a68cb6d32492","datavalue":{"value":"10.1007/S00233-006-0602-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2502268$B649122A-8037-4CE9-8C03-4C90E82C74D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"213b1fcedcc1d2b138d380d1c5fabf4fd8c2adfe","datavalue":{"value":{"entity-type":"item","numeric-id":3149082,"id":"Q3149082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef6ba009bdd5730aea59c3a65fcdbaf9d1f318a7","datavalue":{"value":{"amount":"+0.8963425755500793","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":"Q2502268$3BAB949A-7EDC-48C2-A0B1-3E2AE604E637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"190433eb497a95929c8afd72cd635abe8ec8fa67","datavalue":{"value":{"entity-type":"item","numeric-id":5939562,"id":"Q5939562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90ac86b59ebaf10d4bdd2d62785a178dbe0c2b8f","datavalue":{"value":{"amount":"+0.8123487830162048","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":"Q2502268$6D164F0A-4525-4488-A72D-E1A969C21E3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00ddc9919e404ef1f16f004b50ec1f572939c81e","datavalue":{"value":{"entity-type":"item","numeric-id":4934090,"id":"Q4934090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f1763439b5a54eb520e4d87fb46b1d296dd73bd","datavalue":{"value":{"amount":"+0.8092622756958008","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":"Q2502268$9ADDA6B9-E544-404A-9D2C-FF27355C868D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"066410f176b45e500cec043fcd1481791566fedc","datavalue":{"value":{"entity-type":"item","numeric-id":3838758,"id":"Q3838758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f1763439b5a54eb520e4d87fb46b1d296dd73bd","datavalue":{"value":{"amount":"+0.8092622756958008","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":"Q2502268$30E4C3DA-072E-49E4-BDF1-95FBD033D331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d16faf793e132899be508087eb3167a9075241ae","datavalue":{"value":{"entity-type":"item","numeric-id":2482061,"id":"Q2482061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7eeb40f8b2bb287217206aa519e1ac3ee730cac3","datavalue":{"value":{"amount":"+0.801436722278595","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":"Q2502268$182C9ADD-0191-4084-A360-1C978F2D451B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2502268","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2502268"}}}}}