{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T02:22:41Z","timestamp":1777429361790,"version":"3.51.4"},"reference-count":56,"publisher":"Vilnius University Press","license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:p>A special class of monotone Boolean functions coming from shadow minimization theory of finite set-systems \u2013 KK-MBF functions \u2013 is considered. These functions are a descriptive model for systems of compatible groups of constraints, however, the class of all functions is unambiguously complex and it is sensible to study relatively simple subclasses of functions such as KK-MBF. Zeros of KK-MBF functions correspond to initial segments of lexicographic order on hypercube layers. This property is used to simplify the recognition. Lexicographic order applies priorities over constraints which is applicable property of practices. Query-based algorithms for KK-MBF functions are investigated in terms of their complexities.<\/jats:p>","DOI":"10.15388\/24-infor542","type":"journal-article","created":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T12:05:20Z","timestamp":1707912320000},"page":"1-20","source":"Crossref","is-referenced-by-count":4,"title":["Shadow Minimization Boolean Function Reconstruction"],"prefix":"10.15388","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5354-2730","authenticated-orcid":false,"given":"Levon","family":"Aslanyan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0188-0391","authenticated-orcid":false,"given":"Gyula","family":"Katona","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8449-6845","authenticated-orcid":false,"given":"Hasmik","family":"Sahakyan","sequence":"additional","affiliation":[]}],"member":"6097","published-online":{"date-parts":[[2024,2,14]]},"reference":[{"key":"2024031410102051048_j_infor542_ref_001","first-page":"85","article-title":"The discrete isoperimetry problem and related extremal problems for discrete spaces","volume":"36","year":"1979","journal-title":"Problemy Kibernetiki"},{"key":"2024031410102051048_j_infor542_ref_002","first-page":"132","volume-title":"Intenational Book Series Information Science and Computing, Book 8, Classification, Forecasting, Data Mining","year":"2009"},{"key":"2024031410102051048_j_infor542_ref_003","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1016\/j.dam.2016.04.008","article-title":"The splitting technique in monotone recognition","volume":"216","year":"2017","journal-title":"Discrete Applied Mathematics"},{"key":"2024031410102051048_j_infor542_ref_004","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1109\/CSITechnol.2019.8895058","volume-title":"2019 Computer Science and Information Technologies (CSIT)","year":"2019"},{"issue":"3","key":"2024031410102051048_j_infor542_ref_005","first-page":"398","article-title":"Target class classification recursion preliminaries","volume":"11","year":"2023","journal-title":"Baltic Journal of Modern Computing"},{"key":"2024031410102051048_j_infor542_ref_006","first-page":"119","volume-title":"2023 Computer Science and Information Technologies (CSIT)","year":"2023"},{"key":"2024031410102051048_j_infor542_ref_007","doi-asserted-by":"crossref","first-page":"103201","DOI":"10.1016\/j.ejc.2020.103201","article-title":"The domination number of the graph defined by two levels of the n-cube, II","volume":"91","year":"2021","journal-title":"European Journal of Combinatorics"},{"issue":"12","key":"2024031410102051048_j_infor542_ref_008","doi-asserted-by":"crossref","first-page":"113632","DOI":"10.1016\/j.disc.2023.113632","article-title":"Pull-push method: a new approach to edge-isoperimetric problems","volume":"346","year":"2023","journal-title":"Discrete Mathematics"},{"key":"2024031410102051048_j_infor542_ref_009"},{"key":"2024031410102051048_j_infor542_ref_010"},{"key":"2024031410102051048_j_infor542_ref_011","first-page":"731","volume-title":"Learning Theory and Kernel Machines","year":"2003"},{"issue":"1\u20133","key":"2024031410102051048_j_infor542_ref_012","first-page":"155","article-title":"Pseudo-Boolean optimization","volume":"123","year":"2002","journal-title":"Discrete Applied Mathematics"},{"key":"2024031410102051048_j_infor542_ref_013","first-page":"104","volume-title":"ISA\u201991 Algorithms: 2nd International Symposium on Algorithms Taipei","year":"1991"},{"key":"2024031410102051048_j_infor542_ref_014"},{"issue":"1","key":"2024031410102051048_j_infor542_ref_015","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1515\/jmc-2014-0030","article-title":"Cryptographic properties of monotone Boolean functions","volume":"10","year":"2016","journal-title":"Journal of Mathematical Cryptology"},{"key":"2024031410102051048_j_infor542_ref_016"},{"issue":"2","key":"2024031410102051048_j_infor542_ref_017","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0012-365X(73)90074-5","article-title":"A minimization problem concerning subsets of a finite set","volume":"4","year":"1973","journal-title":"Discrete Mathematics"},{"key":"2024031410102051048_j_infor542_ref_018","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/j.tcs.2022.04.045","article-title":"Joint realizability of monotone Boolean functions","volume":"922","year":"2022","journal-title":"Theoretical Computer Science"},{"key":"2024031410102051048_j_infor542_ref_019","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.dam.2020.09.003","article-title":"Adaptive majority problems for restricted query graphs and for weighted sets","volume":"288","year":"2021","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"2024031410102051048_j_infor542_ref_020","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0097-3165(74)90011-9","article-title":"Existence theorems for Sperner families","volume":"17","year":"1974","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"2024031410102051048_j_infor542_ref_021"},{"key":"2024031410102051048_j_infor542_ref_022","article-title":"On strengthenings of the intersecting shadow theorem","volume":"184","year":"2021","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"2024031410102051048_j_infor542_ref_023","doi-asserted-by":"publisher","DOI":"10.1080\/02331934.2022.2154126"},{"issue":"8","key":"2024031410102051048_j_infor542_ref_024","first-page":"1250","article-title":"On one criterion of the optimality of an algorithm for evaluating monotonic Boolean functions","volume":"24","year":"1984","journal-title":"Zhurnal Vychislitel\u2019noi Matematiki i Matematicheskoi Fiziki"},{"key":"2024031410102051048_j_infor542_ref_025","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s11083-022-09622-6","article-title":"The saturation spectrum for antichains of subsets","volume":"40","year":"2023","journal-title":"Order"},{"issue":"20","key":"2024031410102051048_j_infor542_ref_026","first-page":"1088","article-title":"Sur le nombre des fonctions Bool\u00e9ennes monotones de n variables","volume":"262","year":"1966","journal-title":"Comptes Rendus de l\u2019Acad\u00e9mie des Sciences"},{"issue":"5","key":"2024031410102051048_j_infor542_ref_027","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.dam.2010.08.022","article-title":"Learning random monotone DNF","volume":"159","year":"2011","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"2024031410102051048_j_infor542_ref_028","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/s00373-023-02634-y","article-title":"Shadow ratio of hypergraphs with bounded degree","volume":"39","year":"2023","journal-title":"Graphs and Combinatorics"},{"key":"2024031410102051048_j_infor542_ref_029","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/ICISCT52966.2021.9670370","volume-title":"2021 International Conference on Information Science and Communications Technologies (ICISCT)","year":"2021"},{"key":"2024031410102051048_j_infor542_ref_030","volume-title":"Theory of Graphs (Proceedings of the Colloquim held at Tihany)","year":"1968"},{"key":"2024031410102051048_j_infor542_ref_031"},{"key":"2024031410102051048_j_infor542_ref_032","first-page":"5","article-title":"On monotone functions of the algebra of logic","volume":"13","year":"1965","journal-title":"Problemy Kibernetiki"},{"key":"2024031410102051048_j_infor542_ref_033","first-page":"5","article-title":"On the number of monotone Boolean menge","volume":"38","year":"1981","journal-title":"Problemy Kibernetiki"},{"issue":"5","key":"2024031410102051048_j_infor542_ref_034","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1070\/RM2003v058n05ABEH000667","article-title":"Monotone Boolean functions","volume":"58","year":"2003","journal-title":"Russian Mathematical Surveys"},{"key":"2024031410102051048_j_infor542_ref_035","first-page":"387","volume-title":"Visual and Spatial Analysis: Advances in Data Mining, Reasoning, and Problem Solving","year":"2005"},{"key":"2024031410102051048_j_infor542_ref_036","first-page":"251","article-title":"The number of simplices in a complex","volume":"10","year":"1963","journal-title":"Mathematical Optimization Techniques"},{"key":"2024031410102051048_j_infor542_ref_037","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/CSITechnol.2019.8895166","volume-title":"2019 Computer Science and Information Technologies (CSIT)","year":"2019"},{"key":"2024031410102051048_j_infor542_ref_038"},{"key":"2024031410102051048_j_infor542_ref_039","volume-title":"Combinatorial Problems and Exercises","year":"2007","edition":"3nd edition"},{"key":"2024031410102051048_j_infor542_ref_040"},{"issue":"2","key":"2024031410102051048_j_infor542_ref_041","first-page":"79","article-title":"Estimates of the degrees of separating polynomials for monotone and self-dual functions","volume":"27","year":"2023","journal-title":"Intelligent Systems. Theory and Applications"},{"key":"2024031410102051048_j_infor542_ref_042"},{"key":"2024031410102051048_j_infor542_ref_043","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/CSITechnol.2013.6710342","volume-title":"Ninth International Conference on Computer Science and Information Technologies Revised Selected Papers","year":"2013"},{"issue":"5","key":"2024031410102051048_j_infor542_ref_044","first-page":"243","article-title":"On the set of simple hypergraph degree sequences","volume":"9","year":"2015","journal-title":"Applied Mathematical Sciences"},{"key":"2024031410102051048_j_infor542_ref_045","first-page":"47","volume-title":"2023 Computer Science and Information Technologies (CSIT)","year":"2023"},{"key":"2024031410102051048_j_infor542_ref_046","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/CSITechnol.2017.8312153","volume-title":"2017 Computer Science and Information Technologies (CSIT)","year":"2017"},{"key":"2024031410102051048_j_infor542_ref_047","volume-title":"Proceedings of \u201cMiddle-European Conference on Applied Theoretical Computer Science\u201d Conference","year":"2022"},{"key":"2024031410102051048_j_infor542_ref_048"},{"key":"2024031410102051048_j_infor542_ref_049","volume-title":"Ordered Sets: An Introduction with Connections from Combinatorics to Topology","year":"2016"},{"issue":"6","key":"2024031410102051048_j_infor542_ref_050","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0041-5553(87)90211-4","article-title":"Optimal reconstruction of monotone Boolean functions","volume":"27","year":"1987","journal-title":"Computational Mathematics and Mathematical Physics"},{"key":"2024031410102051048_j_infor542_ref_051","first-page":"2866","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition","year":"2021"},{"issue":"6","key":"2024031410102051048_j_infor542_ref_052","first-page":"1532","article-title":"Chain partitioning of n-cube vertices and deciphering of monotone Boolean functions","volume":"19","year":"1979","journal-title":"Journal of Computational Mathematics and Mathematical Physics"},{"issue":"11","key":"2024031410102051048_j_infor542_ref_053","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"27","year":"1984","journal-title":"Communications of the ACM"},{"key":"2024031410102051048_j_infor542_ref_054","doi-asserted-by":"publisher","first-page":"8964","DOI":"10.1109\/CVPR52688.2022.00876","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition","year":"2022"},{"key":"2024031410102051048_j_infor542_ref_055","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1134\/S1054661819030246","article-title":"On a classification method for a large number of classes","volume":"29","year":"2019","journal-title":"Pattern Recognition and Image Analysis"},{"key":"2024031410102051048_j_infor542_ref_056","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1134\/S105466182003030X","article-title":"Comparison of different dichotomous classification algorithms","volume":"30","year":"2020","journal-title":"Pattern Recognition and Image Analysis"}],"container-title":["Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/informatica.vu.lt\/journal\/INFORMATICA\/article\/1320\/text","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/informatica.vu.lt\/journal\/INFORMATICA\/article\/1320\/text","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T09:59:26Z","timestamp":1710410366000},"score":1,"resource":{"primary":{"URL":"https:\/\/informatica.vu.lt\/doi\/10.15388\/24-INFOR542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":56,"alternative-id":["10.15388\/24-INFOR542"],"URL":"https:\/\/doi.org\/10.15388\/24-infor542","relation":{},"ISSN":["0868-4952","1822-8844"],"issn-type":[{"value":"0868-4952","type":"print"},{"value":"1822-8844","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]}}}