Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

On Incompleteness in Abstract Argumentation: Complexity and Expressiveness

  • Conference paper
  • First Online:
Scalable Uncertainty Management (SUM 2022)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 13562))

Included in the following conference series:

  • 368 Accesses

Abstract

One of the recent trends in research about abstract argumentation is the study of how incomplete knowledge can be integrated to argumentation frameworks (AFs). In this paper, we survey main results on Incomplete AFs (IAFs), following two directions: how hard is it to reason with IAFs? And what can be expressed with IAFs? We show that two generalizations of IAFs, namely Rich IAFs and Constrained IAFs, despite having a higher expressive power than IAFs, have the same complexity regarding classical reasoning tasks.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    For R a set of attacks and A a set of arguments, we define the projection of R on A by \(R_{|A} = R \cap (A \times A)\).

  2. 2.

    See [31] for an overview of other relevant decision problems.

  3. 3.

    And arguably most semantics defined in the literature.

References

  1. Amgoud, L., Cayrol, C.: A reasoning model based on the production of acceptable arguments. Ann. Math. Artif. Intell. 34(1–3), 197–215 (2002)

    Article  MathSciNet  Google Scholar 

  2. Baroni, P., Caminada, M., Giacomin, M.: Abstract argumentation frameworks and their semantics. In: Baroni, P., Gabbay, D., Giacomin, M., van der Torre, L. (eds.) Handbook of Formal Argumentation, pp. 159–236. College Publications (2018)

    Google Scholar 

  3. Baumeister, D., Järvisalo, M., Neugebauer, D., Niskanen, A., Rothe, J.: Acceptance in incomplete argumentation frameworks. Artif. Intell. 295, 103470 (2021)

    Article  MathSciNet  Google Scholar 

  4. Baumeister, D., Neugebauer, D., Rothe, J.: Verification in attack-incomplete argumentation frameworks. In: Walsh, T. (ed.) ADT 2015. LNCS (LNAI), vol. 9346, pp. 341–358. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23114-3_21

    Chapter  Google Scholar 

  5. Baumeister, D., Neugebauer, D., Rothe, J.: Credulous and skeptical acceptance in incomplete argumentation frameworks. In: 7th International Conference on Computational Models of Argument (COMMA 2018), pp. 181–192 (2018)

    Google Scholar 

  6. Baumeister, D., Neugebauer, D., Rothe, J., Schadrack, H.: Verification in incomplete argumentation frameworks. Artif. Intell. 264, 1–26 (2018)

    Article  MathSciNet  Google Scholar 

  7. Baumeister, D., Rothe, J., Schadrack, H.: Verification in argument-incomplete argumentation frameworks. In: Walsh, T. (ed.) ADT 2015. LNCS (LNAI), vol. 9346, pp. 359–376. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23114-3_22

    Chapter  Google Scholar 

  8. Bonzon, E., Delobelle, J., Konieczny, S., Maudet, N.: A comparative study of ranking-based semantics for abstract argumentation. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pp. 914–920. AAAI Press (2016)

    Google Scholar 

  9. Cayrol, C., Devred, C., Lagasquie-Schiex, M.C.: Handling ignorance in argumentation: semantics of partial argumentation frameworks. In: Mellouli, K. (ed.) ECSQARU 2007. LNCS (LNAI), vol. 4724, pp. 259–270. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75256-1_25

    Chapter  Google Scholar 

  10. Coste-Marquis, S., Devred, C., Konieczny, S., Lagasquie-Schiex, M., Marquis, P.: On the merging of Dung’s argumentation systems. Artif. Intell. 171(10–15), 730–753 (2007)

    Article  MathSciNet  Google Scholar 

  11. Coste-Marquis, S., Konieczny, S., Mailly, J.G., Marquis, P.: On the revision of argumentation systems: minimal change of arguments statuses. In: Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR 2014). AAAI Press (2014)

    Google Scholar 

  12. Coste-Marquis, S., Konieczny, S., Mailly, J.G., Marquis, P.: Extension enforcement in abstract argumentation as an optimization problem. In: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), pp. 2876–2882 (2015)

    Google Scholar 

  13. Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. 17, 229–264 (2002). https://doi.org/10.1613/jair.989

    Article  MathSciNet  MATH  Google Scholar 

  14. Delobelle, J., Haret, A., Konieczny, S., Mailly, J.G., Rossit, J., Woltran, S.: Merging of abstract argumentation frameworks. In: Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning (KR 2016), pp. 33–42 (2016)

    Google Scholar 

  15. Dimopoulos, Y., Mailly, J.G., Moraitis, P.: Control argumentation frameworks. In: 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), pp. 4678–4685 (2018)

    Google Scholar 

  16. Dimopoulos, Y., Mailly, J.G., Moraitis, P.: Argumentation-based negotiation with incomplete opponent profiles. In: 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019), pp. 1252–1260 (2019)

    Google Scholar 

  17. Dimopoulos, Y., Mailly, J.G., Moraitis, P.: Arguing and negotiating using incomplete negotiators profiles. Auton. Agents Multi-Agent Syst. 35(2), 18 (2021). https://doi.org/10.1007/s10458-021-09493-y

    Article  Google Scholar 

  18. Dung, P.M.: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artif. Intell. 77(2), 321–358 (1995)

    Article  MathSciNet  Google Scholar 

  19. Dunne, P.E., Dvorák, W., Linsbichler, T., Woltran, S.: Characteristics of multiple viewpoints in abstract argumentation. Artif. Intell. 228, 153–178 (2015)

    Article  MathSciNet  Google Scholar 

  20. Dunne, P.E., Hunter, A., McBurney, P., Parsons, S., Wooldridge, M.J.: Weighted argument systems: basic definitions, algorithms, and complexity results. Artif. Intell. 175(2), 457–486 (2011)

    Article  MathSciNet  Google Scholar 

  21. Gaignier, F., Dimopoulos, Y., Mailly, J.G., Moraitis, P.: Probabilistic control argumentation frameworks. In: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2021), pp. 519–527 (2021)

    Google Scholar 

  22. Herzig, A., Yuste-Ginel, A.: Abstract argumentation with qualitative uncertainty: an analysis in dynamic logic. In: Baroni, P., Benzmüller, C., Wáng, Y.N. (eds.) CLAR 2021. LNCS (LNAI), vol. 13040, pp. 190–208. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-89391-0_11

    Chapter  Google Scholar 

  23. Katsuno, H., Mendelzon, A.O.: On the difference between updating a knowledge base and revising it. In: 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR 1991), pp. 387–394 (1991)

    Google Scholar 

  24. Konieczny, S., Pérez, R.P.: Merging information under constraints: a logical framework. J. Log. Comput. 12(5), 773–808 (2002)

    Article  MathSciNet  Google Scholar 

  25. Li, H., Oren, N., Norman, T.J.: Probabilistic argumentation frameworks. In: Proceedings of the First International Workshop on Theory and Applications of Formal Argumentation (TAFA 2011), pp. 1–16 (2011)

    Google Scholar 

  26. Mailly, J.G.: Yes, no, maybe, I don’t know: complexity and application of abstract argumentation with incomplete knowledge. Argum. Comput. (2021, to appear). https://doi.org/10.3233/AAC-210010

  27. Mailly, J.G.: A note on rich incomplete argumentation frameworks. CoRR abs/2009.04869 (2020). https://arxiv.org/abs/2009.04869

  28. Mailly, J.G.: Possible controllability of control argumentation frameworks. In: 8th International Conference on Computational Models of Argument (COMMA 2020), pp. 283–294 (2020)

    Google Scholar 

  29. Mailly, J.-G.: Constrained incomplete argumentation frameworks. In: Vejnarová, J., Wilson, N. (eds.) ECSQARU 2021. LNCS (LNAI), vol. 12897, pp. 103–116. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-86772-0_8

    Chapter  Google Scholar 

  30. Mailly, J.-G.: Extension-based semantics for incomplete argumentation frameworks. In: Baroni, P., Benzmüller, C., Wáng, Y.N. (eds.) CLAR 2021. LNCS (LNAI), vol. 13040, pp. 322–341. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-89391-0_18

    Chapter  Google Scholar 

  31. Mailly, J.G.: Yes, no, maybe, I don’t know: complexity and application of abstract argumentation with incomplete knowledge. Argum. Comput. (2022, to appear). https://doi.org/10.3233/AAC-210010

  32. Nielsen, S.H., Parsons, S.: A generalization of Dung’s abstract framework for argumentation: arguing with sets of attacking arguments. In: Maudet, N., Parsons, S., Rahwan, I. (eds.) ArgMAS 2006. LNCS (LNAI), vol. 4766, pp. 54–73. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75526-5_4

    Chapter  MATH  Google Scholar 

  33. Niskanen, A., Neugebauer, D., Järvisalo, M.: Controllability of control argumentation frameworks. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 1855–1861 (2020)

    Google Scholar 

  34. Rossit, J., Mailly, J.G., Dimopoulos, Y., Moraitis, P.: United we stand: accruals in strength-based argumentation. Argum. Comput. 12(1), 87–113 (2021)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université Paris Cité, LIPADE, 75006, Paris, France

    Jean-Guy Mailly

Authors
  1. Jean-Guy Mailly
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jean-Guy Mailly .

Editor information

Editors and Affiliations

  1. IRIT-Université Toulouse, Toulouse, France

    Florence Dupin de Saint-Cyr

  2. Université Paris-Dauphine - PSL, Paris, France

    Meltem Öztürk-Escoffier

  3. Imperial College London, London, UK

    Nico Potyka

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Mailly, JG. (2022). On Incompleteness in Abstract Argumentation: Complexity and Expressiveness. In: Dupin de Saint-Cyr, F., Öztürk-Escoffier, M., Potyka, N. (eds) Scalable Uncertainty Management. SUM 2022. Lecture Notes in Computer Science(), vol 13562. Springer, Cham. https://doi.org/10.1007/978-3-031-18843-5_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-18843-5_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-18842-8

  • Online ISBN: 978-3-031-18843-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation