In this section
@inproceedings{Law:2019:10.1609/aaai.v33i01.33012919,
author = {Law, M and Russo, A and Bertino, E and Broda, K and Lobo, J},
doi = {10.1609/aaai.v33i01.33012919},
pages = {2919--2928},
publisher = {Association for the Advancement of Artificial Intelligence},
title = {Representing and learning grammars in answer set programming},
url = {http://dx.doi.org/10.1609/aaai.v33i01.33012919},
year = {2019}
}
TY - CPAPER
AB - 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.
AU - Law,M
AU - Russo,A
AU - Bertino,E
AU - Broda,K
AU - Lobo,J
DO - 10.1609/aaai.v33i01.33012919
EP - 2928
PB - Association for the Advancement of Artificial Intelligence
PY - 2019///
SP - 2919
TI - Representing and learning grammars in answer set programming
UR - http://dx.doi.org/10.1609/aaai.v33i01.33012919
UR - http://hdl.handle.net/10044/1/66154
ER -
Artificial Intelligence Network
South Kensington Campus
Imperial College London
SW7 2AZ
To reach the elected speaker of the network, Dr Rossella Arcucci, please contact:
To reach the network manager, Diana O'Malley - including to join the network - please contact: