{"entities":{"Q897653":{"pageid":899501,"ns":120,"title":"Item:Q897653","lastrevid":57211113,"modified":"2026-03-27T11:56:59Z","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":"Publication:897653","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:897653"}}}}}