Complexity of Nonrecursive Logic Programs with Complex Values.

@inproceedings{DBLP:conf/pods/VorobyovV98,
  author    = {Sergei G. Vorobyov and
               Andrei Voronkov},
  title     = {Complexity of Nonrecursive Logic Programs with Complex Values},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {244-253},
  ee        = {http://doi.acm.org/10.1145/275487.275515, db/conf/pods/VorobyovV98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX

[2]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[3]

...

[4]

...

[5]

Krzysztof R. Apt, Howard A. Blair: Arithmetic Classification of Perfect Models of Stratified Programs. ICLP/SLP 1988: 765-779 BibTeX

[6]

...

[7]

Krzysztof R. Apt, Roland N. Bol: Logic Programming and Negation: A Survey. J. Log. Program. 19/20: 9-71(1994) BibTeX

[8]

...

[9]

Catriel Beeri, Shamim A. Naqvi, Oded Shmueli, Shalom Tsur: Set Constructors in a Logic Database Language. J. Log. Program. 10(1/2/3&4): 181-232(1991) BibTeX

[10]

Michael Benedikt, Leonid Libkin: Languages for Relational Databases over Interpreted Structures. PODS 1997: 87-98 BibTeX

[11]

Leonard Berman: Precise Bounds for Presburger Arithmetic and the Reals with Addition: Preliminary Report. FOCS 1977: 95-99 BibTeX

[12]

Leonard Berman: The Complexitiy of Logical Theories. Theor. Comput. Sci. 11: 71-77(1980) BibTeX

[13]

...

[14]

Anna R. Bruss, Albert R. Meyer: On Time-Space Classes and their Relation to the Theory of Real Addition. Theor. Comput. Sci. 11: 59-69(1980) BibTeX

[15]

Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981) BibTeX

[16]

...

[17]

...

[18]

...

[19]

...

[20]

...

[21]

...

[22]

Agostino Dovier, Eugenio G. Omodeo, Enrico Pontelli, Gianfranco Rossi: A Language for Programming in Logic with Finite Sets. J. Log. Program. 28(1): 1-44(1996) BibTeX

[23]

Moreno Falaschi, Giorgio Levi, Catuscia Palamidessi, Maurizio Martelli: Declarative Modeling of the Operational Behavior of Logic Languages. Theor. Comput. Sci. 69(3): 289-318(1989) BibTeX

[24]

...

[25]

Jean H. Gallier, Stan Raatz: Extending SLD Resolution to Equational Horn Clauses using E-Unification. J. Log. Program. 6(1&2): 3-43(1989) BibTeX

[26]

...

[27]

...

[28]

Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 BibTeX

[29]

Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX

[30]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[31]

Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX

[32]

...

[33]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX

[34]

Kenneth Kunen: Answer Sets and Negation-as-Failure. ICLP 1987: 219-228 BibTeX

[35]

Kenneth Kunen: Negation in Logic Programming. J. Log. Program. 4(4): 289-308(1987) BibTeX

[36]

Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model. Theor. Comput. Sci. 116(1&2): 33-57(1993) BibTeX

[37]

Gabriel M. Kuper: Logic Programming with Sets. J. Comput. Syst. Sci. 41(1): 44-64(1990) BibTeX

[38]

...

[39]

John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX

[40]

Michael J. Maher: Complete Axiomatizations of the Algebras of Finite, Rational and Infinite Trees. LICS 1988: 348-357 BibTeX

[41]

Michael J. Maher: A CLP View of Logic Programming. ALP 1992: 364-383 BibTeX

[42]

Michael J. Maher: A Logic Programming View of CLP. ICLP 1993: 737-753 BibTeX

[43]

...

[44]

...

[45]

...

[46]

Christos H. Papadimitriou, Mihalis Yannakakis: On the Complexity of Database Queries. PODS 1997: 12-19 BibTeX

[47]

...

[48]

...

[49]

...

[50]

Oded Shmueli, Shalom Tsur, Carlo Zaniolo: Compilation of Set Terms in the Logic Data Language (LDL). J. Log. Program. 12(1&2): 89-119(1992) BibTeX

[51]

Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX

[52]

Larry J. Stockmeyer, Albert R. Meyer: Word Problems Requiring Exponential Time: Preliminary Report. STOC 1973: 1-9 BibTeX

[53]

...

[54]

...

[55]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[56]

Moshe Y. Vardi: On the Complexity of Bounded-Variable Queries. PODS 1995: 266-276 BibTeX

[57]

...

[58]

...

[59]

Hugo Volger: Turing Machines with Linear Alternation, Theories of Bounded Concatenation and the Decision Problem of First Order Theories. Theor. Comput. Sci. 23: 333-337(1983) BibTeX

[60]

Sergei G. Vorobyov: An Improved Lower Bound for the Elementary Theories of Trees. CADE 1996: 275-287 BibTeX

[61]

Sergei G. Vorobyov: The "Hardest" Natural Decidable Theory. LICS 1997: 294-305 BibTeX

[62]

...

Referenced by

1. Evgeny Dantsin, Andrei Voronkov: Expressive Power and Data Complexity of Query Languages for Trees and Lists. PODS 2000: 157-165