(Work in progress) This repository contains:
-
An implementation of the construction of the direct product of two directed labelled multigraphs, as presented in "The complexity of reverse engineering problems for conjunctive queries" (by Barceló and Romero, 2016).
-
An implementation of a 'brute force', NP-hard algorithm to check for the existence of an homomorphism between the direct product construction and the negative examples, plus a check of the 'safety' property.
-
An implementation of a faster, polynomial-time version of the algorithm in 2).