{"entities":{"Q1116702":{"pageid":1127451,"ns":120,"title":"Item:Q1116702","lastrevid":49254769,"modified":"2026-01-06T20:49:19Z","type":"item","id":"Q1116702","labels":{"en":{"language":"en","value":"Complementing deterministic B\u00fcchi automata in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090812"}},"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":"Q1116702$ED5EF90C-5C43-42EB-B582-41111DBA2E7F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"748d298ce6d0b56b5d796fbe442e230532e6f55c","datavalue":{"value":{"text":"Complementing deterministic B\u00fcchi automata in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116702$A64C3D38-2DA6-442E-8EFE-04E9EC041382","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5ffc646597616a3ae611d8b15addc6a10159fb2e","datavalue":{"value":"0666.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116702$E18F0B15-72CD-4D49-8198-D0F441E7B34F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"24941901a42791610208907781daef1620c8185a","datavalue":{"value":"10.1016/0022-0000(87)90036-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116702$FA95669E-20A9-45A6-A620-5B12B9DC7742","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$CBEF1D98-48AD-4606-A505-69424D4C9CF2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1116702$FF6F1E8C-901F-48F4-BF80-028D60FFA146","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b694eec421d8a3f76243c21b9fb89daa91b3a839","datavalue":{"value":"The main result of the paper is a construction which to each deterministic edge recurring B\u00fcchi automaton A with n states yields a nondeterministic edge recurring B\u00fcchi automaton with 2n states accepting the complement of the language accepted by A. For nondeterministic A the construction yields in general a superclass of the complement. The basic idea of the construction is quite simple and transparent, however some local optimizations are included.    The author also presents polynomial time algorithms for    - deciding emptiness of the complement for deterministic B\u00fcchi automata,    - deciding whether the main construction applied to a nondeterministic automaton yields exactly the complement.    A state-splitting algorithm converting state recurring automaton into an equivalent edge recurring automaton is also given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116702$98CA6E3B-11B3-4072-8D4D-3EB1C57C9779","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116702$FBC5D20D-589D-4921-B711-6BD6E2816F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116702$20962CF2-F508-475F-B589-AAFEA28A787C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cf24a855ec4fe87356a244a7d672c2dd6ecbe049","datavalue":{"value":"4090812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116702$48952BCE-2741-4A6E-8E2A-13549C74B50C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcf2a057de8eb374b1423ef5c75edbf8cd95a789","datavalue":{"value":"\\(\\omega\\)-language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116702$A0008762-7CE3-4EE0-804F-F0FE34A73B62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f81406898349e4c73610116261aaccda50fa702","datavalue":{"value":"formal language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116702$895DC437-562C-4B76-8A97-72A64C4FB6BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116702$A7A5A396-85C1-451E-AE54-D030949C54BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5e8ee6d6c130ba687d9b7eb1c058acea995f4c2","datavalue":{"value":"B\u00fcchi automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116702$7749DEAF-D0EC-4D6D-8265-DE17BF5A1245","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a17f242a3e8e18424e964720afec0852d4e8feae","datavalue":{"value":{"entity-type":"item","numeric-id":1696591,"id":"Q1696591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$20E4F5F9-26E8-403A-9D41-386E5C661035","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":"Q1116702$5C7B619B-02B1-4304-9979-81DFF6B3EC14","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d6f610a78b8a8e407c433a427a7cb19c732fdfb2","datavalue":{"value":"https://doi.org/10.1016/0022-0000(87)90036-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116702$921526F8-9DCE-45C8-A52B-A8D03B652C55","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cd2237267941b40204d592d6483aa8b220a1f0ba","datavalue":{"value":"W1994797527","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116702$87F70FE3-5E46-431E-93C8-89393BF95B00","rank":"normal"}],"P223":[{"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":"Q1116702$5A735920-5FE6-43EC-AE3D-B5510F0A219C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5cfea5bdbc02b200e92b0f9e04163ab1b03e86a","datavalue":{"value":{"entity-type":"item","numeric-id":5725174,"id":"Q5725174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$E1499F02-7C18-40F3-8267-9AA1E0DC4A53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"582a65df1b12b43edf2256d93f3704a733686548","datavalue":{"value":{"entity-type":"item","numeric-id":5525259,"id":"Q5525259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$1BA39737-892E-4C18-AB94-F5B86712AF94","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":"Q1116702$A50EE9EB-D9E2-480E-8336-16C12B6B34B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b476279f9ef74fddb27272ad70ec34f0a4ec2a74","datavalue":{"value":{"entity-type":"item","numeric-id":5625141,"id":"Q5625141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$0BEC1314-989A-4194-B1AA-967D110439DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0a874e23987afa0b2bf86d5ca9debc0e077e4ee","datavalue":{"value":{"entity-type":"item","numeric-id":1254240,"id":"Q1254240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$FA1A58B0-FFC1-48B4-AA7D-E41DD523BF23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75292f6880dd3275361618ebb07df15f46377e02","datavalue":{"value":{"entity-type":"item","numeric-id":4074888,"id":"Q4074888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$1DB23F42-3237-4A05-BE5E-6A82C0C3F09E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c82154e66a2e8fea69e3328eced4f67343c9f4c7","datavalue":{"value":{"entity-type":"item","numeric-id":1214411,"id":"Q1214411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$54DD8394-F117-495F-BFBB-975DEF3F4B9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e4c9eb0bc39c2db4fa09c1fc685181796f068e9","datavalue":{"value":{"entity-type":"item","numeric-id":1211504,"id":"Q1211504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$F0D64B06-16E1-42E9-837A-A41751832837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d9e735882f0114d9d1bd74d7bde93766d995370","datavalue":{"value":{"entity-type":"item","numeric-id":4065051,"id":"Q4065051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$73DB15B7-63D4-48E9-93BA-7F7B3B56B2E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca6e0bfbd7e8ce7f5b89d10be4ea3c5fe4ffddf5","datavalue":{"value":{"entity-type":"item","numeric-id":3673090,"id":"Q3673090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$788B9FBA-D124-40BA-9F27-3A32F94AA0E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb563d9804d4caf7feb90542ec0093c805ad5975","datavalue":{"value":{"entity-type":"item","numeric-id":3690204,"id":"Q3690204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$FEE5EE2C-4050-4C58-B9EA-7A8403A29472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d5214b688b20c085ca517a35ba494bf283ee476","datavalue":{"value":{"entity-type":"item","numeric-id":3698787,"id":"Q3698787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116702$5738CC05-5297-4FB2-9395-640176355D22","rank":"normal"}],"P1643":[{"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":"6dfc56cf3e55bea3deedaab47a3a39155012b612","datavalue":{"value":{"amount":"+0.8773713111877441","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":"Q1116702$2929B972-B5BA-460A-97A6-02F10184E753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"388e541e3208693a2afb88e2290b8dfba7abd2af","datavalue":{"value":{"entity-type":"item","numeric-id":3698787,"id":"Q3698787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a8e4b3a968167b7e51769d5140738f08e418ea9","datavalue":{"value":{"amount":"+0.8561961650848389","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":"Q1116702$3EA340FB-9ACC-40DC-92B0-8EC60E79CF1F","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":"e57cc305cceed41f9e24fa855cc4dd25ac372e40","datavalue":{"value":{"amount":"+0.8503584861755371","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":"Q1116702$2C40706B-342B-49B3-9642-BA8304FA5072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89f3f4a327a0395ccdbeb41db1d17a0ba224c396","datavalue":{"value":{"entity-type":"item","numeric-id":5390016,"id":"Q5390016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7f5f1f1ebbf98881d4724a89dace03e4b5b7bad","datavalue":{"value":{"amount":"+0.8493560552597046","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":"Q1116702$59872079-FCCF-4589-AF32-D6601664A51C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c95111abec2da19a096dbfaf2c123d478504e675","datavalue":{"value":{"entity-type":"item","numeric-id":5145275,"id":"Q5145275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9930436eb98e2db0d6b43eb09461d5d1f1f411d","datavalue":{"value":{"amount":"+0.8432890772819519","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":"Q1116702$77DAD8B0-BFF8-44EE-881A-018878F3A7B8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1116702","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1116702"}}}}}