Two algorithms to decide Quantifier-free Definability in Finite Algebraic Structures

Miguel Campercholi, Mauricio Tellechea, Pablo Ventura

This work deals with the definability problem by quantifier-free first-order formulas over a finite algebraic structure. We show the problem to be coNP-complete and present two dec…