{"entities":{"Q2365762":{"pageid":2376505,"ns":120,"title":"Item:Q2365762","lastrevid":72612483,"modified":"2026-04-14T06:04:43Z","type":"item","id":"Q2365762","labels":{"en":{"language":"en","value":"Inference of finite automata using homing sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 222735"}},"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":"Q2365762$4BDE6610-332C-4C54-8BC5-52F4CC7982CA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d21d54a0fcd3d5b093e32e8363abdc6f1a9f292","datavalue":{"value":{"text":"Inference of finite automata using homing sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2365762$8CD3BBCF-F667-40D2-AD5D-F628038097F3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"91a68557c18e72a77ab43705ed076a4846d0989f","datavalue":{"value":"0786.68082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365762$6C8577F4-993F-4739-A12D-FFC7B4B3F02E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3aef41116742d0118bdd5de24a9c8fc5c09099c9","datavalue":{"value":{"entity-type":"item","numeric-id":198993,"id":"Q198993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365762$A5B6D18B-95FD-47E0-95F2-1F8B65785E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e274e1e627d8192877996877ffbdf70313b7c6","datavalue":{"value":{"entity-type":"item","numeric-id":207981,"id":"Q207981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365762$F9395D7B-4F68-4DD6-BFB3-71DECDCDD31F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2365762$0691929C-2580-49B1-9ADF-41058D5F1A02","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2365762$EEC7B8B9-607F-4949-8B3E-DC9031A132B5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"107d3b58e8a9524d19cf3ef3a44e03a503d90e5e","datavalue":{"value":"https://semanticscholar.org/paper/9a62d26420afc77543c8f17bae1b482bcb28dc66","type":"string"},"datatype":"url"},"type":"statement","id":"Q2365762$B05BE2C6-5B5C-4F0C-A089-C4F0A56A7500","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8fddf3d56ba64bd63df91ef32e3f2f764c2ba6ef","datavalue":{"value":"We present new algorithms for inferring an unknown finite-state automaton from its input/output behavior, even in the absence of a means of resetting the machine to a start state. A key technique used is inference of a homing sequence for the unknown automaton. Our inference procedures experiment with the unknown machine, and from time to time require a teacher to supply counterexamples to incorrect conjectures about the structure of the unknown automaton. In this setting, we describe a learning algorithm that, with probability \\(1-\\delta\\), outputs a correct description of the unknown machine in time polynomial in the automaton's size, the length of the longest counterexample, and \\(\\log (1/ \\delta)\\). We present an analogous algorithm that makes use of a diversity-based representation of the finite-state system. Our algorithms are the first which are provable effective for these problems, in the absence of a ``reset''. We also present probabilistic algorithms for permutation automata which do not require a teacher to supply counterexamples. For inferring a permutation automaton of diversity \\(D\\), we improve the best previous time bound by roughly a factor of \\(D^ 3/ \\log D\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365762$6D9DB36E-3C9D-41C1-A199-4AB12A923E6B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365762$EC99C19E-0C2A-4CB1-87BB-B41F315B0227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365762$30ADE605-E32E-4280-AEB9-4D8E29A456D9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bb3d888b0f4b9bedd4a2880d74290795034d7e1d","datavalue":{"value":"222735","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365762$E3B406F5-A98A-47AD-AD17-E742E0E14CA2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0afe30fcd4cd25e8e8273c02ad48a97b4a0e001","datavalue":{"value":"machine learning","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365762$AD3BDA04-0048-4FC5-8CF0-D6422199568F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"81a56cecd4c580bb9e8a640d3f487f2f064f44f0","datavalue":{"value":"computational learning theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365762$468FE429-96F4-4C45-84FD-6E033BFF4C09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf7e1360e2c6e18648753069c3301a5c4a403945","datavalue":{"value":"autonomous robot","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365762$BE631E42-0DB2-4BC7-BC42-1CE6D0AC1965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f96ab68362ecc7785c310a8bc5d1601c40b4b65","datavalue":{"value":"finite-state automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365762$C8AF620A-F696-45D0-9CDC-A5A148CF88C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f030b447315b4371bb0bfc676cd365844227399","datavalue":{"value":"homing sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365762$643008F6-ECD3-4838-A07F-97FA49057FA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"898f6c9f815b5e5de842b82c42360a6749afde20","datavalue":{"value":"learning algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365762$DA3472B2-5E3A-4CB1-9205-3968C808B3A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9b5d0c5aa6fceadb44a9e4899a1ae967f92644b","datavalue":{"value":"permutation automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2365762$FF4D0B3A-0128-4906-A65B-BB1AC28176F9","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":"Q2365762$DD383080-C93D-4E1B-A9C8-153F2BFE37BD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"620a7c14e83ea17793235c804fffedc0913dfb24","datavalue":{"value":"W2140606869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365762$0CEB4173-D774-4619-BE57-67351CCFD9A9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eb329607023cddfdc6b4b98051a374b4cc2f1dfe","datavalue":{"value":"10.1006/INCO.1993.1021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2365762$B13CBC6C-B82B-451F-B866-64EA63EA44D8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e26f38cc65b7861ece7e281aa5d0f5f4d4f7b5ff","datavalue":{"value":{"entity-type":"item","numeric-id":4305673,"id":"Q4305673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac3afc9445ecc761c6634d9559ecce99e3395d75","datavalue":{"value":{"amount":"+0.8566904664039612","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":"Q2365762$3788AABD-964A-43C2-A473-BB45FA34C447","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2107f0368c94f7f0911039e0a1a886c9b577e0e0","datavalue":{"value":{"entity-type":"item","numeric-id":4336266,"id":"Q4336266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac3afc9445ecc761c6634d9559ecce99e3395d75","datavalue":{"value":{"amount":"+0.8566904664039612","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":"Q2365762$0BDFE3DD-E994-4FDB-9027-CA8DD16E42A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f43c6423feb68033fc4637150c96305ede6422b8","datavalue":{"value":{"entity-type":"item","numeric-id":3219768,"id":"Q3219768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2d296bcfc3ee953a40f3b90ae6a5f6a868f3f90","datavalue":{"value":{"amount":"+0.8170664310455322","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":"Q2365762$8C696D1D-8495-4B28-A444-6D3E031A3E29","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":"8a3527fff1631d1d9fe67ec7bd619a0998d7a6d1","datavalue":{"value":{"amount":"+0.8020106554031372","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":"Q2365762$7CAF2F6F-A748-4D5A-8276-EF3739238C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cd9bfb26ae3bdcea52062f729db82996722be65","datavalue":{"value":{"entity-type":"item","numeric-id":1098326,"id":"Q1098326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a3527fff1631d1d9fe67ec7bd619a0998d7a6d1","datavalue":{"value":{"amount":"+0.8020106554031372","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":"Q2365762$D0B78FB1-0E19-4E45-8CA9-D90FD5E722B0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Inference of finite automata using homing sequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Inference_of_finite_automata_using_homing_sequences"}}}}}