Automata Theory for Database Theoreticans.

@inproceedings{DBLP:conf/pods/Vardi89,
  author    = {Moshe Y. Vardi},
  title     = {Automata Theory for Database Theoreticans},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {83-92},
  ee        = {http://doi.acm.org/10.1145/73721.73729, db/conf/pods/Vardi89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

• 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

[AP87]

Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213 BibTeX

[BKBR87]

Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX

[BR86]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX

[CGKV88]

Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi: Decidable Optimization Problems for Database Logic Programs (Preliminary Report). STOC 1988: 477-490 BibTeX

[Do70]

John Doner: Tree Acceptors and Some of Their Applications. J. Comput. Syst. Sci. 4(5): 406-451(1970) BibTeX

[Ga76]

Zvi Galil: Hierarchies of Complete Problems. Acta Inf. 6: 77-88(1976) BibTeX

[GMSV87]

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

[GS84]

...

[HU79]

John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX

[Io85]

Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 BibTeX

[Jo75]

Neil D. Jones: Space-Bounded Reducibility among Combinatorial Problems. J. Comput. Syst. Sci. 11(1): 68-85(1975) BibTeX

[KiRS88]

Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60 BibTeX

[KrRS88]

Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163 BibTeX

[Na86]

Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989) BibTeX

[NS87]

Jeffrey F. Naughton, Yehoshua Sagiv: A Decidable Class of Bounded Recursions. PODS 1987: 227-236 BibTeX

[Ra70]

...

[RBS87]

Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX

[RS59]

...

[Sa85]

Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180 BibTeX

[Sh59]

...

[Sl85]

Giora Slutzki: Alternating Tree Automata. Theor. Comput. Sci. 41: 305-318(1985) BibTeX

[SV89]

Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171 BibTeX

[Th88]

...

[TW68]

James W. Thatcher, Jesse B. Wright: Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic. Mathematical Systems Theory 2(1): 57-81(1968) BibTeX

[Ul85]

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX

[UV86]

Jeffrey D. Ullman, Allen Van Gelder: Parallel Complexity of Logical Query Programs. FOCS 1986: 438-454 BibTeX

[Va88]

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

Referenced by

1. Frank Neven, Thomas Schwentick: Query Automata. PODS 1999: 205-214
2. Frank Neven, Jan Van den Bussche: Expressiveness of Structured Document Query Languages Based on Attribute Grammars. PODS 1998: 11-17
3. Alon Y. Levy, Yehoshua Sagiv: Semantic Query Optimization in Datalog Programs. PODS 1995: 163-173
4. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122
5. Alon Y. Levy, Yehoshua Sagiv: Constraints and Redundancy in Datalog. PODS 1992: 67-80
6. Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160
7. Serge Abiteboul, Paris C. Kanellakis, Emmanuel Waller: Method Schemas. PODS 1990: 16-27