{"entities":{"Q2344745":{"pageid":2355488,"ns":120,"title":"Item:Q2344745","lastrevid":52261310,"modified":"2026-01-21T07:18:33Z","type":"item","id":"Q2344745","labels":{"en":{"language":"en","value":"On the boundary of regular languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6436196"}},"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":"Q2344745$6B989043-1AC0-4B92-BE98-2CF72C37E23D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"33d8ad63b4e7ae80603882bc38fdd0d5da036548","datavalue":{"value":{"text":"On the boundary of regular languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2344745$E358B114-8CA5-4686-9DC4-19693CC2ADA5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"adc391dc8fe456abcedb9cbb30a020a22a6eb843","datavalue":{"value":"1317.68098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344745$1B410EF6-874D-4D1F-B102-62D44774195B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$EECA3555-3050-4648-B07E-31DE7F76C04A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$F845FEA8-C52B-4CD0-8952-5C7697A8E66D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3d4eb1898e7e9f37f96fc2bc2b93f3d306019019","datavalue":{"value":{"time":"+2015-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2344745$A27B59FB-0DFB-4EC7-A8CE-E63787D67100","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cdf0561ebd8c54a6d89c22fb726278a2c20cf5c7","datavalue":{"value":"This paper considers the computation of the boundary of a regular language, defined as the intersection of the Kleene star of this language with the Kleene star of its complement. The precise state complexity of the boundary of a regular language is found. The upper bound is obtained by counting unreachable states in the automaton produced using standard constructions for Kleene star and intersection, and it is proved that this upper bound can be reached by automata over a five-letter alphabet. A precise bound in the case of a four-letter alphabet and asymptotic bounds for two- and three-letter alphabets are also provided.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344745$E37E1E55-8AA7-41B1-B3F8-EA7739E051BE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e360e835094103aee0817dd4cb43ec4ae2adb196","datavalue":{"value":{"entity-type":"item","numeric-id":443745,"id":"Q443745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$3FAD8BA9-704F-4FAF-824B-15A1B0D28F91","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344745$30377457-887E-4B62-AEC3-174ACD256F11","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0bde4d3a5c8456ba9606a3d641236e021a561dfd","datavalue":{"value":"6436196","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344745$ED75E670-204E-4C6A-B9E7-DB5C8475B860","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ea9b35a533d874f0a32d77e584c8b61e0e7c2fe","datavalue":{"value":"regular language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344745$657C7149-F064-4570-8AA3-A639D80D858D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7bec7616c0be493e40dda725b70b950dbe2a763","datavalue":{"value":"boundary","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344745$422B4EC0-5E6D-4F97-B339-F197D31B08CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a19bb379ed3c76df6d16665e227f00a03e1e7c2","datavalue":{"value":"deterministic finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344745$43B4FF9B-C0D7-4602-A3AD-5C303F36FAE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b10ab4d2fc75823309415cc3027a505ded7b2f","datavalue":{"value":"state complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344745$E70CB8D2-F0F4-42BF-B8AE-7FCDCEF72F1F","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":"Q2344745$55552295-BE8A-4894-9D5D-E1B4A1C3173E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ccc8531d4b5ef699504f2da81f7e1d5a70d4f8dd","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2015.01.022","type":"string"},"datatype":"url"},"type":"statement","id":"Q2344745$17265589-2021-4CFE-AA58-46A6E51280E6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"311eca08e6004615476c20d51354ae6c14bca8aa","datavalue":{"value":"W2146264489","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344745$A053D8DF-5962-46D0-83FA-2A88342778A7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"41c596c88f69d00357cba44a6f4932c4104c2834","datavalue":{"value":{"entity-type":"item","numeric-id":3086240,"id":"Q3086240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$3333A637-59F5-45A9-A4EF-CC2A2ECFACF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90fd153b66dff4e37a4dc2c04f79d8c1ea7a4eff","datavalue":{"value":{"entity-type":"item","numeric-id":3984193,"id":"Q3984193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$4AC47CAA-EA57-4324-AA40-9D5742313FEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b58918ceeecf0581b85b43f223a73361388306e6","datavalue":{"value":{"entity-type":"item","numeric-id":3167511,"id":"Q3167511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$49A1BC7D-DD55-4658-A85B-4A6203E478E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c745de6da02d2b989411ace16a713d0d8c986929","datavalue":{"value":{"entity-type":"item","numeric-id":5628039,"id":"Q5628039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$45218C1E-BE64-449D-83D2-DA814D0A6202","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":"Q2344745$8F9DF511-E61F-45AA-BCD6-85CF38F185F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba794783ca1771a8a365f5183a591f3d1a7e4f96","datavalue":{"value":{"entity-type":"item","numeric-id":2383591,"id":"Q2383591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$8B56ADD1-43A3-43AB-888A-C85AB8AF73B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a34f4e568c2469f8063f69f8c16802976e475eb9","datavalue":{"value":{"entity-type":"item","numeric-id":3392273,"id":"Q3392273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$9CAD72AB-F857-487E-857D-2CA7ED7BD647","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":"Q2344745$51DB9504-E608-49E3-976D-CAF5D4AE1B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd892181c3e615e393cab5bfa821f8fa2f710cad","datavalue":{"value":{"entity-type":"item","numeric-id":1318694,"id":"Q1318694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344745$9CF30F6F-E820-465E-B6BA-728F3C997187","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8553b93e75fb302e5f42260d1b79239d6627d3fa","datavalue":{"value":"10.1016/J.TCS.2015.01.022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344745$D58380FA-9119-4A55-A389-C497ABBE4FA3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6860cda04df3ef37c2310838d53db0ae68df2d8e","datavalue":{"value":{"entity-type":"item","numeric-id":5327496,"id":"Q5327496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64673fd40b17992a1c360402962de980e5ff0152","datavalue":{"value":{"amount":"+0.9283154606819152","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":"Q2344745$2155DBC6-13C6-4D76-966B-B5BC6B71EB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5ada37a7cef351a7caddf99a28eb6bd2f4ca495","datavalue":{"value":{"entity-type":"item","numeric-id":3451111,"id":"Q3451111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42d1320969f1fd9eb10d0ce57c5d7fb63404f92d","datavalue":{"value":{"amount":"+0.8583908081054688","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":"Q2344745$8D9B1545-D4DC-4FA7-9C23-3743705B5BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0659b53722bea8ae4e3e2e013f796bab2c5ba35f","datavalue":{"value":{"entity-type":"item","numeric-id":896680,"id":"Q896680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8f6b2662128652f3f5184f24da2059bf698b8f6","datavalue":{"value":{"amount":"+0.8519749641418457","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":"Q2344745$58682636-5DD4-433D-9696-D0A0A39F9C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf90a11d38d30707c7e650b3c0e55ad46bbc3286","datavalue":{"value":{"entity-type":"item","numeric-id":5496186,"id":"Q5496186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed8cb19ce8777c65dc7dec59d37b89a2e9ae6dae","datavalue":{"value":{"amount":"+0.8483070731163025","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":"Q2344745$AAE00DEA-46F0-4AC4-884C-469235C960CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"862378b0d49b8d33e8b055f7ba137e2502e1b8c2","datavalue":{"value":{"entity-type":"item","numeric-id":3455750,"id":"Q3455750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53644a40a7a418bb4473e3fbb9ce5b4af5055887","datavalue":{"value":{"amount":"+0.8265987038612366","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":"Q2344745$DD0A7571-5A22-4356-A6DE-499F43EFF7FB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2344745","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2344745"}}}}}