NP-completeness results concerning the transformation of logic programs into attribute grammars
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
1998
|
| Series: | Acta cybernetica
13 No. 3 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12587 |
| Summary: | 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. |
|---|---|
| Physical Description: | 209-224 |
| ISSN: | 0324-721X |