An efficient algorithm of fuzzy reinstatement labelling

Shuangyan Zhao; Jiachao Wu; Shuangyan Zhao; Jiachao Wu

doi:10.3934/math.2022625

AIMS Mathematics

2022, Volume 7, Issue 6: 11165-11187. doi: 10.3934/math.2022625

Previous Article Next Article

Research article Special Issues

An efficient algorithm of fuzzy reinstatement labelling

Shuangyan Zhao ,
Jiachao Wu ^,

School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, China

Received: 16 January 2022 Revised: 13 March 2022 Accepted: 01 April 2022 Published: 11 April 2022
MSC : 03E72, 03E75

The fuzzy reinstatement labelling ($ FRL $) puts forward a reasonable method to rewind the acceptable degrees of arguments in fuzzy argumentation frameworks. The fuzzy labelling algorithm ($ FLAlg $) computes the $ FRL $ by infinitely approximating the limits of an iteration sequence. However, the $ FLAlg $ is unable to provide an exact $ FRL $, and its computation complexity depends on not only the number of arguments but also the accuracy. This brings a quick increase in complexity when higher accuracy is acquired. In this paper, through the in-depth study of the $ FLAlg $, we introduce an effective algorithm for decomposing $ FRL $ by strongly connected components. For simple fuzzy frameworks in the form of trees, odd cycles, and even cycles, the new algorithm provides an exact value of the limit. Therefore, by avoiding the infinite approximation process, it is independent of accuracy. And for complex frames, the new algorithm outputs an approximate value to the $ FLAlg $. It is more efficient because the number of arguments in the approximation process is usually reduced.
- fuzzy reinstatement labelling,
- argumentation framework,
- strongly connected component,
- algorithm,
- fuzzy argumentation framework
Citation: Shuangyan Zhao, Jiachao Wu. An efficient algorithm of fuzzy reinstatement labelling[J]. AIMS Mathematics, 2022, 7(6): 11165-11187. doi: 10.3934/math.2022625

Related Papers:

Abstract

The fuzzy reinstatement labelling ($ FRL $) puts forward a reasonable method to rewind the acceptable degrees of arguments in fuzzy argumentation frameworks. The fuzzy labelling algorithm ($ FLAlg $) computes the $ FRL $ by infinitely approximating the limits of an iteration sequence. However, the $ FLAlg $ is unable to provide an exact $ FRL $, and its computation complexity depends on not only the number of arguments but also the accuracy. This brings a quick increase in complexity when higher accuracy is acquired. In this paper, through the in-depth study of the $ FLAlg $, we introduce an effective algorithm for decomposing $ FRL $ by strongly connected components. For simple fuzzy frameworks in the form of trees, odd cycles, and even cycles, the new algorithm provides an exact value of the limit. Therefore, by avoiding the infinite approximation process, it is independent of accuracy. And for complex frames, the new algorithm outputs an approximate value to the $ FLAlg $. It is more efficient because the number of arguments in the approximation process is usually reduced.

References

