{"entities":{"Q1100919":{"pageid":1111671,"ns":120,"title":"Item:Q1100919","lastrevid":69641727,"modified":"2026-04-13T08:24:06Z","type":"item","id":"Q1100919","labels":{"en":{"language":"en","value":"Cyclic automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4045200"}},"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":"Q1100919$EBE3526E-C935-4199-B9E6-6D86ABB9EEED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d94962e732f73211e72cf00fdc08ef51dbd37308","datavalue":{"value":{"text":"Cyclic automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1100919$BA5C21B1-A987-4CF8-A22E-2E43F70F7EEA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e54c6c8ba115909e4937cdff87f0d1be926ff1cd","datavalue":{"value":"0641.68116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100919$541DB048-179F-4953-8FB3-4F2BBD1BE894","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e442c52e380b006e1970954f0cf355d5fa4bafb6","datavalue":{"value":"10.1016/0304-3975(87)90071-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100919$7DE85273-3336-4D98-8998-3EC5523D0006","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":"Q1100919$B6F2F040-EADD-4E4A-96FB-98F0F4CAC26C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1100919$1F01E61D-4BA5-4E74-AA6F-9E1DF1463127","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0d02e4b8f0a986f5c2d3fd935be436ad732895cc","datavalue":{"value":"The author defines Cayley automata. These are finite state devices, acting as acceptors, capable of ``walking'' on an input Cayley graph (of some group) and eventually deciding whether to accept or reject the graph. Such an automaton is equipped with a finite number of pebbles (markers) which it can rop on (and pick from) the nodes of the graph.    The paper is devoted to questions about the simplest kind of Cayley automata, those on (one-generator) cyclic graphs, here called cyclic automata. A complete characterization is give of cyclic graph languages accepted by o-pebble cyclic automata while arbitrary n-pebble cyclic automata are shown to define a strict hierarchy.    Various decision problems are also discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100919$CC0AAAB4-7398-4D5F-8BB2-47BB49F78C86","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100919$693417C7-92FF-4335-A71A-3B7EB1BD8C08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100919$60193D62-BA52-46AC-B977-2AC0EC43E04D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"067046ee38d91882f161f6573f3e1ccbdac67631","datavalue":{"value":"4045200","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100919$CB927C2A-CE87-436D-B15C-5A3F5C1D0D93","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0eb41bef4f95010ffe7ecae9642a3a5dca3e09e6","datavalue":{"value":"logspace","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100919$EE98638F-4A32-4E77-AA79-C6624DF39CBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bddc80f5d765e3379359120ce37cab9455d19579","datavalue":{"value":"ordinary Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100919$C5CA05EB-DCC0-490D-B488-8B0098C025CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab585b3625f2756aed7d3b12370f4b3bf613d06b","datavalue":{"value":"pebble automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100919$EDF87F34-2D67-45DD-A8CE-669DF80D83B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d85462600a498c59551527c98614a1a8ddc3a0be","datavalue":{"value":"Cayley automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100919$AF9EFB22-F474-4771-B9C8-C9A933DC1960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9f046045effe4d96bd7d28b79a6e3ca55890681","datavalue":{"value":"Cayley graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100919$BCB7482A-DE3B-4F74-AD6F-994FD15E7945","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3180392d969cbdb9f38ed7f9105ae3fe08580ec","datavalue":{"value":"cyclic automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100919$887BCBF5-2298-462C-907F-ABF259A2EF99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211c085a21fcd6ebc794856e642cf5ae4d9daa37","datavalue":{"value":"graph languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100919$2196AAE2-D2AF-466F-BBA4-2AFA927DE4B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a38efac09ece9e0b5c9a633205b8b5dc6c122ab0","datavalue":{"value":"strict hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100919$4F5ACBAF-105B-4F34-A1DC-8646CF9CEA5B","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":"Q1100919$BFC2BC4E-EC84-451C-8EFA-36796A786706","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$90E92A14-A1AA-401C-9BE2-B116A4E360F5","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":"Q1100919$324FD676-D31C-4CF1-B500-C2EB76ABB1A1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7f0231bb925199d15a28feab75d7621e0b81758","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90071-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1100919$C58BF917-B757-40D0-B5A9-5B72EE43149B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5757cabe94a1d73841fc11fea9259f744d70ea7c","datavalue":{"value":"W2913506727","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100919$E47D1075-19CE-4ADA-8F66-86F0724C8E8B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$4FCAF256-D51E-4D69-9FEF-B8B60DD0B859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf79dd85aa883318752687b0ce6dfc9ed9e62cbd","datavalue":{"value":{"entity-type":"item","numeric-id":2550291,"id":"Q2550291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$C3311956-5724-445C-98EF-2F0361DC8C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9684d84be3b8355a2edee9961c6843594427ba04","datavalue":{"value":{"entity-type":"item","numeric-id":4167584,"id":"Q4167584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$27A1E333-D90F-47B6-9659-7CA659171006","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":"Q1100919$2FEA49E2-23D9-4087-B623-91B11FDA6568","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d87263b35d8a1eb872937886d3408dce48c795e","datavalue":{"value":{"entity-type":"item","numeric-id":3956398,"id":"Q3956398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$206B8225-2655-4D56-BC09-5404B6CB1DE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2031f8bb3115f52425ff4dd04c9a69b45d8420a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241509,"id":"Q1241509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$773D2AA7-A34B-4A3B-8B5F-654BAD4267F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40c3ec42f7298cc5bc87787b6d3b98d85b4ebf8e","datavalue":{"value":{"entity-type":"item","numeric-id":3885190,"id":"Q3885190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$5430C107-2E12-46E8-8A73-A1B62B24CB93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d693759536f36f5e10c6e72192ac554ac26bf47","datavalue":{"value":{"entity-type":"item","numeric-id":1235979,"id":"Q1235979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$10BBED7D-20BE-4653-A317-0125FADCC780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc419969a8aad450cb9de70ca2e1a6cef07c697a","datavalue":{"value":{"entity-type":"item","numeric-id":1235980,"id":"Q1235980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$1F849157-3C38-4150-B418-C699EB908B41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e11de7132c10164732e9b26841e64c659613e5","datavalue":{"value":{"entity-type":"item","numeric-id":4142695,"id":"Q4142695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100919$E84F846A-6D8D-43AF-B913-5748DF6600C6","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":"Q1100919$4AAC8AB3-EE20-4250-8A53-6A8047A2D7F4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7064ba69a6773e2ecd34f5746737941f0513bcb","datavalue":{"value":{"entity-type":"item","numeric-id":685452,"id":"Q685452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49a05747612d8d1ea1bce03a85df5f06c2c5e884","datavalue":{"value":{"amount":"+0.8872756361961365","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":"Q1100919$E7B9E768-527D-49AE-B744-5AFCDCDAF9F7","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":"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":"Q1100919$5307EE41-73CA-4EAE-9B0F-E3B60CEC3926","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":"b394122bdac4f91f56655bd77ca710ec543f7828","datavalue":{"value":{"amount":"+0.8281478881835938","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":"Q1100919$CFD36DDF-47EF-44BC-9FC0-CF4673BCFDD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2ebe286a8cb0b75a1ef296d726432e9c680d7cd","datavalue":{"value":{"entity-type":"item","numeric-id":3823802,"id":"Q3823802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4400e977d723d5dd951f3cac3816c1489e04679","datavalue":{"value":{"amount":"+0.7962314486503601","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":"Q1100919$B1C9E38A-00B0-44C0-B01E-44ADE8618BBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d1cf6f9c5b0c7c49014562ef07ca9a10d5108ae","datavalue":{"value":{"entity-type":"item","numeric-id":3984700,"id":"Q3984700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afae590793b72b1e2108a3bb2b9b23df596ae48f","datavalue":{"value":{"amount":"+0.7755481004714966","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":"Q1100919$757D65D6-4FD4-4A72-B17B-E227708A0BEF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Cyclic automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Cyclic_automata"}}}}}