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 Abstract Freely available
Right arrow Full Text (PDF)
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.

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



References

  1. Aguzzoli S, Gerla B, Haniková Z. Complexity issues in basic logic. Soft Computing (2005) 9:919–934.[CrossRef][Web of Science]
  2. Baaz M. Infinite-valued Gödel logic with 0-1-projections and relativisations. Hájek P, ed. (1996) Brno: Springer-Verlag. 23–33. Gödel'96: Logical Foundations of Mathematics, Computer Science, and Physics, Vol. 6 of Lecture Notes in Logic.
  3. Baaz M, Hájek P, Montagna F, Veith H. Complexity of t-tautologies. Annals of Pure and Applied Logic (2002) 113:3–12.[Web of Science]
  4. Blok WJ, Ferreirim I. On the structure of hoops. Algebra Universalis (2000) 43:233–257.[CrossRef][Web of Science]
  5. Canny J. Some algebraic and geometric computation in PSPACE. Proceedings of the 20th Symposium on Theory of Computing (1988) 460–467.
  6. Ciabattoni A, Metcalfe G, Montagna F. Adding modalities to fuzzy logics. In: Proceedings of the Linz Seminar (2005) Volume preprint.
  7. Cignoli R, D'Ottaviano I, Mundici D. Algebraic Foundations of Many-Valued Reasoning, volume 7 of Trends in Logic. (1999) Dordercht: Kluwer.
  8. De Baets B. Idempotent uninorms. European Journal of Operational Research (1999) 118:631–642.[CrossRef][Web of Science]
  9. Esteva F, Domingo X. Sobre funciones de negación en [0, 1]. Stochastica (1980) 4:141–166.
  10. Esteva F, Gispert J, Godo L, Montagna F. On the standard and rational completeness of some axiomatic extensions of the Monoidal T-norm Logic. Studia Logica (2002) 71:199–226.[CrossRef]
  11. Esteva F, Gispert J, Godo L, Noguera C. Adding truth-constants to logics of continuous t-norms: axiomatization and completeness results. Fuzzy Sets and Systems (2007) 158:597–618.[CrossRef][Web of Science]
  12. Esteva F, Godo L. Monoidal T-norm based logic: towards a logic for left-continuous t-norms. Fuzzy Sets and Systems (2001) 124:271–288.[CrossRef][Web of Science]
  13. Esteva F, Godo L, Noguera C. On rational Weak Nilpotent Minimum logics. Journal of Multiple-Valued Logic and Soft Computing (2006) 12:9–32.
  14. Esteva F, Godo L, Noguera C. On expansions of t-norm based logics with truth-constants. In: Fuzzy Logics and Related Structures—Gottwald S, Hájek P, Höhle U, Klement E, eds. (2007) Elsevier. (forthcoming).
  15. Fagin R, Halpern J, Megiddo N. A logic for reasoning about probabilities. Information and Computation (1990) 87:78–128.[CrossRef][Web of Science]
  16. Fodor J, Yager R, Rybalov A. Structure of uninorms. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems (1997) 5:411–427.[CrossRef]
  17. Gabbay D, Metcalfe G. Fuzzy logics based on [0, 1)-continuous uninorms. Archive for Mathematical Logic (2007) 46:425–449.[CrossRef][Web of Science]
  18. Galli A, Lewin R, Sagastume M. The logic of equilibrium and abelian lattice ordered groups. Archive for Mathematical Logic (2004) 43:141–158.[CrossRef][Web of Science]
  19. Gottwald S, Hájek P. Triangular norm based mathematical fuzzy logic. In: Logical, Algebraic, Analytic and Probabilistic Aspects of Triangular Norms—Klement EP, Mesiar R, eds. (2005) Amsterdam: Elsevier. 275–300.
  20. Hähnle R. Many-valued logics and Mixed Integer Programming. Annals of Mathematics and Artificial Intelligence (1994) 12:231–264.[CrossRef]
  21. Hájek P. Metamathematics of Fuzzy Logic, Vol. 4. In: Trends in Logic (1998) Dordercht: Kluwer.
  22. Hájek P. Observations on the monoidal t-norm logic. Fuzzy Sets and Systems (2002) 132:107–112.[CrossRef][Web of Science]
  23. Hájek P. Computational complexity of t-norm based fuzzy logics with rational truth constants. Fuzzy Sets and Systems (2006) 157:677–682.[CrossRef][Web of Science]
  24. Haniková Z. A note on the complexity of propositional tautologies of individual t-algebras. Special Issue on SOFSEM 2002 of Neural Network World (2002) 12:453–460.
  25. Haniková Z. Mathematical and Metamathematical Properties of Fuzzy Logics (2003) Charles University in Prague. PhD thesis.
  26. Harrop R. On the existence of finite models and decision procedures for propositional calculi. Proceedings of the Cambridge Philosophical Society (1958) 54:1–13.[CrossRef]
  27. Horcík R. Standard completeness theorem for {Pi}MTL. Archive for Mathematical Logic (2005) 44:413–424.[CrossRef][Web of Science]
  28. Horcík R. Decidability of cancellative extension of Monoidal T-norm based Logic. Logic Journal of the IGPL (2006) 14:827–843.[CrossRef][Web of Science]
  29. Hu S, Li Z. The structure of continuous uni-norms. Fuzzy Sets and Systems (2001) 124:43–52.[CrossRef][Web of Science]
  30. Jenei S, Montagna F. A proof of standard completeness for Esteva and Godo's logic MTL. Studia Logica (2002) 70:183–192.[CrossRef]
  31. Klement EP, Mesiar R, Pap E. Triangular norms, Vol. 8. Trends in Logic (2000) Dordrecht: Kluwer.
  32. Ling C. Representation of associative functions. Publications Mathematical Debrecen (1965) 12:189–212.
  33. Marchioni E, Montagna F. Complexity and definability issues in Formula . Journal of Logic and Computation (2007) 17:311–331.[Abstract/Free Full Text]
  34. Marchioni E, Montagna F. On triangular norms and uninorms definable in Formula . International Journal of Approximate Reasoning (2008) 47:179–201.[CrossRef][Web of Science]
  35. Marker D. Model Theory: An Introduction. (2002) New York: Springer-Verlag.
  36. Mckenzie R, McNulty G, Taylor W. Algebras, Lattices, Varieties (1987) Vol. I. Monterey, CA: Wadsworth and Brooks/Cole.
  37. Metcalfe G, Montagna F. Substructural fuzzy logics. Journal of Symbolic Logic (2007) 72:834–864.[CrossRef][Web of Science]
  38. Mostert P, Shields A. On the structure of semigroups on a compact manifold with boundary. The Annals of Mathematics (1957) 65:117–143.[CrossRef]
  39. Mundici D. Satifiability in many-valued sentential logic is NP-complete. Theoretical Computer Science (1987) 52:145–153.[CrossRef][Web of Science]
  40. Savicky P, Cignoli R, Esteva F, Godo L, Noguera C. On product logic with truth constants. Journal of Logic and Computation (2006) 16:205–225.[Abstract/Free Full Text]
  41. Tsinakis C, Blount K. The structure of residuated lattices. International Journal of Algebra and Computation (2003) 13:437–461.[CrossRef][Web of Science]
  42. van den Dries L. Tame Topology and O-minimal Structures. (1998) Cambridge (UK): Cambridge University Press.
  43. Yager R, Rybalov A. Uninorm aggregation operators. Fuzzy Sets and Systems (1996) 80:111–120.[CrossRef][Web of Science]

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



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
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?