{"entities":{"Q1077932":{"pageid":1088684,"ns":120,"title":"Item:Q1077932","lastrevid":66828354,"modified":"2026-04-12T13:08:07Z","type":"item","id":"Q1077932","labels":{"en":{"language":"en","value":"Alternating tree automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3958738"}},"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":"Q1077932$1EC11802-BC0E-4F28-8D0A-45849AEEA010","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8567b7057774188d9b1ed2bc014b4c218ce93c82","datavalue":{"value":{"text":"Alternating tree automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1077932$D4CAD8E7-B39D-4D58-A6E0-9F19FC215C75","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"00288ade24c02182c73aee1042044faa93053cb7","datavalue":{"value":"0595.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077932$18CA421C-7A48-4723-8BAB-F2AEC5E38887","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3b8fc467c878bf236f9b5ade76d1780dca731a6f","datavalue":{"value":"10.1016/0304-3975(85)90077-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077932$7DB95AB5-AB17-4E7C-A85F-345EFEED2209","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":"Q1077932$EB49EEBF-BE9E-465D-BE41-4A7390F417C4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1077932$4F65A9E5-E61F-4B5D-B745-9D5A53D09F66","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"00302bf0f0e3e283d6e336922c6cfce7ec4fe045","datavalue":{"value":"The concept of alternation has been introduced by Chandra, Stockmeyer and Kozen as a natural extension of the concept of nondeterminism. The effect of alternation has been studied in the context of computational complexity, automata theory, algebra, dynamic logic and combinatorial games.    This paper discusses the effect of alternation on several varieties of tree automata. In the case of top-down tree automata, alternation turns out to be equivalent to nondeterminism. In the case of two-way tree automata, alternation turns out to be more powerful than nondeterminism and alternating two-way tree automata define exactly RECOG, the class of recognizable tree languages. When the two-way tree automata are also equipped with a synchronized pushdown facility, then the alternating version is equivalent to the deterministic one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077932$2317023E-9A3E-4EF6-97E5-204FBF88C6BC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077932$F62D9181-8760-4E0B-B8B7-D225B6AF280C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077932$E3B44F94-B975-4EA4-9600-2F8878261B96","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3053d8d80023e3fe6be0e348b34ea1dc15b4b9b4","datavalue":{"value":"3958738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077932$7DFB5C63-593F-4C92-8C3D-5F0E5735BAA0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8248a1dce4178bcbdf50d1b921f9653b658d3d1b","datavalue":{"value":"alternation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077932$2818D104-CC16-4595-9D2D-1590C2650891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f532e2b08234dd6967fc70eafbf0c8f20a836d3e","datavalue":{"value":"nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077932$4ACDD45A-6A8D-4C2D-B55F-2082680CF4AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44145f7b77d9cb4361d75410e1fefe0aa54ec2e4","datavalue":{"value":"recognizable tree languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1077932$2DF21E66-13FB-4875-A03F-21011EDCC62D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ba637809b53e4790813aa0d55f52c072a29a3af","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$2B186236-CFA1-4E2D-AE87-8D39BF6C1791","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":"Q1077932$5A3AB04B-11A3-4F45-BF0A-4A1F0204AF38","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ce5a505e36d0afd8cf6427745ccec4c24da792f5","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90077-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1077932$AB2DF491-80BD-4FF4-97C9-F4A981BD65E4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c9dac9651de3356a34a15f00a293b89840023cef","datavalue":{"value":"W2115587183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1077932$BE822049-424E-4101-A9ED-D3145A0C6088","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$C67E9FCD-B348-43EA-9EF6-69BF5AE72A01","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":"Q1077932$2286C22B-5025-4762-8E13-7962B2A687EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b643a8d09bd8403e1962f987e39daf358462913","datavalue":{"value":{"entity-type":"item","numeric-id":4954439,"id":"Q4954439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$B87B9C87-9E63-446A-AB77-B2C34B6DDDBF","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":"Q1077932$A06303F6-8D7E-4863-A538-149C09B33E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"980a6530e26b95b1ccced773b6d57739ceae5608","datavalue":{"value":{"entity-type":"item","numeric-id":1136239,"id":"Q1136239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$D0173CF9-EF40-4CD9-AB55-78CC0E39BE17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a4d1b54f39385e475024bcf36a9244162838f1e","datavalue":{"value":{"entity-type":"item","numeric-id":1137036,"id":"Q1137036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$F5C1E44E-B1FD-4D98-8464-01296696B844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87fba3c352dd072afdaa3ef7f373c14213882346","datavalue":{"value":{"entity-type":"item","numeric-id":3662632,"id":"Q3662632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$F81D0147-98C0-428D-BD45-3111C41E1AE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c36f5fc0175b05ce89677072f9081151bd22eac","datavalue":{"value":{"entity-type":"item","numeric-id":3862399,"id":"Q3862399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$0D906007-3B64-4283-942C-CC53CF47E3A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eff7b494305474d41d7d2b0a9428a63fd5d0cca","datavalue":{"value":{"entity-type":"item","numeric-id":3940852,"id":"Q3940852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$37BE385B-CDC9-4AB7-A1A4-93CE4BA0CB1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36e3848cdc04c763ff41f4fd530dd2e68c6a199b","datavalue":{"value":{"entity-type":"item","numeric-id":2542994,"id":"Q2542994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$81DBAADC-577B-41AB-9821-CC70F501A688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"671f946425b9d8a9eed0a4cf558cd13d172e4050","datavalue":{"value":{"entity-type":"item","numeric-id":5583072,"id":"Q5583072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$5CE41B54-E59F-4DC2-90A6-C30F790ABCBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"348ea46eb2336e82df887e43a2ff889e1f10ee80","datavalue":{"value":{"entity-type":"item","numeric-id":3854623,"id":"Q3854623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1077932$3309D048-14DB-4F43-8EE0-F85F65ED7394","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":"Q1077932$1448F2B7-2F83-4FB9-9019-4876515405E1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0562f737c75d8f8326adf7238cdf8e0fafdb15d","datavalue":{"value":{"entity-type":"item","numeric-id":3813317,"id":"Q3813317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8b5cfa60bec46a30fa93e70e7c9bc0443072a3b","datavalue":{"value":{"amount":"+0.9652324","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":"Q1077932$20428719-719A-489A-BB2A-73F55939421C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5f9548e0e5517a8ec8429f1b31c063f18ae0ac1","datavalue":{"value":{"entity-type":"item","numeric-id":1098325,"id":"Q1098325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cf66876ddf85d1c628b645d7e8a66e2aebe6626","datavalue":{"value":{"amount":"+0.9383876","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":"Q1077932$7ED905C5-5E76-4106-BB05-E499C1D6FD62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26b23d56f33c2b6272b64d1ff018d2c0fba7bcb6","datavalue":{"value":{"entity-type":"item","numeric-id":2373699,"id":"Q2373699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9d63c585c3f00a6cc87862c41fa192ea3aaccb0","datavalue":{"value":{"amount":"+0.9333328","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":"Q1077932$BE377D0D-7BC6-43DF-BFE9-899A233294BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f61004ea8e4f7b0c70b1994a76a44468198461be","datavalue":{"value":{"entity-type":"item","numeric-id":3323279,"id":"Q3323279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79a5fe39222bd5280886bd2e229cb74752387109","datavalue":{"value":{"amount":"+0.93088245","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":"Q1077932$31C2E717-DE7A-4F6A-8935-E10288E7C46F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9f050ed4ab60c36104be5fde193343566d5d68c","datavalue":{"value":{"entity-type":"item","numeric-id":5418248,"id":"Q5418248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac9ccc9a6d685d9f0d8d722da65d44b8bc7e5c87","datavalue":{"value":{"amount":"+0.93088233","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":"Q1077932$8A975A3B-DA18-4335-B236-09E8CEBDA80B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39203a70f53ca53a941d0348c9bee56a36a13d5f","datavalue":{"value":{"entity-type":"item","numeric-id":4036177,"id":"Q4036177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6245c562f3bb814c55213c88da27cc6492f3804","datavalue":{"value":{"amount":"+0.9217863","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":"Q1077932$CAE33945-CAF3-44FF-A5C2-618D01A6FEEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf8102ca51d7b3ea87836bad642376bdeef6da75","datavalue":{"value":{"entity-type":"item","numeric-id":3306921,"id":"Q3306921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41e4393b16a0c98d634a024e42e80fecc8605e38","datavalue":{"value":{"amount":"+0.91128445","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":"Q1077932$76A85BF8-A84A-4CAE-AA7C-E2CEF4B38209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96745fba719914b12ac11b6f4ad0a2e0133ee129","datavalue":{"value":{"entity-type":"item","numeric-id":4412832,"id":"Q4412832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd3395380162001325f6710a02bf6f5d3764ccc9","datavalue":{"value":{"amount":"+0.9077053","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":"Q1077932$43F2CFD5-9850-46ED-9BC4-4BDC55272460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0204b868bbd8b6798edf95391f9a77b6a6270eb4","datavalue":{"value":{"entity-type":"item","numeric-id":2881089,"id":"Q2881089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5383e7f5acb5044a2a28e73c508743632125940","datavalue":{"value":{"amount":"+0.903312","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":"Q1077932$E6A67F95-C1C1-451E-8488-3EF702E7D0F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0aeb899e390ce625a7e72f5900defd7828c3373f","datavalue":{"value":{"entity-type":"item","numeric-id":796998,"id":"Q796998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f94212f0ca2aec2f66a3485711eae2e349c301e","datavalue":{"value":{"amount":"+0.90286475","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":"Q1077932$8341E487-5508-4FA1-8A00-068B6A62E589","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Alternating tree automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Alternating_tree_automata"}}}}}