{"entities":{"Q596085":{"pageid":597861,"ns":120,"title":"Item:Q596085","lastrevid":48313261,"modified":"2026-01-04T08:22:04Z","type":"item","id":"Q596085","labels":{"en":{"language":"en","value":"On groups whose word problem is solved by a counter automaton."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2085504"}},"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":"Q596085$4BDAF735-DE32-4CDF-9F67-0A56B46CF9E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9d69876471057f988e0d0e7f42fa8c18a9bd7523","datavalue":{"value":{"text":"On groups whose word problem is solved by a counter automaton.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q596085$DF7BD809-0FE6-4D9F-8415-67E6A31A24D9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a64f90229c217f324dfd73c4a729f1540be73dc8","datavalue":{"value":"1061.20029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596085$1AB358CB-9817-4A14-8978-BC8AB5954A08","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"47849d9a0d395b221359652b0eb63bc84cad8c60","datavalue":{"value":{"entity-type":"item","numeric-id":596084,"id":"Q596084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596085$457D7666-DC49-49D0-80E0-4F5D9122C548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97d6b8a67dce742908bc3ce3f6a33d63600eae05","datavalue":{"value":{"entity-type":"item","numeric-id":375211,"id":"Q375211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596085$1BAB5A38-330A-403E-AF59-598AB5FE8988","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596085$205C4434-9E20-4EA4-98DE-A997CB6C4ED4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7e0adf53a19cddd0f150137b2408eb7868ef6930","datavalue":{"value":{"time":"+2004-08-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q596085$CCC41CD3-7E5A-4C2C-B1E1-6A9B75044927","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"87c73c5b449272929ffb77c17f53c0eb8e26b879","datavalue":{"value":"Let \\(H\\) be a group given by a finite presentation \\(\\langle X \\mid R\\rangle\\), and let \\(W(H)\\) be the word problem for \\(H\\). That is, let \\(W(H)\\) be the set of words in the free monoid \\((X\\cup X^{-1})^*\\) that represent the identity element in \\(H\\). It is a well known that \\(W(H)\\) is a regular language if and only if \\(H\\) is finite. Muller and Schupp proved that \\(W(H)\\) is a context-free language if and only if \\(H\\) has a free subgroup of finite index.   Let \\(G\\) be a group. A \\(G\\)-automaton \\(A_G\\) over a finite set \\(X\\) is a finite directed graph with distinguished initial vertex (state), some distinguished terminal vertices, and with edges labelled by \\(G\\times(X^\\pm)^*\\). In particular, a \\(\\mathbb{Z}^k\\)-automaton is called a counter automaton, and a \\(\\mathbb{Z}\\)-automaton is a one-counter automaton.   A \\(G\\)-automaton over \\(X\\) is said to accept a word \\(w\\in(X^\\pm)^*\\) if there is a path \\(p\\) from the initial state to some terminal state such that \\(w(p)=w\\), and \\(g(p)=1\\), where \\(w(p)\\) is the product of all second coordinates of labels of edges, and \\(g(p)\\) is the product of all first ones, appearing in \\(p\\).   It is proved that the set \\(W(H)\\) for a finitely generated group \\(H\\) is accepted by a deterministic \\(G\\)-automaton with the inverse property if and only if the group \\(H\\) has a finite index subgroup \\(K\\) such that \\(K\\) is isomorphic to a subgroup of \\(G\\). The inverse property is a weakened version of the assumption that for each edge from \\(\\sigma\\) to \\(\\tau\\) labeled by \\(x\\) there is a corresponding edge from \\(\\tau\\) to \\(\\sigma\\) labeled by \\(x^{-1}\\).   It follows that in the case of the counter \\(G\\)-automaton for \\(W(H)\\) the finitely generated group \\(H\\) should be virtually-free Abelian. Combining the results by the authors and Muller and Schupp we get the following corollary: Let \\(H\\) be a finitely generated group, \\(W(H)\\) is context-free if and only if there is a deterministic \\(G\\)-automaton \\(A_G\\) with the inverse property and \\(G\\) free such that \\(A_G\\) accepts \\(W(H)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q596085$F468D1D0-E86D-4586-8C82-2E6AE0B6FB37","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596085$8200A00A-37E7-42CA-A20E-90E845C128AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596085$CD2DB7CA-B6FE-4520-A95A-87000087B2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5608e4dbe85e8f6c220cc8afcea2a4ada066e3fa","datavalue":{"value":"20F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596085$C34DACA1-E378-43A1-A8CE-7AAAE65AE23C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596085$8EF5BFD8-1764-476D-964B-9D543E203EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ea37469d91f3037e8b6809fc66f770f1b27a461d","datavalue":{"value":"20E07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596085$9A8B48EF-6951-4D9F-AD0B-C5E7D6C5FB89","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b1a9967248577df6edc48cfa440294221d50cf8","datavalue":{"value":"2085504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596085$7318FEA8-1ACA-4398-AFCF-62464B229B77","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"278889c234cf01d7d5e7d0a30acad59211bfe558","datavalue":{"value":"counter automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q596085$2A81BA00-7E90-433E-8F0A-79785D55C09D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795414f846fccd6517b35b46d219d01dfd08d3da","datavalue":{"value":"context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q596085$729C53FE-D547-4725-9ACB-C2A0A2849380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae7ab853ffbc22613822b033cc2902215b997c3d","datavalue":{"value":"virtually Abelian groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q596085$56A8DE2C-C473-426F-B138-6825207E9D9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q596085$E6BCB8EE-22FF-48D1-B68B-0EBA4D8C213A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cb45a7fad3616cfdc6377269f8a1b970b78470f","datavalue":{"value":"finitely presented groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q596085$A6A3358D-E9E1-441D-BE4B-AEE4C3B27A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c48b241c2e53ac9c4073e4f6a37f6442b7c79d7d","datavalue":{"value":"free monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q596085$212C1505-1C0E-468C-A051-1DE468FF56A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"478f5436c841f182abd749d3648a229ca752fd86","datavalue":{"value":"subgroups of finite index","type":"string"},"datatype":"string"},"type":"statement","id":"Q596085$A150D4ED-2A89-491F-BE02-B1F2D1F59437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"542470d6f63fefcd2ae937cc78d1c833a1db112c","datavalue":{"value":"finitely generated groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q596085$2EF58AB4-DBAF-44BD-99D0-028509749C10","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c75e46d52756574cc2c3b6666627a330102767ca","datavalue":{"value":{"entity-type":"item","numeric-id":338846,"id":"Q338846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596085$9AB71EF4-718D-4765-A23F-78FED335F517","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":"Q596085$C7B4F1BF-62B8-4643-A144-A27C5B58C684","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e4c933af39afd96121920ae4224edcf8781f4bf5","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2003.09.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q596085$8FCBC3ED-602D-4457-AEB2-D795B5248C3A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e213348702add41f7cb24ca68fabd31ca36d40b2","datavalue":{"value":"W1993619792","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596085$8C70471C-9EAC-4CAC-86F6-226B16CA0FE9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"999968a37f79519f4778fc7fdfc8575cbc2c2685","datavalue":{"value":{"entity-type":"item","numeric-id":4085266,"id":"Q4085266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596085$927A184A-0040-4E43-B40F-8577456A220E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30e5914d41f4ae56d9392d79ff36b7b7f78450ff","datavalue":{"value":{"entity-type":"item","numeric-id":2709977,"id":"Q2709977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596085$8BD0F4EB-88D9-4EA0-83A5-8F444860998A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d84aa78f0d96f7d40459af01bc21793f5962fa","datavalue":{"value":{"entity-type":"item","numeric-id":4079524,"id":"Q4079524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596085$E9EA9F19-DB5A-4FC5-9A85-62E1632EF81B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34bed4c2b4475236f2522c75bb98ad99df444276","datavalue":{"value":{"entity-type":"item","numeric-id":4867134,"id":"Q4867134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596085$A878D7FE-86BE-43A9-B73A-CA10BF9C4BC5","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":"Q596085$2C45549D-9626-479B-B42E-8EFCD8D2D9B7","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":"Q596085$2CB361FB-074E-4257-B7A7-FC444B8EA815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cd06688d0a2118d72cedd0d86de5ca69bef5bfd","datavalue":{"value":{"entity-type":"item","numeric-id":1084096,"id":"Q1084096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596085$3ABE0D33-AD46-4D81-8E94-AE9F91B7E965","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"21009d3cc57a0a658303075e6d3b51cab485e582","datavalue":{"value":"10.1016/J.TCS.2003.09.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596085$CC080420-03DA-46A9-87EC-79D6C50C5B1C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1f2f58757fe602b5f4f6350ebff50b644bc522a","datavalue":{"value":{"entity-type":"item","numeric-id":3601328,"id":"Q3601328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db0e4fbb0b9a90c1d46c611a7a3cbee601717c34","datavalue":{"value":{"amount":"+0.9141546487808228","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":"Q596085$E4DDDFCF-FC64-40DD-AF27-7D422A2F5ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"966e7eae6fdad85752ca1bf933dca65aa173ae65","datavalue":{"value":{"entity-type":"item","numeric-id":5322915,"id":"Q5322915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b377424048422db21dca294b8f73b5c6da80da1","datavalue":{"value":{"amount":"+0.8617666363716125","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":"Q596085$1101E33C-729D-4073-B060-B60123DC7C32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"620cc7456c65650a9ae78b123aae069e4e0392bd","datavalue":{"value":{"entity-type":"item","numeric-id":1623276,"id":"Q1623276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f402da91d259e31d79265fc40cc411720ebc1ae7","datavalue":{"value":{"amount":"+0.8497499823570251","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":"Q596085$26EBE165-DD7C-4A64-8E38-AB621CF30EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"475ef3ac5f64bc201b890cc1381a2e6d9b130f6a","datavalue":{"value":{"entity-type":"item","numeric-id":3978768,"id":"Q3978768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fdd7509cec21839580a639c037ea5cf4709b470","datavalue":{"value":{"amount":"+0.8289780020713806","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":"Q596085$5F7F4515-8A35-41C4-ADCF-C060266E16B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f65f5d61420b5025e20e922767ce900613cef24","datavalue":{"value":{"entity-type":"item","numeric-id":3442616,"id":"Q3442616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cad1ed19f52ca95f8a2b16e7b9e8821e6ee3abc","datavalue":{"value":{"amount":"+0.8218768835067749","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":"Q596085$6E8F9ACC-ED70-4BEE-BA38-3F01E170CE50","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:596085","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:596085"}}}}}