JACIII Vol.20 No.5 pp. 813-827
doi: 10.20965/jaciii.2016.p0813


Method for Combining Paraconsistency and Probability in Temporal Reasoning

Norihiro Kamide* and Daiki Koizumi**

*Faculty of Science and Engineering, Department of Information and Electronic Engineering, Teikyo University
1-1 Toyosatodai, Utsunomiya, Tochigi 320-8551, Japan
**Faculty of Commerce, Department of Information and Management Science, Otaru University of Commerce
3-5-21 Midori, Otaru, Hokkaido 047-8501, Japan

June 7, 2016
July 25, 2016
Online released:
September 20, 2016
September 20, 2016
computation tree logic, paraconsistent reasoning, probabilistic reasoning, embedding theorem, model-checking

Computation tree logic (CTL) is known to be one of the most useful temporal logics for verifying concurrent systems by model checking technologies. However, CTL is not sufficient for handling inconsistency-tolerant and probabilistic accounts of concurrent systems. In this paper, a paraconsistent (or inconsistency-tolerant) probabilistic computation tree logic (PpCTL) is derived from an existing probabilistic computation tree logic (pCTL) by adding a paraconsistent negation connective. A theorem for embedding PpCTL into pCTL is proven, thereby indicating that we can reuse existing pCTL-based model checking algorithms. A relative decidability theorem for PpCTL, wherein the decidability of pCTL implies that of PpCTL, is proven using this embedding theorem. Some illustrative examples involving the use of PpCTL are also presented.

  1. [1] D. Chen and J. Wu, “Reasoning about inconsistent concurrent systems: A non-classical temporal logic,” Proc. of the 32nd Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM 2006), Lecture Notes in Computer Science, Vol.3831, pp. 207-217, 2006.
  2. [2] A. Bianco and L. de Alfaro, “Model checking of probabilistic and nondeterministic systems,” Proc. of the 15th Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 1995), Lecture Notes in Computer Science, Vol.1026, pp. 499-513, 1995.
  3. [3] E. M. Clarke and E. A. Emerson, “Design and synthesis of synchronization skeletons using branching time temporal logic,” Proc. of the Workshop on Logics of Programs, Lecture Notes in Computer Science, Vol.131, pp. 52-71, 1981.
  4. [4] E.M. Clarke, O. Grumberg, and D.A. Peled, “Model checking,” The MIT Press, 1999.
  5. [5] A. Pnueli, “The temporal logic of programs,” Proc. of the 18th IEEE Symp. on Foundations of Computer Science, pp. 46-57, 1977.
  6. [6] N. Kamide and K. Kaneiwa, “Paraconsistent negation and classical negation in computation tree logic,” Proc. of the 2nd Int. Conf. on Agents and Artificial Intelligence (ICAART 2010), Vol. 1, pp. 464-469, 2010.
  7. [7] K. Kaneiwa and N. Kamide, “Paraconsistent computation tree logic,” New Generation Computing, Vol.29, No.4, pp. 391-408, 2011.
  8. [8] A. Aziz, V. Singhal, and F. Balarin, “It usually works: The temporal logic of stochastic systems,” Proc. of the 7th Int. Conf. on Computer Aided Verification (CAV 1995), Lecture Notes in Computer Science 939, pp. 155-165, 1995.
  9. [9] M. Sonoda, T. Matsuda, D. Koizumi, and S. Hirasawa, “On automatic detection of SQL injection attacks by the feature extraction of the single character,” Proc. of the 4th Int. Conf. on Security of Information and Networks (SIN 2011), pp. 81-86, 2011.
  10. [10] W. Carnielli, M. Coniglio, D.M. Gabbay, P. Gouveia, and C. Sernadas, “Analysis and synthesis of logics: How to cut and paste reasoning systems,” Applied Logic Series, Vol.35, Springer, 2008.
  11. [11] A. Almukdad and D. Nelson, “Constructible falsity and inexact predicates,” J. of Symbolic Logic, Vol.49, pp. 231-233, 1984.
  12. [12] D. Nelson, Constructible falsity, J. of Symbolic Logic, 14, pp. 16-26, 1949.
  13. [13] G. Priest and R. Routley, Introduction: paraconsistent logics, Studia Logica, 43, pp. 3-16, 1982.
  14. [14] N.C.A. da Costa, J. Béziau and O.A. Bueno, Aspects of paraconsistent logic, Bulletin of the IGPL 3 (4), pp. 597-614, 1995.
  15. [15] H. Wansing, The logic of information structures, Lecture Notes in Artificial Intelligence 681, pp. 1-163, 1993.
  16. [16] N. Kamide and H. Wansing, Proof theory of Nelson’s paraconsistent logic: A uniform perspective, Theoretical Computer Science 415, pp. 1-38, 2012.
  17. [17] N. Kamide, Inconsistency-tolerant bunched implications, Int. J. of Approximate Reasoning 54 (2), pp. 343-353, 2013.
  18. [18] N. Kamide and H. Wansing, Combining linear-time temporal logic with constructiveness and paraconsistency, J. of Applied Logic 8 (1), pp. 33-61, 2010.
  19. [19] N. Kamide and H. Wansing, A paraconsistent linear-time temporal logic, Fundamenta Informaticae 106 (1), pp. 1-23, 2011.
  20. [20] Y. Gurevich, Intuitionistic logic with strong negation, Studia Logica 36, pp. 49-59, 1977.
  21. [21] W. Rautenberg, Klassische und nicht-klassische Aussagenlogik, Vieweg, Braunschweig, 1979.
  22. [22] N.N. Vorob’ev, A constructive propositional calculus with strong negation (in Russian), Doklady Akademii Nauk SSR 85, pp. 465-468, 1952.
  23. [23] N. Kamide and D. Koizumi, Combining paraconsistency and probability in CTL, Proc. of the 7th Int. Conf. on Agents and Artificial Intelligence (ICAART 2015), pp. 285-293, 2015.
  24. [24] M.C. Browne, E.M. Clarke, and O. Grumberg, Characterizing finite Kripke structures in propositional temporal logic, Theoretical Computer Science 59, pp. 115-131, 1988.
  25. [25] J. Clarke, SQL injection attacks and defense, 2nd Edition, Syngress Publishing, 2009.
  26. [26] Lwin Khin Shar and Hee Beng Kuan Tan, Defeating SQL Injection, Computer, Vol.46, Issue 3, IEEE Computer Society, pp. 69-77, 2013.
  27. [27] T. Matsuda, D. Koizumi, M. Sonoda, and S. Hirasawa, On predictive errors of SQL injection attack detection by the feature of the single character, Proc. of the IEEE Int. Conf. on Systems, Man and Cybernetics, (SMC 2011), pp. 1722-1727, 2011.
  28. [28] D. Koizumi, T. Matsuda, M. Sonoda, and S. Hirasawa, A learning algorithm of threshold value on the automatic detection of SQL injection attack, Proc. of the 2012 Int. Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA 2012), Vol.2, pp. 933-937, 2012.
  29. [29] N. Kamide, A spatial modal logic with a location interpretation, Mathematical Logic Quarterly,Vol.51, No.4, pp. 331-341, 2005.
  30. [30] N. Kamide, Linear and affine logics with temporal, spatial and epistemic operators, Theoretical Computer Science, Vol.353, No.1-3, pp. 165-207, 2006.
  31. [31] N. Kobayashi, T. Shimizu, and A. Yonezawa, Distributed concurrent linear logic programming, Theoretical Computer Science, Vol.227, pp. 185-220, 1999.
  32. [32] N. Kamide, Modeling and verifying inconsistency-tolerant temporal reasoning with hierarchical information: Dealing with students’ learning processes, Proc. of the IEEE Int. Conf. on Systems, Man, and Cybernetics (SMC 2013), pp. 1859-1864, 2013.
  33. [33] N. Kamide, Inconsistency-tolerant temporal reasoning with hierarchical information, Information Sciences, Vol.320, pp. 140-155, 2015.
  34. [34] N. Kamide, Bunched sequential information, J. of Applied Logic, Vol.15, pp. 150-170, 2016.
  35. [35] N. Kamide and K. Kaneiwa, Extended full computation-tree logic with sequence modal operator: Representing hierarchical tree structures, Proc. of the 22nd Australasian Joint Conf. on Artificial Intelligence (AI’09), Lecture Notes in Artificial Intelligence, Vol.5866, pp. 485-494, 2009.
  36. [36] K. Kaneiwa and N. Kamide, Sequence-indexed linear-time temporal logic: Proof system and application, Applied Artificial Intelligence, Vol.24, pp. 896-913, 2010.
  37. [37] K. Kaneiwa and N. Kamide, Conceptual modeling in full computation-tree logic with sequence modal operator, Int. J. of Intelligent Systems, Vol.26, No.7, pp. 636-651, 2011.
  38. [38] S. Easterbrook, and M. Chechik, A framework for multi-valued reasoning over inconsistent viewpoints, Proc. of the 23rd Int. Conf. on Software Engineering (ICSE 2001), pp. 411-420, 2001.
  39. [39] N. Kamide, Extended full computation tree logics for paraconsistent model checking, Logic and Logical Philosophy, Vol.15, No.3, pp. 251-276, 2006.
  40. [40] H. Hansson and B. Jonsson, A logic for reasoning about time and reliability, Formal Aspects of Computing, Vol.6, No.5, pp. 512-535, 1994.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, IE9,10,11, Opera.

Last updated on Mar. 28, 2017