Deciding quantifier-free definability in finite algebraic structures

DOI10.1016/J.ENTCS.2020.02.003MaRDI QIDQ2219074zbMATH OpenOpenAlexWikidataFDO

Authors Mauricio Tellechea, Pablo Ventura, Miguel Campercholi

Publication date 19 January 2021

Full work available at URL https://doi.org/10.1016/j.entcs.2020.02.003

zbMATH Keywords

complexitydecision algorithmdefinabilitylogic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Deciding open definability via subisomorphisms
• Decidability of definability
• Quantifier Free Definability on Infinite Algebras
• The complexity of definability by open first-order formulas
• Decision Problems for Finite Automata over Infinite Algebraic Structures

Cites work

• Deciding open definability via subisomorphisms
• scientific article; zbMATH DE number 612169 (Why is no real title available?)
• The Exact Complexity of the First-Order Logic Definability Problem
• The Inverse Satisfiability Problem
• Using logic in the generation of referring expressions

Cited in

(6)

• Deciding open definability via subisomorphisms
• Quantifier Free Definability on Infinite Algebras
• scientific article; zbMATH DE number 7264200 (Why is no real title available?)
• Decidability of definability
• Two algorithms to decide Quantifier-free Definability in Finite Algebraic Structures
• The complexity of deciding quantifier-free definability for unary signatures

Describes a project that uses

Uses Software

• MINION

This page was built for publication: Deciding quantifier-free definability in finite algebraic structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2219074)