{"entities":{"Q493651":{"pageid":495418,"ns":120,"title":"Item:Q493651","lastrevid":62257614,"modified":"2026-04-11T04:51:31Z","type":"item","id":"Q493651","labels":{"en":{"language":"en","value":"Deciding determinism of regular languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6478532"}},"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":"Q493651$70AC4C44-5876-4617-ABFB-62F5E889316C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"23f47d2c2d16ac900fdc5f1436fb0074edeb80d3","datavalue":{"value":{"text":"Deciding determinism of regular languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q493651$10229A86-1194-40AE-A561-C87B081B29DB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a12e2abaa49dc90551b3fd77488b0dc708c6f15a","datavalue":{"value":"1339.68151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493651$138AD263-04DF-4713-8ADD-D8B850023E05","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a7b7fb7cd82e8d3f5ccd130a1f0c1cc04179e6b","datavalue":{"value":{"entity-type":"item","numeric-id":493649,"id":"Q493649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$E8451853-32A1-452F-887E-B3229339BF5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c24c4fec7427e3b88795b3f61c9b233b13e48547","datavalue":{"value":{"entity-type":"item","numeric-id":493650,"id":"Q493650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$F4F294AA-AE75-41F6-AC61-C66E94343930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c726ca44d8b29953a360b291f7d3727b22939a07","datavalue":{"value":{"entity-type":"item","numeric-id":208299,"id":"Q208299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$9E69DB81-926A-4475-B6C7-5D646EFE48A8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$1E21AB51-A8DF-4582-9FA4-9DEC2DA622C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"78c696a28fe9bd077d52d8c9c7a03ea79d54978b","datavalue":{"value":{"time":"+2015-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q493651$F343750A-51DE-4EB0-BD44-4C2F23D3CEC9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ae3ea91ae0382aef2239982e93729609753c7302","datavalue":{"value":"The paper deals with the problem of deciding whether a given regular language \\(L\\) can be described by a deterministic (also called one-unambiguous) regular expression, that is, a regular expression such that each occurrence of a letter in any word from \\(L\\) can be uniquely matched to a symbol in this expression, without looking ahead in the word. The algorithm for this problem due to \\textit{A. Br\u00fcggemann-Klein} and \\textit{D. Wood} [Inf. Comput. 142, No. 2, 182--206 (1998; Zbl 0912.68112)] is modified so that recursive calls are avoided. In this way it is shown that the problem is NL-complete if input languages are given by deterministic finite automata and the size of the alphabet is either constant or logarithmic. Using the same approach, it is also proved that the problem can be solved in quadratic space if input languages are given by nondeterministic finite automata or regular expressions, thereby improving the result of \\textit{W. Czerwi\u0144ski} et al. [Lect. Notes Comput. Sci. 7794, 289--304 (2013; Zbl 1260.68199)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q493651$8CF43DCC-4277-4708-ADBF-85E3242D06BF","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":"Q493651$2DE306E8-5BAB-4573-B99E-5EEE8A312410","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493651$9F28DAF3-9F90-41CC-8BB1-C6CF3D10A40D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493651$0CBAF652-5E29-4D98-9C46-AB5C82D8C706","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d11ebc0c70d68741b011cfee7bcfd45a1fe888c5","datavalue":{"value":"6478532","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493651$09B13397-3165-4700-BDBB-F1AEC42656AA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d084e454cfd99c8fccd075ee8930cb46851b160","datavalue":{"value":"deterministic regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q493651$5A6B75CC-A2D6-47AF-B93E-1E60F16BFC0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"605cc6ead77d2709d00cd6a896329a4b0ff4e5ec","datavalue":{"value":"one-unambiguous regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q493651$207871C2-BDD8-4E61-8187-4C6451235859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79cb28405b7714946d14103df086f4f72c990666","datavalue":{"value":"NL-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q493651$384DA4B8-545F-4A29-AC9B-8953204847C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f48f92ff0b29adb938dd74e93c94c7ffbb091bf4","datavalue":{"value":"polynomial space","type":"string"},"datatype":"string"},"type":"statement","id":"Q493651$AB336F40-7B89-4645-87E4-705F5C50EDB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"103d028ce898eba226b70953735f1270d90e792d","datavalue":{"value":"nondeterministic logspace","type":"string"},"datatype":"string"},"type":"statement","id":"Q493651$BD38BCDC-1932-490D-AB65-56505A8260E8","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":"Q493651$31EF4571-5136-45FA-BF9A-E80F6C0FBDDD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1941898a2c9078987856783ac439a455fbdd98b0","datavalue":{"value":"https://doi.org/10.1007/s00224-014-9576-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q493651$878D9DBB-954A-471F-AB7D-306E8841EC15","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2f7f111a17247993b510890a1d61f937090a1408","datavalue":{"value":"W2154985586","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493651$6107774C-97FD-455E-9064-0E4988EBD547","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"32dff001305e11e3b75e408c6f8130784404b1f1","datavalue":{"value":{"entity-type":"item","numeric-id":4376789,"id":"Q4376789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$FA91A363-1CAA-40D6-9730-1EE29446D5CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bcd71ac0ee1662e3c5c0f5046af9d7c75419ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1221749,"id":"Q1221749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$FBEE9B37-0596-4ADA-B17F-6894A0D3BE14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4eb55a9a5e4c111bddeb36cf19bf8e8abc5d737","datavalue":{"value":{"entity-type":"item","numeric-id":1314367,"id":"Q1314367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$35988B2D-2F19-49D6-989A-18982CA08B66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"108ba3fd5201fe0305322ff4f7361f671bc41615","datavalue":{"value":{"entity-type":"item","numeric-id":5906297,"id":"Q5906297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$49751891-6128-477B-A7F2-E2AF3D571E9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8959705eba7016ec687f9bbd49d3858cdead7011","datavalue":{"value":{"entity-type":"item","numeric-id":5199959,"id":"Q5199959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$CE5DFDE4-E9C7-4B06-B557-BB6198673DB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9e71f9f3b7e407bdff49b0af1ad185d8f9ce259","datavalue":{"value":{"entity-type":"item","numeric-id":3167507,"id":"Q3167507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$CBA317AE-794B-4255-AC85-AD73536C9B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c27675f9615fd59470e84e43f74af44a74bf14a5","datavalue":{"value":{"entity-type":"item","numeric-id":4910426,"id":"Q4910426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$D69BCD43-DB34-4EE3-81F1-9593997CE610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$EB7DE4CC-83A1-4683-B6E7-340D5DC255D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0da9007df3d683da233677991a25cbc5816385d","datavalue":{"value":{"entity-type":"item","numeric-id":5891559,"id":"Q5891559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$60B7DD47-6F68-430D-8A88-63F7EEECAF5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09ec0346c7c69cefc06dbbc0c0175e3cadefef3b","datavalue":{"value":{"entity-type":"item","numeric-id":3289362,"id":"Q3289362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$309FB05C-812F-4D24-B8B1-676030C8753A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2be2ce44bdf80df52f5a97dfe72ac01ea51570a9","datavalue":{"value":{"entity-type":"item","numeric-id":4045961,"id":"Q4045961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$44235C5A-BB4B-4439-987D-8D9555ED8C39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$AB69E2C7-1ECA-4C77-A276-ACB397A32947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0b3cb0eec2663a59b78b80cf736228e0ac10f95","datavalue":{"value":{"entity-type":"item","numeric-id":2890202,"id":"Q2890202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$73B5417C-4AEA-4BDB-B1EF-39C694A875C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$9E560C44-09B0-4D06-A1B5-D7E349B90A79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81b1b27d04b9dacde4c1315253fdd86d79d8ef53","datavalue":{"value":{"entity-type":"item","numeric-id":2912763,"id":"Q2912763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$3039907B-0F62-44BF-A3F8-B92D9E8994F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q493651$254B81F3-EEB1-4104-9470-81A56C753E41","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":"Q493651$86BB5411-3817-42F3-A043-F1CB3535F365","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"859fb86b0edce955a7241bf77f11de9ea2f8c4ab","datavalue":{"value":"10.1007/S00224-014-9576-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q493651$F9032370-32A3-43FF-BBA2-A20C5C967343","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70e07ca98430ea0f67988363309b9e28969d4e3b","datavalue":{"value":{"entity-type":"item","numeric-id":2361347,"id":"Q2361347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a15bbf8e29198de37d88c200875c68410ece6fa5","datavalue":{"value":{"amount":"+0.8267734050750732","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":"Q493651$EB980355-637F-4F20-88D9-A8784A71E02C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4027ea4599b37695586a1fa21ebfec4a14310c4e","datavalue":{"value":{"entity-type":"item","numeric-id":4910426,"id":"Q4910426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9e9eb0c0594b27f9d7720acab34ecb57fdf7c93","datavalue":{"value":{"amount":"+0.808275580406189","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":"Q493651$B8C38BE0-2194-4FC7-BEA7-6610DD0D00AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76772aa5f198f13a3a368d16f0fe201db3640809","datavalue":{"value":{"entity-type":"item","numeric-id":897659,"id":"Q897659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0d48bde1b2c723fa18a1d6f02e72be22d2c53cb","datavalue":{"value":{"amount":"+0.7887921929359436","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":"Q493651$34B3CD36-0C1A-4609-AAAD-117AA54228A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"828afd99bcecae6e0274c10f1a03a007e8f8b213","datavalue":{"value":{"entity-type":"item","numeric-id":2271457,"id":"Q2271457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fa10077c9a3eb985bbf285834467a9403861c61","datavalue":{"value":{"amount":"+0.784430205821991","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":"Q493651$3B3992DF-8F25-4841-A976-C4AD1CA8052F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e313270f7eae7fe515c77fd1e98a61970f0bca0","datavalue":{"value":{"entity-type":"item","numeric-id":4277533,"id":"Q4277533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf618ea08837a552de63525aaa3976bcdb0c5390","datavalue":{"value":{"amount":"+0.7778708338737488","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":"Q493651$22CCC6DD-DACC-4645-AD54-7BE391EEC119","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deciding determinism of regular languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deciding_determinism_of_regular_languages"}}}}}