NP-completeness results concerning the transformation of logic programs into attribute grammars

Lohrey Markus: NP-completeness results concerning the transformation of logic programs into attribute grammars. In: Acta cybernetica, (13) 3. pp. 209-224. (1998)

[thumbnail of cybernetica_013_numb_003_209-224.pdf]
Preview
Cikk, tanulmány, mű
cybernetica_013_numb_003_209-224.pdf

Download (1MB) | Preview

Abstract

Attribute grammars and logic programs axe two well investigated formalisms, which were related in [DM85] for the restricted class of simple logic programs. In this paper we define the more restricted class of very simple logic programs and we prove that the problem of deciding, whether a given logic program is (very) simple, is NP-complete.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1998
Volume: 13
Number: 3
ISSN: 0324-721X
Page Range: pp. 209-224
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38505/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 223-224. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 15:46
URI: http://acta.bibl.u-szeged.hu/id/eprint/12587

Actions (login required)

View Item View Item