Sesión Lógica y Computabilidad (II)

Diciembre 14, 12:00 ~ 12:20

A computational study of open-definability

Campercholi, Miguel

Let $\mathcal{L}$ be a relational first-order language and let $\mathbf{A}$ be an $\mathcal{L}$-model. A subset $S\subseteq A^{k}$ is \emph{open-definable} in $\mathbf{A}$ if there is a quantifier-free first-order formula $\varphi(v_{1},\dots,v_{k})$ in $\mathcal{L}$ such that \[ S=\{\bar{a}\in A^{k}:\mathbf{A}\vDash\varphi[\bar{a}]\}. \] We study the following computational problem. \noindent $\mathrm{OpenDef}$: takes as input a finite relational structure $\mathbf{A}$ and a target relation $S\subseteq 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.

Autores: Areces, Carlos / Campercholi, Miguel / Ventura, Pablo.