skip to main content
article

Finite state machines for strings over infinite alphabets

Published:01 July 2004Publication History
Skip Abstract Section

Abstract

Motivated by formal models recently proposed in the context of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics defining the regular languages on finite alphabets. Specifically, we consider register and pebble automata, and extensions of first-order logic and monadic second-order logic. For each type of automaton we consider one-way and two-way variants, as well as deterministic, nondeterministic, and alternating control. We investigate the expressiveness and complexity of the automata and their connection to the logics, as well as standard decision problems. Some of our results answer open questions of Kaminski and Francez on register automata.

References

  1. Abiteboul, S., Buneman, P., and Suciu, D. 1999. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, San Francisco, CA. Google ScholarGoogle Scholar
  2. Abiteboul, S., Herr, L., and Van den Bussche, J. 1999. Temporal connectives versus explicit timestamps to query temporal databases. J. Comput. Syst. Sci. 58, 1, 54--68. Google ScholarGoogle Scholar
  3. Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley, Reading, MA. Google ScholarGoogle Scholar
  4. Ajtai, M., Fagin, R., and Stockmeyer, L. J. 2000. The closure of monadic NP. J. Comput. Syst. Sci. 60, 3, 660--716. Google ScholarGoogle Scholar
  5. Alon, N., Milo, T., Neven, F., Suciu, D., and Vianu, V. 2001. XML with data values: Typechecking revisited. In Proceedings of the 20th Symposium on Principles of Database Systems (PODS 2001). ACM Press, New York, NY, 560--572. Google ScholarGoogle Scholar
  6. Bex, G. J., Maneth, S., and Neven, F. 2002. A formal model for an expressive fragment of XSLT. Inform. Syst. 27, 1, 21--39. Google ScholarGoogle Scholar
  7. Chandra, A. K., Kozen, D., and Stockmeyer, L. 1981. Alternation. J. ACM 28, 1, 114--133. Google ScholarGoogle Scholar
  8. Courcelle, B. 1990. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science, vol. B, chap. 5, J. van Leeuwen, Ed. Elsevier, Amsterdam, The Netherlands. Google ScholarGoogle Scholar
  9. Ebbinghaus, H.-D. and Flum, J. 1999. Finite Model Theory, 2nd ed. Springer, Berlin, Germany.Google ScholarGoogle Scholar
  10. Globerman, N. and Harel, D. 1996. Complexity results for two-way and multi-pebble automata and their logics. Theoret. Comput. Sci. 169, 2, 161--184. Google ScholarGoogle Scholar
  11. Grädel, E. and Gurevich, Y. 1998. Metafinite model theory. Inform. Computat. 140, 1, 26--81. Google ScholarGoogle Scholar
  12. Greenlaw, R., Hoover, H., and Ruzzo, W. L. 1995. Limits to Parallel Computation. P-Completeness Theory. Oxford University Press, Oxford, U.K. Google ScholarGoogle Scholar
  13. Hennie, F. C. 1965. One-tape, off-line turing machine computations. Inform. Contr. 8, 6, 553--578.Google ScholarGoogle Scholar
  14. Hopcroft, J. and Ullman, J. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA. Google ScholarGoogle Scholar
  15. Hromkovic, J. 2000. Communication Complexity and Parallel Computing. Texts in Theoretical Computer Science---An EATCS Series. Springer-Verlag, Berlin, Germany. Google ScholarGoogle Scholar
  16. Kaminski, M. and Francez, N. 1990. Finite-memory automata. In Proceedings of 31th IEEE Symposium on Foundations of Computer Science (FOCS). 683--688.Google ScholarGoogle Scholar
  17. Kaminski, M. and Francez, N. 1994. Finite-memory automata. Theoret. Comput. Sci. 134, 2, 329--363. Google ScholarGoogle Scholar
  18. Ladner, R. E., Lipton, R. J., and Stockmeyer, L. J. 1984. Alternating pushdown and stack automata. SIAM J. Comput. 13, 1, 135--155.Google ScholarGoogle Scholar
  19. Milo, T., Suciu, D., and Vianu, V. 2000. Type checking for XML transformers. In Proceedings of the Nineteenth ACM Symposium on Principles of Database Systems. ACM Press, New York, NY, 11--22. Google ScholarGoogle Scholar
  20. Neven, F. 2002a. Automata, logic, and XML. In CSL, J. C. Bradfield, Ed. Lecture Notes in Computer Science, vol. 2471. Springer, Berlin, Germany, 2--26. Google ScholarGoogle Scholar
  21. Neven, F. 2002b. On the power of walking for querying tree-structured data. In Proceedings of the 21th Symposium on Principles of Database Systems (PODS 2002). ACM Press, New York, NY, 77--84. Google ScholarGoogle Scholar
  22. Neven, F. and Schwentick, T. 2000. Expressive and efficient pattern languages for tree-structured data. In Proceedings of the 19th Symposium on Principles of Database Systems (PODS 2000). New York, NY, 145--156. Google ScholarGoogle Scholar
  23. Neven, F. and Schwentick, T. 2002. Query automata on finite trees. Theoret. Comput. Sci. 275, 633--674. Google ScholarGoogle Scholar
  24. Otto, F. 1985. Classes of regular and context-free languages over countably infinite alphabets. Discrete Appl. Math. 12, 41--56.Google ScholarGoogle Scholar
  25. Papakonstantinou, Y. and Vianu, V. 2001. DTD inference for views of XML data. In Proceedings of the 20th Symposium on Principles of Database Systems (PODS 2001). ACM Press, New York, NY, 35--46. Google ScholarGoogle Scholar
  26. Sakamoto, H. and Ikeda, D. 2000. Intractability of decision problems for finite-memory automata. Theoret. Comput. Sci. 231, 2, 297--308. Google ScholarGoogle Scholar
  27. Shepherdson, J. C. 1959. The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3, 198--200.Google ScholarGoogle Scholar
  28. Sipser, M. 1980. Halting space-bounded computations. Theoret. Comput. Sci. 10, 335--338.Google ScholarGoogle Scholar
  29. Sudborough, I. H. 1975. On tape-bounded complexity classes and multihead finite automata. J. Comput. Syst. Sci. 10, 1, 62--76.Google ScholarGoogle Scholar
  30. Thomas, W. 1997. Languages, automata, and logic. In Handbook of Formal Languages, vol. 3, chap. 7, G. Rozenberg and A. Salomaa, Eds. Springer, Berlin, Germany, 389--456. Google ScholarGoogle Scholar
  31. Vianu, V. 2001. A Web odyssey: From Codd to XML. In Proceedings of the 20th Symposium on Principles of Database Systems (PODS 2001). ACM Press, New York, NY, 1--15. Google ScholarGoogle Scholar

Index Terms

  1. Finite state machines for strings over infinite alphabets

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in

        Full Access

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader