{"entities":{"Q1178688":{"pageid":1189437,"ns":120,"title":"Item:Q1178688","lastrevid":66437022,"modified":"2026-04-12T10:04:08Z","type":"item","id":"Q1178688","labels":{"en":{"language":"en","value":"Generalized automata on infinite trees and Muller-McNaughton's theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 22280"}},"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":"Q1178688$95E726AD-40C3-4CFA-BA3C-71DFAA2DAC39","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63a9f6ad48a408b84e70e18354109a6b049c9fe6","datavalue":{"value":{"text":"Generalized automata on infinite trees and Muller-McNaughton's theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1178688$B08FE718-7F28-4E11-823C-F7878FB60A74","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d27addfff16ede61f5d8baffc75eb92cbf800309","datavalue":{"value":"0753.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178688$10C8A091-37FB-44BB-B7FF-AC19E9118FB7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a39fc96cfb6812d3e637a09ad6a74dbc30b07dc5","datavalue":{"value":"10.1016/0304-3975(91)90158-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178688$A4B225CE-93A2-4D87-A8E7-5E816F640695","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":"Q1178688$7CD5FFDC-6DB3-4125-ADD5-08178458B0C6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1178688$8103EF87-71FC-4504-BB58-61F03B34535C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c9cc6fc26d4da3bbf3aabed905066b8764ab1e16","datavalue":{"value":"The Muller-McNaughton's theorem characterizes those \\(\\omega\\)-languages which are accepted by deterministic Muller automata in terms of \\(\\omega\\)- languages accepted by deterministic B\u00fcchi automata and in terms of regular languages and their limits.   The concepts of automata on infinite trees are introduced and various concepts of languages accepted by them are considered, too. The relations between them are investigated; in particular, a number of equivalences are proved. It is proved also that, in all considered cases, the nondeterministic top-down automata are more powerful than the deterministic ones some formally possibly generalizations of the Muller- McNaughton theorem are considered, and a number of them are proved to be wrong.   The paper contains a very nice survey of previous work in this area and is written extremely clear.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178688$EC16DC5A-CF4D-4220-91DD-6186802301E1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178688$B12C907C-0F35-4853-A7CA-F73E5B15E6E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178688$70FB37A7-0939-4AF8-9BFC-C84ABB8DAD24","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"925588fef3d0a72ef7d48727659edc2b4a4324e8","datavalue":{"value":"22280","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178688$5FF53819-26D0-447C-AC32-650EED1EFA68","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74fa260c5e3669747340bc507aa2bf686583847b","datavalue":{"value":"automata on trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178688$C032DE34-F69E-490E-A7F2-AFE6656688D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b79c0d46aaed6ae08d529961c9f16b783e44803","datavalue":{"value":"Boolean algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178688$8B1545A3-B22B-403A-BAB0-0B9E15F77588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a0e90a6bc6b662cf81be51dab3806970b4b8374","datavalue":{"value":"Muller-McNaughton's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178688$29BEB0A8-B541-43EC-8174-08DAC4B4A628","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"15744af71e21635dc7da119af963401e48a386e5","datavalue":{"value":{"entity-type":"item","numeric-id":2102735,"id":"Q2102735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$B9C90ADB-BE2B-4C71-A6E6-DD838DA6BD84","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":"Q1178688$D84B7B0E-3047-474B-960E-20EAB809A31E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b83c570bc0fa5f34151a69008a196fd7d52f05","datavalue":{"value":{"entity-type":"item","numeric-id":3900995,"id":"Q3900995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$5EEC2C9D-D31E-4464-BFCC-86C6BFB0F23F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08341059441af41c6921638de5b990f0ab22c6e3","datavalue":{"value":{"entity-type":"item","numeric-id":3907107,"id":"Q3907107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$FAEAA2D3-F215-4D0C-B6FC-C9DFA4DA4875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7409ce12fc521e911d6f4a6b767611cba400d27a","datavalue":{"value":{"entity-type":"item","numeric-id":5517677,"id":"Q5517677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$350258C8-EDD5-443F-A2A7-89BF623F71AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb7b8847a36d076106e01f43c31a170940dd0b60","datavalue":{"value":{"entity-type":"item","numeric-id":1055184,"id":"Q1055184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$D4573F2E-F7BD-42D8-8926-AE8735B242D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d17eb8e40f56b25f178197677473f6105c881e4","datavalue":{"value":{"entity-type":"item","numeric-id":2544414,"id":"Q2544414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$FFD35667-544D-4F0F-AB53-8D07A9AA8AE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef24932abd74e01a026e2e349f03bfd5726d23f7","datavalue":{"value":{"entity-type":"item","numeric-id":4102764,"id":"Q4102764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$0DF21C51-7D67-4795-8E56-09ED3F5CBE2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d34b279e5665ff3f0c5e6f8ec73982d94e9f3ec4","datavalue":{"value":{"entity-type":"item","numeric-id":3036724,"id":"Q3036724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$67B23EFB-7257-4D9F-97DF-FEA737607B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e04745da850ebbd99ee2ce2575f78f2d3a6415c5","datavalue":{"value":{"entity-type":"item","numeric-id":3998008,"id":"Q3998008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$90093789-F1CB-4996-AE05-079B4BFC8160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6e3b1d18c33ecfb7859f089b824dc234ba28b3b","datavalue":{"value":{"entity-type":"item","numeric-id":3341934,"id":"Q3341934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$C91699C3-CD8E-428C-9A8E-4B3999179B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee5b069c4c3ceb2ba2c3ab0fe00dda9539a1f8bd","datavalue":{"value":{"entity-type":"item","numeric-id":1068544,"id":"Q1068544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$275AF19B-CD93-4916-A8EC-DD6B3453CA2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7161985b274b14fb28a3ad2e286151fe52dcea0","datavalue":{"value":{"entity-type":"item","numeric-id":4726235,"id":"Q4726235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$3705B041-ABDE-4C87-9126-0894F63228A3","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":"Q1178688$6CC1A6C2-90FB-49E9-85A3-577F2FC903A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd038af78bc81754eb27c5ac17d87619fd663342","datavalue":{"value":{"entity-type":"item","numeric-id":582913,"id":"Q582913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$9A27EE3D-80E6-402A-AA1A-9C74D7CF06B8","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":"Q1178688$C55C4B75-6AF1-4D87-8F3E-EF06D14B3F97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"300e1e7990d1f1904b1034a2731e332147efe257","datavalue":{"value":{"entity-type":"item","numeric-id":5616162,"id":"Q5616162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$82582250-B21D-4A56-8820-1447C8085518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e906d51c56a617427af2f93b5291f250dafc8c40","datavalue":{"value":{"entity-type":"item","numeric-id":794179,"id":"Q794179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$3275FB7A-A001-46CA-81D8-D08DF0412B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b48fcb02d6e81a5897367606519605757835a93","datavalue":{"value":{"entity-type":"item","numeric-id":5538923,"id":"Q5538923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$FD1E0006-8DDF-44BC-941A-05E98E50FC41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be575331d770a3844c9a53865201d97f80b083ec","datavalue":{"value":{"entity-type":"item","numeric-id":3967525,"id":"Q3967525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$ABD62E46-EA56-413E-8E3C-D1AF63C4F583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15fb510d752d28c4cf4a7d891afb159d6461435e","datavalue":{"value":{"entity-type":"item","numeric-id":3934375,"id":"Q3934375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178688$E1B8E132-AC57-4268-9D42-44C459C7D0D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"269c3d28265e7ee693fe35fb41f9c0ba626209cf","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90158-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1178688$DCD75B10-CF5F-40D2-AB43-1EE839D34BBE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e6a885048f4d6025d7834df853e78a87dbe96178","datavalue":{"value":"W2085563320","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178688$A3B0DCF3-6293-46EC-9B64-4201F6A82276","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9873ff86ed7854fea58f938136888f9bb766d763","datavalue":{"value":{"entity-type":"item","numeric-id":1186604,"id":"Q1186604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cefa7d7e505634cab8457317c09ed78e7e477869","datavalue":{"value":{"amount":"+0.836207389831543","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":"Q1178688$D7EC723C-FF00-4EB9-B269-31887C38AEA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbabd355a4d8db2ad18f9144583c44bf9ba2aafc","datavalue":{"value":{"entity-type":"item","numeric-id":3823145,"id":"Q3823145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a81c6a08d94f352cefc6fd25787e142de3d45e9","datavalue":{"value":{"amount":"+0.8338974118232727","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":"Q1178688$3DB126EB-95A9-4183-9188-386F9B295EBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e53b7ab0216ed2ba427727e7e9b4b630fab1a4f","datavalue":{"value":{"entity-type":"item","numeric-id":4273667,"id":"Q4273667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0b110c84b6b4e71bdf16e238e2c78f7a69f6c25","datavalue":{"value":{"amount":"+0.8243421912193298","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":"Q1178688$5CE7B31E-E327-4AD5-ACD0-E2E93C387498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"810f94063fa2a96aae4c53e77dbdb3695af494c6","datavalue":{"value":{"entity-type":"item","numeric-id":582913,"id":"Q582913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceaa015b1d92a277a80f01c6422146fd1c9c370a","datavalue":{"value":{"amount":"+0.809912383556366","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":"Q1178688$6BA8ABA3-65C0-4FE2-AAFF-5CAD82E30B0D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized automata on infinite trees and Muller-McNaughton's theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalized_automata_on_infinite_trees_and_Muller-McNaughton%27s_theorem"}}}}}