{"entities":{"Q3777461":{"pageid":5807367,"ns":120,"title":"Item:Q3777461","lastrevid":110662403,"modified":"2026-11-19T11:53:21Z","type":"item","id":"Q3777461","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4039305"}},"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":"Q3777461$C20A87FF-4410-416D-A476-D53606671365","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e3b6389f5c740e5100230692f97846e3da2a15d4","datavalue":{"value":"0637.68062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3777461$AAFE1067-B8B9-4DB0-9D50-0A9A917BCA91","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2d9e819c8bf49de9dca6899f76b650f2636ad1b5","datavalue":{"value":{"entity-type":"item","numeric-id":1271621,"id":"Q1271621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3777461$DA0C422D-E6A6-4ECC-8461-7265A4E4E13F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a1693234cb2b94788908b8e8a90f524543aea5b","datavalue":{"value":{"entity-type":"item","numeric-id":166235,"id":"Q166235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3777461$157E7812-D461-499A-A9FB-396F359B43BA","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":"Q3777461$AB3A1239-B8A1-46B1-8908-CF2A442D07EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3777461$A57473F3-979B-47B4-AEBF-0A30F82A1CF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10b85655aba2fdb6347555277df2ffd39ea1a82a","datavalue":{"value":"94C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3777461$2617622A-0342-4DA6-9AE6-F27B62F501BA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97aa500c744d25c227f31122568efd761b812a2c","datavalue":{"value":"4039305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3777461$8CFDC72D-EDF3-4D01-8D69-279EF27E5D2C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba3c10fe65ef9ef43ded4186734bdcebc31f8831","datavalue":{"value":"basic set of automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q3777461$80637CF4-9E58-4DA7-B1D6-088ED5D0B4AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c957bb213163ac2f8666d9e38184f3169da42a9","datavalue":{"value":"basis decision problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3777461$FC4F296B-F361-4630-90D5-D5C7762BBC3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa265656a14c3f2a2ec57918055c44340d98f82b","datavalue":{"value":"structural decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q3777461$30095144-202E-40F8-902D-62B995A5B833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8371bd122b7f3d835b0619b904e28729627d9de1","datavalue":{"value":"Mealy automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q3777461$0E5C0FDD-286A-47C0-839A-854DD9F9B403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ccf92b6260c88ef73a6fc4eccb153846218deb2","datavalue":{"value":"normed networks of automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q3777461$D4DE0044-F94F-465A-B7A6-16F8F7234E2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2be9ff7b78e0efda6309c50a27fc2594d1129e2a","datavalue":{"value":"isomorphic simulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3777461$89B293C3-4B28-4679-B924-0368E1F45CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d098d2885dca1c608e8c81b976d4da1801b685b1","datavalue":{"value":"behaviouristic simulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3777461$CBEDDA11-C08B-4135-B3C5-F12342710E16","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":"Q3777461$E1E416C4-CF85-44D7-BD38-D15856EA26CE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ac02f2af2b0e497c505615b724bef8401ba9bbd","datavalue":{"value":{"entity-type":"item","numeric-id":3731586,"id":"Q3731586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9730ab1e9a968b5546c95f3abda282c55d64ac20","datavalue":{"value":{"amount":"+0.7840281128883362","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":"Q3777461$DEB934B1-5DED-4A32-BE6D-5521EAEB5663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b1a7598e7dfaf2b00be1a3dd1edfd5b09877190","datavalue":{"value":{"entity-type":"item","numeric-id":3970886,"id":"Q3970886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c30f1482a06339b61f14edcd190d58a30e0643af","datavalue":{"value":{"amount":"+0.7806659936904907","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":"Q3777461$A2E0D63C-0248-4B56-8036-43A8CD67F200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfbc5bfb7b3cb8bbaf2b337d89b2985a30ea85b1","datavalue":{"value":{"entity-type":"item","numeric-id":3347307,"id":"Q3347307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c30f1482a06339b61f14edcd190d58a30e0643af","datavalue":{"value":{"amount":"+0.7806659936904907","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":"Q3777461$5585800C-5C94-43BA-BF95-E8425F0A5325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5ae70aad6dd57a97d1d2b2de3fa109e57f9dc59","datavalue":{"value":{"entity-type":"item","numeric-id":1173982,"id":"Q1173982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26c9892ab8a671371f874cff6c548c149b870945","datavalue":{"value":{"amount":"+0.7735140919685364","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":"Q3777461$BF9903BE-82EF-4544-B102-4C9E461DCF28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c2b0b09927b6c7bb1452d863ac35f64dc547349","datavalue":{"value":{"entity-type":"item","numeric-id":3216145,"id":"Q3216145"},"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":"Q3777461$5BFAEC6F-8957-4E45-A62D-3773FBA02B2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bfd464f93d88455a16f0301b5aec7b65dd3a2ebb","datavalue":{"value":"[For the entire collection see Zbl 0624.00016.] To investigate structural decomposition of automata, a special model of computation was introduced in previous papers [see \\textit{A. Br\u00fcggemann}, \\textit{L. Priese}, \\textit{D. R\u00f6dding} and \\textit{R. Sch\u00e4tz}, Lect. Notes Comput. Sci. 171, 198-236 (1984; Zbl 0548.68058)]. The automaton is formally defined here in the same way as a Mealy automaton, however, its interpretation is as follows. Input and output signals of an automaton \\({\\mathcal A}\\) are encoded by 1-out-of-n code, what means that each input line \\(i_{{\\mathcal A}}\\in I_{{\\mathcal A}}\\) presents one letter from the input alphabet and at most one input signal may pass an automaton via at most one input line at any time (analogously for output \\(o_{{\\mathcal A}}\\in O_{{\\mathcal A}}).\\) In the internal state \\(s_{{\\mathcal A}}\\), an automaton may receive an input signal, change its state according to the transition function \\(\\delta (i_{{\\mathcal A}},s_{{\\mathcal A}})\\) and put an output signal on one of the output lines according to \\(\\lambda (i_{{\\mathcal A}},s_{{\\mathcal A}})\\). An automaton \\({\\mathcal A}\\) must be used sequentially, i.e. the environment of \\({\\mathcal A}\\) may give another input signal to \\({\\mathcal A}\\) only after having removed the old output signal from the line. The structural decomposition concerns here the normed networks of automata defined as follows. A normed network over a set \\({\\mathfrak B}\\) of automata consists of some copies of elements from \\({\\mathfrak B}\\) (the components of the network) and interconnections between them, where each interconnection leads from exactly one output line of one component to exactly one input line of the same or another component. Each input line or output line may be used by at most one interconnection. Such networks can be defined inductively by ``parallel composition'' and ``feedback''. The important research problem is to find finite classes of automata which form a ``basis'' in the following sense. For all automata \\({\\mathcal A}\\), there exists a normed network \\({\\mathcal N}\\) over a basis, such that \\({\\mathcal N}\\) simulates \\({\\mathcal A}\\). The results presented in the reviewed paper concern the problem of deciding whether some particular sets of automata constitute a minimal basis or not. Two concepts of simulation are distinguished - isomorphic embedding and behaviouristic. For two automatons \\({\\mathcal A}\\) and \\({\\mathcal B}\\), such that \\(I_{{\\mathcal A}}\\subseteq I_{{\\mathcal B}}\\) and \\(O_{{\\mathcal A}}\\subseteq O_{{\\mathcal B}}\\), \\({\\mathcal A}\\) is isomorphically embedded in \\({\\mathcal B}\\) (or \\({\\mathcal B}\\) simulates \\({\\mathcal A}\\) isomorphically) iff there is a non-empty set \\(S\\subseteq S_{{\\mathcal B}}\\) such that \\({\\mathcal A}\\) and \\({\\mathcal B}| S:=(I_{{\\mathcal A}},O_{{\\mathcal A}},S,\\delta_{{\\mathcal B}| I_{{\\mathcal A}}\\times S},\\lambda_{{\\mathcal B}| I_{{\\mathcal A}}\\times S})\\) are isomorphic. On the other hand, \\({\\mathcal B}\\) simulates \\({\\mathcal A}\\) behaviouristically iff there holds: \\(\\forall \\bar s\\in S_{{\\mathcal A}}\\exists s\\in S_{{\\mathcal B}}:\\) \\(s\\sim \\bar s\\) (``s\\(\\sim \\bar s''\\) denotes equivalence of states in the usual sense such that \\(\\lambda^*_{{\\mathcal B}}(w,s)=\\lambda^*_{{\\mathcal A}}(w,\\bar s)\\) for all \\(w\\in I^*_{{\\mathcal A}}).\\) The authors consider three particular automata \\({\\mathcal F}\\), K and \\({\\mathcal D}\\). It is shown that \\(\\{\\) \\({\\mathcal K},{\\mathcal F},{\\mathcal D}\\}\\) is a minimal basis for isomorphic simulation, while \\(\\{\\) \\({\\mathcal F},{\\mathcal D}\\}\\) is a minimal basis for behaviouristic simulation. Electronic models of the presented automata have been suggested. It is perhaps worthwhile to consider whether the mechanical models (moving tokens for example) would be more suitable?","type":"string"},"datatype":"string"},"type":"statement","id":"Q3777461$65E32F95-B23B-4581-954A-EE5AAE53CF61","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3777461","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3777461"}}}}}