Recursively Indefinite Databases.

@inproceedings{DBLP:conf/icdt/Meyden90,
  author    = {Ron van der Meyden},
  editor    = {Serge Abiteboul and
               Paris C. Kanellakis},
  title     = {Recursively Indefinite Databases},
  booktitle = {ICDT'90, Third International Conference on Database Theory, Paris,
               France, December 12-14, 1990, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {470},
  year      = {1990},
  isbn      = {3-540-53507-1},
  pages     = {364-378},
  ee        = {db/conf/icdt/Meyden90.html},
  crossref  = {DBLP:conf/icdt/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-2 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Journal Version

References

[1]

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

[2]

Bruno Courcelle: An Axiomatic Definition of Context-Free Rewriting and its Application to NLC Graph Grammars. Theor. Comput. Sci. 55(2-3): 141-181(1987) BibTeX

[3]

...

[4]

Bruno Courcelle: The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inf. Comput. 85(1): 12-75(1990) BibTeX

[5]

Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 BibTeX

[6]

...

[7]

Annegret Habel, Hans-Jörg Kreowski: Some Structural Aspects of Hypergraph Languages Generated by Hyperedge Replacement. STACS 1987: 207-219 BibTeX

[8]

Tomasz Imielinski: Incomplete Deductive Databases. Ann. Math. Artif. Intell. 3(2-4): 259-293(1991) BibTeX

[9]

Tomasz Imielinski, Kumar V. Vadaparty: Complexity of Query Processing in Databases with OR-Objects. PODS 1989: 51-65 BibTeX

[10]

Phokion G. Kolaitis, Christos H. Papadimitriou: Some Computational Aspects of Circumscription. J. ACM 37(1): 1-14(1990) BibTeX

[11]

Thomas Lengauer, Egon Wanke: Efficient Analysis of Graph Properties on Context-free Graph Languages (Extended Abstract). ICALP 1988: 379-393 BibTeX

[12]

Vladimir Lifschitz: Computing Circumscription. IJCAI 1985: 121-127 BibTeX

[13]

...

[14]

John McCarthy: Circumscription - A Form of Non-Monotonic Reasoning. Artif. Intell. 13(1-2): 27-39(1980) BibTeX

[15]

John McCarthy: Applications of Circumscription to Formalizing Common-Sense Knowledge. Artif. Intell. 28(1): 89-116(1986) BibTeX

[16]

...

[17]

...

[18]

Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX

[19]

Walter J. Savitch: Relationships Between Nondeterministic and Deterministic Tape Complexities. J. Comput. Syst. Sci. 4(2): 177-192(1970) BibTeX

[20]

Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX

[21]

Moshe Y. Vardi: Querying Logical Databases. J. Comput. Syst. Sci. 33(2): 142-160(1986) BibTeX

[22]

Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351 BibTeX

[23]

Egon Wanke: The Complexity of Connectivity Problems on Context-Free Graph Languages (Extended Abstract). FCT 1989: 470-479 BibTeX

Referenced by

1. Surajit Chaudhuri: Finding Nonrecursive Envelopes for Datalog Predicates. PODS 1993: 135-146
2. Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345
3. Gösta Grahne, Alberto O. Mendelzon, Peter Z. Revesz: Knowledgebase Transformations. PODS 1992: 246-260