Artem Revenko Made a Report "Automatic construction of implication theories"
May 29, Artem Revenko, a Phd student of TU Dresden, made a report at the session of our seminar.
In this talk we considered automation of constructing implicative dependencies between mathematical instances. For this purpose a robust active learning technique called Attribute Exploration is used. The technique collects object-attribute pairs from an expert and builds a concise representation of implicative dependencies (implication basis) between the attributes. The implication basis possesses the "completeness" property, i.e. every valid implication can be deduced from the basis. Two mathematical domains were considered as applications. For algebraic identities it was possible to automatically construct the valid implication basis for all pairwise non-equivalent identities of size up to 5. It was not possible to accomplish this construction using only finite algebras and due to this fact heuristics and an algorithm for finding appropriate algebras over an infinite universe were introduced. For the commuting functions it was possible to automatically construct the implication basis for the functions defined on a domain of size 3, therefore repeating the most advanced result in this scientific field. It was necessary to modify the Attribute Exploration technique as the functions are objects and attributes at the same time, and to introduce an efficient algorithm for finding commuting functions.