{"entities":{"Q1173982":{"pageid":1184731,"ns":120,"title":"Item:Q1173982","lastrevid":66756774,"modified":"2026-04-12T12:39:51Z","type":"item","id":"Q1173982","labels":{"en":{"language":"en","value":"A note on isomorphic simulation of automata by networks of two-state automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7916"}},"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":"Q1173982$0ED6255C-17F2-4C95-9325-C71BD90C9CF2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5fb4121a90b4b8823bb9a6c99a4dd3b1a2a186dd","datavalue":{"value":{"text":"A note on isomorphic simulation of automata by networks of two-state automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1173982$5E541E7E-DDB9-4FC7-8E09-4B87E5726CB4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"447790512ad3ca8bac1d5852a6e80eacd10ca2a8","datavalue":{"value":"0737.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1173982$6E40440F-04EB-4033-9A0E-F1C6A7972073","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"37e57eec8e4b23cce49b08d4a6afc65ce4197803","datavalue":{"value":"10.1016/0166-218X(91)90015-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1173982$7AC061A9-ADA3-42B8-B5D5-718362E8FA3E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2839fa7df2030a45c4fad5ee858120056b896af4","datavalue":{"value":{"entity-type":"item","numeric-id":265801,"id":"Q265801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$A51A3F49-BE38-4E10-9452-F80F92366FAF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$D1938E9C-75B9-44A3-9966-BF423DCED2A5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1173982$92ECD195-5AC5-4AB1-ADA8-EED81216014F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"949780db3388235bf1256ece210598c10d2129d6","datavalue":{"value":"Let \\(A,B\\) be automata. Then \\(A\\) is isomorphically simulated by \\(B\\) if the transformation semigroup \\(T(A)\\) can be embedded into \\(T(B)\\). (The transformation semigroup \\(T(A)\\) of an automaton \\(A=(A,X,\\delta)\\) is the couple \\((A,S(A))\\), where \\(S(A)=\\{f_ x; x\\in X\\}\\), \\(f_ x(a)=\\delta(a,x).)\\) Given a family of automata \\(A_ i=(A_ i,X_ i,\\delta_ i)\\), \\(i\\in I\\), and a family of mappings \\(\\varphi_ i:A\\times X\\to X_ i\\), \\(i\\in I\\), where \\(A=\\prod(A_ i; i\\in I)\\). Then a general product of \\(A_ i\\), \\(i\\in I\\), with the feedback functions \\(\\varphi_ i\\) is the automaton \\(A=(A,X,\\delta)\\) where \\(\\delta\\) is defined by  \\[ \\pi_ i(\\delta(a,x))=\\delta_ i(\\pi_ i(a), \\varphi_ i(a,x)) \\]  for every \\(i\\in I\\) (\\(\\pi_ i\\) is the \\(i\\)-th projection). Let \\(D=(V,E)\\) be a directed graph (it may contain loops). Then a general product \\(A\\) of \\(A_ v\\), \\(v\\in V\\), with the feedback functions \\(\\varphi_ v\\), \\(v\\in V\\), is a \\(D\\)-power of an automaton \\(B\\) if \\(A_ v=B\\) for every \\(v\\in V\\) and \\(\\varphi_ v(a,x)\\) is independent of any \\(\\pi_ u(a)\\) for every \\((u,v)\\notin E\\). Given a class \\({\\mathcal D}\\) of directed graphs. Then an automaton \\(A\\) is a \\({\\mathcal D}\\)-power of \\(B\\) if it is a \\(D\\)-power of \\(B\\) for some \\(D\\in{\\mathcal D}\\). It is proved: Let \\({\\mathcal D}\\) be a class of directed graphs which contains a strongly connected directed graph of order at least \\(n\\) for every \\(n\\geq 1\\). Then every automaton can be isomorphically simulated by a \\({\\mathcal D}\\)-power of the two-state automaton.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1173982$74F0406B-4E19-43ED-AD38-EDC36755B768","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1173982$587CC73A-8D23-4680-953E-BADA0AFD1609","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e09e5deb1f92ac38a56f6e3ec58d76f59852d5a","datavalue":{"value":"7916","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1173982$38565720-76EE-4359-87F8-054142CC2DE2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae07fe120276ee4c21c2b056394433e1dd18622","datavalue":{"value":"automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1173982$8D9F9407-4AE2-4F52-8188-B050ED109A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e72875abb503cf78ea37b307f56b9a19ef339253","datavalue":{"value":"transformation semigroup","type":"string"},"datatype":"string"},"type":"statement","id":"Q1173982$98B18123-34D1-4584-9E06-BE2C9F08276E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94f05495e3972729cd93a8b2c61a1d1e84c4cd41","datavalue":{"value":"two-state automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1173982$A15B813E-97EF-410D-A749-38A5C6F7DDE9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5160355622f16f7db3af37439dc82dfda87a355a","datavalue":{"value":{"entity-type":"item","numeric-id":535117,"id":"Q535117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$60E259CF-6CDC-4C3E-A9A5-70DE17013D56","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":"Q1173982$D76EA1C9-C2E3-4778-82EA-143A8745D8A8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"141790cb81b8fc7641334b4b5fbc49bf022e5aa6","datavalue":{"value":{"entity-type":"item","numeric-id":3326848,"id":"Q3326848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$0161F2AD-11F2-495F-86C2-2F10FDA8007E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daa28b36f1d47ef725ba4acb380f1839600a6b45","datavalue":{"value":{"entity-type":"item","numeric-id":4132170,"id":"Q4132170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$756221C6-B220-4774-89ED-98EB99A8315E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbc46277970004b3235f7463a483e8393fe0f373","datavalue":{"value":{"entity-type":"item","numeric-id":3774951,"id":"Q3774951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$0BB2F607-91AA-4AD5-9443-21AF24DB1262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d99c92839ad817a6966d9878f8280291ce39afd","datavalue":{"value":{"entity-type":"item","numeric-id":3033342,"id":"Q3033342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$B367B615-0A71-426B-B8FA-36C40897461C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd3f5aacab8b165da3e0b98ec43c027e458b7b8c","datavalue":{"value":{"entity-type":"item","numeric-id":3776631,"id":"Q3776631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$4D74250E-57FC-49B4-BE42-2A1D73A61254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d7ebed56b64033a46d5ef073e661fbd2a5fb5df","datavalue":{"value":{"entity-type":"item","numeric-id":3031935,"id":"Q3031935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$790BE805-3EC3-4D5D-A886-C5E80D04647E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8025df7c48fc7789cf60e3a9207390ce5e9174f0","datavalue":{"value":{"entity-type":"item","numeric-id":1149492,"id":"Q1149492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$29C2F428-263F-4226-88C6-BDE30B371FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3540833946d3cb1a60c28c60923c2ee02b58228e","datavalue":{"value":{"entity-type":"item","numeric-id":1210791,"id":"Q1210791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1173982$59C90310-14AF-4022-860F-B28FC271B969","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d1206ca25237bd07834a322e982eeda16bbceb8d","datavalue":{"value":"Q127203036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1173982$E2272FBA-7748-4122-8783-016B50C47E69","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ec6458a0071229b58c7fa0a428db3b4aa867822","datavalue":{"value":{"entity-type":"item","numeric-id":766182,"id":"Q766182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c50ba3e4e98902600dda9195ede3674b72f2966a","datavalue":{"value":{"amount":"+0.7756283283233643","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":"Q1173982$A7E4A5F2-995A-4CB0-9143-C9551D4C395B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c79045c93f93498639eee41c694ab8f573556297","datavalue":{"value":{"entity-type":"item","numeric-id":3777461,"id":"Q3777461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83ee1e782546db71decb59f381db115fd4bc0c9f","datavalue":{"value":{"amount":"+0.7697986960411072","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":"Q1173982$741A1EC8-E22D-426D-9B56-59AF00393E14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37dc1fbc449b6554b4152bacde0d0016024b6a6c","datavalue":{"value":{"entity-type":"item","numeric-id":4005454,"id":"Q4005454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89dcff73f900403ca47871a79ec68725ecf65e1a","datavalue":{"value":{"amount":"+0.7649394273757935","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":"Q1173982$61E34E57-B7A0-478E-A0C3-2294FDBB3B20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bb42508c45a129659464b0fe01cf7ce3104615b","datavalue":{"value":{"entity-type":"item","numeric-id":3468615,"id":"Q3468615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8028723c9b4743857f7f193873911407056c589","datavalue":{"value":{"amount":"+0.7644742131233215","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":"Q1173982$CCB1CF4B-51BD-4869-9AC4-038248F14E5A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on isomorphic simulation of automata by networks of two-state automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_isomorphic_simulation_of_automata_by_networks_of_two-state_automata"}}}}}