{"entities":{"Q1856175":{"pageid":1866917,"ns":120,"title":"Item:Q1856175","lastrevid":69121782,"modified":"2026-04-13T04:55:24Z","type":"item","id":"Q1856175","labels":{"en":{"language":"en","value":"A minimized automaton representation of reachable states"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1862284"}},"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":"Q1856175$065AC2E0-B993-43EC-8756-6B3D93E2441D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6331c9774c671eebedb2612e83d3dfe881ea82a7","datavalue":{"value":{"text":"A minimized automaton representation of reachable states","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1856175$BFA65B80-8E29-428F-81AC-8CD461AE3E48","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dc6ec672c09e8e929719d240ab74d125494ecab1","datavalue":{"value":"1065.68579","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856175$E2E1003B-4E19-421B-9D3B-21DCE9081B9A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"014c09e7b90e04a7c11fd7dd1957177e28b3dbc8","datavalue":{"value":{"entity-type":"item","numeric-id":539427,"id":"Q539427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1856175$BA0CD8CA-169D-4319-9750-6F4EE656FB06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc9cc4db1b065261fd64cae808c2b25a5e5d79f4","datavalue":{"value":{"entity-type":"item","numeric-id":1273865,"id":"Q1273865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1856175$CDDE3EBD-C55C-4D7C-A358-10AD14FBA895","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e1846ce75b2b308fd593b292d943abd351ca6751","datavalue":{"value":{"entity-type":"item","numeric-id":225063,"id":"Q225063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1856175$02E23B1D-A42C-40C3-A75D-E2C8D1FE5C5E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4807edd6e640ad656e01e00a44b61d620e873df6","datavalue":{"value":{"time":"+1999-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":"Q1856175$2AE0F4DC-575B-46D7-9E25-E6A7459907D2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"98914e3d1c5fabc50a1ed02cbe02ed573a2013d7","datavalue":{"value":"We consider the problem of storing a set \\(S \\subseteq \\Sigma ^k\\) as a Deterministic Finite Automaton (DFA). We show that inserting a new string \\(\\sigma \\in \\Sigma ^k\\) or deleting a string from the set \\(S\\) represented as a minimized DFA can be done in expected time \\(O(k | \\Sigma | )\\), while preserving the minimality of the DFA. The method can be applied to reduce the memory requirements of model checkers that are based on explicit state enumeration. As an example, we discuss an implementation of the method for the model checker SPIN.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856175$07A1BF2C-A742-467F-B04B-079E365DF637","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856175$6EED7A1E-94BC-4344-8F95-EF8BFA8815B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856175$E3AD665E-C9B1-4D04-B709-BC70B74B70EE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5612a0cc3bdff7d9eba0c1dba904ee320c4c03ef","datavalue":{"value":"1862284","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856175$3A589357-C7D6-4AD8-B333-7E2E1D77C0A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856175$4F0611D4-75E3-444A-A19D-B33897321A7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb9f8004d477a3922fe8bde53d670f8b57c48852","datavalue":{"value":"model checking","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856175$258C5F76-EC16-42A8-AF11-C0752AD48C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66824d9cf653f7dee3c76f98a8ea1aa06432fa7c","datavalue":{"value":"verification","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856175$250181EF-55BC-4DA5-B690-1C3525F7394F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76da93caf764509e7bfd6c3e7d7357b1a4750cd","datavalue":{"value":"OBDDs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856175$CC8BF31B-DD36-44D8-97F4-D82185088EF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6aa2c71ac21f285b7a3ae606ce23d18f3ec23bf","datavalue":{"value":"sharing trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856175$E5C61B2B-97A3-4A82-90A8-65B3757CCD02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99de46d71759c0d7b682d826cd549f3d1ed09133","datavalue":{"value":"data compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856175$1EE32F79-D28E-4F2D-A628-BDD2D87294A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"772c4ee50d131f1a35ff4b31da11ffcdcf02c815","datavalue":{"value":"SPIN","type":"string"},"datatype":"string"},"type":"statement","id":"Q1856175$57C457D8-24DE-4025-8CD1-83D2252C9ADD","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"53a4a9b6c38d395d5b2eb80cedc3eefcbf3e9947","datavalue":{"value":{"entity-type":"item","numeric-id":15987,"id":"Q15987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1856175$982A618B-FFC4-453E-9FDF-FFDA7D14A4D6","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":"Q1856175$86DC4791-19A0-443A-8902-115D04192A2C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c32b9663c74bd2b0f00ad91e1cc4e710d950ebbc","datavalue":{"value":"https://doi.org/10.1007/s100090050034","type":"string"},"datatype":"url"},"type":"statement","id":"Q1856175$9ADA177F-5E9D-4780-BBD7-6950969F688A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1135376dcb9829db36df2394e8fbc9a75c7b51c1","datavalue":{"value":"W2044309072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856175$AD7875DB-E930-4608-BDF4-B88C618B5F6E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2b0710616dc81df7c9983777cb9870ba616ebcb9","datavalue":{"value":"10.1007/S100090050034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1856175$CD0CAFAA-D8B2-4700-BC22-3FB4534B6D17","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f259d395fb34ce400f4eb8524b11aaf0e69184c9","datavalue":{"value":{"entity-type":"item","numeric-id":437674,"id":"Q437674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b73321793b6176436c6df32a00730c3c32d405a","datavalue":{"value":{"amount":"+0.8189384937286377","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":"Q1856175$3452E7F9-E820-4CA5-8B7D-7CABCCAD6BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96bf1d166352039d3decc6f540410ba0260b55dc","datavalue":{"value":{"entity-type":"item","numeric-id":5166502,"id":"Q5166502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c26eb715c31f5912bb4fc645a662384e6bc07b0","datavalue":{"value":{"amount":"+0.7855814695358276","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":"Q1856175$8975C83C-8388-43C2-9116-3AEA73E2F445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7316ccb7ef0ff536865bea3e776f2e66ea5c6441","datavalue":{"value":{"entity-type":"item","numeric-id":3073619,"id":"Q3073619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31032c8ecee4a871d9b749f75ef7233e82913e2e","datavalue":{"value":{"amount":"+0.7855812311172485","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":"Q1856175$9E647497-8FCC-49A3-89FE-DD4A51D067C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29725702c2d10de2c18b0e4e66f2dfa34005ece9","datavalue":{"value":{"entity-type":"item","numeric-id":5418252,"id":"Q5418252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5892da62d2d4503983ce1ea0701bd525f2065244","datavalue":{"value":{"amount":"+0.7822169065475464","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":"Q1856175$68F216A6-1E5F-4451-B4AC-4F864E5285D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b745e5e850b8cbef6c7afbe9a95963fe6adef931","datavalue":{"value":{"entity-type":"item","numeric-id":3549289,"id":"Q3549289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d298cdd9b10e5ad96568716f8c71128532a55b8","datavalue":{"value":{"amount":"+0.7729154229164124","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":"Q1856175$7C758F4E-3A58-4562-AD0B-5C3C712BCA8A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A minimized automaton representation of reachable states","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_minimized_automaton_representation_of_reachable_states"}}}}}