{"entities":{"Q1853134":{"pageid":1863876,"ns":120,"title":"Item:Q1853134","lastrevid":71501226,"modified":"2026-04-13T22:40:55Z","type":"item","id":"Q1853134","labels":{"en":{"language":"en","value":"Complexity of weak acceptance conditions in tree automata."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856473"}},"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":"Q1853134$C6A15E47-3B76-4FE8-ABC9-84467DD72516","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6cccdaa5acfda29263c0b64d3a20e46aeaa605e0","datavalue":{"value":{"text":"Complexity of weak acceptance conditions in tree automata.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853134$29507344-FD7B-4718-92CA-2DB6E8542D76","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"159fd82bb15f62a022cf3b661c4c2db0b310aa9c","datavalue":{"value":"1042.68068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853134$8908C884-DD31-4C73-898D-639EC4C75D09","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e5fec6226692b18d15e99bf1228c77ef4fb393c5","datavalue":{"value":"10.1016/S0020-0190(02)00285-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853134$4ED37B10-2628-418E-A025-176D89D82AFF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4b77d53ae791bfd03fb89ab07091146b4eee33af","datavalue":{"value":{"entity-type":"item","numeric-id":1853133,"id":"Q1853133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$91543F7E-30E3-4628-8C42-514F8FFEEB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab04ccff5257bfd7d9df0e67238421f4fa3b71ef","datavalue":{"value":{"entity-type":"item","numeric-id":293472,"id":"Q293472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$56206F9D-0D8C-40AD-8F2F-D4F4467983A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"775a644844a555d1fdaddfac8fec302da0d27d3f","datavalue":{"value":{"entity-type":"item","numeric-id":342706,"id":"Q342706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$F401D17D-9FE6-4E42-B37A-5DD2BB6CC7EA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$C9B76A86-264D-49A7-A134-DDA1CDBE2027","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853134$DED432D7-F8FF-487F-B284-FB3F55F53040","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cd21dbe8ec0662b1716d8f0586ef8ae042963709","datavalue":{"value":"Weak acceptance conditions for automata on infinite words or trees are defined in terms of the set of states that appear in the run. This is in contrast with, more usual, strong conditions that are defined in terms of states appearing infinitely often on the run. Weak conditions appear in the context of model-checking and translations of logical formalisms to automata. We study the complexity of the emptiness problem for tree automata with weak conditions. We also study the translations between automata with weak and strong conditions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853134$50B499AA-D7D0-4B31-8BDD-7A461426C97B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853134$204E8708-74FA-4638-9B61-1F7B45BFE883","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e885d08adeb669c8e9fce92d9e0e52e06471913d","datavalue":{"value":"1856473","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853134$93E232B3-1657-4F87-BC7E-34488AD3D401","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be8eb270d4ed4b446b915ab174a0d0120cef86df","datavalue":{"value":"Formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853134$96499B16-228B-4064-8C45-FD696466238E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da67da54e89e7c80f20f3f95c3ceec18bb927753","datavalue":{"value":"Computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853134$B36CEF6B-0C27-4D62-B0AC-4CA1A40A5717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14a5a511a70081ebff631f8fb66688d8f2c0ad26","datavalue":{"value":"Tree automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853134$F3933B61-BD98-4E4D-BE15-5CFE4BC77552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad34faa9adc140ebe77aae2008a856f649d0a473","datavalue":{"value":"Weak conditions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853134$B1CEF544-3BB2-4202-882B-5427AD14B4C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ebff48246f3809f30f7f8df76d7591b802c6f46","datavalue":{"value":"Emptiness problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853134$28BA03EA-59DD-4133-BBBD-879DA5557CDF","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":"Q1853134$D632203D-4AC3-4405-B0EA-87BE5A81146F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e2131bba6823415273c7be26dbfb27eedbb2100","datavalue":{"value":{"entity-type":"item","numeric-id":3739111,"id":"Q3739111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$16372323-2E12-4125-B869-388594F8DF3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b67ee9815f7ab3c8b2b4907677d99ca915d101b0","datavalue":{"value":{"entity-type":"item","numeric-id":1164622,"id":"Q1164622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$EF911463-E24F-4897-8DB3-74D4B63EF0F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d0b3d39649082ff6de9169c6e51eb8e1d8d7a0b","datavalue":{"value":{"entity-type":"item","numeric-id":5385339,"id":"Q5385339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$1804A23A-2F5E-4020-8DFF-7F6BFEA1949F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f24dde664dec592aaf2efc66afcadf834211d90","datavalue":{"value":{"entity-type":"item","numeric-id":4055589,"id":"Q4055589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$5364A1A4-A45E-40AA-8014-3F0EB31CD439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d80c09a488acc12cbf48e92182699f69eca5d3d","datavalue":{"value":{"entity-type":"item","numeric-id":805253,"id":"Q805253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$29A6366E-75A0-479C-BE76-17901975A2F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8fc26db2951dfe925d71fa6328785bd7add11d3","datavalue":{"value":{"entity-type":"item","numeric-id":5286026,"id":"Q5286026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$42DC7B51-5B25-45AE-AD6B-4E405256382A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d617470304ae36e301a88578b6453e59d3adaf9","datavalue":{"value":{"entity-type":"item","numeric-id":3746905,"id":"Q3746905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$E0AE1EEB-60A2-4A0F-8DF2-52CCC2579755","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":"Q1853134$95CFB69B-950C-43BA-BDD0-1C26CCEFA808","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe929f01fa86af5ec1780a3fd0d8f9ac3346a63b","datavalue":{"value":{"entity-type":"item","numeric-id":4714446,"id":"Q4714446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853134$97675957-57AF-433A-9390-84A3FFA50263","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00a6d6205509fa2401173e5575ea5e26acb69cc9","datavalue":{"value":{"entity-type":"item","numeric-id":4737000,"id":"Q4737000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a280ac64b1ad59fa96993273d08c552426743da8","datavalue":{"value":{"amount":"+0.8587847352027893","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":"Q1853134$4967E1DB-ABBD-4F01-9226-0CF9DBA0AA81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ecae1fde35dfe4e78c08c7c1666f2de33c4280d","datavalue":{"value":{"entity-type":"item","numeric-id":1770388,"id":"Q1770388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a13e368b120b64c7c1a8b9f4207058c50e15cf61","datavalue":{"value":{"amount":"+0.8518587946891785","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":"Q1853134$A4366B78-2B17-42FF-8856-4F2CF50F3C17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e48903d2bd0b9073841885b1a09153ee9363cef3","datavalue":{"value":{"entity-type":"item","numeric-id":4542592,"id":"Q4542592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5be0f69cb5d1a84670575eaa50421a9c97608fcb","datavalue":{"value":{"amount":"+0.8287041187286377","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":"Q1853134$BDF12E19-86FB-49CE-ACEA-050B849EF2B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"789c66e93af945020ac63c9c5a14fa8e77c11897","datavalue":{"value":{"entity-type":"item","numeric-id":4726235,"id":"Q4726235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a5cff9b5a23b35d3a5c81679968a7151886a1c2","datavalue":{"value":{"amount":"+0.8051525950431824","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":"Q1853134$F1EDDE19-D72E-4BF8-BF87-1187FC845BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3eda6c78962043f244ba2daf061117aab3597e13","datavalue":{"value":{"entity-type":"item","numeric-id":3746905,"id":"Q3746905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67386d9dfa6c3c3eb259774f4d1e9cce561a51c1","datavalue":{"value":{"amount":"+0.7864874005317688","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":"Q1853134$95B3D1D2-D746-4FAA-9BEB-3C42F5C9A799","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of weak acceptance conditions in tree automata.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_weak_acceptance_conditions_in_tree_automata."}}}}}