Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2024) | last year (2023) | two years ago (2022) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Chaudhuri, Shiva
Dimopoulos, Yannis
Zaroliagis, Christos		dblp
dblp
dblp

BibTeX cite key*:

ChaudhuriDimopoulosZaroliagis-PPL96

Title

Title*:

On the Parallel Complexity of Acyclic Logic Programs

Journal

Journal Title*:

Parallel Processing Letters
Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:

0129-6264

Vol, No, pp, Date

Volume*:

6
Number:

2

Publishing Date:

June 1996

Pages*:

223-230
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We investigate the parallel complexity of computing the stable model of acyclic general logic programs. Within this class of logic programs, we consider the cases of negative and definite logic programs. Both cases are proved to be P-complete. We prove the same for a related problem, namely that of computing the kernel of a directed acyclic graph.

URL for the Abstract:


Categories,
Keywords:

computational complexity, directed graphs, logic programming, parallel algorithms

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Programming Logics Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:
@ARTICLE{ChaudhuriDimopoulosZaroliagis-PPL96,
AUTHOR = {Chaudhuri, Shiva and Dimopoulos, Yannis and Zaroliagis, Christos},
 TITLE = {On the Parallel Complexity of Acyclic Logic Programs},
 JOURNAL = {Parallel Processing Letters},
 YEAR = {1996},
 NUMBER = {2},
 VOLUME = {6},
 PAGES = {223--230},
 MONTH = {June},
 ISBN = {0129-6264},
}

Entry last modified by Uwe Brahm, 03/12/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Uwe Brahm		Created
03/01/1996 02:22:31 PM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm/MPII/DE
Uwe Brahm/MPII/DE		Edit Dates
20.03.97 16:46:30
17.03.97 19:41:51
17.03.97 19:41:36
03/01/96 02:26:48 PM
03/01/96 02:23:40 PM