Representing and learning grammars in answer set programming

Law, Mark; Russo, Alessandra; Bertino, Elisa; Broda, Krysia; Lobo, Jorge

doi:http://dx.doi.org/10.1609/aaai.v33i01.33012919

Representing and learning grammars in answer set programming

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

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.

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.