{"entities":{"Q705070":{"pageid":706919,"ns":120,"title":"Item:Q705070","lastrevid":63759984,"modified":"2026-04-11T15:21:39Z","type":"item","id":"Q705070","labels":{"en":{"language":"en","value":"Learnability and definability in trees and similar structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2130949"}},"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":"Q705070$00C71902-D305-4E75-9A9F-8C41BA8481F7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bcbfa4b5938ab6402cc14e44b5d73c1c98ba9bd2","datavalue":{"value":{"text":"Learnability and definability in trees and similar structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q705070$99D14C00-A7C3-4FAB-B6C4-6EE11F8EF88E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a5f5f5bc099c4060a171313e52f6885b0ce848bd","datavalue":{"value":"1062.03031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705070$45B292F5-F5A0-47DE-A83D-876A8C2F41EF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e472eff586da807ef811f77707a93e380b6a974","datavalue":{"value":{"entity-type":"item","numeric-id":414932,"id":"Q414932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705070$7DAEC31A-4EEA-4A36-836C-A66BA6DAAE99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c66a437d74ae466cacad614cef92f8e5d71204e6","datavalue":{"value":{"entity-type":"item","numeric-id":239429,"id":"Q239429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705070$64D187F4-10FB-4C41-A2E6-9AEF09F554FC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705070$458A0BEB-280D-4023-9B55-F156493A05AD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e1590bd54b214ce942d11ecbfe0ede26ab9b97ec","datavalue":{"value":{"time":"+2005-01-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q705070$F99D28F2-ECC7-4539-8A93-92FC9262D2AE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7e0602a1c63351ace6c424ee783db6dbf3a92be1","datavalue":{"value":"The problem of concept learning is to identify an unknown set from a given family of sets. A universe is a nonempty finite set \\(A\\). A vocabulary \\(\\tau\\) is a finite set of predicates defined on \\(A\\). A structure is the pair (\\(A,\\tau\\)). An atomic formula is \\({x = y}\\) or \\({R(x_1,\\dots ,x_r)}\\), where \\({R \\in \\tau}\\). Formulas of first-order logic (FO) are built up from atomic formulas using Boolean operations and quantification over individual variables. Monadic-second order logic (MSO) is the extension of FO by monadic predicates \\({X(x)}\\) defined on \\(A\\) and quantification over predicate variables. The elements \\({b_1,\\dots ,b_l}\\) from \\(A\\) in the formula \\(\\varphi({x_1,\\dots ,x_k, b_1,\\dots ,b_l})\\) are parameters. A concept class is a family \\(\\mathcal{C} \\subseteq 2^V\\) of subsets of a set \\(V\\). Let \\({U \\subseteq V}\\) and \\(\\mathcal{C} \\cap U = \\{C \\cap U \\mid C \\in\\mathcal{C}\\}\\). The set \\(U\\) is shattered by \\(\\mathcal{C}\\) if \\(\\mathcal{C} \\cap U = 2^U\\). The Vapnik-Chervonenkis dimension, or VC-dimension VC(\\(\\mathcal{C}\\)) of \\(\\mathcal{C}\\) is the maximum of the sizes of the shattered subsets of \\(V\\).  It is shown: 1) MSO formulas (FO formulas) with parameters have bounded VC-dimension over structures of bounded clique-width (local clique-width); 2) MSO formulas of a fixed size have bounded strong consistency dimension over MSO formulas of a fixed larger size, for labelled finite trees; 3) these bounds imply positive learnability results for Probably Approximately Correct (PAC) learning. The proofs are based on bounds for related definability problems for finite automata over labelled trees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q705070$CE7F3833-E8EC-483E-9D64-5F751694B1A2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705070$ECA4525B-9A45-43EF-B20B-D0B3E7CA24E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705070$5883B1AD-C2F8-41D2-82EA-CB283FF54858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c189c45b466f89dd188bd061df8c45f23f05da60","datavalue":{"value":"68Q32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705070$30B34DB7-C3C7-4B9B-977D-E908E2BEEA27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705070$24A6FAEA-6172-4555-8FE8-D31F88378AD7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"13b081810fa7327154d5462c93e6f453ffdbf91d","datavalue":{"value":"2130949","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705070$CFD92427-7C2F-49A8-A659-FFD7A6C0E8EA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2e80a7123e4ea6d0418cb24d37b1837f13e3514","datavalue":{"value":"first-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q705070$4A7CDDFC-B884-45D6-B205-09228E903689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d16b11223dd43ac9feeeb5b11a98ef1a7a06ae9a","datavalue":{"value":"monadic second-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q705070$BFD4A402-F6B5-4F10-B357-D561319E5061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a919145a8d91e5bf18a729fe724788666577777","datavalue":{"value":"logical predicate structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q705070$0EAB68A7-D8F2-498D-8E7C-C55915AC4217","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9759b5a5098d7d24bde4280c4d93c5901710d07","datavalue":{"value":"finite automata over trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q705070$5BCFD721-F2A6-46B9-8FEE-7CAF38E0AC08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2ac3f30d773ef1894fb2eb52711e135b17d0158","datavalue":{"value":"definability","type":"string"},"datatype":"string"},"type":"statement","id":"Q705070$9C712E9C-A5A4-491A-8335-08CC9B36433B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"addf046f49d999feba6e6e34a05ae01173f260e1","datavalue":{"value":"learnability","type":"string"},"datatype":"string"},"type":"statement","id":"Q705070$011E2E95-AE23-41D7-9ADF-08229122CA66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7167f9d72dd838096c8ddd55cff062736c103386","datavalue":{"value":"probably approximately correct (PAC) learning","type":"string"},"datatype":"string"},"type":"statement","id":"Q705070$9CB79B59-6758-4F57-A5A1-E3B4A83FDEA6","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":"Q705070$B641B9B4-2EA3-480F-BEF0-4D6E232A4229","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6a5a17e3bc428ceb096274f4578df95d3b373f73","datavalue":{"value":"https://doi.org/10.1007/s00224-003-1112-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q705070$E67AD610-953A-431C-855C-3BDF3CCE4AF4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f0e1280098b620526f290b4f3be778f88c72e4c5","datavalue":{"value":"W1996805091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705070$7DD5A1F9-F350-41FB-A08E-61952967CE63","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2772735954f66cb2c4959a1b167bb5987fd638ba","datavalue":{"value":"10.1007/S00224-003-1112-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705070$663E406D-A196-43A9-B5B4-5F0A4C1AAF49","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a765165c22a2f322ed77d478ce00914ab70cd0bc","datavalue":{"value":{"entity-type":"item","numeric-id":4736878,"id":"Q4736878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb55c3f51e9dfdc7e05da4a04017eca23216d001","datavalue":{"value":{"amount":"+0.9934898018836976","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":"Q705070$3A6479A2-E0FA-4527-A5D8-6577A80AE5A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"815686a9782e2920c32ea79b860a50654025a423","datavalue":{"value":{"entity-type":"item","numeric-id":5144626,"id":"Q5144626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba6358c34896a5726e4ebeb10e6443e5ee3a7974","datavalue":{"value":{"amount":"+0.7556989789009094","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":"Q705070$BBE026DF-98C0-4125-9D14-9C4FC560E755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de7cb78c3fa8b3e31e569159ae478f26db083f0c","datavalue":{"value":{"entity-type":"item","numeric-id":1426470,"id":"Q1426470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e449ec07b2dddea6fc5434037d5a3fe680cb702","datavalue":{"value":{"amount":"+0.7370890974998474","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":"Q705070$3A25A813-B9DC-48FC-ABDB-F8623BDBECED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c749a5ff924b6c635da17b4111d6f67bec62d94","datavalue":{"value":{"entity-type":"item","numeric-id":5897176,"id":"Q5897176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad9a236200976641d7ddd7ce1c608559fa5e7a43","datavalue":{"value":{"amount":"+0.7338753938674927","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":"Q705070$7C72EB49-EC3F-4000-9BBA-6532933F363E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"480f4965e6d5476140a252caa417a8dc753bee36","datavalue":{"value":{"entity-type":"item","numeric-id":5464509,"id":"Q5464509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d23d1c7b82e87399a213e2478e42064c4cbbf956","datavalue":{"value":{"amount":"+0.7266600728034973","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":"Q705070$F0CA72DB-2528-41D8-99FF-4A97D2B04392","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Learnability and definability in trees and similar structures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Learnability_and_definability_in_trees_and_similar_structures"}}}}}