Complexity in infinite argumentation with structural constraints
Journal of Logic and Computation · 18.06.2026 · 36 (5)
DOI: 10.1093/logcom/exag036 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Logic and Computation, online erschienen am 16.07.2026. Verfasst von Uri Andrews und 1 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Argumentation frameworks (AFs) provide a formal setting to analyse many forms of reasoning with conflicting information. Even for finite AFs, practical use is complicated by the computational intractability of many reasoning problems. As such, a number of researchers have explored special classes of AFs, such as those defined by bipartite, acyclic or symmetric finite directed graphs, wherein many reasoning problems become tractable. In many applications, however, infinite AFs are required to adequately capture the structure of reasoning. Recent work has initiated a systematic study of the complexity of reasoning in infinite AFs using tools from computability theory, revealing that many problems in this setting are not even finite-time approximable. This paper investigates how structural constraints—specifically, bipartiteness, acyclicity and symmetry—affect the complexity of reasoning in infinite AFs. We show that in some cases, these constraints suffice to restore finite-time approximability, while in others they do not. Our results reveal the subtle role of structural properties in shaping computational behaviour, and they provide foundational insights for identifying conditions under which reasoning in infinite AFs becomes computationally feasible.
Zitieren
APA
Andrews, U., & Mauro, L. S. (2026). Complexity in infinite argumentation with structural constraints. Journal of Logic and Computation, 36(5). https://doi.org/10.1093/logcom/exag036
Vancouver
Andrews U, Mauro LS. Complexity in infinite argumentation with structural constraints. Journal of Logic and Computation. 2026;36(5). doi:10.1093/logcom/exag036
BibTeX
@article{Andrews2026,
author = {Andrews, Uri and Mauro, Luca San},
title = {Complexity in infinite argumentation with structural constraints},
journal = {Journal of Logic and Computation},
year = {2026},
volume = {36},
number = {5},
doi = {10.1093/logcom/exag036}
}
EUVIMED