Representing and learning grammars in answer set programming

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Law, Mark
• dc.contributor.author Russo, Alessandra
• dc.contributor.author Bertino, Elisa
• dc.contributor.author Broda, Krysia
• dc.contributor.author Lobo, Jorge
• dc.date.accessioned 2021-03-24T12:01:55Z
• dc.date.available 2021-03-24T12:01:55Z
• dc.date.issued 2019
• dc.description Comunicació presentada a: AAAI Conference on Artificial Intelligence celebrat del 27 de gener a l'1 de febrer de 2019 a Hawaii, Estats Units d'Amèrica.
• dc.description.abstract In this paper we introduce an extension of context-free grammars called answer set grammars (ASGs). These grammars allow annotations on production rules, written in the language of Answer Set Programming (ASP), which can express context-sensitive constraints. We investigate the complexity of various classes of ASG with respect to two decision problems: deciding whether a given string belongs to the language of an ASG and deciding whether the language of an ASG is non-empty. Specifically, we show that the complexity of these decision problems can be lowered by restricting the subset of the ASP language used in the annotations. To aid the applicability of these grammars to computational problems that require context-sensitive parsers for partially known languages, we propose a learning task for inducing the annotations of an ASG. We characterise the complexity of this task and present an algorithm for solving it. An evaluation of a (prototype) implementation is also discussed.
• dc.description.sponsorship This research was sponsored by the U.S. Army Research Laboratory and the U.K. Ministry of Defence under Agreement Number W911NF-16-3-0001. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Army Research Laboratory, the U.S. Government, the U.K. Ministry of Defence or the U.K. Government. The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon. It was also partially supported by the Spanish Ministry of Economy and Competitiveness under Grant Numbers TIN-2016-81032-P & MDM-2015-0502.
• dc.format.mimetype application/pdf
• dc.identifier.citation Law M, Russo A, Bertino E, Broda K, Lobo J. Representing and learning grammars in answer set programming. In: Association for the Advancement of Artificial Intelligence. 33th AAAI Conference on Artificial Intelligence; 2019 Jan 27 - Feb 1; Hawaii, USA. California; Association for the Advancement of Artificial Intelligence; 2019. p. 2919-28. DOI: 10.1609/aaai.v33i01.33012919
• dc.identifier.doi http://dx.doi.org/10.1609/aaai.v33i01.33012919
• dc.identifier.uri http://hdl.handle.net/10230/46926
• dc.language.iso eng
• dc.publisher Association for the Advancement of Artificial Intelligence (AAAI)
• dc.relation.ispartof Association for the Advancement of Artificial Intelligence. 33th AAAI Conference on Artificial Intelligence; 2019 Jan 27 - Feb 1; Hawaii, USA. California; Association for the Advancement of Artificial Intelligence; 2019.
• dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/TIN-2016-81032-P
• dc.rights © 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org)
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.title Representing and learning grammars in answer set programming
• dc.type info:eu-repo/semantics/conferenceObject
• dc.type.version info:eu-repo/semantics/acceptedVersion