Deciding Open Definability via Subisomorphisms

C. Areces, M. Campercholi, and V. Ventura. Deciding Open Definability via Subisomorphisms. In Logic, Language, Information, and Computation - 25th International Workshop, WoLLIC 2018, Bogota, Colombia, July 24-27, 2018, Proceedings, pp. 91–105, 2018.

Download

[pdf] 

Abstract

Given a logic L, the L-Definability Problem for finite structures takes as 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. In this note we present an algorithm that solves the definability problem for quantifier-free first order formulas. Our algorithm takes advantage of a semantic characterization of open definability via subisomorphisms, which is sound and complete. We also provide an empirical evaluation of its performance.

BibTeX

@InCollection{Areces2018,
  author =       "C. Areces and M. Campercholi and V. Ventura",
  booktitle =    "Logic, Language, Information, and Computation - 25th
                 International Workshop, WoLLIC 2018, Bogota, Colombia,
                 July 24-27, 2018, Proceedings",
  title =        "Deciding Open Definability via Subisomorphisms",
  year =         "2018",
  pages =        "91--105",
  abstract =     "Given a logic L, the L-Definability Problem for finite
                 structures takes as 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. In this note we present an
                 algorithm that solves the definability problem for
                 quantifier-free first order formulas. Our algorithm
                 takes advantage of a semantic characterization of open
                 definability via subisomorphisms, which is sound and
                 complete. We also provide an empirical evaluation of
                 its performance.",
  bibsource =    "dblp computer science bibliography, https://dblp.org",
  biburl =       "https://dblp.org/rec/conf/wollic/ArecesCV18.bib",
  doi =          "10.1007/978-3-662-57669-4\_5",
  timestamp =    "Tue, 14 May 2019 10:00:40 +0200",
  URL =          "https://doi.org/10.1007/978-3-662-57669-4\_5",
  ISBN =         "978-3-662-57668-7",
}