[1]	P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and $n$-person games, Artif. Intell., 77 (1995), 321–357. https://dx.doi.org/10.1016/0004-3702(94)00041-X doi: 10.1016/0004-3702(94)00041-X
[2]	J. Ahmmad, T. Mahmood, R. Chinram, A. Lampan, Some average aggregation operators based on spherical fuzzy soft sets and their applications in multi-criteria decision making, AIMS Math., 6 (2021), 7798–7832. https://dx.doi.org/10.3934/math.2021454 doi: 10.3934/math.2021454
[3]	A. Saha, D. Dutta, S. kar, Some new hybrid hesitant fuzzy weighted aggregation operators based on archimedean and dombi operations for multi-attribute decision making, Neural Comput. Appl., 33 (2021), 8753–8776. https://dx.doi.org/10.1007/s00521-020-05623-x doi: 10.1007/s00521-020-05623-x
[4]	P. Baroni, F. Toni, B. Verheij, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and $n$-person games: 25 years later, Argum. Comput., 11 (2020), 1–14. https://dx.doi.org/10.3233/AAC-200901 doi: 10.3233/AAC-200901
[5]	S. P. Ferrando, E. Onaindia, Defeasible-argumentation-based multi-agent planning, Inf. Sci., 411 (2017), 1–22. https://dx.doi.org/10.1016/j.ins.2017.05.014 doi: 10.1016/j.ins.2017.05.014
[6]	X. Li, X. Yang, S. Song, Lyapunov conditions for finite-time stability of time-varying time-delay systems, Automatica, 103 (2019), 135–140. https://dx.doi.org/10.1016/j.automatica.2019.01.031 doi: 10.1016/j.automatica.2019.01.031
[7]	K. Atkinson, T. Bench-Capon, Argumentation schemes in AI and law, Argum. Comput., 12 (2021), 417–434. https://dx.doi.org/10.3233/AAC-200543 doi: 10.3233/AAC-200543
[8]	I. Benedetti, S. Bistarelli, From argumentation frameworks to voting systems and back, Fund. Inform., 150 (2017), 25–48. https://dx.doi.org/10.3233/FI-2017-1459 doi: 10.3233/FI-2017-1459
[9]	J. Janssen, M. De Cock, D. Vermeir, Fuzzy argumentation frameworks, In: Information processing and management of uncertainty in knowledge-based systems, 2008,513–520.
[10]	J. Wu, L. Li, W. Sun, Gödel semantics of fuzzy argumentation frameworks with consistency degrees, AIMS Math., 5 (2020), 4045–4064. https://dx.doi.org/10.3934/math.2020260 doi: 10.3934/math.2020260
[11]	J. Wu, H. Li, N. Oren, T. J. Norman, Gödel fuzzy argumentation frameworks, In: Computational models of argument, IOS Press, 2016,447–458. https://dx.doi.org/10.3233/978-1-61499-686-6-447
[12]	L. Amgoud, J. Ben-Naim, Evaluation of arguments in weighted bipolar graphs, Int. J. Approx. Reason., 99 (2018), 39–55. https://dx.doi.org/10.1016/j.ijar.2018.05.004 doi: 10.1016/j.ijar.2018.05.004
[13]	L. Amgoud, J. Ben-Naim, Weighted bipolar argumentation graphs: Axioms and semantics, In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence Best Sister Conferences, AAAI Press, 2018, 5194–5198. https://dx.doi.org/10.24963/ijcai.2018/720
[14]	L. Amgoud, D. Doder, S. Vesic, Evaluation of argument strength in attack graphs: Foundations and semantics, Artif. Intell., 302 (2022), 103607. https://dx.doi.org/10.1016/j.artint.2021.103607 doi: 10.1016/j.artint.2021.103607
[15]	C. da Costa Pereira, A. G. Tettamanzi, P. Mcburney, Changing ones mind: Erase or rewind? Possibilistic belief revision with fuzzy argumentation based on trust, In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, AAAI Press, 2011,164–171. https://dx.doi.org/10.5591/978-1-57735-516-8/IJCAI11-039
[16]	C. da Costa Pereira, M. Dragoni, A. G. Tettamanzi, S. Villata, Fuzzy labeling for abstract argumentation: An empirical evaluation, In: Scalable uncertainty management, Springer, 2016,126–139. https://doi.org/10.1007/978-3-319-45856-4_9
[17]	L. Amgoud, J. Ben-Naim, D. Doder, S. Vesic, Acceptability semantics for weighted argumentation frameworks, In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017, 56–62. https://dx.doi.org/10.24963/ijcai.2017/9
[18]	P. Dondio, Multi-valued argumentation frameworks, In: Rules on the Web. From theory to applications, Springer, 2014,142–156. https://doi.org/10.1007/978-3-319-09870-8_10
[19]	P. E. Dunne, A. Hunter, P. McBurney, S. Parsons, M. Wooldridge, Weighted argument systems: Basic definitions, algorithms, and complexity results, Artif. Intell., 175 (2011), 457–486. https://dx.doi.org/10.1016/j.artint.2010.09.005 doi: 10.1016/j.artint.2010.09.005
[20]	M. Caminada, On the issue of reinstatement in argumentation, In: Logics in artificial intelligence, Springer, 2006,111–123. https://doi.org/10.1007/11853886_11
[21]	M. Caminada, An algorithm for computing semi-stable semantics, In: Symbolic and quantitative approaches to reasoning with uncertainty, Springer, 2007,222–234. https://doi.org/10.1007/978-3-540-75256-1_22
[22]	S. Dan, S. Majumder, M. B. Kar, K. Samarjit, On type-2 fuzzy weighted minimum spanning tree, Soft Comput., 25 (2021), 14873–14892. https://dx.doi.org/10.1007/s00500-021-06052-1 doi: 10.1007/s00500-021-06052-1
[23]	P. Baroni, M. Romano, F. Toni, M. Aurisicchio, G. Bertanza, Automatic evaluation of design alternatives with quantitative argumentation, Argum. Comput., 6 (2015), 24–49. https://dx.doi.org/10.1080/19462166.2014.1001791 doi: 10.1080/19462166.2014.1001791
[24]	P. Baroni, M. Giacomin, G. Guida, SCC-recursiveness: A general schema for argumentation semantics, Artif. Intell., 168 (2005), 162–210. https://dx.doi.org/10.1016/j.artint.2005.05.006 doi: 10.1016/j.artint.2005.05.006
[25]	F. Cerutti, M. Giacomin, M. Vallati, M. Zanella, A SCC recursive meta-algorithm for computing preferred labellings in abstract argumentation, In: Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning, AAAI Press, 2014.
[26]	T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, 3 Eds., The MIT Press, 2009.
[27]	X. Xie, T. Wei, X. Li, Hybrid event-triggered approach for quasi-consensus of uncertain multi-agent systems With impulsive protocols, IEEE Trans. Circuits Syst. I. Regul. Pap., 69 (2022), 872–883. https://dx.doi.org/10.1109/TCSI.2021.3119065 doi: 10.1109/TCSI.2021.3119065
[28]	X. Li, P. Li, Input-to-state stability of nonlinear systems: Event-triggered impulsive control, IEEE Trans. Automat. Control, 67 (2022), 1460–1465. https://dx.doi.org/10.1109/TAC.2021.3063227 doi: 10.1109/TAC.2021.3063227
[29]	X. Li, T. Zhang, J. Wu, Input-to-state stability of impulsive systems via event-triggered impulsive control, IEEE Trans. Cybernt., 2021, 1–9. https://dx.doi.org/10.1109/TCYB.2020.3044003 doi: 10.1109/TCYB.2020.3044003
[30]	X. Li, H. Zhu, S. Song, Input-to-state stability of nonlinear systems using observer-based event-triggered impulsive control, IEEE Trans. Syst. Man Cybernt., 51 (2021), 6892–6900. https://dx.doi.org/10.1109/TSMC.2020.2964172 doi: 10.1109/TSMC.2020.2964172
[31]	X. Li, D. Peng, J. Cao, Lyapunov stability for impulsive systems via event-triggered impulsive control, IEEE Trans. Automat. Control, 65 (2020), 4908–4913. https://dx.doi.org/10.1109/TAC.2020.2964558 doi: 10.1109/TAC.2020.2964558
[32]	X. Li, D. W. C. Ho, J. Cao, Finite-time stability and settling-time estimation of nonlinear impulsive systems, Automatica, 99 (2019), 361–368. https://dx.doi.org/10.1016/j.automatica.2018.10.024 doi: 10.1016/j.automatica.2018.10.024
[33]	X. Li, X. Yang, J. Cao, Event-triggered impulsive control for nonlinear delay systems, Automatica, 117 (2020), 108981. https://dx.doi.org/10.1016/j.automatica.2020.108981 doi: 10.1016/j.automatica.2020.108981
[34]	K. Skiba, T. Rienstra, M. Thimm, J. Heyninck, G. Kern-Isberner, Ranking extensions in abstract argumentation, In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021, 2047–2053. https://dx.doi.org/10.24963/ijcai.2021/282
[35]	N. Oren, B. Yun, S. Vesic, M. Baptista, The inverse problem for argumentation gradual semantics, arXiv Preprint, 2022. https://doi.org/10.48550/arXiv.2202.00294
[36]	M. G. E. Gonzalez, M. C. D. Budán, G. I. Simari, G. R. Simari, Labeled bipolar argumentation frameworks, J. Artif. Intell. Res., 70 (2021), 1557–1636. https://dx.doi.org/10.1613/jair.1.12394 doi: 10.1613/jair.1.12394
[37]	M. C. D. Budán, G. I. Simari, I. Viglizzo, G. R. Simari, An approach to characterize graded entailment of arguments through a label-based framework, Int. J. Approx. Reason., 82 (2017), 242–269. https://dx.doi.org/10.1016/j.ijar.2016.12.016 doi: 10.1016/j.ijar.2016.12.016
[38]	R. Baumann, Splitting an argumentation framework, In: Logic programming and nonmonotonic reasoning, Springer, 2011, 40–53. https://doi.org/10.1007/978-3-642-20895-9_6
[39]	W. Dvořák, R. Pichler, S. Woltran, Towards fixed-parameter tractable algorithms for abstract argumentation, Artif. Intell., 186 (2012), 1–37. https://dx.doi.org/10.1016/j.artint.2012.03.005 doi: 10.1016/j.artint.2012.03.005
[40]	P. Baroni, M. Giacomin, B. Liao, On topology-related properties of abstract argumentation semantics. A correction and extension to dynamics of argumentation systems: A division-based method, Artif. Intell., 212 (2014), 104–115. https://dx.doi.org/10.1016/j.artint.2014.03.003 doi: 10.1016/j.artint.2014.03.003
[41]	B. Liao, L. Jin, R. C. Koons, Dynamics of argumentation systems: A division-based method, Artif. Intell., 175 (2011), 1790–1814. https://dx.doi.org/10.1016/j.artint.2011.03.006 doi: 10.1016/j.artint.2011.03.006

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)