The complexity of definability by open first-order formulas
From MaRDI portal
Publication:3386916
DOI10.1093/jigpal/jzaa008zbMath1497.68220arXiv1904.04637OpenAlexW3028958672MaRDI QIDQ3386916
Pablo Ventura, Daniel Penazzi, Carlos Areces, Miguel A. Campercholi
Publication date: 8 January 2021
Published in: Logic Journal of the IGPL (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.04637
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Basic properties of first-order languages and structures (03C07) Parameterized complexity, tractability and kernelization (68Q27)