Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-19T02:08:39.307Z Has data issue: false hasContentIssue false
  • English
  • Français

Concurrent goal-based execution of Constraint Handling Rules

Published online by Cambridge University Press:  29 July 2010

EDMUND S. L. LAM  and
MARTIN SULZMANN
EDMUND S. L. LAM
Affiliation:
School of Computing, National University of Singapore, S16 Level 5, 3 Science Drive 2, Singapore 117543 (e-mail: [email protected])
MARTIN SULZMANN
Affiliation:
Informatik Consulting Systems AG, Sonnenbergstr. 13, 70184 Stuttgart, Germany (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce a systematic, concurrent execution scheme for Constraint Handling Rules (CHR) based on a previously proposed sequential goal-based CHR semantics. We establish strong correspondence results to the abstract CHR semantics, thus guaranteeing that any answer in the concurrent, goal-based CHR semantics is reproducible in the abstract CHR semantics. Our work provides the foundation to obtain efficient, parallel CHR execution schemes.

Keywords

multiset rewritingconstraintsconcurrency
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Issue 6 , November 2011 , pp. 841 - 879
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abdennadher, S. 1997. Operational semantics and confluence of constraint propagation rules. In Proceedings of CP'97, Smolka, G., Ed. Lecture Notes in Computer Science, vol. 1330. Springer-Verlag, 252–266.Google Scholar
Abdennadher, S., Fruhwirth, T. W. and Meuss, H. 1999. Confluence and semantics of constraint simplification rules. Constraints 4 (2), 133–165.CrossRefGoogle Scholar
Betz, H., Raiser, F. and Frühwirth, T. 2009. Persistent constraints in Constraint Handling Rules. In WLP '09: Proceedings of the 23rd Workshop on (Constraint) Logic Programming (in press).Google Scholar
De Koninck, L., Stuckey, P. and Duck, G. 2008. Optimizing compilation of CHR with rule priorities. In Proceedings of FLOPS'08. Lecture Notes in Computer Science, vol. 4989. Springer-Verlag, 32–47.Google Scholar
Miranker, D. P., Brant, D., Lofaso, B. and Gadbois, D. 1990. On the performance of lazy matching in production systems. In In Proceedings of International Conference on Artificial Intelligence AAAI. 685–692.Google Scholar
Duck, G. J. 2005. Compilation of Constraint Handling Rules. PhD thesis, The University of Melbourne.Google Scholar
Duck, G. J., Stuckey, P. J., de la Banda, M. J. G. and Holzbaur, C. 2004. The refined operational semantics of Constraint Handling Rules. In Proceedings of ICLP'04. Lecture Notes in Computer Science, vol. 3132. Springer-Verlag, 90–104.Google Scholar
Forgy, C. 1982. Rete: A fast algorithm for the many patterns/many objects match problem. Artificial Intelligence 19, 1, 17–37.CrossRefGoogle Scholar
Forgy, C. and McDermott, J. P. 1977. Ops, a domain-independent production system language. In IJCAI. 933–939.Google Scholar
Frühwirth, T. 1998. Theory and practice of constraint handling rules. Journal of Logic Programming, Special Issue on Constraint Logic Programming 37, 1–3, 95–138.CrossRefGoogle Scholar
Frühwirth, T. 2005. Parallelizing union-find in Constraint Handling Rules using confluence analysis. In Proceedings of ICLP'05. Lecture Notes in Computer Science, vol. 3668. Springer-Verlag, 113–127.Google Scholar
Frühwirth, T. 2006. Constraint handling rules: the story so far. In Proceedings of PPDP '06. ACM Press, 13–14.CrossRefGoogle Scholar
Gamble, R. F. 1990. Transforming rule-based programs: from the sequential to the parallel. In IEA/AIE '90: Proceedings of the 3rd international conference on Industrial and engineering applications of artificial intelligence and expert systems. ACM, New York, NY, 854–863.CrossRefGoogle Scholar
Gupta, A., Forgy, C., Kalp, D., Newell, A., and Tambe, M. 1988. Parallel ops5 on the encore multimax. In ICPP (1). 71–280.Google Scholar
Ishida, T. 1991. Parallel rule firing in production systems. IEEE Transactions on Knowledge and Data Engineering 3, 1, 11–17.CrossRefGoogle Scholar
Lam, E. S. L. and Sulzmann, M. 2007. A concurrent Constraint Handling Rules implementation in Haskell with software transactional memory. In Proc. of ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming (DAMP'07). 19–24.CrossRefGoogle Scholar
Mahajan, M. and Kumar, V. K. P. 1990. Efficient parallel implementation of rete pattern matching. Computer Systems: Science & Engineering 5, 3, 187–192.Google Scholar
Miranker, D. P. 1990. TREAT: A New and Efficient Match Algorithm for AI Production Systems. Morgan Kaufmann Publishers Inc., San Francisco, CA.Google Scholar
Miranker, D. P., Kuo, C. and Browne, J. C. 1989. Parallelizing Transformations for a Concurrent Rule Execution Language. Tech. Rep.: CS-TR-89-30, University of Texas, Austin, TX.Google Scholar
Neiman, D. E. 1991. Control issues in parallel rule-firing production systems. In Proceedings of National Conference on Artificial Intelligence. AAAI Press, 310–316.Google Scholar
Sarna-Starosta, B. and Ramakrishnan, C. R. 2007. Compiling constraint handling rules for efficient tabled evaluation. In Proc. of PADL'07. Lecture Notes in Computer Science, vol. 4354. Springer, 170–184.Google Scholar
Schrijvers, T. 2005. Analyses, optimizations and extensions of Constraint Handling Rules: PhD summary. In Proc. of ICLP'05. Lecture Notes in Computer Science, vol. 3668. Springer-Verlag, 435–436.Google Scholar
Schrijvers, T. and Sulzmann, M. 2008. Transactions in constraint handling rules. In Proc. of ICLP'08. Lecture Notes in Computer Science, vol. 5366. Springer, 516–530.Google Scholar
Sneyers, J., Schrijvers, T. and Demoen, B. 2005. Guard and continuation optimization for occurrence representations of CHR. In Proceedings of ICLP'05. Lecture Notes in Computer Science, vol. 3668. Springer-Verlag, 83–97.Google Scholar
Sneyers, J., Van Weert, P., Schrijvers, T. and De Koninck, L. 2010. As time goes by: Constraint handling rules - a survey of CHR research from 1998 to 2007. Theory and Practice of Logic Programming 10 (1), 1–47.CrossRefGoogle Scholar
Sulzmann, M. and Lam, E. S. L. 2008. Parallel execution of multi-set constraint rewrite rules. In Proc. of PPDP'08. ACM Press, 20–31.CrossRefGoogle Scholar