{"entities":{"Q897653":{"pageid":899501,"ns":120,"title":"Item:Q897653","lastrevid":65179434,"modified":"2026-04-12T00:51:07Z","type":"item","id":"Q897653","labels":{"en":{"language":"en","value":"Profile trees for B\u00fcchi word automata, with application to determinization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6516969"}},"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":"Q897653$DE59F18B-A452-409D-B6B5-32539D5A6542","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e07f38b8af0ded72eb0d23693846274558ecb0bc","datavalue":{"value":{"text":"Profile trees for B\u00fcchi word automata, with application to determinization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q897653$14AABBF4-E769-4630-ACF9-14200B30C2C5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"32ef4e305ffd62bfe165b33faf1cb7176a22db73","datavalue":{"value":"1336.68155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q897653$AF2A7781-B68A-4E77-B7E4-8BFE462E63D8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ad9b262b0ae8ff0257dddfe1046ace092645311","datavalue":{"value":{"entity-type":"item","numeric-id":897652,"id":"Q897652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$71516BDB-25F1-48B6-92EE-3108E7FE03AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3315bf391c0a058853db1fdd065cc2cb8ff023ce","datavalue":{"value":{"entity-type":"item","numeric-id":216121,"id":"Q216121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$7682FF3D-994F-4395-874B-CF0D0EABEAF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce87cbb6ded942a7df2b71cd7e21808de8efe775","datavalue":{"value":{"entity-type":"item","numeric-id":208771,"id":"Q208771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$848F0147-DCDC-4767-8CD1-C58308E6F2EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a26eaa7a3159ba545420366ef8b151ea4c3766e0","datavalue":{"value":{"entity-type":"item","numeric-id":208756,"id":"Q208756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$D409DEE6-104B-4FEA-B391-D7625D20953C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$8E7DDB23-7E8E-4879-AA19-3E084E5059A6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cafd9cf1ea33c2ca629714ee3a1d874af717ffb3","datavalue":{"value":{"time":"+2015-12-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q897653$F407CA02-7597-4850-9B53-F029D4889ECC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"74588bd6b8720a6de9f9936d9c5e50295696e5c7","datavalue":{"value":"https://arxiv.org/abs/1307.4471","type":"string"},"datatype":"url"},"type":"statement","id":"Q897653$73851774-7A16-473C-8D50-043CFC55CFA4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"11bceba6207342b1a9b2af2460ee3a21ff4c56f0","datavalue":{"value":"An \\textit{\\(\\omega\\)-automaton} is a finite-state machine that reads an infinite word, on a finite alphabet, \\textit{accepting} or \\textit{rejecting} the word according to some \\textit{acceptance condition}.  Originally introduced in order to study monadic second-order logic in the 1960s, \\(\\omega\\)-automata have found numerous applications in computer science as a natural model for non-halting computations.  A central question in automata theory is whether, and how, one can replace a nondeterministic automaton by a deterministic automaton accepting exactly the same words.  This question is quite complex in the case of \\(\\omega\\)-automata, where it has been shown to depend on the type of acceptance condition. For instance, deterministic \\(\\omega\\)-automata with B\u00fcchi acceptance conditions (B\u00fcchi automata for short) are strictly less powerful that their nondeterministic counterpart. While a nondeterministic B\u00fcchi \\(\\omega\\)-automaton can be determinized, this process will, in general, yield a deterministic \\(\\omega\\)-automaton with a more powerful acceptance condition, such as a Rabin acceptance condition.  While many approaches to determinize B\u00fcchi automata have been developed over the years, these processes are quite complex and involved. The objective of this paper is to develop principles, concepts and data structures to advance the understanding of the theoretical principles underpinning these determinization algorithms. To this aim, the authors extend their \\textit{profile-based} approach [the first author et al., Log. Methods Comput. Sci. 9, No. 1, Paper No. 14, 26 p. (2013; Zbl 1274.68158)], based on the history of visits to accepting states. In this paper, they introduce a \\textit{profile tree} and show that it allows to develop a new singly exponential B\u00fcchi determinization construction. Contrary to previous approaches, this construction uses a declarative rather than an operational definition for the transitions between states of the deterministic automaton.","type":"string"},"datatype":"string"},"type":"statement","id":"Q897653$F14DDB26-4972-4F10-AFEC-76EE08F0CED2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2daced9896460a81c4c40ff31087aa019e14cb22","datavalue":{"value":{"entity-type":"item","numeric-id":420851,"id":"Q420851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$69FE12D5-3F20-414D-BD78-1C786395852C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q897653$5BC92371-9317-4AD4-90A3-505A1C4CAB07","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"06e72c48b598e92f530cc6362a428ff4862e0784","datavalue":{"value":"6516969","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q897653$E8326998-5615-4F40-B42B-160AD6AF775A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68c261570392928413cb911f93665f42e10898b6","datavalue":{"value":"automata theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q897653$3BB8363A-41FB-4CAC-8405-BCFB58D31F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5b2c19395e09ac6b36261537309647c2eeee797","datavalue":{"value":"profile tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q897653$3A7E248F-0114-4AA3-AF36-8CDC8A4CD375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"368d848d590d02bf21d46d7cce474423bcbd6212","datavalue":{"value":"B\u00fcchi determinization","type":"string"},"datatype":"string"},"type":"statement","id":"Q897653$9C31870E-DF7B-4903-8783-2139FA8BC614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30e6756aff539cfabd95230b27e3568ddb419f44","datavalue":{"value":"B\u00fcchi profiles","type":"string"},"datatype":"string"},"type":"statement","id":"Q897653$7FCAED1B-7AF4-46F9-B464-4C16936D75D5","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":"Q897653$6FC3CC9C-88FA-4536-B667-48655E92B017","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a78dcdc13bd528936f19ceedba803b623a306c9d","datavalue":{"value":"W1495139601","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q897653$FC126091-C19E-41F8-8C7F-A87584DF7346","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d969bd9e9070eb4e4b53be99bf5557f5f64d3d3","datavalue":{"value":{"entity-type":"item","numeric-id":3455546,"id":"Q3455546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$7020E89C-73E7-45BA-BA93-BC33BDA44783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82660ea6e68064c8837b6780b26e46058411945","datavalue":{"value":{"entity-type":"item","numeric-id":860867,"id":"Q860867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$EC415601-7127-4CF9-B3D7-D72A216F7F78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06c411f40bd3fed70a734570dda325013084ac01","datavalue":{"value":{"entity-type":"item","numeric-id":5525343,"id":"Q5525343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$25C01A60-2590-4CFC-B296-FCB89344D1DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c71ee253892b177799592f03938a61eb6c7732cc","datavalue":{"value":{"entity-type":"item","numeric-id":4369884,"id":"Q4369884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$14EF226D-4CB6-4F1B-ABD0-289A0146F214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e41e590ac256592516927020d2f60958d61dd6","datavalue":{"value":{"entity-type":"item","numeric-id":5758127,"id":"Q5758127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$153321A0-CBA0-466D-977E-B056FC826830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1f9c53c6f494471f72e1c0519150de6221c5ccb","datavalue":{"value":{"entity-type":"item","numeric-id":5484906,"id":"Q5484906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$CFF1BB02-0A85-497A-BE7B-D19A79FB2A5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"974d27bb6ae96f431a93b0bde28566a067e2dbb4","datavalue":{"value":{"entity-type":"item","numeric-id":4913776,"id":"Q4913776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$8D000F19-E22C-43DB-8FC8-A677F2D44D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e75cfb2ab625e62feb4087fd15200cab4e676b83","datavalue":{"value":{"entity-type":"item","numeric-id":3557078,"id":"Q3557078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$82532953-3C55-4325-98FB-A92286E9FAE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdbace6415d89fca5d9ba31adb1a3b4e1ba6373e","datavalue":{"value":{"entity-type":"item","numeric-id":3549125,"id":"Q3549125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$23F56F2E-5AD9-4DE1-8391-444794986892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b388c0771db5db3897588379bd4b417551adfb47","datavalue":{"value":{"entity-type":"item","numeric-id":3521961,"id":"Q3521961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$CAB44570-4ED6-4044-ADA7-F3B2D3EA7B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a592cba5bd50a769a8b95145033ff13a570cf73","datavalue":{"value":{"entity-type":"item","numeric-id":5573396,"id":"Q5573396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$15234814-A8C2-4CE3-84BD-6916F21119D9","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":"Q897653$7EFD2D82-39A2-4DEE-9137-EE3481230FE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88c8d4ae13a37c46d4c1c81628960f47d5dea327","datavalue":{"value":{"entity-type":"item","numeric-id":673778,"id":"Q673778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$534F0014-D9CE-4366-92AA-E7EB2E288328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22776ab6df6d965eee7a85c38c01c6d8ff808663","datavalue":{"value":{"entity-type":"item","numeric-id":5426071,"id":"Q5426071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$61EACE8D-8F30-46DD-8979-5ABBF0DDECF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0100b938aa02592e3dcec5a016d883a9d79cc50a","datavalue":{"value":{"entity-type":"item","numeric-id":4205072,"id":"Q4205072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$37667C0C-6DB2-4262-912C-6E946229D1FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8107b480decc678c92b78dee11f4a9915c90692b","datavalue":{"value":{"entity-type":"item","numeric-id":5541339,"id":"Q5541339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$6E8A2EDC-C63F-4869-AF7C-DB4D6FBF097B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66c3da6e8e22eb9ce673b708daba3d803e9c1df4","datavalue":{"value":{"entity-type":"item","numeric-id":5390016,"id":"Q5390016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$47E6B519-3D06-403D-99BB-9DA73F64FD10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f353ad170e54f87f94c55f9cea2b36a3ecf99c4","datavalue":{"value":{"entity-type":"item","numeric-id":3617728,"id":"Q3617728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q897653$4EDB55B4-A43F-4601-9EAF-6F25BC75FC04","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e70ebc8ac710ca430889559a8e2db3424375d515","datavalue":{"value":"10.1016/J.IC.2014.12.021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q897653$14F73537-3452-4D46-96F2-2F0AB4E11AEF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3017c978ea879f454a8cc8fee6ebb5ca366588c3","datavalue":{"value":{"entity-type":"item","numeric-id":4992510,"id":"Q4992510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4590da4ff590dfa2bb680c1f631ce6887d722300","datavalue":{"value":{"amount":"+0.9970982670783995","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":"Q897653$AEC872CE-E7C1-4D32-89CC-A0724B2CD261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b7b10ca4c7bd34d2c044f6e5de59df3355ce9ab","datavalue":{"value":{"entity-type":"item","numeric-id":5357716,"id":"Q5357716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"591493c39bc4a65f7bbf2f0b44d076e433d4fccb","datavalue":{"value":{"amount":"+0.8003726601600647","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":"Q897653$323E2EA2-495B-4E88-BF8B-EFDF8527BBF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ace26560213f4f91c20cc22506856b9aa482da80","datavalue":{"value":{"entity-type":"item","numeric-id":3617728,"id":"Q3617728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"565c3d30dee0d8979bb0d9d03497de73eb41aaa6","datavalue":{"value":{"amount":"+0.7811987400054932","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":"Q897653$3D82D323-EFFA-4B25-B39A-96B9475EF26B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"330e625f62b26c8b69560aa1974f69f682f12864","datavalue":{"value":{"entity-type":"item","numeric-id":4913776,"id":"Q4913776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6a1f0036b7c8bfe5283a6495691d6a273cabe66","datavalue":{"value":{"amount":"+0.7693323493003845","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":"Q897653$27A19F58-3BFF-441A-BE74-A9B1F183219C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"942c381afa7b827065ff879595611113ac99cd86","datavalue":{"value":{"entity-type":"item","numeric-id":989532,"id":"Q989532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1fc07f68f7ce5c79ad9bb070a00f3464cc3af54","datavalue":{"value":{"amount":"+0.7670731544494629","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":"Q897653$B1E2C168-1996-4DCF-BAAA-FA8E25BD3486","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Profile trees for B\u00fcchi word automata, with application to determinization","badges":[]}}}}}