Artículo
Deciding quantifier-free definability in finite algebraic structures
Fecha de publicación:
03/2019
Editorial:
Elsevier
Revista:
Electronic Notes in Theoretical Computer Science
ISSN:
1571-0661
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
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.
Palabras clave:
COMPLEXITY
,
DECISION ALGORITHM
,
DEFINABILITY
,
LOGIC
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CIEM)
Articulos de CENT.INV.Y ESTUDIOS DE MATEMATICA DE CORDOBA(P)
Articulos de CENT.INV.Y ESTUDIOS DE MATEMATICA DE CORDOBA(P)
Citación
Campercholi, Miguel Alejandro Carlos; Tellechea, Mauricio; Ventura, Pablo Gabriel; Deciding quantifier-free definability in finite algebraic structures; Elsevier; Electronic Notes in Theoretical Computer Science; 348; 3-2019; 23-41
Compartir
Altmétricas