{"entities":{"Q1109572":{"pageid":1120321,"ns":120,"title":"Item:Q1109572","lastrevid":42885008,"modified":"2025-07-15T17:23:28Z","type":"item","id":"Q1109572","labels":{"en":{"language":"en","value":"On alternating \\(\\omega\\)-automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070336"}},"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":"Q1109572$E8E87CFA-8750-441C-A73A-2DD77F6A805B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5cd11133424324a520bc7406620ec4403023cce8","datavalue":{"value":{"text":"On alternating \\(\\omega\\)-automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109572$127305F2-EA3A-4C3E-9450-4ACCBEBBEE02","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7953d076a1bbe5d6455ea0d0eec4e0375b6dc9ed","datavalue":{"value":"0655.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109572$6CF947C9-CC76-48C5-BF15-A900BD541D73","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"55f69918c1ed9495103b166ed2effd0b44d9cd5e","datavalue":{"value":"10.1016/0022-0000(88)90018-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109572$3AD7A3CE-9F3B-480E-9E8A-BE987C2A1D39","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4923fc2ead54179b3b2c784f587ba8091123fe6","datavalue":{"value":{"entity-type":"item","numeric-id":1088416,"id":"Q1088416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109572$BFED397C-9524-4F70-B453-3348DBA66594","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109572$C82CBBDF-2E51-4954-83BB-967E8F9D2C44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1109572$D8A4EC0C-E14E-4432-A0CF-637BB393CF01","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3dc45430c9f8cc93694809411690a26ee3d88384","datavalue":{"value":"The \\(\\omega\\)-languages accepted by finite state deterministic and nondeterministic automata have been extensively studied under six natural acceptance conditions. The classes of \\(\\omega\\)-languages accepted by alternating \\(\\omega\\)-automata under four of these conditions were characterized by \\textit{S. Miyano} and \\textit{T. Hayashi} [Theor. Comput. Sci. 32, 321-330 (1984; Zbl 0544.68042)]. The paper considers the two remaining conditions C5 and C6: if \\(M=(Q,f,\\Sigma,\\delta,q_ 0,\\mathcal T)\\) is an alternating finite state automaton, \\(x\\) an \\(\\omega\\)-word, \\(T(M,x)\\) a computation tree of \\(M\\) on \\(x\\), \\(\\alpha\\) a run in \\(T(M,x)\\), and  \\[  \\begin{aligned} I(\\alpha) &= \\{q\\in Q : q \\text{ occurs in \\(\\alpha\\) infinitely often}\\},\\\\ O(\\alpha) &= \\{q\\in Q : q \\text{ occurs in }\\alpha\\}, \\end{aligned}  \\]  then C5 is \\(I(\\alpha)=F\\), and C6 is \\(O(\\alpha)=F\\), where \\(F\\) is some set from \\(\\mathcal T\\), the family of designated sets.    It is proved that the alternating \\(\\omega\\)-automata accept precisely the \\(\\omega\\)-regular languages under these conditions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109572$4C944A1A-405D-4C18-90A9-FB14D4DC66E9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109572$7FCA0BD8-19A3-4A38-86E3-6A910C74DA01","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7da3840067997648af98c6a6e21f6729d177bb46","datavalue":{"value":"4070336","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109572$EA92931A-473F-4B04-82D1-084945EE80F0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f515424d27d017d0630befca2ee9b779fc3dbafb","datavalue":{"value":"alternating \\(\\omega\\)-automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109572$F09741E4-E941-4866-BB9A-05B7D8E43971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c0b65ec3a2203625e099be9b073fc50289e061d","datavalue":{"value":"\\(\\omega\\)-regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109572$88720947-47DA-4E5D-9389-D0A8C68058CF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"98f8d1ec5e9233000dec12f560cd1dd5afbb6119","datavalue":{"value":{"entity-type":"item","numeric-id":1650374,"id":"Q1650374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109572$CDCEEB6F-704D-4E8D-8EC6-275F46DE6F74","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":"Q1109572$B5547FFA-29D9-4BF5-B990-C0C89FB6C83E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9934fef3f84e1f673d408307e396c70476c3753b","datavalue":{"value":"https://doi.org/10.1016/0022-0000(88)90018-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109572$CC1477FC-78AD-4658-829F-5663E5EB02D4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d800cbe559e1fd638db67ab3bee6676f9c128b4e","datavalue":{"value":"W2012182995","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109572$6D4D3FB2-1FD2-4BFD-86A9-6F6A1878D630","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"534913bd52f8bff798206f4217803778d1e40622","datavalue":{"value":{"entity-type":"item","numeric-id":1088417,"id":"Q1088417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109572$FCC20BC4-A4AC-4A98-9B5C-1E3F20F4C771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e9159e9095f8ca510d538d7e9904c6f3ff891ad","datavalue":{"value":{"entity-type":"item","numeric-id":796990,"id":"Q796990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109572$9C69C81E-6882-4E16-BAA7-6EFB778AB98D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"676e0d168e75a8c1494a4e34b5d529a073c874bb","datavalue":{"value":{"entity-type":"item","numeric-id":3748266,"id":"Q3748266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109572$EC4B2E6F-D319-4989-8C7B-EE0929170E13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b476279f9ef74fddb27272ad70ec34f0a4ec2a74","datavalue":{"value":{"entity-type":"item","numeric-id":5625141,"id":"Q5625141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109572$9EBF6794-AB40-4A44-8F50-605EEDF00371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd1e092eb099a32d4d756ee9e4c56322cfbee0af","datavalue":{"value":{"entity-type":"item","numeric-id":3873568,"id":"Q3873568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109572$36827D3A-1354-4E7C-B5F9-B4A47A9D4BAE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a53a15ef638d4855ae4e6c874fb67227a0dfcf2f","datavalue":{"value":{"entity-type":"item","numeric-id":1116351,"id":"Q1116351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41bb5fdcd25def9bbd29b296c0e5046814f3cd8d","datavalue":{"value":{"amount":"+0.8735609","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$46F3C8DC-7982-4C3E-B9E9-8F90698300D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1a844520828737a6f5573fbeffe0e6c28723b4c","datavalue":{"value":{"entity-type":"item","numeric-id":796990,"id":"Q796990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cffe5db3a0fd3d252bd576bacfe78ccfc20899bd","datavalue":{"value":{"amount":"+0.8568439","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$237DBBE0-0A73-420C-8E1C-D954DBDDF20F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73640d960b1ab7ad1084d913a16cdc8453565683","datavalue":{"value":{"entity-type":"item","numeric-id":4490053,"id":"Q4490053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e82b1a83b14ad1141208ae3b9232051399112c80","datavalue":{"value":{"amount":"+0.8323289","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$672BF328-749C-4371-BF89-A774E412C435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbb331b4087ee7d14c100ea9f6d383f227ab7a9c","datavalue":{"value":{"entity-type":"item","numeric-id":1269902,"id":"Q1269902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c86c61bd3cbe4c98ca1a4e3dfd49e9ac5ab2e40","datavalue":{"value":{"amount":"+0.82234126","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$D298B4E3-91D0-4E45-9E50-4D29C4F09E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ecd3a7afc979ba117f58586761a08d8608a5ea5","datavalue":{"value":{"entity-type":"item","numeric-id":3167506,"id":"Q3167506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9720aa1b61e934f02a042b760963c2c1d877f464","datavalue":{"value":{"amount":"+0.81870496","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$4C816E5E-B78C-493D-AB69-6D8B133C4091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"565121846bdb8ab0c39285c4d4e61e7107bab56c","datavalue":{"value":{"entity-type":"item","numeric-id":800737,"id":"Q800737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"127f1daad34700ba8a8b7327f99b9f05373b3e99","datavalue":{"value":{"amount":"+0.7958522","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$FD62E41E-B01A-48D8-8C0B-5B105E9424BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"396cf242424d31957e68300a1caa9dadf3b5e363","datavalue":{"value":{"entity-type":"item","numeric-id":1061503,"id":"Q1061503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"910b6a9f93a852a5844af497562667b28bcb7efa","datavalue":{"value":{"amount":"+0.7819041","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$C6646D09-159B-4436-9036-D1846B9C07B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7839c8b4ea0a47f401fa9091ef33ab649369b086","datavalue":{"value":{"entity-type":"item","numeric-id":1058863,"id":"Q1058863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a31f4bc0e46516e88e0c9a7ef02856fc2e43d04a","datavalue":{"value":{"amount":"+0.7795514","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$A4098D72-D946-4468-B594-0AE145CC4C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e66518b10dedbf3e9692ab77947c8a72453c264","datavalue":{"value":{"entity-type":"item","numeric-id":1123638,"id":"Q1123638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eef2209899a125b694a630b4b0c188acfdc5792d","datavalue":{"value":{"amount":"+0.77008635","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$B9576BF0-21AC-4FD2-99A4-062DD6B31A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"663d441460a1530f71e776b6a6b43b67c87ee3d5","datavalue":{"value":{"entity-type":"item","numeric-id":4299865,"id":"Q4299865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0151acf45fd523a95c152e64235650ece12d6efd","datavalue":{"value":{"amount":"+0.76826125","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1109572$89CA28DC-170D-49E8-94FB-25166B0B5FA7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1109572","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1109572"}}}}}