English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

On the Parallel Complexity of Acyclic Logic Programs

MPS-Authors
/persons/resource/persons44233

Chaudhuri,  Shiva
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44325

Dimopoulos,  Yannis
Programming Logics, MPI for Informatics, Max Planck Society;

/persons/resource/persons45787

Zaroliagis,  Christos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Chaudhuri, S., Dimopoulos, Y., & Zaroliagis, C. (1996). On the Parallel Complexity of Acyclic Logic Programs. Parallel Processing Letters, 6(2), 223-230.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-ABF6-3
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.