Skip Navigation


Journal of Logic and Computation Advance Access originally published online on June 27, 2008
Journal of Logic and Computation 2008 18(6):941-958; doi:10.1093/logcom/exn017
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
18/6/941    most recent
exn017v1
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Marchioni, E.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Articles

On Computational Complexity of Semilinear Varieties

Enrico Marchioni

Department of Information and Communication Sciences, Open University of Catalonia, Rambla del Poblenou 156, 08018 Barcelona, Spain.

E-mail: enrico{at}iiia.csic.es

Received 30 March 2007.


  Abstract

We propose a method for characterizing the complexity of satisfiability and tautologicity of equational theories of varieties of algebras by relying on their representability in the theory of the ordered additive group of reals FormulaQ with rational constants. We call semilinear those varieties which are generated by a subclass of algebras in which the operations are representable as semilinear functions with rational coefficients. Those functions are definable in the theory of FormulaQ which admits quantifier elimination and whose existential theory is NP-complete. We prove that there is a polynomial time translation of the equational theories of semilinear varieties into the existential theory of FormulaQ. Then, if the variety is generated (up to isomorphism) by one semilinear algebra, the satisfiability problem is in NP, while the tautologicity problem is in co-NP. We apply this method in order to provide a comprehensive study of complexity of several varieties related to logics based on left-continuous conjunctive uninorms and left-continuous t-norms.

Keywords: Computational complexity; ordered divisible Abelian groups; varieties; semilinear functions; uninorms; triangular norms


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.