{"entities":{"Q442154":{"pageid":443921,"ns":120,"title":"Item:Q442154","lastrevid":61988145,"modified":"2026-04-11T03:01:22Z","type":"item","id":"Q442154","labels":{"en":{"language":"en","value":"Nondeterministic Moore automata and Brzozowski's minimization algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6064530"}},"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":"Q442154$13DD2A4B-B008-4159-BFC6-AF181835B393","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7a396bc367f01c4a7320a5992bf326a73a5bbd8a","datavalue":{"value":{"text":"Nondeterministic Moore automata and Brzozowski's minimization algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q442154$0F71F2A9-B332-4B22-92F7-15BC9CED04A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8652caed096eef50d1b574e308bd3cea943680d9","datavalue":{"value":"1280.68116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442154$010F825D-6AB6-4BA3-94EB-17FA4C9968B5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"50c3c49819b0b784f4fb01d0bfdb0237c61bfd45","datavalue":{"value":{"entity-type":"item","numeric-id":405565,"id":"Q405565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$9AE2D248-0690-44EA-BC5C-6F30E261C2B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5e2efc55074779211d096350576fb59f084efdf","datavalue":{"value":{"entity-type":"item","numeric-id":405566,"id":"Q405566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$F5539359-F623-4300-A886-903406C52464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4b45831a6b64c2923a356b04498cc64a6cee6312","datavalue":{"value":{"entity-type":"item","numeric-id":490306,"id":"Q490306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$8F9A58D9-630E-44F0-A5D9-6121B595CDEB","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":"Q442154$4DAE48C9-315B-429C-8001-928342C4218F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0276b87afe391e9d9e1b89aef5cbae8088ca3cb0","datavalue":{"value":{"time":"+2012-08-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q442154$33D16131-36CB-4C45-A7BB-8358ED606128","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2daced9896460a81c4c40ff31087aa019e14cb22","datavalue":{"value":{"entity-type":"item","numeric-id":420851,"id":"Q420851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$BAA15453-7F3E-4236-88F5-91C37EB2941C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442154$040E0A23-4545-4B5F-9066-BF58E7C5166A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"666ecb472ee793e8bcfcf269fd784fe124e96324","datavalue":{"value":"6064530","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442154$851A55D3-39FA-401F-910F-2A1B9BBA1EE9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f209cf137d56e6e9ca51b59d41e57fcc7a371f11","datavalue":{"value":"nondeterministic Moore automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q442154$6C2DB9B1-C2E4-4E19-9AC1-56D0B817EEDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dad8f3419a69dce0e11fceb737e4e64fdd4182a5","datavalue":{"value":"Brzozowski's minimization algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q442154$96E007CE-CB76-49C3-9111-B3B58C157D79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41bf607c7a0c685b49cc655a4d057166c465434e","datavalue":{"value":"automata minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q442154$3825D85D-B674-421F-95DD-3E78A25D37D3","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"08de333d5f9c1cef479eb9e6712bf8f744d2f019","datavalue":{"value":{"entity-type":"item","numeric-id":45359,"id":"Q45359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$D68C9CAC-D0DF-469A-88F9-241068DF45E6","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":"Q442154$A6CCF7E0-3C0C-41A3-B73E-A2A11B2E66C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a6f852098fd1dde29314fe03b6af2bee4aaa44ab","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2012.04.029","type":"string"},"datatype":"url"},"type":"statement","id":"Q442154$3B284193-D4AA-4559-B360-19BF38489DBD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d05c581559b15a55a0a8187b110aaa7c844b6b2a","datavalue":{"value":"W2007783859","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442154$041B68CA-674B-492D-B1E9-1FBE06CCFC56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2be0c1bba2f641b3f64ee1887e836cb60d4c3d7","datavalue":{"value":{"entity-type":"item","numeric-id":2271419,"id":"Q2271419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$A72A3F30-DDEB-4E8D-8822-DCDABB0867AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe955fb7f9026c48a3b74bf365e86ce77d5a2f05","datavalue":{"value":{"entity-type":"item","numeric-id":5725992,"id":"Q5725992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$B2CAC386-D943-4D6E-86AC-D4BA65D0356B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c0f22b57a807ac031aded68a4b6e43abbd3ae34","datavalue":{"value":{"entity-type":"item","numeric-id":4520526,"id":"Q4520526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$FFD89F3C-AA38-44BE-BEF2-287D6CACCE59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da09b563966886f2182a20f92f905ff33519be01","datavalue":{"value":{"entity-type":"item","numeric-id":3073644,"id":"Q3073644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$EEF8B0F7-9190-4D22-BB58-62460A996F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e65d8868bfa2d9e33ae01a7544458eb2fcbae75e","datavalue":{"value":{"entity-type":"item","numeric-id":1959649,"id":"Q1959649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$49BFCA8D-1930-48CC-A4C7-3A666D9235B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c01843707f489f5c4a51e0f0fd78a485500a9ed1","datavalue":{"value":{"entity-type":"item","numeric-id":3006159,"id":"Q3006159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$C209B366-3D2E-4F48-BCB8-0F8F07EFD027","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19a41ce9784000fa7227fe54ae4a34ca708923e9","datavalue":{"value":{"entity-type":"item","numeric-id":5892494,"id":"Q5892494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$C46DA90F-9FEE-41FC-9BFB-95B426227ADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d3feabf7738470c05cc9bc57fe6125054132512","datavalue":{"value":{"entity-type":"item","numeric-id":5684962,"id":"Q5684962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$8E6D1FD7-F996-4820-844F-CCB6BA108770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5998689ab44651e98658e9c5576f460285f482fc","datavalue":{"value":{"entity-type":"item","numeric-id":553320,"id":"Q553320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$F7522066-BAD7-48E3-BC27-79F4B7576FEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a43c803a4ad1fe6b307a5c428e2fea86a94776c","datavalue":{"value":{"entity-type":"item","numeric-id":5590818,"id":"Q5590818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$222679C4-AD99-41E2-9147-1781061594A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b65ce1b67969a15448bf3b77aebd5948a5c516d","datavalue":{"value":{"entity-type":"item","numeric-id":5452607,"id":"Q5452607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$C43042DD-7539-4CBA-8C1A-8AB1DD2FA2B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b1c31cee64415c39c3ff4e8c3f5fceb5dcd694e","datavalue":{"value":{"entity-type":"item","numeric-id":4270071,"id":"Q4270071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$B0893896-7E81-4DC9-BDD9-CFBEF839AD3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7387814e897496366be1dcfb6f4dc443c1abd1da","datavalue":{"value":{"entity-type":"item","numeric-id":1575676,"id":"Q1575676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$BB74997A-61E7-4BBC-8FF3-3478104D430F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ced1ca6d3091fee8f0501be4a496153b516599f1","datavalue":{"value":{"entity-type":"item","numeric-id":5072548,"id":"Q5072548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$E6F08E9F-6D83-4EC8-A93F-B392FE692755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a900a1b2fff17c3475869d05f2ce6a6836bfa390","datavalue":{"value":{"entity-type":"item","numeric-id":4991691,"id":"Q4991691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$88785488-CD2D-4AB7-B0F3-C0B962D292FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aac07977249f660020231d45d08993200a68880","datavalue":{"value":{"entity-type":"item","numeric-id":5551476,"id":"Q5551476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$895B418C-7FB0-4EEE-BE3F-D76EE57BB767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b3daa3db03ea11be8dc2196c96ebade778eaf14","datavalue":{"value":{"entity-type":"item","numeric-id":5387853,"id":"Q5387853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$64C5E610-991A-441E-ADB6-EDDBB4EC961A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8772472ae60c3eab2c99e04d5c03feb01833a434","datavalue":{"value":{"entity-type":"item","numeric-id":4848749,"id":"Q4848749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442154$AC8B4B76-1F24-4219-AC53-732B8AE31AF6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"913418a25009860de01221d473e17cfbd65549e3","datavalue":{"value":"10.1016/J.TCS.2012.04.029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442154$43B152E8-A538-4419-A9A9-904276C00BDB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"44f0d4dfc18f13857bfca2a193dce470ac6f8cd2","datavalue":{"value":"A Moore automaton is a finite state machine where states are labeled by output symbols. Such an automaton defines the function that maps an input string to the output symbol labeling the last state of the run. This paper considers non-deterministic variants.NEWLINENEWLINEThe authors hence consider non-deterministic Moore automata (NMA), in which there could be many possible next states for some input symbol and in which all states don't necessarily have to be labeled by an output symbol. In order to still be able to define a function, the authors introduce \\textit{coherent} NMA, which furthermore satisfy the following two properties. First, if an input word has a run, then there is one ending on a state labeled by an output symbol. Secondly, for any input word, all runs ending on a state labeled by an output symbol ends on a states labeled by the \\textit{same} output symbol.NEWLINENEWLINEThe main result of the paper is a variant of \\textit{J. A. Brzozowski}'s algorithm [in: Proc. Symp. Math. Theor. Automata, New York 1962, 529--561 (1963; Zbl 0116.33605)] to produce an equivalent deterministic Moore automaton with minimal number of states, from a coherent NMA. As for the case of the original Brzozowski algorithm, the time complexity is here also exponential in the worst case.NEWLINENEWLINEFinally the authors consider \\textit{semi-coherent} NMA, defined as coherent NMA but keeping only the second property. They show that semi-coherent NMA are more expressible than coherent (in terms of function definition) but that nevertheless their algorithm still produces a minimal deterministic equivalent automaton.","type":"string"},"datatype":"string"},"type":"statement","id":"Q442154$7CF6BECD-2CCA-4307-94FE-E38D65D69DA2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f05da545cc1f99596c887e8586f2afcdcc18ec1d","datavalue":{"value":{"entity-type":"item","numeric-id":5200055,"id":"Q5200055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dc9427803832438fbfad3eb7a8e978b50be8e91","datavalue":{"value":{"amount":"+0.9778544902801514","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":"Q442154$92892F6B-E5CB-4CFE-A25F-5003482D1550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"590184ebccf3760ba517370b5aee13ff93be1161","datavalue":{"value":{"entity-type":"item","numeric-id":5327494,"id":"Q5327494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26d6c1d4d85fd9c6dc1dd0222cf2637cd4f0b3cb","datavalue":{"value":{"amount":"+0.8099340796470642","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":"Q442154$2C439D8F-082F-44B7-809B-C6406F53F35A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6843723bbbf33bd295023deb8183c2a86c72ee91","datavalue":{"value":{"entity-type":"item","numeric-id":5410330,"id":"Q5410330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3938b492c1472a3379641fb8a676826926ab3297","datavalue":{"value":{"amount":"+0.7914981245994568","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":"Q442154$13EFF0EC-BF5F-401D-937C-82B0F735CF61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e94acc5918cf06bf5ee942ddb428fdf7a2bf6d80","datavalue":{"value":{"entity-type":"item","numeric-id":2074212,"id":"Q2074212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c38602f99e3564c6d932983b64cbce4e654946bd","datavalue":{"value":{"amount":"+0.77671879529953","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":"Q442154$D948FB81-581E-4366-B063-4A8F3ACFB17F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abc996f3615f0bbc9ddafde1d1db794048ca354b","datavalue":{"value":{"entity-type":"item","numeric-id":2897941,"id":"Q2897941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc8bd0ab6a291fda0d1f611d2b507b070d8a8fc2","datavalue":{"value":{"amount":"+0.7657352685928345","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":"Q442154$8BA1437C-0E14-4610-B3E2-F9D6DFE1480B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nondeterministic Moore automata and Brzozowski's minimization algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nondeterministic_Moore_automata_and_Brzozowski%27s_minimization_algorithm"}}}}}