Loading…
Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning
We survey the use and effect of decomposition-based techniques in qualitative spatial and temporal constraint-based reasoning, and clarify the notions of a tree decomposition, a chordal graph, and a partitioning graph, and their implication with a particular constraint property that has been extensi...
Saved in:
| Published in: | Knowledge engineering review 2017, Vol.32, Article e4 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c351t-cc51af803828a16b16ab7b05bbf8f5c8d9c91a4c8157f893fc0d0beb44f794723 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c351t-cc51af803828a16b16ab7b05bbf8f5c8d9c91a4c8157f893fc0d0beb44f794723 |
| container_end_page | |
| container_issue | |
| container_start_page | |
| container_title | Knowledge engineering review |
| container_volume | 32 |
| creator | Sioutis, Michael Salhi, Yakoub Condotta, Jean-François |
| description | We survey the use and effect of decomposition-based techniques in qualitative
spatial and temporal constraint-based reasoning, and clarify the notions of a
tree decomposition, a chordal graph, and a partitioning graph, and their
implication with a particular constraint property that has been extensively used
in the literature, namely, patchwork. As a consequence, we prove that a recently
proposed decomposition-based approach that was presented in the study by
Nikolaou and Koubarakis for checking the satisfiability of qualitative spatial
constraint networks lacks soundness. Therefore, the approach becomes quite
controversial as it does not seem to offer any technical advance at all, while
results of an experimental evaluation of it in a following work presented in the
study by Sioutis become questionable. Finally, we present a particular tree
decomposition that is based on the biconnected components of the constraint
graph of a given large network, and show that it allows for cost-free
utilization of parallelism for a qualitative constraint language that has
patchwork for satisfiable atomic networks. |
| doi_str_mv | 10.1017/S026988891600014X |
| format | article |
| fullrecord | <record><control><sourceid>proquest_hal_p</sourceid><recordid>TN_cdi_hal_primary_oai_HAL_hal_02067922v1</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><cupid>10_1017_S026988891600014X</cupid><sourcerecordid>4319594071</sourcerecordid><originalsourceid>FETCH-LOGICAL-c351t-cc51af803828a16b16ab7b05bbf8f5c8d9c91a4c8157f893fc0d0beb44f794723</originalsourceid><addsrcrecordid>eNp1kM1LAzEQxYMoWD_-AG8BTx5WZ_YzOUpRKxQ8VMHbms0mbaTdbJOs4H9v1hYRxNMw837vMTxCLhCuEbC6WUBacsYYxxIAMH89IBPMS54wgOKQTEY5GfVjcuL9e0QyhGxC3hZhaD9Nt6RhpejgFRVdS5XWSgZqNV060a9oq6Td9NabYGxHTUe3g1ibIIL5UNT3cYr1tzGoiLm4OCW87WLuGTnSYu3V-X6ekpf7u-fpLJk_PTxOb-eJzAoMiZQFCs0gYykTWDZYiqZqoGgazXQhWcslR5FLhkWlGc-0hBYa1eS5rnhepdkpudrlrsS67p3ZCPdZW2Hq2e28Hm-QQlnxNP3AyF7u2N7Z7aB8qN_t4Lr4Xo2sKoBVHItI4Y6SznrvlP6JRajH0us_pUdPtveITeNMu1S_ov91fQHQ_oQ_</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1875087915</pqid></control><display><type>article</type><title>Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning</title><source>ABI/INFORM Global</source><source>Cambridge University Press</source><creator>Sioutis, Michael ; Salhi, Yakoub ; Condotta, Jean-François</creator><creatorcontrib>Sioutis, Michael ; Salhi, Yakoub ; Condotta, Jean-François</creatorcontrib><description>We survey the use and effect of decomposition-based techniques in qualitative
spatial and temporal constraint-based reasoning, and clarify the notions of a
tree decomposition, a chordal graph, and a partitioning graph, and their
implication with a particular constraint property that has been extensively used
in the literature, namely, patchwork. As a consequence, we prove that a recently
proposed decomposition-based approach that was presented in the study by
Nikolaou and Koubarakis for checking the satisfiability of qualitative spatial
constraint networks lacks soundness. Therefore, the approach becomes quite
controversial as it does not seem to offer any technical advance at all, while
results of an experimental evaluation of it in a following work presented in the
study by Sioutis become questionable. Finally, we present a particular tree
decomposition that is based on the biconnected components of the constraint
graph of a given large network, and show that it allows for cost-free
utilization of parallelism for a qualitative constraint language that has
patchwork for satisfiable atomic networks.</description><identifier>ISSN: 0269-8889</identifier><identifier>EISSN: 1469-8005</identifier><identifier>DOI: 10.1017/S026988891600014X</identifier><language>eng</language><publisher>Cambridge, UK: Cambridge University Press</publisher><subject>Algebra ; Artificial Intelligence ; Computer Science ; Decomposition ; Language ; Temporal logic</subject><ispartof>Knowledge engineering review, 2017, Vol.32, Article e4</ispartof><rights>Cambridge University Press, 2017</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c351t-cc51af803828a16b16ab7b05bbf8f5c8d9c91a4c8157f893fc0d0beb44f794723</citedby><cites>FETCH-LOGICAL-c351t-cc51af803828a16b16ab7b05bbf8f5c8d9c91a4c8157f893fc0d0beb44f794723</cites><orcidid>0000-0001-7562-2443 ; 0000-0003-0100-4428 ; 0000-0002-7321-7855</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/1875087915?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>230,314,780,784,885,4024,11688,27923,27924,27925,36060,44363,72832</link.rule.ids><backlink>$$Uhttps://hal.science/hal-02067922$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Sioutis, Michael</creatorcontrib><creatorcontrib>Salhi, Yakoub</creatorcontrib><creatorcontrib>Condotta, Jean-François</creatorcontrib><title>Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning</title><title>Knowledge engineering review</title><addtitle>The Knowledge Engineering Review</addtitle><description>We survey the use and effect of decomposition-based techniques in qualitative
spatial and temporal constraint-based reasoning, and clarify the notions of a
tree decomposition, a chordal graph, and a partitioning graph, and their
implication with a particular constraint property that has been extensively used
in the literature, namely, patchwork. As a consequence, we prove that a recently
proposed decomposition-based approach that was presented in the study by
Nikolaou and Koubarakis for checking the satisfiability of qualitative spatial
constraint networks lacks soundness. Therefore, the approach becomes quite
controversial as it does not seem to offer any technical advance at all, while
results of an experimental evaluation of it in a following work presented in the
study by Sioutis become questionable. Finally, we present a particular tree
decomposition that is based on the biconnected components of the constraint
graph of a given large network, and show that it allows for cost-free
utilization of parallelism for a qualitative constraint language that has
patchwork for satisfiable atomic networks.</description><subject>Algebra</subject><subject>Artificial Intelligence</subject><subject>Computer Science</subject><subject>Decomposition</subject><subject>Language</subject><subject>Temporal logic</subject><issn>0269-8889</issn><issn>1469-8005</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kM1LAzEQxYMoWD_-AG8BTx5WZ_YzOUpRKxQ8VMHbms0mbaTdbJOs4H9v1hYRxNMw837vMTxCLhCuEbC6WUBacsYYxxIAMH89IBPMS54wgOKQTEY5GfVjcuL9e0QyhGxC3hZhaD9Nt6RhpejgFRVdS5XWSgZqNV060a9oq6Td9NabYGxHTUe3g1ibIIL5UNT3cYr1tzGoiLm4OCW87WLuGTnSYu3V-X6ekpf7u-fpLJk_PTxOb-eJzAoMiZQFCs0gYykTWDZYiqZqoGgazXQhWcslR5FLhkWlGc-0hBYa1eS5rnhepdkpudrlrsS67p3ZCPdZW2Hq2e28Hm-QQlnxNP3AyF7u2N7Z7aB8qN_t4Lr4Xo2sKoBVHItI4Y6SznrvlP6JRajH0us_pUdPtveITeNMu1S_ov91fQHQ_oQ_</recordid><startdate>2017</startdate><enddate>2017</enddate><creator>Sioutis, Michael</creator><creator>Salhi, Yakoub</creator><creator>Condotta, Jean-François</creator><general>Cambridge University Press</general><general>Cambridge University Press (CUP)</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7TB</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FR3</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>KR7</scope><scope>L.-</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>Q9U</scope><scope>1XC</scope><orcidid>https://orcid.org/0000-0001-7562-2443</orcidid><orcidid>https://orcid.org/0000-0003-0100-4428</orcidid><orcidid>https://orcid.org/0000-0002-7321-7855</orcidid></search><sort><creationdate>2017</creationdate><title>Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning</title><author>Sioutis, Michael ; Salhi, Yakoub ; Condotta, Jean-François</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c351t-cc51af803828a16b16ab7b05bbf8f5c8d9c91a4c8157f893fc0d0beb44f794723</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Algebra</topic><topic>Artificial Intelligence</topic><topic>Computer Science</topic><topic>Decomposition</topic><topic>Language</topic><topic>Temporal logic</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Sioutis, Michael</creatorcontrib><creatorcontrib>Salhi, Yakoub</creatorcontrib><creatorcontrib>Condotta, Jean-François</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical & Transportation Engineering Abstracts</collection><collection>ABI/INFORM Collection (ProQuest)</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies & Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Engineering Research Database</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>Civil Engineering Abstracts</collection><collection>ABI/INFORM Professional Advanced</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Global</collection><collection>Computing Database</collection><collection>Science Database (ProQuest)</collection><collection>ProQuest Advanced Technologies & Aerospace Database</collection><collection>ProQuest Advanced Technologies & Aerospace Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central Basic</collection><collection>Hyper Article en Ligne (HAL)</collection><jtitle>Knowledge engineering review</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Sioutis, Michael</au><au>Salhi, Yakoub</au><au>Condotta, Jean-François</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning</atitle><jtitle>Knowledge engineering review</jtitle><addtitle>The Knowledge Engineering Review</addtitle><date>2017</date><risdate>2017</risdate><volume>32</volume><artnum>e4</artnum><issn>0269-8889</issn><eissn>1469-8005</eissn><abstract>We survey the use and effect of decomposition-based techniques in qualitative
spatial and temporal constraint-based reasoning, and clarify the notions of a
tree decomposition, a chordal graph, and a partitioning graph, and their
implication with a particular constraint property that has been extensively used
in the literature, namely, patchwork. As a consequence, we prove that a recently
proposed decomposition-based approach that was presented in the study by
Nikolaou and Koubarakis for checking the satisfiability of qualitative spatial
constraint networks lacks soundness. Therefore, the approach becomes quite
controversial as it does not seem to offer any technical advance at all, while
results of an experimental evaluation of it in a following work presented in the
study by Sioutis become questionable. Finally, we present a particular tree
decomposition that is based on the biconnected components of the constraint
graph of a given large network, and show that it allows for cost-free
utilization of parallelism for a qualitative constraint language that has
patchwork for satisfiable atomic networks.</abstract><cop>Cambridge, UK</cop><pub>Cambridge University Press</pub><doi>10.1017/S026988891600014X</doi><tpages>24</tpages><orcidid>https://orcid.org/0000-0001-7562-2443</orcidid><orcidid>https://orcid.org/0000-0003-0100-4428</orcidid><orcidid>https://orcid.org/0000-0002-7321-7855</orcidid></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0269-8889 |
| ispartof | Knowledge engineering review, 2017, Vol.32, Article e4 |
| issn | 0269-8889 1469-8005 |
| language | eng |
| recordid | cdi_hal_primary_oai_HAL_hal_02067922v1 |
| source | ABI/INFORM Global; Cambridge University Press |
| subjects | Algebra Artificial Intelligence Computer Science Decomposition Language Temporal logic |
| title | Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T19%3A37%3A56IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_hal_p&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Studying%20the%20use%20and%20effect%20of%20graph%20decomposition%20in%20qualitative%20spatial%20and%20temporal%20reasoning&rft.jtitle=Knowledge%20engineering%20review&rft.au=Sioutis,%20Michael&rft.date=2017&rft.volume=32&rft.artnum=e4&rft.issn=0269-8889&rft.eissn=1469-8005&rft_id=info:doi/10.1017/S026988891600014X&rft_dat=%3Cproquest_hal_p%3E4319594071%3C/proquest_hal_p%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c351t-cc51af803828a16b16ab7b05bbf8f5c8d9c91a4c8157f893fc0d0beb44f794723%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1875087915&rft_id=info:pmid/&rft_cupid=10_1017_S026988891600014X&rfr_iscdi=true |