{"entities":{"Q1314367":{"pageid":1325117,"ns":120,"title":"Item:Q1314367","lastrevid":46301538,"modified":"2025-12-24T12:55:42Z","type":"item","id":"Q1314367","labels":{"en":{"language":"en","value":"Regular expressions into finite automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 501178"}},"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":"Q1314367$E7EBCB5D-F316-4723-B31C-B90B886771E6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a90d40b95f45079b5adbbe6a8f3dc0628c00f13","datavalue":{"value":{"text":"Regular expressions into finite automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1314367$51741752-202F-406F-9D5C-2A89E06104BF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c3bdb7aecfffa6d07049a091bee23910f93855e","datavalue":{"value":"0811.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314367$7B9DBF08-CE9B-46C5-9BA3-99B680B7910D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e8c51f9d3b8dfa830688ccc5b2940385798cbd3a","datavalue":{"value":"10.1016/0304-3975(93)90287-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314367$D546EC75-215F-48A7-A459-A5B1AFEE291C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2d9e819c8bf49de9dca6899f76b650f2636ad1b5","datavalue":{"value":{"entity-type":"item","numeric-id":1271621,"id":"Q1271621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$F5CE97C5-541F-4C4D-86EF-6CC923F6AFEB","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":"Q1314367$0A6AF5E6-11E1-4624-B90B-1A6ED0771102","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e26b88711e08010d610855bece2ce31f95b0ae14","datavalue":{"value":{"time":"+1994-02-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":"Q1314367$BCB7EC7B-450F-4D42-915A-C6379BA82FDF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd8f520d15aaf8ee4ecccd00d3cc58a62f33405d","datavalue":{"value":"It is well-known that the regular expressions can be translated into non- deterministic finite automata \\((NFA)\\) with or without \\(\\lambda\\)- transitions. The standard method first translate a regular expression, in linear time, into an NFA with \\(\\lambda\\)-transitions and then the \\(\\lambda\\)-transitions are eliminated in quadratic time. There is another method, proposed by Glushkov and based on the fact that, if a word is denoted by an expression, it must be possible to spell out that word by tracing an appropriate ``path'' through the expression. It was shown that the Glushkov's method can be described in terms of Brzozowski derivatives and on the other hand this method plays an important role in document processing.   In this paper the author shows that the Glushkov automaton associated to a regular expression can be constructed in quadratic time in the size of the expression, and in the case of deterministic expressions the construction can be done in linear time. The result is obtained first for regular expressions in star normal form (also introduced in this paper) and then it is translated to the general case. The paper is directed then on the unambiguity of the regular expressions and it is shown that the weak unambiguity can be tested in quadratic time improving the methods known until now. Finally, some interesting open problems are mentioned.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314367$746A1FBF-B761-4B0E-A938-D226FDA0B0B9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314367$5B6B9B02-3177-4039-B178-45AF5E52B464","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f78b2d680964406f7210f939ddab8c43b44e78ac","datavalue":{"value":"501178","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314367$2F003D71-EFC5-496E-BF73-BE654C3E35E3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb8d04c869a7c957a2fb637bf61f6c6b39fe9a39","datavalue":{"value":"regular expressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314367$C2EEC30E-159F-4AE0-ACA9-D23293C5B7EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc60233cf319d9be11153b1ea4e311eb8d0371be","datavalue":{"value":"non-deterministic finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314367$7E9AA871-5ED7-4F0E-BC6B-D7681F018660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03ceea31cb22ad4f43c91ee2489b4dddfc258d5b","datavalue":{"value":"Glushkov automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1314367$2128A889-7786-4418-8155-F67867AF60CF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6157837de11f2e28fe479554c99ef4c02d4ee00e","datavalue":{"value":{"entity-type":"item","numeric-id":172108,"id":"Q172108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$D7BD9D02-BD18-448A-B2EC-61CE77626EE8","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"a214f907d878c7541e6a379563f2001ac071efd6","datavalue":{"value":{"entity-type":"item","numeric-id":35548,"id":"Q35548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$201DD55E-5319-49A2-92C2-8D8A75BB4269","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":"Q1314367$5FCB7993-BED8-4F3B-B4C0-E728AD3E8DB5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"24e78d1fb1c2644e483b0cb685865f0905ee628c","datavalue":{"value":"Q61458432","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314367$66A4A838-275E-4329-A906-3BCE35FE6BEF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b63e83253ad4f160a0157bce3be14836b79e15d9","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90287-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1314367$BB43515F-528B-4765-8A54-F8254B78F920","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"27038171656f62ee4c26b96a6223b4e7e4e58c0c","datavalue":{"value":"W2099540492","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314367$38F29F6A-771D-4E09-80A7-EEA50A69F137","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ea781952ee29ddc900e481ff0b4c20e5c00fd6f","datavalue":{"value":{"entity-type":"item","numeric-id":3992625,"id":"Q3992625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$6AF9AC18-A967-4EAA-AC4A-F45A1A302FCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd4a0c107773baf4c7b30e2c05565087fb2ff673","datavalue":{"value":{"entity-type":"item","numeric-id":5452362,"id":"Q5452362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$71A2E323-9676-40E9-89DA-459735078D76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f1b9235789d6a4d289a8f96fbfa1512b9c5d8b7","datavalue":{"value":{"entity-type":"item","numeric-id":3036710,"id":"Q3036710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$E72357F2-6690-4916-851C-43738D5FF371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cf72cd39e1a458db54e84dc9cd6dc2728e5f092","datavalue":{"value":{"entity-type":"item","numeric-id":580983,"id":"Q580983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$D560291F-E590-44D6-8CA2-F8CDA304C354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be753f5e40f4b7a03751602e0b99145a8ec2ef00","datavalue":{"value":{"entity-type":"item","numeric-id":5628042,"id":"Q5628042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$70BEA7A5-8F03-44AE-A917-C0602AB979FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1780c531bef2cce514180b12f47d2d5de6c9687","datavalue":{"value":{"entity-type":"item","numeric-id":5096780,"id":"Q5096780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$9A0C174E-3E65-4A1A-8BB4-74557175B89A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41e7ff1139dda6caf30f086ee8bbcc3bc037598a","datavalue":{"value":{"entity-type":"item","numeric-id":5632482,"id":"Q5632482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$D0467680-7AF4-4E5F-B23B-13E83CD3536E","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":"Q1314367$D83E7C08-F90D-47FE-8D76-F51D47617833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2e2c4b4a4074f62b2d103e7140bf1d267e85818","datavalue":{"value":{"entity-type":"item","numeric-id":5579037,"id":"Q5579037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$32409A43-EB27-405B-A09F-8EF9FCBB5C58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$76153593-5CEC-4EBB-A5FE-9885628E08B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7abcf3c66c015fe58635dbc51e77992ec0cd49f5","datavalue":{"value":{"entity-type":"item","numeric-id":4103466,"id":"Q4103466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$64C75DAD-0371-479B-AE81-918CB9CA61DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de5c706af26597a23c59f8b94c3772be3a8c03c9","datavalue":{"value":{"entity-type":"item","numeric-id":4040284,"id":"Q4040284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$B7A66BED-94EE-4733-9E5A-23D436816C8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d617310b37fc85fd09ec7dd2c4fe23b8a3c75fd8","datavalue":{"value":{"entity-type":"item","numeric-id":4692941,"id":"Q4692941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1314367$CCE1DCC3-4C9E-404B-8B44-46FB61F83C72","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"8f212c858802451b223854430e9ee0c51acb6a19","datavalue":{"value":"journals/tcs/Bruggemann-Klein93","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1314367$D65C184D-04B0-40FC-810C-D24818ED53B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf151e3446cc9ed7fb68b41dcb85302f74e6c86a","datavalue":{"value":{"entity-type":"item","numeric-id":4944659,"id":"Q4944659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25466e465322fd959f39515a587595a4fc7afbe2","datavalue":{"value":{"amount":"+0.8560657501220703","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":"Q1314367$7B12A361-62CF-44AB-9D5B-937FC2F8E22D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f235ca16265bb53666ff5ff0592f7706a06cb10b","datavalue":{"value":{"entity-type":"item","numeric-id":4412097,"id":"Q4412097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e099a84005d0a39db62e74ca65b1f2b4e03111ce","datavalue":{"value":{"amount":"+0.8502011299133301","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":"Q1314367$0995D1E2-C740-4B97-8EB7-4AED8BFFFEE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0adc5605201d2721cc47fe401006605205a9a1b7","datavalue":{"value":{"entity-type":"item","numeric-id":580983,"id":"Q580983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fac8e74b5f5e7a370b961814c4b3f9a3ff8e99d4","datavalue":{"value":{"amount":"+0.8429487347602844","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":"Q1314367$D21CE83C-9CE7-4F2D-BF98-6F5402BEF98D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53cbbf2058d9ef8c914ae041e338f368d52a20b9","datavalue":{"value":{"entity-type":"item","numeric-id":1575946,"id":"Q1575946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17541a542631082bb949ee2d5014590af2c01021","datavalue":{"value":{"amount":"+0.8418018817901611","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":"Q1314367$23FE2DB9-3863-4327-BB6C-83E6F0EC39A9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1314367","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1314367"}}}}}