Access Restriction

Author Afrati, Foto ♦ Papadimitriou, Christos H.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1993
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword NC ♦ P-completeness ♦ Automaton ♦ Polynomial fringe ♦ Polynomial stock ♦ Pushdown
Abstract We consider logic programs with a single recursive rules, whose right-hand side consists of binary relations forming a chain. We give a complete characterization of all programs of this form that are computable in NC (assuming that $\textit{P}$ ≠ ). Our proof uses ideas from automata and language theory, and the combinatorics of strings.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1993-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 40
Issue Number 4
Page Count 26
Starting Page 891
Ending Page 916

Open content in new tab

   Open content in new tab
Source: ACM Digital Library