Finding p-indecomposable Functions

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Finding p-indecomposable Functions

Vortrag von Artem Revenko
Parametric expressibility of functions is a generalization of expressibility via composition. All parametrically closed classes of functions form a lattice. For finite domains the lattice is shown to be finite, however straight-forward iteration over all functions is infeasible, and so far the indecomposable functions are only known for domains with two and three elements. In this work we show how p-indecomposable functions can be computed more efficiently by means of an extended version of attribute exploration - a robust active learning technique. Under certain assumptions it is possible to complete the lattice of parametrically closed classes of functions for a finite domain. Attribute exploration relies on the routine of finding counter-examples to attribute implications. This routine will be the focus of the talk.