IRUS Total

Representing and learning grammars in answer set programming

File Description SizeFormat 
paper_full.pdfAccepted version321.05 kBAdobe PDFView/Open
Title: Representing and learning grammars in answer set programming
Authors: Law, M
Russo, A
Bertino, E
Broda, K
Lobo, J
Item Type: Conference Paper
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.
Issue Date: 23-Jul-2019
Date of Acceptance: 31-Oct-2018
URI: http://hdl.handle.net/10044/1/66154
DOI: 10.1609/aaai.v33i01.33012919
Publisher: Association for the Advancement of Artificial Intelligence
Start Page: 2919
End Page: 2928
Journal / Book Title: Proceedings of the Thirty-third AAAI Conference on Artificial Intelligence
Volume: 33
Issue: 1
Copyright Statement: © 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All Rights Reserved.
Sponsor/Funder: IBM United Kingdom Ltd
Funder's Grant Number: 4603317662
Conference Name: AAAI-19: Thirty-third AAAI Conference on Artificial Intelligence
Keywords: Science & Technology
Computer Science, Artificial Intelligence
Computer Science, Theory & Methods
Engineering, Electrical & Electronic
Computer Science
Publication Status: Published
Start Date: 2019-01-27
Finish Date: 2019-02-01
Conference Place: Honolulu. Hawaii
Online Publication Date: 2019-07-17
Appears in Collections:Computing
Faculty of Engineering