{"entities":{"Q685452":{"pageid":687301,"ns":120,"title":"Item:Q685452","lastrevid":47188987,"modified":"2025-12-31T23:10:57Z","type":"item","id":"Q685452","labels":{"en":{"language":"en","value":"Cayley automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417374"}},"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":"Q685452$34AA7F1B-9B59-4BB9-A39B-27E93841B850","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"532ba269dd76e7fbbdc50fefa84fc5c60a0c5f9e","datavalue":{"value":{"text":"Cayley automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685452$FCDD35D0-31B4-4FFF-94BB-03BBCC28BDBA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"32b9e518170374f230ea7ec045a11692f469b617","datavalue":{"value":"0781.68087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685452$18E96566-75FE-48F5-A2AA-3785DC62D703","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"df250a98da5a0d7e491b678fbfc7822ce320b5cc","datavalue":{"value":"10.1016/0304-3975(93)90231-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685452$F43B4CC6-B441-4C6E-AF91-341DBC36B1D2","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":"Q685452$D6AFFCDD-DD20-4ED3-B469-BB1523DC272F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea9458ce3029a7f683c04e43e886fdc910ea299c","datavalue":{"value":{"time":"+1993-10-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685452$1FCEA43B-ED13-40CE-B673-21EDAEFAF83C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7914c54877cebd278ce2e4ad1a9f88305e599cec","datavalue":{"value":"For a finite symmetrized set \\(X\\) of abstract generators of a group \\(G\\) and their inverses, the \\textit{Cayley graph} of \\(G\\) w.r.t. \\(X\\) is the regular digraph of degree \\(| X|\\) with vertex set \\(G\\) in which every \\(g\\in G\\) is connected to each product \\(gx\\), \\(x\\in X\\), by an edge labeled \\(x\\). A (0-\\textit{pebble}) \\textit{Cayley automaton} \\(M=(Q,\\Sigma,X,\\delta,q_ 0,F)\\) is a generalized finite-state automaton that admits as inputs Cayley graphs of a fixed degree (corresponding to a fixed set \\(X\\) of abstract generators and their inverses) whose vertices are labeled from a two-element alphabet \\(\\Sigma=\\{0,1\\}\\) such that exactly one vertex (corresponding to the group identity) is marked by 1, and all other vertices are marked 0. The automaton starts in an initial state \\(q_ 0\\in Q\\) with the (read-only) input head positioned on the marked initial vertex of the input Cayley graph. In each step, it changes its state and moves along one edge in the Cayley graph according to the (non-deterministic) transition function \\(\\delta:Q\\times\\Sigma\\to 2^{Q\\times X}\\). The \\textit{language} recognized by \\(M\\) is the set of labeled Cayley graphs for which \\(M\\) reaches one of the accepting states \\(F\\subseteq Q\\).   The paper discusses properties of languages accepted by (special classes of) Cayley automata. By reduction from the word problem of group theory, it is shown that the emptiness decision problem for the subclass of halting deterministic Cayley automata is unsolvable. It is also proved that the language accepted by a deterministic halting Cayley automaton is equational, i.e. characterized by a finite set of equations and inequalities of words over the generators \\(X\\). Furthermore, the author shows that nondeterministic Cayley automata with at least two generators \\((| X|\\geq 4)\\) are more powerful than deterministic ones.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685452$81F58C86-5CB4-4921-94A0-54F83027BAAD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685452$EE2FAB31-C304-4E7F-8DB7-C50863725016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685452$B1A15760-F6FF-45DB-A7F7-7ED25D84E467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfec936c9f92116ab04a417b25b0b6b0e8ab90","datavalue":{"value":"20F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685452$4A7761CA-0118-4E81-A362-88227FB686B2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"274f4ec60d556a3dcacd4f067bdcd80bd9d6858c","datavalue":{"value":"417374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685452$7D7F3A9E-F7F3-44C6-93AD-4D4DB1831C7E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55ed650460bb1982789f02aaba8968eaa24a0493","datavalue":{"value":"equational languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q685452$26D920FC-EF06-434F-A282-F30EF255A61F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64e1ee688b6f898d32c9c2776a1d825855a56d60","datavalue":{"value":"Cayley graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q685452$EA0D2A0A-777D-4CD4-844F-1E99FF3F6A02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q685452$812CD8E6-E52A-4195-8AB6-AE4A72293FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d85462600a498c59551527c98614a1a8ddc3a0be","datavalue":{"value":"Cayley automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q685452$4220B9CC-7C76-4567-8960-24154D855B90","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7dec9c274675ab1cf3162789e1a3526ee1820da9","datavalue":{"value":{"entity-type":"item","numeric-id":702491,"id":"Q702491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$B482A37C-DFAB-44B4-A629-ED2F45994C0E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4b79e10cd9b8c0f9d5fd29c0d2d77f1f9c811d42","datavalue":{"value":{"entity-type":"item","numeric-id":705547,"id":"Q705547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$C8CC1210-C2C0-4455-8422-626AC48358BC","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":"Q685452$7E1EBB04-E0A0-46A7-8952-D83D566A6BD4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa15a12163fac3e89d5444caaa728ff4b5498a67","datavalue":{"value":{"entity-type":"item","numeric-id":5559251,"id":"Q5559251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$22DB3530-FE5D-4371-9DDB-161A9FC38A62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8eb8fceaa39376123eea800b4e71a07e55bdfbb","datavalue":{"value":{"entity-type":"item","numeric-id":5650865,"id":"Q5650865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$02BC1568-E32B-491B-B00E-F1C60F854548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f52c180a0ddfeb6b0c09cb0494499ba742adf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1100919,"id":"Q1100919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$BB97A1EC-3195-456B-B148-978288ECDED8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af002cbee81102903946f6011d280d99b646755e","datavalue":{"value":{"entity-type":"item","numeric-id":4347961,"id":"Q4347961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$9FBEA471-E360-4E07-88C0-98B8E4069187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc783605cda78290bafd704b1465d4b5cdcc1fbf","datavalue":{"value":{"entity-type":"item","numeric-id":1177176,"id":"Q1177176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$777D7107-8D17-4728-B670-246C998F6769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9991d12c610af612098995f36bb9f37d525e6bf2","datavalue":{"value":{"entity-type":"item","numeric-id":5557460,"id":"Q5557460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$92B44E08-F70B-4CA8-83CC-E3CAC5277778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bf7346f3f7c28de1ed88698865e20f79dfbfedb","datavalue":{"value":{"entity-type":"item","numeric-id":4077997,"id":"Q4077997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$988DFD00-20E4-48E2-A970-70234DE24016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82d3cbffed8a301b84b1253490d8c6b17bf2e322","datavalue":{"value":{"entity-type":"item","numeric-id":4145882,"id":"Q4145882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$C7E7105F-9F30-48A7-8F4B-7E53FE61AF90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b20cfc018ab6e5a56059403136b49d5687c82de8","datavalue":{"value":{"entity-type":"item","numeric-id":4135772,"id":"Q4135772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$A5B487B8-9216-45F7-B301-11967165FBF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ca785ae66399f324eaf01525fe79152876a5485","datavalue":{"value":{"entity-type":"item","numeric-id":3484350,"id":"Q3484350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$C3303A97-431E-4374-9A00-3EE93CFB7778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57e71e5b556401efd16915950de24e05b8ad7db1","datavalue":{"value":{"entity-type":"item","numeric-id":4156452,"id":"Q4156452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685452$0A12128A-EC88-43CB-A9D1-713E9073B56F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7cf47d3af3cbc6b87db6e56bdaaa636dd447c7db","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90231-h","type":"string"},"datatype":"url"},"type":"statement","id":"Q685452$3948422F-D1BC-4753-89A3-950ADC4AED96","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b61f0735dcacf6aff04d7193d15918acfe3fa7e4","datavalue":{"value":"W2914958828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685452$9BBC2428-241E-45E0-A1C8-BD31A468E2F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e650dfcb6b1776e3683462129a0b39d042485282","datavalue":{"value":{"entity-type":"item","numeric-id":1100919,"id":"Q1100919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2369bd1aee57030a16e993dc36dc47d25b7bfc9","datavalue":{"value":{"amount":"+0.8827986717224121","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":"Q685452$EAB31491-A82C-4132-96FD-C862A662D5A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb71e652f9bcb89449f0718b80018fe9e32787b2","datavalue":{"value":{"entity-type":"item","numeric-id":4820531,"id":"Q4820531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4ac6eeecea4d79ec5d9cf94d8d7efa9ad411629","datavalue":{"value":{"amount":"+0.844241738319397","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":"Q685452$2C639979-2AB9-49ED-AA0B-D982525E8FEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51ce873eefc5b9710351f6d5ba77b93573531831","datavalue":{"value":{"entity-type":"item","numeric-id":2016098,"id":"Q2016098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40eff747c19534403dc9a992789b743047620872","datavalue":{"value":{"amount":"+0.8155795931816101","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":"Q685452$FF738B30-8EEC-4C22-AFD9-BD34BAAF9630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6135ba3ab53e38c0bec23259d20be5d067ac17b3","datavalue":{"value":{"entity-type":"item","numeric-id":5507059,"id":"Q5507059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bde063bfb7796d41eb9ca6ef0ff9297f160e8a78","datavalue":{"value":{"amount":"+0.8051401972770691","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":"Q685452$CF35C128-03EB-421C-A89F-0EDF5925D16D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0fe44550790f64d7d8cb29f76afd528cc37c0f3","datavalue":{"value":{"entity-type":"item","numeric-id":3621431,"id":"Q3621431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5b6f6af96249b71062322aafe987debe33b843d","datavalue":{"value":{"amount":"+0.7967467308044434","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":"Q685452$BB6D6AD8-3BE1-4160-91B4-8CFDA67BCFEB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685452","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685452"}}}}}