Deciding Quantifier-free Definability in Finite Algebraic Structures | Zendy

Miguel Campercholi | Zendy; Mauricio Tellechea | Zendy; Pablo Ventura | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Deciding Quantifier-free Definability in Finite Algebraic Structures

Author(s) -

Miguel Campercholi,

Mauricio Tellechea,

Pablo Ventura

Publication year - 2020

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2020.02.003

Subject(s) - quantifier elimination , soundness , completeness (order theory) , mathematics , mathematical proof , isomorphism (crystallography) , algebraic number , tuple , algebra over a field , discrete mathematics , pure mathematics , computer science , programming language , mathematical analysis , chemistry , geometry , crystal structure , crystallography

This work deals with the definability problem by quantifier-free first-order formulas over a finite algebraic structure. We show the problem to be coNP-complete and present a decision algorithm based on a semantical characterization of definable relations as those preserved by isomorphisms of substructures. Our approach also includes the design of an algorithm that computes the isomorphism type of a tuple in a finite algebraic structure. Proofs of soundness and completeness of the algorithms are presented, as well as empirical tests assessing their performances.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research