Abstract
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}\). (This paper is an extension of a short paper [20] by the same authors.)
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We say a norm (a, x) is triggered by A if \(a \in Cn (A)\)).
References
Ågotnes, T., van der Hoek, W., Rodríguez-Aguilar, J.A., Sierra, C., Wooldridge, M.: On the logic of normative systems. In: Veloso, M.M. (ed.) Proceedings of the 20th International Joint Conference on Artificial Intelligence, pp. 1175–1180, Hyderabad, India, January 6–12, 2007. http://dli.iiit.ac.in/ijcai/IJCAI-2007/PDF/IJCAI07-190.pdf
Alechina, N., Dastani, M., Logan, B.: Reasoning about normative update. In: Rossi, F. (ed.) Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI/AAAI, Beijing, China, August 3–9, 2013. http://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6884
Andrighetto, G., Governatori, G., Noriega, P., van der Torre, L.W.N. (eds.): Normative Multi-Agent Systems, Dagstuhl Follow-Ups, vol. 4. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013). http://drops.dagstuhl.de/opus/portals/dfu/index.php?semnr=13003
Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, New York (2009)
Bochman, A.: A causal approach to nonmonotonic reasoning. Artif. Intell. 160(1–2), 105–143 (2004)
Boella, G., van der Torre, L.W.N.: A logical architecture of a normative system. In: Goble, L., Meyer, J.-J.C. (eds.) DEON 2006. LNCS (LNAI), vol. 4048, pp. 24–35. Springer, Heidelberg (2006)
Boella, G., van der Torre, L., Verhagen, H.: Introduction to the special issue on normative multiagent systems. Auton. Agent. Multi-Agent Syst. 17(1), 1–10 (2008)
Tosatto, C.S., Boella, G., van der Torre, L., Villata, S.: Abstract normative systems: Semantics and proof theory. In: Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, pp. 358–368 (2012)
Gabbay, D., Horty, J., Parent, X., van der Meyden, R., van der Torre, L. (eds.): Handbook of Deontic Logic and Normative Systems. College Publications, London (2013)
Gottlob, G.: Complexity results for nonmonotonic logics. J. Log. Comput. 2(3), 397–425 (1992). http://dx.doi.org/10.1093/logcom/2.3.397
Herzig, A., Lorini, E., Moisan, F., Troquard, N.: A dynamic logic of normative systems. In: Walsh, T. (ed.) Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI/AAAI, pp. 228–233, Barcelona, Catalonia, Spain, July 16–22, 2011. http://ijcai.org/papers11/Papers/IJCAI11-049.pdf
Makinson, D., van der Torre, L.: Input-output logics. J. Philos. Logic 29, 383–408 (2000)
Makinson, D., van der Torre, L.: Constraints for input/output logics. J. Philos. Logic 30(2), 155–185 (2001)
Makinson, D., van der Torre, L.: Permission from an input/output perspective. J. Philos. Logic 32, 391–416 (2003)
Parent, X., van der Torre, L.: I/O logic. In: Horty, J., Gabbay, D., Parent, X., van der Meyden, R., van der Torre, L. (eds.) Handbook of Deontic Logic and Normative Systems. College Publications, London (2013)
Reiter, R.: A logic for default reasoning. Artif. Intell. 13(1–2), 81–132 (1980)
Shoham, Y., Leyton-Brown, K.: Multiagent Systems - Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, Cambridge (2009)
Sipser, M.: Introduction to the Theory of Computation, 3rd edn. Cengage Learning, Boston (2012)
Sun, X.: How to build input/output logic. In: Bulling, N., van der Torre, L., Villata, S., Jamroga, W., Vasconcelos, W. (eds.) CLIMA 2014. LNCS, vol. 8624, pp. 123–137. Springer, Heidelberg (2014)
Sun, X., Ambrossio, D.A.: On the complexity of input/output logic. In: the Proceedings of the Fifth International Conference on Logic, Rationality and Interaction (LORI) (2015)
Weiss, G. (ed.): Multiagent Systems, 2nd edn. MIT press, Cambridge (2013)
Wooldridge, M.J.: An Introduction to Multiagent Systems, 2nd edn. Wiley, Chichester (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Sun, X., Ambrossio, D.A. (2015). Computational Complexity of Input/Output Logic. In: Bikakis, A., Zheng, X. (eds) Multi-disciplinary Trends in Artificial Intelligence. MIWAI 2015. Lecture Notes in Computer Science(), vol 9426. Springer, Cham. https://doi.org/10.1007/978-3-319-26181-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-26181-2_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26180-5
Online ISBN: 978-3-319-26181-2
eBook Packages: Computer ScienceComputer Science (R0)