Distributed computation of web queries using automata

ABSTRACT

We introduce and investigate a distributed computation model for querying the Web. Web queries are computed by interacting automata running at different nodes in the Web. The automata which we are concerned with can be viewed as register automata equipped with an additional communication component. We identify conditions necessary and sufficient for systems of automata to compute Web queries, and investigate the computational power of such systems.

REFERENCES

• 1: Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Journal of Computer and System Sciences, v.58 n.3, p.428-452, June 1999 [doi>10.1006/jcss.1999.1627]
• 2: Serge Abiteboul , Victor Vianu, Queries and computation on the Web, Theoretical Computer Science, v.239 n.2, p.231-255, May 28, 2000 [doi>10.1016/S0304-3975(99)00221-2]
• 3: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
• 4: H. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, 1995.
• 5: Daniela Florescu , Alon Levy , Alberto Mendelzon, Database techniques for the World-Wide Web: a survey, ACM SIGMOD Record, v.27 n.3, p.59-74, Sept. 1, 1998 [doi>10.1145/290593.290605]
• 6: I. Foster. Internet computing and the emerging grid. Nature, Dec. 2000.
• 7: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 8: Distributed Query Processing on the Web, Proceedings of the 16th International Conference on Data Engineering, p.84, February 28-March 03, 2000
• 9: Yuri Gurevich, Evolving algebras 1993: Lipari guide, Specification and validation methods, Oxford University Press, Inc., New York, NY, 1995
• 10: Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
• 11: Michael Kaminski , Nissim Francez, Finite-memory automata, Theoretical Computer Science, v.134 n.2, p.329-363, Nov. 21, 1994 [doi>10.1016/0304-3975(94)90242-9]
• 12: Dan Werthimer , Jeff Cobb , Matt Lebofsky , David Anderson , Eric Korpela, SETI@HOME—massively distributed computing for SETI, Computing in Science and Engineering, v.3 n.1, p.78-83, January 1, 2001 [doi>10.1109/5992.895191]
• 13: Alberto O. Mendelzon , Tova Milo, Formal models of Web queries, Information Systems, v.23 n.9, p.615-637, Dec. 1998
• 14: Frank Neven , Thomas Schwentick , Victor Vianu, Towards Regular Languages over Infinite Alphabets, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, p.560-572, August 27-31, 2001
• 15: Maya Ramanath , Jayant R. Haritsa, DIASPORA: A highly distributed web-query processing system, World Wide Web, v.3 n.2, p.111-124, 2000 [doi>10.1023/A:1019233713818]
• 16: Vladimir Yu. Sazonov, Using Agents for Concurrent Querying of Web-Like Databases via a Hyper-Set-Theoretic Approach, Revised Papers from the 4th International Andrei Ershov Memorial Conference on Perspectives of System Informatics: Akademgorodok, Novosibirsk, Russia, p.378-394, July 02-06, 2001
• 17: M. Spielmann. Abstract State Machines: Verification Problems and Complexity. PhD thesis, RWTH Aachen, 2000.
• 18: Andrew S. Tanenbaum, Computer networks (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

          Nouns: Web View

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Cellular arrays and automata

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

General Terms:
Design, Languages, Theory