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.

 

If you are interested contact Prof. Frühwirth or Daniel Gall.

Graph Tool for Mason Marks

We are developing a rule-based implementation of a tool to analyse and generate graphs. It is used in the domain of mason’s marks. For thousands of years, stonemasons have been inscribing these symbolic signs on dressed stone. Geometrically, mason’s marks are line drawings. They consist of a pattern of straight lines, sometimes circles and arcs. We represent mason’s marks by connected planar graphs. Our prototype tool for analysis and generation of graphs is written in the rule-based declarative language Constraint Handling Rules. One or several of following features could be improved in this proposed work:

  • 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.
Prerequesites: Good knowledge of Prolog and CHR, Lecture Rule-based Programming
Type: Project, Bachelor, Master

References

Thom 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.

Goal

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).

References

Computational Psychology

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.

Required knowledge: knowledge about Prolog and CHR. Lectures Constraint Programming and Rule-based Programming are advantageous.

Type: Masters thesis