Asian Science Citation Index is committed to provide an authoritative, trusted and significant information by the coverage of the most important and influential journals to meet the needs of the global scientific community.  
ASCI Database
308-Lasani Town,
Sargodha Road,
Faisalabad, Pakistan
Fax: +92-41-8815544
Contact Via Web
Suggest a Journal
 
Articles by M Bodirsky
Total Records ( 1 ) for M Bodirsky
  M Bodirsky and H. Chen
 

Establishing local consistency is one of the main algorithmic techniques in temporal and spatial reasoning. Acentral question for the various proposed temporal and spatial constraint languages is whether local consistency implies global consistency. Showing that a constraint language has this ‘local-to-global’ property implies polynomial-time tractability of the constraint language, and has further pleasant algorithmic consequences. In the present article, we study the ‘local-to-global’ property by making use of a recently established connection of this property with universal algebra. Roughly speaking, the connection shows that this property is equivalent to the presence of a so-called quasi near-unanimity (QNU) polymorphism of the constraint language. We obtain new algorithmic results and give very concise proofs of previously known theorems. Our results concern well-known and heavily studied formalisms such as the point algebra, Allen's interval algebra and the spatial reasoning language RCC-5.

 
 
 
Copyright   |   Desclaimer   |    Privacy Policy   |   Browsers   |   Accessibility