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.
- 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 Scholar
- 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 Scholar
- Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley, Reading, MA. Google Scholar
- Ajtai, M., Fagin, R., and Stockmeyer, L. J. 2000. The closure of monadic NP. J. Comput. Syst. Sci. 60, 3, 660--716. Google Scholar
- 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 Scholar
- 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 Scholar
- Chandra, A. K., Kozen, D., and Stockmeyer, L. 1981. Alternation. J. ACM 28, 1, 114--133. Google Scholar
- 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 Scholar
- Ebbinghaus, H.-D. and Flum, J. 1999. Finite Model Theory, 2nd ed. Springer, Berlin, Germany.Google Scholar
- 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 Scholar
- Grädel, E. and Gurevich, Y. 1998. Metafinite model theory. Inform. Computat. 140, 1, 26--81. Google Scholar
- Greenlaw, R., Hoover, H., and Ruzzo, W. L. 1995. Limits to Parallel Computation. P-Completeness Theory. Oxford University Press, Oxford, U.K. Google Scholar
- Hennie, F. C. 1965. One-tape, off-line turing machine computations. Inform. Contr. 8, 6, 553--578.Google Scholar
- Hopcroft, J. and Ullman, J. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA. Google Scholar
- Hromkovic, J. 2000. Communication Complexity and Parallel Computing. Texts in Theoretical Computer Science---An EATCS Series. Springer-Verlag, Berlin, Germany. Google Scholar
- Kaminski, M. and Francez, N. 1990. Finite-memory automata. In Proceedings of 31th IEEE Symposium on Foundations of Computer Science (FOCS). 683--688.Google Scholar
- Kaminski, M. and Francez, N. 1994. Finite-memory automata. Theoret. Comput. Sci. 134, 2, 329--363. Google Scholar
- Ladner, R. E., Lipton, R. J., and Stockmeyer, L. J. 1984. Alternating pushdown and stack automata. SIAM J. Comput. 13, 1, 135--155.Google Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- Neven, F. and Schwentick, T. 2002. Query automata on finite trees. Theoret. Comput. Sci. 275, 633--674. Google Scholar
- Otto, F. 1985. Classes of regular and context-free languages over countably infinite alphabets. Discrete Appl. Math. 12, 41--56.Google Scholar
- 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 Scholar
- Sakamoto, H. and Ikeda, D. 2000. Intractability of decision problems for finite-memory automata. Theoret. Comput. Sci. 231, 2, 297--308. Google Scholar
- Shepherdson, J. C. 1959. The reduction of two-way automata to one-way automata. IBM J. Res. Develop. 3, 198--200.Google Scholar
- Sipser, M. 1980. Halting space-bounded computations. Theoret. Comput. Sci. 10, 335--338.Google Scholar
- Sudborough, I. H. 1975. On tape-bounded complexity classes and multihead finite automata. J. Comput. Syst. Sci. 10, 1, 62--76.Google Scholar
- 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 Scholar
- 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 Scholar
Index Terms
Finite state machines for strings over infinite alphabets
Recommendations
Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
Eilenberg, Elgot and Shepherdson showed in 1969, [S. Eilenberg, C.C. Elgot, J.C. Shepherdson, Sets recognized by n-tape automata, Journal of Algebra 13 (1969) 447-464], that a relation on finite words over a finite, non-unary alphabet with p letters is ...
Regular Expressions for Languages over Infinite Alphabets
In this paper we introduce a notion of a regular expression over infinite alphabets and show that a language is definable by an infinite alphabet regular expression if and only if it is accepted by finite-state unification based automaton - a model of ...
Regular Expressions for Languages over Infinite Alphabets
In this paper we introduce a notion of a regular expression over infinite alphabets and show that a language is definable by an infinite alphabet regular expression if and only if it is accepted by finite-state unification based automaton - a model of ...
Comments