A computational study of open-definability

CAMPERCHOLI, MIGUEL

Buenos Aires

Congreso; RSME-UMA 2017; 2017

Let mathcal{L} be a relational first-order language and let mathbf{A} be an mathcal{L}-model. A subset Ssubseteq A^{k} is open-definable in mathbf{A} if there is a quantifier-free first-order formula arphi(v_{1},dots,v_{k}) in mathcal{L} such thatS={ar{a}in A^{k}:mathbf{A}Dasharphi[ar{a}]}.We study the following computational problem.mathrm{OpenDef}: takes as input a finite relational structure mathbf{A} and a target relation Ssubseteq A^{k} and decides if S is open-definable in mathbf{A}.We introduce an algorithm that solves this problem exploiting a semantical characterization of open-definability. We also investigate the time-complexity of mathrm{OpenDef}, and show that it is mathrm{coNP}-complete. However, it is polynomial when parameterized in the arity of the target relation.