{"entities":{"Q580983":{"pageid":582750,"ns":120,"title":"Item:Q580983","lastrevid":49095943,"modified":"2026-01-06T14:24:30Z","type":"item","id":"Q580983","labels":{"en":{"language":"en","value":"From regular expressions to deterministic automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4018391"}},"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":"Q580983$C3884C19-8E31-42D0-ADB2-8DD4E61FB105","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4beda9851242a697750f0248d77121914ef9affa","datavalue":{"value":{"text":"From regular expressions to deterministic automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q580983$216252BF-F2A5-4BCF-9E95-E81DB005682C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d39aed4e643ed2d45a789638ceb410bc2a5a6531","datavalue":{"value":"0626.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580983$69DF6CAF-A7CB-4D88-A9DC-6B49346F4104","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a1bd4901832a1481392f128dd6209c81ee4837dd","datavalue":{"value":"10.1016/0304-3975(86)90088-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580983$A8CD9EE1-78E1-4F4D-A839-CB96EF748C1A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bb9dcdaeb781d4881f605361aa1b5039bd39915","datavalue":{"value":{"entity-type":"item","numeric-id":580982,"id":"Q580982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580983$B8BD890F-D7F0-42C4-8322-8BBA2577CAF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b8ec1468d428238f8d4531c8e2ef03fc061c69d","datavalue":{"value":{"entity-type":"item","numeric-id":453538,"id":"Q453538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580983$8EC390E6-2F37-4E73-836D-DA929DDEB46C","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":"Q580983$3394C997-2EAE-40A9-BE2D-DEF80231958F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q580983$FBEB28EB-E3AD-4B3F-8A38-7A845951FF5C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"18c190f09bbc12b2d0aac199b4a87129d1ab4ba6","datavalue":{"value":"https://hal.inria.fr/inria-00075904/file/RR-0649.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q580983$076E313D-5941-4561-B72D-1A8BD0C8A595","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1af66d45d6306537750e76d0398457a0b960fc9a","datavalue":{"value":"The main theorem allows an elegant algorithm to be refined into an efficient one. The elegant algorithm for constructing a finite automaton from a regular expression is based on `derivatives of ' regular expressions; the efficient algorithm is based on `marking of' regular expressions.    Derivatives of regular expressions correspond to state transitions in finite automata. When a finite automaton makes a transition under input symbol a, a leading a is stripped from the remaining input. Correspondingly, if the input string is generated by a regular expression E, then the derivative of E by a generates the remaining input after a leading a is stripped. \\textit{J. A. Brzozowski} [J. Assoc. Comput. Mach. 11, 481-494 (1964; Zbl 0225.94044)] used derivatives to construct finite automata; the state for expression E has a transition under a to the state for the derivative of E by a. This approach extends to regular expressions with new operators, including intersection and complement; however, explicit computation of derivatives can be expensive.    Marking of regular expressions yields an expression with distinct input symbols. Following \\textit{R. McNaughton} and \\textit{H. Yamada} [IRE Trans. Electron. Comput. EC-9, 38-47 (1960; Zbl 0156.255)], we attach subscripts to each input symbol in an expression; \\((ab+b)^*ba\\) becomes \\((a_ 1b_ 2+b_ 3)^*b_ 4a_ 5\\). Conceptually, the efficient algorithm constructs an automaton for the marked expression. The marks on the transitions are then erased, resulting in a nondeterministic automaton for the original unmarked expression. This approach works for the usual operations of union, concatenation, and iteration; however, intersection and complement cannot be handled because marking and unmarking do not preserve the languages generated by regular expressions with these operators.","type":"string"},"datatype":"string"},"type":"statement","id":"Q580983$6160B067-5D76-48D5-8350-303C8338616E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580983$F30AB56C-9A30-44F7-8B98-D45D515D1CF0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1774c429c805f57ef5dbee889c4e585064a01b1d","datavalue":{"value":"4018391","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580983$4024FAB8-01C7-427D-B5D1-41EF811D870B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d785ae6de5cb459b43d38cfb079ec8fa6c7a5ad4","datavalue":{"value":"algorithm for constructing a finite automaton from a regular expression","type":"string"},"datatype":"string"},"type":"statement","id":"Q580983$414B07B7-054F-48EC-9D70-135A5C42B2D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4364d21acd66d915b62f94bfe69e0065826249a1","datavalue":{"value":"efficient algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q580983$26868E77-791A-4005-927B-809E15E9A8AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eda59d78b8df632d2b1ac6724f729a1b1908002c","datavalue":{"value":"Derivatives of regular expressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q580983$AFCEE65C-B178-432E-ABF8-4EE69475C36D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dabc04d0dd78de8a753f0e716b4b8266a2a6ec86","datavalue":{"value":"marked expression","type":"string"},"datatype":"string"},"type":"statement","id":"Q580983$B6A1B74A-77F0-4EC4-8B12-B1982208BC0F","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"70849c7de8b1fba6771cc05a0e9adf71b0d9785e","datavalue":{"value":{"entity-type":"item","numeric-id":31835,"id":"Q31835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580983$AC574AAA-B1FE-43B7-AD55-AA6F5A05EAC0","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":"Q580983$121DA3EB-2977-48F1-AC27-3C2EAC265F07","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b4654b3fb809c9a4a39cacfc56adc0590e6c6479","datavalue":{"value":"W2092860912","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580983$9DC64226-9229-4968-90BC-29BACDB5EE14","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f6779191cd8c1961961953c405806b5ee830c45","datavalue":{"value":{"entity-type":"item","numeric-id":3735065,"id":"Q3735065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580983$8449168B-060D-443C-A96F-23B3C9811A21","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":"Q580983$F1316185-26F6-48E6-ADF6-8206D9481344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff2cf228e7f6980c3ee8de846819585d642e9839","datavalue":{"value":{"entity-type":"item","numeric-id":5536277,"id":"Q5536277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580983$7AE47601-76C1-42D8-AF29-2670AA436F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37011f2d1f562172b8f9857d6459d11fb09eac21","datavalue":{"value":{"entity-type":"item","numeric-id":1057072,"id":"Q1057072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580983$1082E546-7404-4FC5-9B98-6393934F07FA","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":"Q580983$FC2EC06F-D2AE-4356-B712-B98C0E3FB862","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a03efa3e8a787ca556e8f11efd48be51043692c","datavalue":{"value":{"entity-type":"item","numeric-id":5549415,"id":"Q5549415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580983$C10A980C-9025-4673-A771-80C046142BAD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be45673658443702daab6f33ccf08b9317c38d49","datavalue":{"value":{"entity-type":"item","numeric-id":672142,"id":"Q672142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9ec36fdf18627f46a3ca4565f49a768cfc93718","datavalue":{"value":{"amount":"+0.8683158755302429","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":"Q580983$019529B6-D450-44D3-9D4D-EAFB09888D2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23a63f16161d0a06c12a24053c62b542bf425945","datavalue":{"value":{"entity-type":"item","numeric-id":5463999,"id":"Q5463999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9ec36fdf18627f46a3ca4565f49a768cfc93718","datavalue":{"value":{"amount":"+0.8683158755302429","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":"Q580983$C7822A6D-8E84-4276-BF7D-530C5FF7BDE3","rank":"normal"},{"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":"e8477007184931db57028b34cde3f5efa1e0bd1c","datavalue":{"value":{"amount":"+0.8662382960319519","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":"Q580983$FCB06E8E-68D0-4158-9910-341A2372E922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89771217e4db2ee421236642d679d5d4ebc1d5c3","datavalue":{"value":{"entity-type":"item","numeric-id":4596644,"id":"Q4596644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a56e1d81e183140966eea894636c9fb0a7a1f079","datavalue":{"value":{"amount":"+0.8563767075538635","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":"Q580983$B2057EE6-0838-49CA-952B-2B61C1C350DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"547c73f41064eaa102ddf1f584d09803f65734fb","datavalue":{"value":{"entity-type":"item","numeric-id":4540960,"id":"Q4540960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd8efd8f00147ceb390525a72d4fb8a1d6999045","datavalue":{"value":{"amount":"+0.8557747006416321","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":"Q580983$0720870E-F9F0-4B29-8DE2-D5D4F868A00B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:580983","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:580983"}}}}}