{"entities":{"Q459826":{"pageid":461593,"ns":120,"title":"Item:Q459826","lastrevid":61994988,"modified":"2026-04-11T03:04:41Z","type":"item","id":"Q459826","labels":{"en":{"language":"en","value":"Active learning of nondeterministic finite state machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6354255"}},"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":"Q459826$439144D7-D67A-4174-A4B5-CBA2EFEB0FC3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d097e23d3b9074be9a1710d33254efbeeeec659","datavalue":{"value":{"text":"Active learning of nondeterministic finite state machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q459826$AC8724CF-2007-47BB-BF02-DDFE5F9C1D79","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c33aabbe34de9c9a6d0bb1db5f5bc18baf9dcfaa","datavalue":{"value":"1296.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q459826$29F61047-7486-4C19-BABC-9A33F2B480AA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"95856d596e1cc448c06f201387808bf0fac76670","datavalue":{"value":"10.1155/2013/373265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q459826$B1358931-618E-4362-BF86-8526A8A0E800","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1272f8e9635d1187c2a3e9cd240b1ee6180bfc3e","datavalue":{"value":{"entity-type":"item","numeric-id":459823,"id":"Q459823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$8D2FC433-9722-47AE-94CF-F5EC30BC0753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd4a77274663ae4a880a8303ba34699c875575a8","datavalue":{"value":{"entity-type":"item","numeric-id":459824,"id":"Q459824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$406DCF22-038D-418C-AD56-50B0716D1E34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e548c855d1a2755e760914fa0480ab0e38db566","datavalue":{"value":{"entity-type":"item","numeric-id":459825,"id":"Q459825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$0DE7F8A5-AE73-417B-9E23-6681115B8A02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"de8de419e4ead4f2e7381ea60601c45eba12a49e","datavalue":{"value":{"entity-type":"item","numeric-id":223823,"id":"Q223823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$7B615293-B194-40DD-823B-FE7217AB3A9C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc97bc0aff607b9c22ce37ffa18b6de85001d90","datavalue":{"value":{"entity-type":"item","numeric-id":86199,"id":"Q86199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$816F6E4E-937D-425E-8FA3-CA8B94C63FD8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0bd9ab9676ef0df75a1a28ac03b07e1906746565","datavalue":{"value":{"time":"+2014-10-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q459826$2C4EEBA0-5472-4104-8EC0-D836092D6A53","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9b7191534d8da03b34f0aaa09afe4ad7e1fc7082","datavalue":{"value":"Summary: We consider the problem of learning nondeterministic finite state machines (NFSMs) from systems where their internal structures are implicit and nondeterministic. Recently, an algorithm for inferring observable NFSMs (ONFSMs), which are the potentially learnable subclass of NFSMs, has been proposed based on the hypothesis that the complete testing assumption is satisfied. According to this assumption, with an input sequence (query), the complete set of all possible output sequences is given by the so-called Teacher, so the number of times for asking the same query is not taken into account in the algorithm. In this paper, we propose \\(L^*_{NM}\\), a refined ONFSM learning algorithm that considers the amount for repeating the same query as one parameter. Unlike the previous work, our approach does not require all possible output sequences in one answer. Instead, it tries to observe the possible output sequences by asking the same query many times to the Teacher. We have proved that \\(L^*_{NM}\\) can infer the corresponding ONFSMs of the unknown systems when the number of tries for the same query is adequate to guarantee the complete testing assumption. Moreover, the proof shows that our algorithm will eventually terminate no matter whether the assumption is fulfilled or not. We also present the theoretical time complexity analysis of \\(L^*_{NM}\\). In addition, experimental results demonstrate the practical efficiency of our approach.","type":"string"},"datatype":"string"},"type":"statement","id":"Q459826$0F829F53-77DB-4990-88BB-A7847FF88C2E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q459826$5109BD4E-8EBD-46AA-A951-6E4B1EA1B7CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c189c45b466f89dd188bd061df8c45f23f05da60","datavalue":{"value":"68Q32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q459826$BEC37EED-0E22-4CBB-A103-8FD763FE74FD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83d7782dc6e134c34cb8f2f686ec0ed267aed290","datavalue":{"value":"6354255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q459826$DB115111-CAE8-45FC-BC79-08E8632AB2BB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b0cc8c7873a1a5fbf58b0cc703739ec008b6c1b6","datavalue":{"value":"Q59024126","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q459826$CEF8F84F-8969-449F-8825-9E6CCDC15BF0","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":"Q459826$1F730196-5CB8-47A6-9A70-79FE1F1A7E9A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fcc75fabf65def5497697a961c138ecb7c24ece7","datavalue":{"value":"https://doi.org/10.1155/2013/373265","type":"string"},"datatype":"url"},"type":"statement","id":"Q459826$C3FA571D-DD12-45B2-944B-AA4E193F2B14","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1b43c69145acece0129102bbcc0ccea1b693caed","datavalue":{"value":"W2123884022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q459826$F51DF45F-AD27-4174-8BB0-3C907F687262","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b08353f64bee56a663ab8a98982684a8b6497fb1","datavalue":{"value":{"entity-type":"item","numeric-id":4942015,"id":"Q4942015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$670329BC-8B9F-4E85-B9E7-4AEC514DD37C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d4e7a0cd98168872b74e4720bfb341f7c43af37","datavalue":{"value":{"entity-type":"item","numeric-id":4472253,"id":"Q4472253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$A5125D30-7A3C-482E-8CF1-D023ECCBF86C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"600d8a1514e6fed4e4c66ebeb9b62bee4bc86b61","datavalue":{"value":{"entity-type":"item","numeric-id":4417936,"id":"Q4417936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$90046AC7-EFF4-42AD-915A-20B21E2BA03B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da19bc3f85f394f3fc14e169b9411f95cb999873","datavalue":{"value":{"entity-type":"item","numeric-id":934712,"id":"Q934712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$6A65662E-7160-432A-9DCB-405BCDB089BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c55114ff063225064064e30c2c7ef5bef45a55b0","datavalue":{"value":{"entity-type":"item","numeric-id":1098326,"id":"Q1098326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$A330E62C-2289-4C94-8009-609B36FBC02E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"087f07f8e392be8ceb30b855fec239a8224e2118","datavalue":{"value":{"entity-type":"item","numeric-id":1892226,"id":"Q1892226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$7441CC6D-1E66-49B7-B2A2-D5DD687FC9BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0dec50908c32d07c05c855f5a8c285a4aa8a804","datavalue":{"value":{"entity-type":"item","numeric-id":2754000,"id":"Q2754000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$D31B3389-08BA-4454-9E79-87EE1F4031AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c9920d6eb16c77ebc9b527db6ed34a828dbb75f","datavalue":{"value":{"entity-type":"item","numeric-id":5897337,"id":"Q5897337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$1292240C-0C77-428D-8923-8C0FE5C0CFB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa72176d9b398bde0913c7a0d1cf7102b6c4a4db","datavalue":{"value":{"entity-type":"item","numeric-id":3434652,"id":"Q3434652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$1ECB67A2-93E0-4439-8A92-D900571FC8B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60da585cac100a31c125360c9cbd2d207cbfe7df","datavalue":{"value":{"entity-type":"item","numeric-id":1148667,"id":"Q1148667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$EE5D3009-419B-4EE5-9937-55E9157A210B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76099d3985ce0bd1b9edd9e0509dad34e0187d18","datavalue":{"value":{"entity-type":"item","numeric-id":4332902,"id":"Q4332902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$236BA4E5-8F4D-4E31-877A-23D31D13FE10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc28dddf049d43cbc4ed2b070e02de10dd49d06","datavalue":{"value":{"entity-type":"item","numeric-id":5900687,"id":"Q5900687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$725E1298-355E-4A91-BE0F-ED5746FDE55B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27d82d8fbef7207e3a8c855b494fb9281aee4749","datavalue":{"value":{"entity-type":"item","numeric-id":2365762,"id":"Q2365762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$D455B03B-340A-4833-80D6-911E93A00B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fbd0246ccd92887228ae4f6364f614170f1de35","datavalue":{"value":{"entity-type":"item","numeric-id":3434606,"id":"Q3434606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$DE711D89-C3E5-4080-9BBB-1A1B596F9292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a6f8c676c75552273283518d2daf462d7c08824","datavalue":{"value":{"entity-type":"item","numeric-id":4240122,"id":"Q4240122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$CEC8BF24-5EB0-46FA-80E2-86A6A2916C3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba7be545c35e3ad5c544a918892ae90433812d0b","datavalue":{"value":{"entity-type":"item","numeric-id":2849548,"id":"Q2849548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q459826$BD1CBF55-806C-4F4C-9497-6E8490D1B72A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62c52f644e47a413c8db0fdc5aaebd27ea4a4228","datavalue":{"value":{"entity-type":"item","numeric-id":1982638,"id":"Q1982638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9018167ede510e1548afe4b5d96dc73237696f2b","datavalue":{"value":{"amount":"+0.7872182130813599","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":"Q459826$AB2958C1-63ED-4500-8B8D-C6F969622A90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"162ea63d51bac9ec51c423b2c9a9027c460e0fd3","datavalue":{"value":{"entity-type":"item","numeric-id":736459,"id":"Q736459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e004d852d1d3ef99a8c434d65859c81b72f02cbd","datavalue":{"value":{"amount":"+0.7813277244567871","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":"Q459826$197A42B5-09D1-4C0D-8315-502EA34B7AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62bcd031b16e1fb9e128b66b5c70450e7d13a33b","datavalue":{"value":{"entity-type":"item","numeric-id":3602804,"id":"Q3602804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e403832b7a5898ae6b8b07d05e348420470a32b6","datavalue":{"value":{"amount":"+0.7685998678207397","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":"Q459826$FE31023F-9975-41FB-A318-E46EC06F95D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46152ae0517cd20f6efd37439b6044dbcf774ff1","datavalue":{"value":{"entity-type":"item","numeric-id":1373138,"id":"Q1373138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bcca25e457c75c16f7946803290c4742d58cc6f","datavalue":{"value":{"amount":"+0.761256217956543","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":"Q459826$B9FAC175-782C-4778-B008-BEA77F4BB1CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0016d64152255d67c702bb7c63d281a17c685903","datavalue":{"value":{"entity-type":"item","numeric-id":4240998,"id":"Q4240998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bcca25e457c75c16f7946803290c4742d58cc6f","datavalue":{"value":{"amount":"+0.761256217956543","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":"Q459826$37325C64-3BCC-4B84-BC8B-9EEED475FD2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Active learning of nondeterministic finite state machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Active_learning_of_nondeterministic_finite_state_machines"}}}}}