{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T20:14:25Z","timestamp":1777407265686,"version":"3.51.4"},"reference-count":46,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["2021-04109"],"award-info":[{"award-number":["2021-04109"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Soft. Eng. Knowl. Eng."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:p> A Qualitative Constraint Network (QCN) is a constraint graph representing problems under qualitative temporal or spatial relations. More formally, a QCN includes a set of entities and a list of qualitative constraints defining the possible scenarios between these entities. Qualitative constraints are expressed as disjunctions of binary relations capturing the (incomplete) knowledge between the involved entities. QCNs effectively represent various real-world applications, including scheduling and planning, configuration, and Geographic Information Systems (GIS). It is, however, challenging to elicit, from the user, the QCN representing a given problem. To overcome this difficulty in practice, we propose a new algorithm for learning, through membership queries, a QCN from a non-expert. Membership queries are asked to elicit temporal or spatial relationships between pairs of temporal or spatial entities. To improve the time performance of our learning algorithm, constraint propagation and ordering heuristics are enforced. The goal is to reduce the number of membership queries needed to reach the target QCN. We conducted several experiments on randomly generated temporal and spatial QCN instances to assess the practical effect of constraint propagation and ordering heuristics. The results of the experiments are encouraging and promising. <\/jats:p>","DOI":"10.1142\/s0218194023500171","type":"journal-article","created":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T06:33:05Z","timestamp":1681108385000},"page":"837-863","source":"Crossref","is-referenced-by-count":4,"title":["Exact Learning of Qualitative Constraint Networks from Membership Queries"],"prefix":"10.1142","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7381-1064","authenticated-orcid":false,"given":"Malek","family":"Mouhoub","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Regina, 3737 Wascana Pkwy, Regina SK S4S 0A2, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamad","family":"Al Marri","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Regina, 3737 Wascana Pkwy, Regina SK S4S 0A2, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eisa","family":"Alanazi","sequence":"additional","affiliation":[{"name":"Um Al Qura University Aif Road, 21955, Mecca, Makkah Province, 8XH2+XVP, Makkah 24382, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2023,5,17]]},"reference":[{"key":"S0218194023500171BIB001","first-page":"1361","volume-title":"Proc. Twenty-Fifth Int. Joint Conf. Artificial Intelligence","author":"Alanazi E.","year":"2016"},{"key":"S0218194023500171BIB002","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2019.103182","volume":"278","author":"Alanazi E.","year":"2020","journal-title":"Artif. Intell."},{"issue":"11","key":"S0218194023500171BIB003","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"Allen J. F.","year":"1983","journal-title":"Commun. ACM"},{"key":"S0218194023500171BIB004","first-page":"108","volume-title":"The Thirty-Second Int. Flairs Conf.","author":"Allen J.","year":"2019"},{"key":"S0218194023500171BIB005","first-page":"8","volume-title":"The Thirtieth Int. Flairs Conf.","author":"Allen T. E.","year":"2017"},{"issue":"2","key":"S0218194023500171BIB006","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"Angluin D.","year":"1987","journal-title":"Inf. Comput."},{"issue":"4","key":"S0218194023500171BIB007","first-page":"319","volume":"2","author":"Angluin D.","year":"1988","journal-title":"Mach. Learn."},{"key":"S0218194023500171BIB008","first-page":"698","volume-title":"Workshop on Constraints and Preferences for Configuration and Recommendation, the Twenty-Forth Int. Joint Conf. Artificial Intelligence","author":"Arcangioli R.","year":"2015"},{"key":"S0218194023500171BIB009","first-page":"442","volume-title":"Proc. 16th Int. Joint Conf. Artificial intelligence - Volume 1","author":"Balbiani P.","year":"1999"},{"key":"S0218194023500171BIB010","first-page":"3690","volume-title":"Proc. AAAI Conf. Artificial Intelligence","author":"Belaid M.-B.","year":"2022"},{"key":"S0218194023500171BIB011","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/978-3-642-33558-7_13","volume-title":"Int. Conf. Principles and Practice of Constraint Programming","author":"Beldiceanu N.","year":"2012"},{"key":"S0218194023500171BIB012","doi-asserted-by":"crossref","unstructured":"N. Beldiceanu and  H. Simonis,  ModelSeeker: Extracting Global Constraint Models from Positive Examples  (Springer International Publishing,  Cham,  2016), pp.  77\u201395.","DOI":"10.1007\/978-3-319-50137-6_4"},{"key":"S0218194023500171BIB013","first-page":"1004","volume-title":"IEEE 24th Int. Conf. Tools with Artificial Intelligence","author":"Belouaer L.","year":"2012"},{"key":"S0218194023500171BIB014","first-page":"50","volume-title":"Proc. Twentiest Int. Joint Conf. Artificial Intelligence","author":"Bessiere C.","year":"2007"},{"key":"S0218194023500171BIB015","first-page":"7","volume-title":"23rd Int. Joint Conf. Artificial Intelligence","author":"Bessiere C.","year":"2013"},{"key":"S0218194023500171BIB016","first-page":"3","volume-title":"Proc. ECAI\u201996","author":"Bessiere C.","year":"1996"},{"key":"S0218194023500171BIB017","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.artint.2015.08.001","volume":"244","author":"Bessiere C.","year":"2017","journal-title":"Artif. Intell."},{"key":"S0218194023500171BIB018","first-page":"456","volume-title":"Int. Joint Conf. Artificial Intelligence","author":"Bliek C.","year":"1999"},{"key":"S0218194023500171BIB019","first-page":"1084","volume-title":"Proc. AAAI Conf. Artificial Intelligence","author":"Cohen-Solal Q.","year":"2017"},{"key":"S0218194023500171BIB020","first-page":"586","volume-title":"FLAIRS Conf.","author":"Condotta J.-F.","year":"2008"},{"key":"S0218194023500171BIB021","first-page":"7965","volume-title":"Thirty-Second AAAI Conf. Artificial Intelligence, Assoc. Advancement Artificial Intelligence","author":"De Raedt L.","year":"2018"},{"key":"S0218194023500171BIB022","volume-title":"Constraint Processing","author":"Dechter R.","year":"2003"},{"issue":"2","key":"S0218194023500171BIB024","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1080\/02693799108927841","volume":"5","author":"Egenhofer M. J.","year":"1991","journal-title":"Int. J. Geogr. Inf. Syst."},{"key":"S0218194023500171BIB025","author":"Fajemisin A.","year":"2022","journal-title":"CoRR"},{"issue":"1","key":"S0218194023500171BIB026","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0004-3702(92)90090-K","volume":"54","author":"Freksa C.","year":"1992","journal-title":"Artif. Intell."},{"key":"S0218194023500171BIB027","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1006\/jcss.1995.1003","volume":"50","author":"Goldman S. A.","year":"1995","journal-title":"J. Comput. Syst. Sci."},{"key":"S0218194023500171BIB028","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/978-3-642-41575-3_16","volume-title":"Algorithmic Decision Theory","author":"Guerin J.","year":"2013"},{"issue":"11","key":"S0218194023500171BIB029","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1016\/j.artint.2010.04.019","volume":"174","author":"Koriche F.","year":"2010","journal-title":"Artif. Intell."},{"issue":"1","key":"S0218194023500171BIB030","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0004-3702(02)00372-7","volume":"145","author":"Li S.","year":"2003","journal-title":"Artif. Intell."},{"key":"S0218194023500171BIB031","first-page":"99","volume-title":"Workshop on Spatial and Temporal Reasoning, ECAI-94","author":"Ligozat G.","year":"1994"},{"key":"S0218194023500171BIB032","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/978-3-319-23374-1_17","volume-title":"Int. Conf. Spatial Information Theory","author":"Long Z.","year":"2015"},{"key":"S0218194023500171BIB033","first-page":"1202","volume-title":"Proc. Twenty-Fifth Int. Joint Conf. Artificial Intelligence","author":"Long Z.","year":"2016"},{"key":"S0218194023500171BIB034","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"Mackworth A. K.","year":"1977","journal-title":"Artif. Intell."},{"issue":"2","key":"S0218194023500171BIB035","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0004-3702(86)90083-4","volume":"28","author":"Mohr R.","year":"1986","journal-title":"Artif. Intell."},{"key":"S0218194023500171BIB036","first-page":"393","volume-title":"The 21st IASTED Int. Multi-Conf. Applied Informatics (AI 2003)","author":"Mouhoub M.","year":"2003"},{"issue":"1","key":"S0218194023500171BIB037","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1023\/B:AIRE.0000007179.60276.39","volume":"21","author":"Mouhoub M.","year":"2004","journal-title":"Artif. Intell. Rev."},{"key":"S0218194023500171BIB038","first-page":"19:1","volume-title":"25th Int. Symp. Temporal Representation and Reasoning, TIME","author":"Mouhoub M.","year":"2018"},{"issue":"1","key":"S0218194023500171BIB039","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1080\/13875860801930407","volume":"8","author":"Mouhoub M.","year":"2008","journal-title":"Spatial Cogn. Comput."},{"issue":"1","key":"S0218194023500171BIB040","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/s10489-010-0246-z","volume":"36","author":"Mouhoub M.","year":"2012","journal-title":"Appl. Intell."},{"key":"S0218194023500171BIB041","volume-title":"Genetic Programming","author":"Pawlak T. P.","year":"2017"},{"issue":"1","key":"S0218194023500171BIB042","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1109\/TEVC.2018.2835565","volume":"23","author":"Pawlak T. P.","year":"2019","journal-title":"IEEE Trans. Evol. Comput."},{"key":"S0218194023500171BIB043","first-page":"136","volume-title":"Eighth Symposium on Abstraction, Reformulation, and Approximation","author":"Revesz P.","year":"2009"},{"issue":"1","key":"S0218194023500171BIB044","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4067\/S0718-18762016000100001","volume":"11","author":"Sadaoui S.","year":"2016","journal-title":"J. Theor. Appl. Electron. Comm. Res."},{"key":"S0218194023500171BIB045","first-page":"1813","volume-title":"Proc. Twenty-Ninth Int. Conf. Int. Joint Conf. Artificial Intelligence","author":"Sioutis M.","year":"2021"},{"key":"S0218194023500171BIB046","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/978-3-319-98334-9_25","volume-title":"Int. Conf. Principles and Practice of Constraint Programming","author":"Tsouros D. C.","year":"2018"},{"issue":"1","key":"S0218194023500171BIB047","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.232","volume":"4","author":"Beek P. V.","year":"1996","journal-title":"J. Artif. Intell. Res."}],"container-title":["International Journal of Software Engineering and Knowledge Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218194023500171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T13:20:20Z","timestamp":1687785620000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218194023500171"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,17]]},"references-count":46,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10.1142\/S0218194023500171"],"URL":"https:\/\/doi.org\/10.1142\/s0218194023500171","relation":{},"ISSN":["0218-1940","1793-6403"],"issn-type":[{"value":"0218-1940","type":"print"},{"value":"1793-6403","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,17]]}}}