{"entities":{"Q1623004":{"pageid":1633744,"ns":120,"title":"Item:Q1623004","lastrevid":71538054,"modified":"2026-04-13T22:55:11Z","type":"item","id":"Q1623004","labels":{"en":{"language":"en","value":"Complementation of finitely ambiguous B\u00fcchi automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6983406"}},"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":"Q1623004$F0B6E82C-6CF2-4733-BF37-739D509DCA25","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7984fc96e64b728ae6c8004344075d1740cb380b","datavalue":{"value":{"text":"Complementation of finitely ambiguous B\u00fcchi automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1623004$5524C860-DEC5-4272-A81E-963F0793A44D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c83b923764f6b525e9ae7d92ffae933fde87dd3","datavalue":{"value":"1457.68148","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1623004$74A82F64-20C9-41D6-A133-A0096EA24FED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d98384810deb701754c40fe23a3eac498b519123","datavalue":{"value":"10.1007/978-3-319-98654-8_44","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1623004$CF65FB72-FC42-419B-98BD-8823559B11D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"91a6d5b55b11b7c5072badc33d9b23eaf1c7a459","datavalue":{"value":{"entity-type":"item","numeric-id":259067,"id":"Q259067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1623004$5640D1B3-88CA-44D4-9C69-0003F4AB98D1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"18cf30b5eb4a6f9f904a0abe2b57b56fd1dee870","datavalue":{"value":{"time":"+2018-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1623004$004F3E57-8E06-4D0C-AEEB-4503679F3C3B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fc268d8d018b5edef8d991baba3e3f48c01a6072","datavalue":{"value":"The complementation of B\u00fcchi automata is a classical problem in the theory of automata on infinite words.  A nondeterministic automaton on infinite words is called \\textit{finitely ambiguous} if for each input there are at most finitely many accepting runs. The author proves that the complement of an \\(\\omega\\)-language accepted by a finitely ambiguous B\u00fcchi automaton with \\(n\\) states is accepted by an unambiguous B\u00fcchi automaton with \\(2\\cdot 5^n\\) states.  This bound is lower than the tight \\(\\Omega((0.76n)^n)\\) lower and upper bounds for complementation of arbitrary nondeterministic B\u00fcchi automata shown by \\textit{Q. Yan} [Log. Methods Comput. Sci. 4, No. 1, Paper 5, 20 p. (2008; Zbl 1158.68022)] and \\textit{S. Schewe} [LIPIcs -- Leibniz Int. Proc. Inform. 3, 661--672 (2009; Zbl 1236.68176)].  In the final section the author announces results on forbidden patterns for certain types of ambiguity (bounded, finite, or countable).  For the entire collection see [Zbl 1398.68030].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1623004$7583BF6A-13B9-4D6C-B857-0B1C55B17F4C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"02bc07e7fdf69b7795d4694a59f3d739066e6204","datavalue":{"value":{"entity-type":"item","numeric-id":259038,"id":"Q259038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1623004$69BC2618-835B-4AB9-BA09-5E7F67F0E68C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1623004$3C7C93BB-FA2A-46BC-8E89-3F6805B79154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1623004$0CB3D6CF-F0CD-4AA8-9C17-6E4ACF2BDF49","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"be3ae561760ae522e1f464284a1826b46f654c71","datavalue":{"value":"6983406","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1623004$DB63FA25-AB9E-4CC1-AB65-8F3EDAFE90DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1623004$D66FFCF2-82FD-4AE1-828A-61B5D0E4C2AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91bf40d767c64624931b686e81b905c7b43bef72","datavalue":{"value":"infinite words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1623004$94CD6518-C91D-431B-982A-77A7667DDE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9025a2e231a3d99af12246374a3c1e886fff7db2","datavalue":{"value":"unambiguous B\u00fcchi automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1623004$14A7F5CF-7FF0-42C2-B096-C1FD89C477D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bd2b411df4ec5da5d4932208cc92c897b0a58e1","datavalue":{"value":"complementation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1623004$323D110B-8068-4D44-AC7E-BE229DA50D24","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":"Q1623004$C34B14D5-E9B6-4CAD-B1D7-66FC14EC7D31","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e000c2d600b4ee9decafb359fc409c04a1e3bea8","datavalue":{"value":"https://doi.org/10.1007/978-3-319-98654-8_44","type":"string"},"datatype":"url"},"type":"statement","id":"Q1623004$697CB535-C952-4CEA-A1B3-2E2CF133F894","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f03aee6e34ed866ef8a3fd3aba2c3204b0765870","datavalue":{"value":"W2885721066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1623004$EE804D80-8DCA-44FD-BE9C-6FC4B748C494","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f941c16176be4dd037e61bbb58d2bde41d0b66df","datavalue":{"value":{"entity-type":"item","numeric-id":1623000,"id":"Q1623000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81a249c085f04debd1d8e270682ba3699f17296d","datavalue":{"value":{"amount":"+0.8503936529159546","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":"Q1623004$C28DB683-9452-4746-8631-35F37BAF2C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0a8e211b83811b0e0a0bc1fa84737ef2884f8da","datavalue":{"value":{"entity-type":"item","numeric-id":1822512,"id":"Q1822512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e10d87aa5bc71c5888ebba5c821d2b6f5e3d59a5","datavalue":{"value":{"amount":"+0.8419218063354492","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":"Q1623004$001B7A80-A5D8-473A-9F4C-F6E0AF349797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df921c9f1cc90a47dc2e21f3be23602126178f86","datavalue":{"value":{"entity-type":"item","numeric-id":3521961,"id":"Q3521961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3e33ae5042504af6cb0a26c4dccda795571494a","datavalue":{"value":{"amount":"+0.8377657532691956","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":"Q1623004$3BD87F95-2F4D-492E-BEA2-83FA8DEB7620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ce367f3f1be4c0be523bb10eb040463e4daae47","datavalue":{"value":{"entity-type":"item","numeric-id":4412827,"id":"Q4412827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58fd31a4f1d281775ef5924dc85ea6fe8a8b2864","datavalue":{"value":{"amount":"+0.8165162801742554","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":"Q1623004$AA7FEA01-8288-4522-8BB2-A66341D00627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d24c93222bfe20c865410ce3d30e5152a6aa9941","datavalue":{"value":{"entity-type":"item","numeric-id":1401292,"id":"Q1401292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdac044071c6ee9145b0cc7fa44baf2dd545005b","datavalue":{"value":{"amount":"+0.8122161030769348","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":"Q1623004$AC8148CA-E007-4717-96A7-86224AA24181","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complementation of finitely ambiguous B\u00fcchi automata","badges":[]}}}}}