MESSAGE-BASED SEMANTICA FOR SAT PROBLEMS

Iaroslav PETIK

PETIK I. (2024), MESSAGE-BASED SEMANTICA FOR SAT PROBLEMS.
PHILOSOPHY, ECONOMICS AND LAW REVIEW. Volume 4, no. 1, 67-74

DOI: 10.31733/2786-491X-2024-1-67-74

 

Abstract. This paper outlines the logical system of MSSG-logic originally developed by the author to represent a particular theory in analytic philosophy of language. That was a theory by philosopher Paul Grice that proposed to consider the intention of the speaker as an important context for the definition of the true meaning of his speech act. MSSG-logic proposes to use special sets of symbols for the additional interpretation of the logical formulas as well as the supersets of these sets (“trees of messages”) with defined algebras on them for more complex cases. This particular paper proposes to modify the “linguistic” MSSG-logic to represent the famous computer science boolean satisfiability problems (SAT) with the similar tools. The consequences for computer science and philosophy of language are also discussed.

Keywords: SAT, boolean satisfiability, computer science, logic for CS, Paul Grice, formal language, analytic philosophy of language.

References

  • Jonsson, B. (1984). Maximal Algebras of Binary Relations. Contributions to Group Theory. Contemporary Mathematics. Vol. 33. Providence/RI: American Mathematical Society. Pp. 299–307.
  • Graham, G. (1928). The Logics and the Social Sciences. Social Forces, 7 (1). Pp. 24-32. Grice, H. (1972). Intention and Uncertainty Oxford Universtiy Press. 19 p.
  • Manquinho V.M., Marques-Silva J. (2004). Satisfiability-based algorithms for Boolean optimization. Annals of Mathematics and Artificial Intelligence. No. 40. Pp. 353-372.
  • Petik, I. (2022). Message-based logic semantics and intentional linguistic semantics of Paul Grice. Humanitarian Vision. 8 (1). Pp. 19-24.
  • Russell, S. & Norvig, P. (2010). Artificial Intelligence: A Modern Approach. New Jersey: Prentice Hall, 1151 p.
  • Wybraniec-Skardowska, U. (2020). What Is the Sense in Logic and Philosophy of Language. Bulletin of the Section of Logic. 49 (2). Pp.185-211.
  • Abadi, M. & Lamport, L. (2008). The existence of refinement mappings. Theoretical Computer Science. 319 (1-3). Pp. 437-449.
  • Biere, A., Cimatti, A., Clarke, E. M. & Zhu, Y. (2003). Symbolic model checking without BDDs. Tools and Algorithms for the Construction and Analysis of Systems. Pp. 193- 207.
  • Clarke, E. M. & Emerson, E. A. (2002). Design and Synthesis of Synchronization Skeletons using Branching Time Temporal Logic. ACM Transactions on Programming Languages and Systems (TOPLAS). 23 (5). Pp. 845-871.
  • Goranko, V. & Passy, S. (2007). Algorithmic Correspondence for Dynamic Logics: Complexity and Expressiveness. Journal of Logic, Language, and Information. 16 (4). Pp. 397-422.
  • Sipser, M. (2008). A Complexity-Theoretic Perspective on Formal Languages. Communications of the ACM. 51 (7). Pp. 76-83.
  • Vardi, M. Y. & Wolper, P. (2008). An automata-theoretic approach to automatic program verification. A Decade of Concurrency: Reflections and Perspectives. Pp. 317-331.
Views: 63