Computational Complexity of Input/Output Logic

[en] Input/output logics are abstract structures designed to represent conditional norms. The complexity of input/output logic has been sparsely developed. In this paper we study the complexity of input/output logics. We show that the lower bound of the complexity of the fulfillment problem of 4 input/output logics is coNP, while the upper bound is either coNP or P^NP.

Disciplines :

Computer science

Author, co-author :

SUN, Xin ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)

AMBROSSIO, Diego Agustin ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)

External co-authors :

yes

Language :

English

Title :

Computational Complexity of Input/Output Logic

Publication date :

2015

Event name :

The 9th Multi-Disciplinary International Workshop on Artificial Intelligence 2015 (MIWAI)

Event place :

Fuzhou, China

Event date :

November 13-15, 2015

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Berlin, Germany

Volume :

9426

Peer reviewed :

Peer reviewed

Available on ORBilu :

since 27 January 2016

Statistics

Number of views

103 (7 by Unilu)

Number of downloads

187 (3 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

WoS citations^™

publications

supporting

mentioning

contrasting

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.