2 papers
cs.LO2023
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…
cs.CC2019
The Complexity of Definability by Open First-Order Formulas
Carlos Areces, Miguel Campercholi, Daniel Penazzi +1
In this article we formally define and investigate the computational complexity of the Definability Problem for open first-order formulas (i.e., quantifier free first-order formula…