The complexity of definability by open first-order formulas

Areces, Carlos Eduardo et al · Oxford University Press · 2020

Open-access full text

Quick overview. Review the resource’s basic details, then access the content using the main button. This page shows only the information needed to identify, cite, and open the work.

Author / responsible party

Areces, Carlos Eduardo et al

Publisher

Oxford University Press

Year

2020

ISSN

1093-1105

ISSN

1093-1105

Language

English

Resource access

Open the content from the main option or choose another available source.

CONICET Digital CONICET Digital OAI-PMH

Entrar por CONICET Digital

Main access

Open-access full text

Texto completo identificado como acceso abierto.

Open text

Summary

Descripción general del contenido del recurso.

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 formulas) with equality. Given a logic L, the L-definability problem for finite structures takes as an input a finite structure A and a target relation T over the domain of A and determines whether there is a formula of L whose interpretation in A coincides with T. We show that the complexity of this problem for open first-order formulas (open definability, for short) is coNP-complete. We also investigate the parametric complexity of the problem and prove that if the size and the arity of the target relation T are taken as parameters, then open definability is coW[1]-complete for every vocabulary τ with at least one, at least binary, relation. Fil: Areces, Carlos Eduardo. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Córdoba; Argentina Fil: Campercholi, Miguel Alejandro Carlos. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Córdoba; Argentina

How to cite

Elegí el formato que necesitás y copiá la referencia al portapapeles.

APA 7

Areces, C. E. E. A. (2020). The complexity of definability by open first-order formulas. http://hdl.handle.net/11336/145168

MLA

Areces, Carlos Eduardo et al. "The complexity of definability by open first-order formulas." 2020. http://hdl.handle.net/11336/145168.

Chicago

Areces, Carlos Eduardo et al. 2020. "The complexity of definability by open first-order formulas.". http://hdl.handle.net/11336/145168.

Harvard

Areces, C. E. E. A. 2020, The complexity of definability by open first-order formulas, Oxford University Press, available at: http://hdl.handle.net/11336/145168 [Accessed 8 Aug. 2026].

Share and print

Save the record, copy its permanent link, or print it as a PDF.

Export reference

You can export the record in common formats for use in a reference manager.

RIS BibTeX

Resource details

Bibliographic information to help confirm that this is the correct material.

Title: The complexity of definability by open first-order formulas

Author / contributors: Areces, Carlos Eduardo et al

Publisher: Oxford University Press

Publication year: 2020

ISSN: 1093-1105

ISSN: 1093-1105

Language: English

Subjects

Explore related resources through these subjects.

Definability; Open formulas; First order logic; Complexity; https://purl.org/becyt/ford/1.2; https://purl.org/becyt/ford/1