{"entities":{"Q1338892":{"pageid":1349631,"ns":120,"title":"Item:Q1338892","lastrevid":68500563,"modified":"2026-04-13T00:07:44Z","type":"item","id":"Q1338892","labels":{"en":{"language":"en","value":"Deterministic asynchronous automata for infinite traces"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 695000"}},"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":"Q1338892$FF3EBACD-6459-4A38-B62E-ECA0FC420266","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2a6506376bf82afde7aacee87194b6e28a02031d","datavalue":{"value":{"text":"Deterministic asynchronous automata for infinite traces","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1338892$7D3EA228-2B42-4E81-BF91-E7BABA5CE504","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6b8d9fc1ee90599cc5e2224da75e445081767410","datavalue":{"value":"0818.68100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338892$46579812-04BC-4B22-8599-8906B4A00016","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"50d6d29680b79745263d25436c056424354b1f79","datavalue":{"value":"10.1007/BF01178512","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338892$CC9362E5-B48E-4E8E-BE04-18BE30F347A7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"81c83c28843efefafe1f80734e19c2e6ff309a9c","datavalue":{"value":{"entity-type":"item","numeric-id":213104,"id":"Q213104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$A23B1FBC-ADE8-44F3-9EDE-B62AB787374D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5a53865c1f184b73cba92d65c57544179b9e023","datavalue":{"value":{"entity-type":"item","numeric-id":407517,"id":"Q407517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$59175582-0D60-4E28-9378-11AF7FF84EEF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$E95BAAAC-49CA-4FEC-AD01-5F66C92C28F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3816e5ad4c8d1e2e98cee6e1e740e168fa32f19b","datavalue":{"value":{"time":"+1994-11-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1338892$7CE767F3-ED33-45E7-AA07-666145FDAB4F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"32e215513997d4ea50989b3fefab855a0d6156cf","datavalue":{"value":"Infinite traces form a suitable framework for describing non-terminating concurrent systems. Especially interesting are systems which may be observed using finite state devices. From the automata-theoretic viewpoint we are interested in automata with distributed control, more precisely in asynchronous cellular automata. The main result of the present paper provides a positive answer to the main open question in this field and extends McNaughton's Theorem from \\(\\omega\\)-word languages to recognizable real trace languages. Concretely, we show the equivalence between the family of recognizable real trace languages and the family of real trace languages which can be accepted by deterministic asynchronous cellular Muller automata. As a special case we obtain that every closed (w.r.t. the independence relation \\(I)\\) \\(\\omega\\)-word language is accepted by some \\(I\\)-diamond deterministic Muller automaton.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338892$DFCF1F0C-DD93-45C1-BAA8-EE737E2A7FFC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338892$BAEC80D6-11C9-4833-98F6-4E2BDFC52903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338892$F4D89884-9D6E-4084-B862-64F8A70E3DBA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6f7ae2d3679ee60f56568e642f050cc06a51340a","datavalue":{"value":"695000","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338892$5F1B6707-AA70-4E82-A85D-920C28346926","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91e54f0fcca86d22578fde7c7afa55151c5a5352","datavalue":{"value":"infinite traces","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338892$4B40188A-FD40-4E73-A711-2AD67C168964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea5c13ab3d5e22591bdcd6db68685adaa33e6ef3","datavalue":{"value":"non-terminating concurrent systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338892$17223E89-E9DA-4B78-B93A-B6CBEF6DA577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a9aa08d4be7bede55b28d707a559b83a7a8ca40","datavalue":{"value":"Muller automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338892$949827B7-1B1A-4657-A7DB-97F55AE14B8F","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":"Q1338892$F723DEC0-C1A2-4373-8CD9-2B503A04B451","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"71f809b829ad226aaf187e107ba4f2f8abde5cfa","datavalue":{"value":{"entity-type":"item","numeric-id":1066675,"id":"Q1066675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$6C21A3C7-1131-4095-97CF-9DAFFE475B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2321ffc17406524f453e4fee8339197a12bf2512","datavalue":{"value":{"entity-type":"item","numeric-id":2536784,"id":"Q2536784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$5A11EDA5-B4C0-4E37-AB80-A166BBE5ED9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cad72f183563a822760617a5ef6445d62af8f5b","datavalue":{"value":{"entity-type":"item","numeric-id":690237,"id":"Q690237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$574ED1D7-FFC1-40B5-B9E9-9218055728CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78b31a52389be07054ca875395c649c7b29fc713","datavalue":{"value":{"entity-type":"item","numeric-id":3736919,"id":"Q3736919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$76203E8F-4EA6-43CC-B0FB-5CE6F96DC1BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c3224b3ee4e2065842acb7ecef1d84c9102fafc","datavalue":{"value":{"entity-type":"item","numeric-id":1188891,"id":"Q1188891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$0EC7CA7F-284B-4338-986C-932E3BB61D1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cf863f54a7b5b61ab2956c2c67d3998a92fbdef","datavalue":{"value":{"entity-type":"item","numeric-id":4035661,"id":"Q4035661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$9D4CB385-2B1C-47CC-A7A9-1EC596F7D48A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68f0fcb34bc14db9e31435b24f5733f70168f374","datavalue":{"value":{"entity-type":"item","numeric-id":4035660,"id":"Q4035660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$E6BB65FB-CE9C-4254-AA93-9388D17A1819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1a6c071c6e2d18eb21a8b04c6da14687ed1a771","datavalue":{"value":{"entity-type":"item","numeric-id":4036568,"id":"Q4036568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$A9AC4BD9-A383-435B-BD9B-CD781186E1F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61d0c0414f31a6b3576fbfd0d45b9a6a5da110cc","datavalue":{"value":{"entity-type":"item","numeric-id":689293,"id":"Q689293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$6E297D81-10C2-47C2-B33E-EE61DA18749C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c97a70b43971e16830c739a7218a89c43f2b2a45","datavalue":{"value":{"entity-type":"item","numeric-id":911785,"id":"Q911785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$0608039A-59F1-42CB-A8E7-EDE21560FC87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a5aa94c8e45c27c05c3a12795740c87d5e2ef2f","datavalue":{"value":{"entity-type":"item","numeric-id":5613960,"id":"Q5613960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$01E0112A-7BD2-4155-8D8D-C6AEFBB9DF74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f1d821bd2a1a38500df8bdaf1b0ad70b8c8ee08","datavalue":{"value":{"entity-type":"item","numeric-id":4385530,"id":"Q4385530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338892$888E71A3-B25D-4E8C-A640-37F52475F43A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efde864148a3f63c6447ead1be04afe4517d561d","datavalue":{"value":{"entity-type":"item","numeric-id":4281564,"id":"Q4281564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a3976a9be589a575457ae780dd2be0e2f68dd79","datavalue":{"value":{"amount":"+0.983461","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$615F48EC-382D-448D-B9FA-49A2BF8EC2F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8663cc87ce4b3be91c83e5c36e992c1ec9696f8b","datavalue":{"value":{"entity-type":"item","numeric-id":4632421,"id":"Q4632421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8527dc0fd4bacd5934ca234e860b77b53c1b421f","datavalue":{"value":{"amount":"+0.9218693","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$C32BA3C6-1363-4700-982C-8940E9223F8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25f7e1b9512a31c8daa13fc8dca4072cef8c5c1a","datavalue":{"value":{"entity-type":"item","numeric-id":3988805,"id":"Q3988805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e84e308cdabf221a9dc6f3090c15a2a9eb0747dc","datavalue":{"value":{"amount":"+0.9108932","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$A0F4F4F9-F606-4C9C-89C5-9DD8BF7DB5EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57b430e41bc354431e2e1e881c4cc973571b7e06","datavalue":{"value":{"entity-type":"item","numeric-id":3687721,"id":"Q3687721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"875ac1ded53a1b1782def10bda200d478a227fdb","datavalue":{"value":{"amount":"+0.9090904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$8BFCC64F-89EA-4BA1-A89A-117D5EF3C195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b9904743748c66ea912c84ddd5a54348885705d","datavalue":{"value":{"entity-type":"item","numeric-id":4721652,"id":"Q4721652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"875ac1ded53a1b1782def10bda200d478a227fdb","datavalue":{"value":{"amount":"+0.9090904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$246BC60B-F652-4D1B-84AB-97EC2503C3FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e8aee3a9446ce1ad90bccce4d8967483d37e7ff","datavalue":{"value":{"entity-type":"item","numeric-id":5465887,"id":"Q5465887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf6b670831e69b04219fa63ed75a8713825aa1c3","datavalue":{"value":{"amount":"+0.9048394","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$6836B381-59B6-4683-81AC-332460FE9302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"661abb18f5b1bb5214599d8a0efb01b7c72bbc94","datavalue":{"value":{"entity-type":"item","numeric-id":466372,"id":"Q466372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ae5c3ed88cc4e07363ec908d32e0c2acb13ef9f","datavalue":{"value":{"amount":"+0.90233994","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$A586AFB1-F320-4E00-9FCE-AB9180068D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ae9b72c54beff00de5f6ade89e1411e6c65ca51","datavalue":{"value":{"entity-type":"item","numeric-id":5204349,"id":"Q5204349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fec3b9fd6f46a0ac375f29580964f6d1aed97dbb","datavalue":{"value":{"amount":"+0.90122265","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$0A897C72-6E54-41B8-B296-DCE34111BE82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b8544193c205327b3ab79cb57e852044d1a3883","datavalue":{"value":{"entity-type":"item","numeric-id":2956703,"id":"Q2956703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e798f79c910db06292a2e39950a72e31caceb9b3","datavalue":{"value":{"amount":"+0.8972882","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$74F8B27B-CC8B-44B5-A939-DEF4F6DBEB74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ee9622da94a14b5384fc661baf961060fdb5241","datavalue":{"value":{"entity-type":"item","numeric-id":3761703,"id":"Q3761703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e0caf3d68dd0b9bbfc383f939eae0344b192431","datavalue":{"value":{"amount":"+0.88092506","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1338892$F2DE213E-2659-4668-B648-F5325E7C4FE6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deterministic asynchronous automata for infinite traces","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deterministic_asynchronous_automata_for_infinite_traces"}}}}}