Source-to-Source Transformation Engine for Constraint Handling Rules
The CHR research community often prototypes possible extensions of CHR by means of source-to-source transformations, i.e. new features of the language are realized by providing implementations based on the core CHR language.
The task in this thesis is to develop an engine that facilitates prototyping of these source-to-source transformations. The resulting tool should be evaluated by prototypically implementing well-known transformations (e.g. high-level compiler optimizations).
Requirements: Lecture Rule-based Programming
Type: Bachelor thesis, Master thesis
Topics related to constraint programming and Constraint Handling Rules
Below is a list of possible topics for practicals and diploma/bachelor/master theses related to constraint programming and Constraint Handling Rules. The topics serve as suggestions and can be adjusted accordingly. Additional topic suggestions are welcome.
Graph Tool for Mason Marks
- improve the vertex-centric logical graph representation, i.e. adding arcs, colors, labels,
- encode existing mason marks either by hand, from images or import from existing databases,
- recognize (sub)graphs and patterns in a graph, in particular (self-)similarities and correlations between graphs,
- perform classical algorithms on graphs like shortest paths,
- derive properties and statistics from graphs,
- generate (randomly or exhaustively) and draw graphs from given constrained subgraphs based on properties and statistics.
Type: Project, Bachelor, Master
ReferencesThom Frühwirth: Rule-Based Drawing, Analysis and Generation of Graphs for Mason's Mark Design, 2018
Justifications in CHR for Logical Retraction in Dynamic Algorithms
CHR with Justifications
When algorithms are written in CHR, constraints represent both data and operations. CHR is already incremental by nature, i.e. constraints can be added at runtime. Logical retraction adds decrementality. Hence any algorithm written in CHR with justifications will become fully dynamic. Operations can be undone and data can be removed at any point in the computation without compromising the correctness of the result.
A straightforward source-to-source transformation can introduce justifications for user-defined constraints into the CHR. Then a scheme of two rules suffices to allow for logical retraction (deletion, removal) of constraints during computation. Without the need to recompute from scratch, these rules remove not only the constraint but also undo all consequences of the rule applications that involved the constraint.
Further work should investigate implementation, dynamic algorithms and application domains of CHR with justifications:
- research how logical as well as classical algorithms implemented in CHR behave when they become dynamic.
- improve the implementation, optimize and benchmark it.
- support detection and repair of inconsistencies (for error diagnosis), - support nonmonotonic logical behaviors (e.g. default logic, abduction, defeasible reasoning).
- Thom Frühwirth. Justifications in Constraint Handling Rules for Logical Retraction in Dynamic Algorithms.
- CHR translator
Prerequisites: good knowledge of Prolog and CHR, lecture Rule-based Programming, interest to learn about formal analysis methods of rule-based languages
Type: Project Bachelor Thesis, Master Thesis
Science is based on the notion of a model that faithfully describes an aspect of the reality around us. Often, these models exist only on paper. The aim of the thesis is to identify a well-defined models in the scientific field of Computational Psychology and to implement them using the high-level language CHR. Such an implementation can than be efficiently executed in CHR, compared with experimental results and subjected to the wealth of CHR analysis techniques.
Computational Psychology combines experimental psychology with computer simulation and mathematical modeling. On the basis of well-defined theoretical concepts, computational approaches can provide a unifying language and methodology across disciplines ranging from neurobiology to cognitive science, systems biology, and information technology.
Cognitive science is the interdisciplinary study of the mind and its processes. It includes research on intelligence and behavior, focusing on how information is represented, processed, and transformed (e.g. in perception, language, memory, reasoning, and emotion). Cognitive science touches multiple research disciplines, including psychology, artificial intelligence, philosophy, neuroscience, linguistics, anthropology, sociology, and education.
Type: Bachelors thesis, Masters thesis
Completion of non-confluent CHR programs
Non-confluent CHR programs, i.e. programs that can yield different results dependent on the order of the rules, can be completed such that they are confluent.
Within this work the student should familiarize herself with CHR and confluence. The completion algorithm should be implemented in a sound and reusable way.
Type: Masters thesis