-
Slim Abdennadher,
Abdellatif Olama,
Noha Salem,
and Amira Thabet.
ARM: Automatic Rule Miner.
In LOPSTR '06, Revised Selected Papers,
volume 4407 of Lecture Notes in Computer Science,
July 2006.
Springer-Verlag.
Keyword(s): program generation.
@inproceedings{abd_et_al_arm_lopstr06,
author = {Slim Abdennadher and Abdellatif Olama and Noha Salem and Amira Thabet},
title = {{ARM}: {A}utomatic {R}ule {M}iner},
keywords = {program generation},
booktitle = LOPSTR06,
location = {Venice, Italy},
city = {Venice, Italy},
year = 2006,
month = jul,
publisher = SV,
series = LNCS,
volume = 4407,
}
-
Dulce Aguilar-Solis.
Learning Semantic Parsers: A Constraint Handling Rule Approach.
In S. Etalle and M. Truszczynski, editors,
ICLP '06: Proc. 22nd Intl. Conf. Logic Programming,
volume 4079 of Lecture Notes in Computer Science,
pages 447-448,
August 2006.
Springer-Verlag.
Note: Poster Paper.
[doi:10.1007/11799573_42]
Keyword(s): applications,
linguistics.
Abstract: |
Semantic parsing is the process of mapping a natural language input into some structure representing its meaning. Even though this process is natural and smooth for human beings, it constitutes a huge problem for a machine. Semantic parsing is a challenging and interesting problem that has been severely understudied. Most of the research in natural language understanding has focused on shallow semantic analysis (i.e. word sense disambiguation, case-role analysis, etc). Previous approaches to semantic parsing are not robust enough or are limited in its applicability because they are applied to simple domains where semantic parsing reduces to filling slots on a frame. |
@inproceedings{aguilar_solis_semantic_parsing_iclp06,
author = {Dulce Aguilar-Solis},
title = {Learning Semantic Parsers: A {C}onstraint {H}andling {R}ule Approach},
crossref = {piclp06},
pages = {447--448},
note = {Poster Paper},
keywords = {applications, linguistics},
abstract = { Semantic parsing is the process of mapping a natural language input into some structure representing its meaning. Even though this process is natural and smooth for human beings, it constitutes a huge problem for a machine. Semantic parsing is a challenging and interesting problem that has been severely understudied. Most of the research in natural language understanding has focused on shallow semantic analysis (i.e. word sense disambiguation, case-role analysis, etc). Previous approaches to semantic parsing are not robust enough or are limited in its applicability because they are applied to simple domains where semantic parsing reduces to filling slots on a frame. },
doi = {10.1007/11799573_42},
}
-
Susan E. Brennan,
Klaus Mueller,
Greg Zelinsky,
IV Ramakrishnan,
David S. Warren,
and Arie Kaufman.
Toward a Multi-Analyst, Collaborative Framework for Visual Analytics.
In 2006 IEEE Symposium On Visual Analytics Science And Technology,
October-November 2006.
@inproceedings{brennan_visual_analytics_06,
title = {Toward a Multi-Analyst, Collaborative Framework for Visual Analytics},
author = {Susan E. Brennan and Klaus Mueller and Greg Zelinsky and IV Ramakrishnan and David S. Warren and Arie Kaufman},
booktitle = {2006 IEEE Symposium On Visual Analytics Science And Technology},
month = {October-November},
year = {2006},
location = {Baltimore, MD, USA}
}
-
Henning Christiansen.
On the Implementation of Global Abduction.
In Katsumi Inoue,
Ken Satoh,
and Francesca Toni, editors,
CLIMA '06: 7th Intl. Workshop on Computational Logic in Multi-Agent Systems – Revised, Selected and Invited Papers,
volume 4371 of Lecture Notes in Computer Science,
pages 226-245,
May 2006.
Springer-Verlag.
Keyword(s): abduction.
@inproceedings{christiansen_clima06,
author = {Henning Christiansen},
title = {On the Implementation of Global Abduction},
year = {2006},
pages = {226--245},
editor = {Katsumi Inoue and Ken Satoh and Francesca Toni},
keywords = {abduction},
booktitle = {CLIMA '06: 7th Intl.\ Workshop on Computational Logic in Multi-Agent Systems -- Revised, Selected and Invited Papers},
location = {Hakodate, Japan},
city = {Hakodate, Japan},
month = may,
publisher = SV,
series = LNCS,
volume = 4371,
}
-
Verónica Dahl and Baohua Gu.
Semantic Property Grammars for Knowledge Extraction from Biomedical Text.
In S. Etalle and M. Truszczynski, editors,
ICLP '06: Proc. 22nd Intl. Conf. Logic Programming,
volume 4079 of Lecture Notes in Computer Science,
pages 442-443,
August 2006.
Springer-Verlag.
Note: Poster Paper.
[doi:10.1007/11799573_40]
Keyword(s): applications,
linguistics.
Abstract: |
We present \emph{Semantic Property Grammars}, designed to extract concepts and relations from biomedical texts. The implementation adapts a CHRG parser we designed for Property Grammars, which views linguistic constraints as properties between sets of categories and solves them by constraint satisfaction, can handle incomplete or erroneous text, and extract phrases of interest selectively. We endow it with concept and relation extraction abilities as well. |
@inproceedings{dahl_gu_property_gram_biomed_iclp06,
author = {Ver{\'o}nica Dahl and Baohua Gu},
title = {Semantic Property Grammars for Knowledge Extraction from Biomedical Text},
crossref = {piclp06},
pages = {442--443},
note = {Poster Paper},
doi = {10.1007/11799573_40},
keywords = {applications, linguistics},
abstract = { We present \emph{Semantic Property Grammars}, designed to extract concepts and relations from biomedical texts. The implementation adapts a CHRG parser we designed for Property Grammars, which views linguistic constraints as properties between sets of categories and solves them by constraint satisfaction, can handle incomplete or erroneous text, and extract phrases of interest selectively. We endow it with concept and relation extraction abilities as well. },
}
-
Leslie De Koninck,
Tom Schrijvers,
and Bart Demoen.
INCLP(ℝ) - Interval-based nonlinear constraint logic programming over the reals.
In M. Fink,
H. Tompits,
and S. Woltran, editors,
WLP '06: Proc. 20th Workshop on Logic Programming,
T.U.Wien, Austria, INFSYS Research report 1843-06-02,
pages 91-100,
February 2006.
Keyword(s): applications.
@inproceedings{dekoninck_schr_demoen_inclpr_wlp06,
author = {De Koninck, Leslie and Schrijvers, Tom and Demoen, Bart},
title = {{INCLP($\mathbb{R}$)} - {I}nterval-based nonlinear constraint logic programming over the reals},
keywords = {applications},
pages = {91--100},
crossref = {pwlp06}
}
-
Leslie De Koninck,
Tom Schrijvers,
and Bart Demoen.
Search strategies in CHR(Prolog).
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 109-124,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
[POSTSCRIPT]
Keyword(s): CHR 2006,
disjunction,
CHR 2006,
CHR 2006.
Abstract: |
We extend the refined operational semantics of Constraint Handling Rules to support the implementation of different search strategies. Such search strategies are necessary to build efficient Constraint Logic Programming systems. This semantics is then further refined so that it is more suitable as a basis for a trailing based implementation. We propose a source to source transformation to implement breadth first search in CHR(Prolog): CHR with Prolog as a host language. Breadth first search is chosen because it exhibits the main difficulties in the implementation of search strategies, while being easy to understand. We evaluate our implementation and give directions for future work. |
@inproceedings{dekoninck_schr_demoen_search_chr06,
author = {De Koninck, Leslie and Schrijvers, Tom and Demoen, Bart},
title = {Search strategies in {CHR(Prolog)}},
pages = {109--124},
crossref = {pchr06},
abstract = { We extend the refined operational semantics of Constraint Handling Rules to support the implementation of different search strategies. Such search strategies are necessary to build efficient Constraint Logic Programming systems. This semantics is then further refined so that it is more suitable as a basis for a trailing based implementation. We propose a source to source transformation to implement breadth first search in CHR(Prolog): CHR with Prolog as a host language. Breadth first search is chosen because it exhibits the main difficulties in the implementation of search strategies, while being easy to understand. We evaluate our implementation and give directions for future work. },
keywords = {CHR 2006, disjunction},
ps = PAPERSHOME # {chr2006/dekoninck_schr_demoen_search_chr06.ps},
}
-
Gregory J. Duck,
Peter J. Stuckey,
and Sebastian Brand.
ACD Term Rewriting.
In S. Etalle and M. Truszczynski, editors,
ICLP '06: Proc. 22nd Intl. Conf. Logic Programming,
volume 4079 of Lecture Notes in Computer Science,
pages 117-131,
August 2006.
Springer-Verlag.
[doi:10.1007/11799573_11]
Keyword(s): related formalisms.
Abstract: |
In this paper we introduce Associative Commutative Distributive Term Rewriting (ACDTR), a rewriting language for rewriting logical formulae. ACDTR extends AC term rewriting by adding distribution of conjunction over other operators. Conjunction is vital for expressive term rewriting systems since it allows us to require that multiple conditions hold for a term rewriting rule to be used. ACDTR uses the notion of a ``conjunctive context'', which is the conjunction of constraints that must hold in the context of a term, to enable the programmer to write very expressive and targeted rewriting rules. ACDTR can be seen as a general logic programming language that extends Constraint Handling Rules and AC term rewriting. In this paper we define the semantics of ACDTR and describe our prototype implementation. |
@inproceedings{duck_stuck_brand_acd_term_rewriting_iclp06,
author = {Gregory J. Duck and Peter J. Stuckey and Sebastian Brand},
title = {{ACD} Term Rewriting},
pages = {117--131},
crossref = {piclp06},
keywords = {related formalisms},
doi = {10.1007/11799573_11},
abstract = { In this paper we introduce Associative Commutative Distributive Term Rewriting (ACDTR), a rewriting language for rewriting logical formulae. ACDTR extends AC term rewriting by adding distribution of conjunction over other operators. Conjunction is vital for expressive term rewriting systems since it allows us to require that multiple conditions hold for a term rewriting rule to be used. ACDTR uses the notion of a ``conjunctive context'', which is the conjunction of constraints that must hold in the context of a term, to enable the programmer to write very expressive and targeted rewriting rules. ACDTR can be seen as a general logic programming language that extends Constraint Handling Rules and AC term rewriting. In this paper we define the semantics of ACDTR and describe our prototype implementation. },
}
-
Gregory J. Duck,
Peter J. Stuckey,
and Martin Sulzmann.
Observable Confluence for Constraint Handling Rules.
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 61-76,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
[POSTSCRIPT]
Keyword(s): CHR 2006,
confluence,
CHR 2006,
CHR 2006.
Abstract: |
Constraint Handling Rules (CHRs) are a powerful rule based language for specifying constraint solvers. Critical for any rule based language is the notion of confluence, and for terminating CHRs there is a decidable test for confluence. But many CHR programs that in practice are confluent fail this confluence test. The problem is that the states that illustrate non-confluence are not reachable in practice. In this paper we introduce the notion of observable confluence, a weaker notion of confluence which takes into account whether states are observable. We show for an important class of non-confluent programs arising from Haskell type class programs with functional dependencies, that they are observable confluent. |
@inproceedings{duck_stuckey_sulzmann_observable_confl_chr06,
author = {Gregory J. Duck and Peter J. Stuckey and Martin Sulzmann},
title = {Observable Confluence for {C}onstraint {H}andling {R}ules},
pages = {61--76},
crossref = {pchr06},
abstract = { Constraint Handling Rules (CHRs) are a powerful rule based language for specifying constraint solvers. Critical for any rule based language is the notion of confluence, and for terminating CHRs there is a decidable test for confluence. But many CHR programs that in practice are confluent fail this confluence test. The problem is that the states that illustrate non-confluence are not reachable in practice. In this paper we introduce the notion of observable confluence, a weaker notion of confluence which takes into account whether states are observable. We show for an important class of non-confluent programs arising from Haskell type class programs with functional dependencies, that they are observable confluent. },
keywords = {CHR 2006, confluence},
ps = PAPERSHOME # {chr2006/duck_stuckey_sulzmann_observable_confl_chr06.ps},
}
-
Thom Frühwirth.
Complete Propagation Rules for Lexicographic Order Constraints over Arbitrary Domains.
In Recent Advances in Constraints — CSCLP '05: Joint ERCIM/CoLogNET Intl. Workshop on Constraint Solving and CLP, Revised Selected and Invited Papers,
volume 3978 of Lecture Notes in Artificial Intelligence,
2006.
Springer-Verlag.
@inproceedings{fru_lexico_csclp05:06,
author = {Thom Fr{\"u}hwirth},
title = {Complete Propagation Rules for Lexicographic Order Constraints over Arbitrary Domains},
booktitle = {Recent Advances in Constraints --- CSCLP '05: Joint ERCIM/CoLogNET Intl.\ Workshop on Constraint Solving and CLP, Revised Selected and Invited Papers},
year = 2006,
location = {Uppsala, Sweden},
city = {Uppsala, Sweden},
series = LNAI,
volume = 3978,
publisher = SV,
}
-
Thom Frühwirth.
Constraint Handling Rules: the story so far.
In A. Bossi and M.J. Maher, editors,
PPDP '06: Proc. 8th Intl. Conf. Princ. Pract. Declarative Programming,
pages 13-14,
July 2006.
ACM Press.
ISBN: 1-59593-388-3.
Keyword(s): tutorial.
@inproceedings{fru_chr_story_so_far_ppdp06,
author = {Thom Fr{\"u}hwirth},
title = {{C}onstraint {H}andling {R}ules: the story so far},
pages = {13--14},
keywords = {tutorial},
crossref = {pppdp06}
}
-
Thom Frühwirth.
Deriving Linear-Time Algorithms from Union-Find in CHR.
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 49-60,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
[POSTSCRIPT]
Keyword(s): CHR 2006,
algorithms,
CHR 2006,
CHR 2006.
Abstract: |
The union-find algorithm can be seen as solving simple equations between variables or constants. With a few lines of code change, we generalise its implementation in CHR from equality to arbitrary binary relations. By choosing the appropriate relations, we can derive fast algorithms for solving certain propositional logic (SAT) problems as well as certain polynomial equations in two variables. While linear-time algorithms are known to check satisfiability and to exhibit certain solutions of these problems, our algorithms are simple instances of the generic algorithm and have additional properties that make them suitable for incorporation into constraint solvers: From classical union-find, they inherit simplicity and quasi-linear time and space. By nature of CHR, they are anytime and online algorithms. They can be parallelised. They solve and simplify the constraints in the problem, and can test them for entailment, even when the constraints arrive incrementally, one after the other. We show that instances where relations are bijective functions yield precise and correct algorithm instances of our generalised union-find. |
@inproceedings{fru_deriving_linear_algorithms_from_uf_chr06,
author = {Thom Fr{\"u}hwirth},
title = {Deriving Linear-Time Algorithms from Union-Find in {CHR}},
pages = {49--60},
crossref = {pchr06},
abstract = { The union-find algorithm can be seen as solving simple equations between variables or constants. With a few lines of code change, we generalise its implementation in CHR from equality to arbitrary binary relations. By choosing the appropriate relations, we can derive fast algorithms for solving certain propositional logic (SAT) problems as well as certain polynomial equations in two variables. While linear-time algorithms are known to check satisfiability and to exhibit certain solutions of these problems, our algorithms are simple instances of the generic algorithm and have additional properties that make them suitable for incorporation into constraint solvers: From classical union-find, they inherit simplicity and quasi-linear time and space. By nature of CHR, they are anytime and online algorithms. They can be parallelised. They solve and simplify the constraints in the problem, and can test them for entailment, even when the constraints arrive incrementally, one after the other. We show that instances where relations are bijective functions yield precise and correct algorithm instances of our generalised union-find. },
keywords = {CHR 2006, algorithms},
ps = PAPERSHOME # {chr2006/fru_deriving_linear_algorithms_from_uf_chr06.ps},
}
-
Maurizio Gabbrielli,
Maria Chiara Meo,
and Paolo Tacchella.
A compositional Semantics for CHR with propagation rules.
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 93-107,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
[POSTSCRIPT]
Keyword(s): CHR 2006,
semantics,
CHR 2006,
CHR 2006.
@inproceedings{gabbrielli_meo_tacchella_compositional_semantics_chr06,
author = {Maurizio Gabbrielli and Maria Chiara Meo and Paolo Tacchella},
title = {A compositional Semantics for {CHR} with propagation rules},
pages = {93--107},
crossref = {pchr06},
abstract = {
},
keywords = {CHR 2006, semantics},
ps = PAPERSHOME # {chr2006/gabbrielli_meo_tacchella_compositional_semantics_chr06.ps},
}
-
Sandrine-Dominique Gouraud and Arnaud Gotlieb.
Using CHRs to Generate Functional Test Cases for the Java Card Virtual Machine.
In P. Van Hentenryck, editor,
PADL '06: Proc. 8th Intl. Symp. Practical Aspects of Declarative Languages,
volume 3819 of Lecture Notes in Computer Science,
pages 1-15,
January 2006.
Springer-Verlag.
[doi:10.1007/11603023_1]
Keyword(s): applications,
testing.
@inproceedings{gouraud_gotlieb_javacard_padl06,
author = {Sandrine-Dominique Gouraud and Arnaud Gotlieb},
title = {Using {CHR}s to Generate Functional Test Cases for the {J}ava Card Virtual Machine},
keywords = {applications, testing},
booktitle = {PADL '06: Proc.\ 8th Intl.\ Symp.\ Practical Aspects of Declarative Languages},
year = {2006},
pages = {1--15},
editor = {P. {Van Hentenryck}},
publisher = SV,
series = LNCS,
volume = 3819,
location = {Charleston, SC, USA},
city = {Charleston, SC, USA},
month = jan,
doi = {10.1007/11603023_1},
}
-
Michael Hanus.
Adding Constraint Handling Rules to Curry.
In M. Fink,
H. Tompits,
and S. Woltran, editors,
WLP '06: Proc. 20th Workshop on Logic Programming,
T.U.Wien, Austria, INFSYS Research report 1843-06-02,
pages 81-90,
February 2006.
Keyword(s): implementation.
@INPROCEEDINGS{hanus_chr_curry_wlp06,
author = {Michael Hanus},
title = {Adding {C}onstraint {H}andling {R}ules to {Curry}},
keywords = {implementation},
pages = {81--90},
crossref = {pwlp06}
}
-
Martin Kaeser and Marc Meister.
Implementation of an F-Logic Kernel in CHR.
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 33-47,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
[PDF]
Keyword(s): CHR 2006,
CHR 2006,
CHR 2006.
Abstract: |
Constraint Handling Rules (CHR) is a concurrent, committed- choice, rule-based language, rewriting constraints in relational syntax. Frame-Logic is an extension of classical predicate logic which accounts in a declarative way for many features of object-orientation. This exploratory paper gives a concise CHR implementation of Frame-Logic's core features, including object-oriented constraint syntax, type-checking, and interaction of Frame-Logic deduction with non-monotonic overriding by inheritance. |
@inproceedings{kaeser_meister_flogic_chr06,
author = {Martin Kaeser and Marc Meister},
title = {Implementation of an {F-Logic} Kernel in {CHR}},
pages = {33--47},
crossref = {pchr06},
abstract = { Constraint Handling Rules (CHR) is a concurrent, committed- choice, rule-based language, rewriting constraints in relational syntax. Frame-Logic is an extension of classical predicate logic which accounts in a declarative way for many features of object-orientation. This exploratory paper gives a concise CHR implementation of Frame-Logic's core features, including object-oriented constraint syntax, type-checking, and interaction of Frame-Logic deduction with non-monotonic overriding by inheritance. },
keywords = {CHR 2006},
pdf = PAPERSHOME # {chr2006/kaeser_meister_flogic_chr06.pdf},
}
-
Nikolai Kosmatov.
A constraint solver for sequences and its applications.
In Proc. 2006 ACM Symp. on Applied Computing,
pages 404-408,
2006.
ACM Press.
@inproceedings{kosmatov_sequences_06,
author = {Nikolai Kosmatov},
title = {A constraint solver for sequences and its applications},
booktitle = {Proc.\ 2006 ACM Symp.\ on Applied Computing},
pages = {404--408},
year = 2006,
location = {Dijon, France},
city = {Dijon, France},
publisher = ACM,
}
-
Nikolai Kosmatov.
Constraint Solving for Sequences in Software Validation and Verification.
In INAP '05: Proc. 16th Intl. Conf. Applications of Declarative Programming and Knowledge Management,
volume 4369 of Lecture Notes in Computer Science,
pages 25-37,
2006.
Springer-Verlag.
@inproceedings{kosmatov_sequences_inap05,
author = {Nikolai Kosmatov},
title = {Constraint Solving for Sequences in Software Validation and Verification},
booktitle = {INAP '05: Proc.\ 16th Intl.\ Conf.\ Applications of Declarative Programming and Knowledge Management},
location = {Fukuoka, Japan},
city = {Fukuoka, Japan},
year = 2006,
pages = {25--37},
series= LNCS,
volume = 4369,
publisher = SV,
}
-
Edmund S.L. Lam and Martin Sulzmann.
Towards Agent Programming in CHR.
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 17-31,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
[PDF]
Keyword(s): linear logic,
CHR 2006,
CHR 2006,
CHR 2006.
Abstract: |
We investigate an approach to the design and implementation of linear logic based agent systems via the linear logic semantics of Constraint Handling Rules (CHR). The intuition behind our approach is simple: Linear logic provides strong logical foundations to reason, verify and specify agent systems beyond the limitations of classical logics, while with CHR, one can implement and analyse agent systems in a concise and compact manner by executable inference rules. We discuss necessary refinements of the CHR semantics to allow for sequential computations of actions and the verification of action determinism. Our approach can possibly provide a seemless integration of the formal specification and implementation of agent programs via CHRs. |
@inproceedings{lam_sulz_linear_logic_agents_chr06,
author = {Edmund S.L. Lam and Martin Sulzmann},
title = {Towards Agent Programming in {CHR}},
pages = {17--31},
crossref = {pchr06},
abstract = {We investigate an approach to the design and implementation of linear logic based agent systems via the linear logic semantics of Constraint Handling Rules (CHR). The intuition behind our approach is simple: Linear logic provides strong logical foundations to reason, verify and specify agent systems beyond the limitations of classical logics, while with CHR, one can implement and analyse agent systems in a concise and compact manner by executable inference rules. We discuss necessary refinements of the CHR semantics to allow for sequential computations of actions and the verification of action determinism. Our approach can possibly provide a seemless integration of the formal specification and implementation of agent programs via CHRs.},
keywords = {linear logic},
keywords = {CHR 2006},
pdf = PAPERSHOME # {chr2006/lam_sulz_linear_logic_agents_chr06.pdf},
}
-
Marc Meister.
Fine-grained Parallel Implementation of the Preflow-Push Algorithm in CHR.
In M. Fink,
H. Tompits,
and S. Woltran, editors,
WLP '06: Proc. 20th Workshop on Logic Programming,
T.U.Wien, Austria, INFSYS Research report 1843-06-02,
pages 172-181,
February 2006.
Keyword(s): algorithms,
parallelism.
@InProceedings{meister_preflow_push_wlp06,
title = "Fine-grained Parallel Implementation of the Preflow-Push Algorithm in {CHR}",
author = "Marc Meister",
pages = "172--181",
keywords = {algorithms, parallelism},
crossref = {pwlp06}
}
-
Marc Meister,
Khalil Djelloul,
and Thom Frühwirth.
Complexity of a CHR Solver for Existentially Quantified Conjunctions of Equations over Trees.
In F. Azevedo and others, editors,
CSCLP '06: Proc. 11th Annual ERCIM Workshop on Constraint Solving and Constraint Programming,
volume 4651 of Lecture Notes in Computer Science,
pages 139-153,
June 2006.
Springer-Verlag.
ISBN: 978-3-540-73816-9.
[doi:10.1007/978-3-540-73817-6_9]
Keyword(s): complexity,
algorithms.
@InProceedings{meister_djelloul_fru_compl_tree_equations_csclp06,
title = "Complexity of a {CHR} Solver for Existentially Quantified Conjunctions of Equations over Trees",
author = "Marc Meister and Khalil Djelloul and Thom Fr{\"u}hwirth",
publisher = SV,
year = "2006",
volume = "4651",
keywords = {complexity, algorithms},
booktitle = "CSCLP '06: Proc.\ 11th Annual ERCIM Workshop on Constraint Solving and Constraint Programming",
location = {Caparica, Portugal},
city = {Caparica, Portugal},
month = jun,
editor = "F. Azevedo and others",
ISBN = "978-3-540-73816-9",
pages = "139--153",
series = LNCS,
doi = "10.1007/978-3-540-73817-6_9",
}
-
Marc Meister and Thom Frühwirth.
Complexity of the CHR Rational Tree Equation Solver.
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 77-91,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
[POSTSCRIPT]
Keyword(s): CHR 2006,
complexity,
algorithms,
CHR 2006,
CHR 2006.
Abstract: |
Constraint Handling Rules (CHR) is a concurrent, committed- choice, rule-based language. One of the first CHR programs is the classic constraint solver for syntactic equality of rational trees that performs unification. The worst-case time (and space) complexity of this short and elegant solver so far was an open problem and assumed to be polynomial. In this paper we show that under the standard operational semantics of CHR there exist particular computations with n occurrences of variables and function symbols that produce O(2n) constraints, thus leading to exponential time and space complexity. We also show that the standard implementation of the solver in CHR libraries for Prolog may not terminate due to the Prolog built-in order used in comparing terms. Complexity can be improved to be quadratic for any term order under both standard and refined CHR semantics without changing the equation solver, when equations are transformed into that normal form. |
@inproceedings{meister_fru_compl_rational_tree_chr06,
author = {Marc Meister and Thom Fr{\"u}hwirth},
title = {Complexity of the {CHR} Rational Tree Equation Solver},
pages = {77--91},
crossref = {pchr06},
abstract = { Constraint Handling Rules (CHR) is a concurrent, committed- choice, rule-based language. One of the first CHR programs is the classic constraint solver for syntactic equality of rational trees that performs unification. The worst-case time (and space) complexity of this short and elegant solver so far was an open problem and assumed to be polynomial. In this paper we show that under the standard operational semantics of CHR there exist particular computations with n occurrences of variables and function symbols that produce O(2n) constraints, thus leading to exponential time and space complexity. We also show that the standard implementation of the solver in CHR libraries for Prolog may not terminate due to the Prolog built-in order used in comparing terms. Complexity can be improved to be quadratic for any term order under both standard and refined CHR semantics without changing the equation solver, when equations are transformed into that normal form. },
keywords = {CHR 2006, complexity, algorithms},
ps = PAPERSHOME # {chr2006/meister_fru_compl_rational_tree_chr06.ps},
}
-
Jacques Robin and Jairson Vitorino.
ORCAS: Towards a CHR-Based Model-Driven Framework of Reusable Reasoning Components.
In M. Fink,
H. Tompits,
and S. Woltran, editors,
WLP '06: Proc. 20th Workshop on Logic Programming,
T.U.Wien, Austria, INFSYS Research report 1843-06-02,
pages 192-199,
February 2006.
@inproceedings{robin_vitorino_orcas_wlp06,
author = {Jacques Robin and Jairson Vitorino},
title = {{ORCAS}: Towards a {CHR}-Based Model-Driven Framework of Reusable Reasoning Components},
pages = {192--199},
crossref = {pwlp06}
}
-
Tom Schrijvers and Maurice Bruynooghe.
Polymorphic algebraic data type reconstruction.
In A. Bossi and M.J. Maher, editors,
PPDP '06: Proc. 8th Intl. Conf. Princ. Pract. Declarative Programming,
pages 85-96,
July 2006.
ACM Press.
ISBN: 1-59593-388-3.
Keyword(s): type systems.
@inproceedings{schr_bruynooghe_polymorphic_type_reconstruction_ppdp06,
author = {Tom Schrijvers and Maurice Bruynooghe},
title = {Polymorphic algebraic data type reconstruction},
keywords = {type systems},
pages = {85--96},
crossref = {pppdp06}
}
-
Tom Schrijvers,
Bart Demoen,
Gregory J. Duck,
Peter J. Stuckey,
and Thom Frühwirth.
Automatic implication checking for CHR constraints.
In RULE '05: 6th Intl. Workshop on Rule-Based Programming,
volume 147(1) of Electronic Notes in Theoretical Computer Science,
pages 93-111,
January 2006.
Elsevier.
@inproceedings{schr_demoen_duck_stuck_fru_implication_checking_entcs06,
author = {Tom Schrijvers and Bart Demoen and Gregory J. Duck and Peter J. Stuckey and Thom Fr{\"u}hwirth},
title ={Automatic implication checking for {CHR} constraints},
year = 2006,
month = jan,
pages = {93--111},
booktitle = {RULE '05: 6th Intl.\ Workshop on Rule-Based Programming},
location = {Nara, Japan},
city = {Nara, Japan},
series = ENTCS,
volume = {147(1)},
publisher = Elsevier,
}
-
Tom Schrijvers,
Neng-Fa Zhou,
and Bart Demoen.
Translating Constraint Handling Rules into Action Rules.
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 141-155,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
[POSTSCRIPT]
Keyword(s): CHR 2006,
implementation,
related formalisms,
CHR 2006,
CHR 2006.
Abstract: |
CHR is a popular high-level language for implementing constraint solvers and other general purpose applications. It has a well-established operational semantics and quite a number of different implementations, prominently in Prolog. However, there is still much room for exploring the compilation of CHR to Prolog. Nearly all implementations rely on attributed variables. In this paper, we explore a different implementation target for CHR: B-Prolog's Action Rules (ARs). As a rule-based language, it is a good match for particular aspects of CHR. However, the strict adherence to CHR's refined operational semantics poses some difficulty. We report on our work in progress: a novel compilation schema, required changes to the AR language and the preliminary benchmarks and experiences. |
@inproceedings{schr_zhou_demoen_action_rules_chr06,
author = {Tom Schrijvers and Neng-Fa Zhou and Bart Demoen},
title = {Translating {C}onstraint {H}andling {R}ules into {Action Rules}},
pages = {141--155},
crossref = {pchr06},
abstract = { CHR is a popular high-level language for implementing constraint solvers and other general purpose applications. It has a well-established operational semantics and quite a number of different implementations, prominently in Prolog. However, there is still much room for exploring the compilation of CHR to Prolog. Nearly all implementations rely on attributed variables. In this paper, we explore a different implementation target for CHR: B-Prolog's Action Rules (ARs). As a rule-based language, it is a good match for particular aspects of CHR. However, the strict adherence to CHR's refined operational semantics poses some difficulty. We report on our work in progress: a novel compilation schema, required changes to the AR language and the preliminary benchmarks and experiences. },
keywords = {CHR 2006, implementation, related formalisms},
ps = PAPERSHOME # {chr2006/schr_zhou_demoen_action_rules_chr06.ps},
}
-
Jon Sneyers,
Tom Schrijvers,
and Bart Demoen.
Dijkstra's Algorithm with Fibonacci Heaps: An Executable Description in CHR.
In M. Fink,
H. Tompits,
and S. Woltran, editors,
WLP '06: Proc. 20th Workshop on Logic Programming,
T.U.Wien, Austria, INFSYS Research report 1843-06-02,
pages 182-191,
February 2006.
Keyword(s): algorithms.
@inproceedings{sney_schr_demoen_dijkstra_chr_wlp06,
author = {Jon Sneyers and Tom Schrijvers and Bart Demoen},
title = {Dijkstra's Algorithm with {Fibonacci} Heaps: An Executable Description in {CHR}},
pages = {182--191},
keywords = {algorithms},
crossref = {pwlp06}
}
-
Jon Sneyers,
Tom Schrijvers,
and Bart Demoen.
Memory reuse for CHR.
In S. Etalle and M. Truszczynski, editors,
ICLP '06: Proc. 22nd Intl. Conf. Logic Programming,
volume 4079 of Lecture Notes in Computer Science,
pages 72-86,
August 2006.
Springer-Verlag.
[doi:10.1007/11799573_8]
Keyword(s): implementation,
optimizing compilation.
Abstract: |
Two Constraint Handling Rules compiler optimizations that drastically reduce the memory footprint of CHR programs are introduced. The reduction is the result of reusing suspension terms, the internal CHR constraint representation, and avoiding the overhead of constraint removal followed by insertion. The optimizations are defined formally and their correctness is proved. Both optimizations were implemented in the K.U.Leuven CHR system. Significant memory savings and speedups were measured on classical and well-known benchmarks. |
@inproceedings{sney_schr_demoen_memory_reuse_iclp06,
author = {Jon Sneyers and Tom Schrijvers and Bart Demoen},
title = {Memory reuse for {CHR}},
pages = {72--86},
crossref = {piclp06},
doi = {10.1007/11799573_8},
keywords = {implementation, optimizing compilation},
abstract = { Two Constraint Handling Rules compiler optimizations that drastically reduce the memory footprint of CHR programs are introduced. The reduction is the result of reusing suspension terms, the internal CHR constraint representation, and avoiding the overhead of constraint removal followed by insertion. The optimizations are defined formally and their correctness is proved. Both optimizations were implemented in the K.U.Leuven CHR system. Significant memory savings and speedups were measured on classical and well-known benchmarks. },
}
-
Peter J. Stuckey,
Martin Sulzmann,
and Jeremy Wazny.
Type Processing by Constraint Reasoning.
In N. Kobayashi, editor,
APLAS '06: Proc. 4th Asian Symp. on Programming Languages and Systems,
volume 4279 of Lecture Notes in Computer Science,
pages 1-25,
November 2006.
Springer-Verlag.
Note: Invited talk.
ISBN: 3-540-48937-1.
Keyword(s): type systems.
@inproceedings{stuck_sulz_wazny_type_processing_by_constraint_reasoning_aplas06,
author = {Peter J. Stuckey and Martin Sulzmann and Jeremy Wazny},
title = {Type Processing by Constraint Reasoning},
keywords = {type systems},
note = "Invited talk",
pages = {1--25},
crossref = {paplas06}
}
-
Martin Sulzmann,
Tom Schrijvers,
and Peter J. Stuckey.
Principal Type Inference for GHC-Style Multi-parameter Type Classes.
In N. Kobayashi, editor,
APLAS '06: Proc. 4th Asian Symp. on Programming Languages and Systems,
volume 4279 of Lecture Notes in Computer Science,
pages 26-43,
November 2006.
Springer-Verlag.
ISBN: 3-540-48937-1.
Keyword(s): type systems.
@inproceedings{sulz_schr_stuck_aplas06,
author = {Martin Sulzmann and Tom Schrijvers and Peter J. Stuckey},
title = {Principal Type Inference for {GHC}-Style Multi-parameter Type Classes},
keywords = {type systems},
pages = {26--43},
crossref = {paplas06}
}
-
Martin Sulzmann and Meng Wang.
Modular generic programming with extensible superclasses.
In Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming,
WGP '06,
pages 55-65,
2006.
ACM.
ISBN: 1-59593-492-8.
[WWW]
Keyword(s): type systems.
@inproceedings{Sulzmann:2006:MGP:1159861.1159869,
author = {Sulzmann, Martin and Wang, Meng},
title = {Modular generic programming with extensible superclasses},
booktitle = {Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming},
series = {WGP '06},
year = {2006},
isbn = {1-59593-492-8},
location = {Portland, Oregon, USA},
pages = {55--65},
url = {http://doi.acm.org/10.1145/1159861.1159869},
publisher = {ACM},
keywords = {type systems},
}
-
Martin Sulzmann,
Jeremy Wazny,
and Peter J. Stuckey.
A Framework for Extended Algebraic Data Types.
In FLOPS '06: Proc. 8th Intl. Symp. Functional and Logic Programming,
volume 3945 of Lecture Notes in Computer Science,
pages 47-64,
2006.
Springer-Verlag.
[doi:10.1007/11737414_5]
Keyword(s): type systems.
@inproceedings{sulzm_wazny_stuckey_eadt_flops06,
author = {Martin Sulzmann and Jeremy Wazny and Peter J. Stuckey},
title = {A Framework for Extended Algebraic Data Types},
booktitle = {FLOPS '06: Proc.\ 8th Intl.\ Symp.\ Functional and Logic Programming},
keywords = {type systems},
pages = {47--64},
publisher = SV,
series = LNCS,
volume = 3945,
year = 2006,
doi = {10.1007/11737414_5},
}
-
Kazunori Ueda,
Norio Kato,
Koji Hara,
and Ken Mizuno.
LMNtal as a Unifying Declarative Language.
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 1-15,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
Note: Invited talk.
[PDF]
Keyword(s): related formalisms,
CHR 2006,
CHR 2006,
CHR 2006.
Abstract: |
LMNtal (pronounced "elemental") is a simple language model based on hierarchical graph rewriting that uses logical variables to represent connectivity and membranes to represent hierarchy. LMNtal is an outcome of the attempt to unify constraint-based concurrency and Constraint Handling Rules (CHR), the two notable extensions to concurrent logic programming. LMNtal is intended to be a substrate language of various computational models, especially those addressing concurrency, mobility and multiset rewriting. Another important goal of LMNtal has been to put hierarchical graph rewriting into practice and demonstrate its versatility by designing and implementing a full-fledged, monolithic programming language. In this paper, we demonstrate the practical aspects of LMNtal using a number of examples taken from diverse areas of computer science. Also, we discuss the relationship between LMNtal and CHR, which exhibit both commonalities and differences in various respects. |
@inproceedings{ueda_LMNtal_chr06,
author = {Kazunori Ueda and Norio Kato and Koji Hara and Ken Mizuno},
title = {{LMNtal} as a Unifying Declarative Language},
pages = {1--15},
note = {Invited talk},
crossref = {pchr06},
keywords = {related formalisms},
abstract = { LMNtal (pronounced "elemental") is a simple language model based on hierarchical graph rewriting that uses logical variables to represent connectivity and membranes to represent hierarchy. LMNtal is an outcome of the attempt to unify constraint-based concurrency and Constraint Handling Rules (CHR), the two notable extensions to concurrent logic programming. LMNtal is intended to be a substrate language of various computational models, especially those addressing concurrency, mobility and multiset rewriting. Another important goal of LMNtal has been to put hierarchical graph rewriting into practice and demonstrate its versatility by designing and implementing a full-fledged, monolithic programming language. In this paper, we demonstrate the practical aspects of LMNtal using a number of examples taken from diverse areas of computer science. Also, we discuss the relationship between LMNtal and CHR, which exhibit both commonalities and differences in various respects. },
keywords = {CHR 2006},
pdf = PAPERSHOME # {chr2006/ueda_LMNtal_chr06.pdf},
}
-
Peter Van Weert,
Jon Sneyers,
Tom Schrijvers,
and Bart Demoen.
Extending CHR with Negation as Absence.
In T. Schrijvers and Th. Frühwirth, editors,
CHR '06: Proc. 3rd Workshop on Constraint Handling Rules,
pages 125-140,
July 2006.
K.U.Leuven, Department of Computer Science, Technical report CW 452.
[POSTSCRIPT]
Keyword(s): CHR 2006,
extensions,
CHR 2006,
CHR 2006.
Abstract: |
In this exploratory paper we introduce an extension of the CHR language with negation as absence, an established feature in production rule systems. Negation as absence is a procedural notion that allows a more concise and clean programming style. We propose a formal operational semantics close to CHR's refined operational semantics. We illustrate and motivate its properties with examples. |
@inproceedings{vanweert_sney_schr_demoen_negation_chr06,
author = {Van Weert, Peter and Jon Sneyers and Tom Schrijvers and Bart Demoen},
title = {Extending {CHR} with Negation as Absence},
pages = {125--140},
crossref = {pchr06},
abstract = { In this exploratory paper we introduce an extension of the CHR language with negation as absence, an established feature in production rule systems. Negation as absence is a procedural notion that allows a more concise and clean programming style. We propose a formal operational semantics close to CHR's refined operational semantics. We illustrate and motivate its properties with examples. },
keywords = {CHR 2006, extensions},
ps = PAPERSHOME # {chr2006/vanweert_sney_schr_demoen_negation_chr06.ps},
}