Regular Expressions for Languages over Infinite Alphabets

• Autorzy: Kaminski M. , Tan T.
• Języki publikacji: EN

Abstrakty

EN

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 computation that is tightly related to other models of automata over infinite alphabets.

Słowa kluczowe

EN

finite state automata; infinite alphabets; regular expressions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 69, nr 3
• Strony: 301--318
• Opis fizyczny: bibliogr. 17 poz.

Twórcy

autor

Kaminski M.

autor

Tan T.

• Computer Science Department, Technion-Israel Institute of Technology, Haifa 32000. Israel,

Bibliografia

• [1] Aho, A., Hopcroft, J., Ullman, J.: The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, USA, 1981.
• [2] Autebert, J.-M., Beauquir, J., Boasson, L.: Langages des Alphabets Infinis, Discrete Applied Mathematics, 2, 1980, 1-20.
• [3] Autebert, J.-M., Beauquir, J., Boasson, L.: Formes de langages et de grammaries, Acta Informatica, 17, 1982, 193-213.
• [4] Bielecki, M., Hidders, J., Paredaens, J., Tyszkiewicz, J., den Bussch, J. V.: Navigating with a browser, Proceedings of the 29th International Colloquium on Automata, Languages and Programming - ICALP 2002 (P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz, R. Conejo, Eds.), Springer, Berlin, 2002, 764-775, Lecture Notes in Computer Science 2380.
• [5] Bolling, B., Leucker, M., Noll, T.: Regular MSA Languages, Technical report, Department of Computer Science, Aachen University of Technology, 2001.
• [6] Itd, J.: Automates a pile sur des alphabets infinis, Proceedings of the Symposium of Theoretical Aspects of Computer Science, Springer-Verlag, Berlin, 1984, 260-273, Lecture Notes in Computer Science 166.
• [7] Kaminski, M., Francez, N.: Finite-Memory Automata, Proceedings of the 31th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1990, 683-688.
• [8] Kaminski,M., Francez, N.: Finite-memory automata, Theoretical Computer Science A, 138, 1994, 329-363.
• [9] Kleene, S.: Representation of Events by Nerve Nets and Finite Automata, in: Automata Studies (C. Shannon, J. McCarthy, Eds.), Princeton University Press, Princeton NJ, USA, 1956, 3-42.
• [10] Lewis, H., Papadimitriou, C.: Elements of the Theory of Computation, Prentice-Hall, Inc., Englewood Cliffs, NJ, USA, 1981.
• [11] Neven, F., Schwentick, T., Vianu, V.: Towards Regular Languages over Infinite Alphabets, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (J. Sgall, A. Pultr, P. Kolman, Eds.), Springer, Berlin, 2001, 560-572, Lecture Notes in Computer Science 2136.
• [12] Neven, F., Schwentick, T., Vianu, V.: Finite State Machines for Strings over Infinite Alphabets, ACM Transactions on Computational Logic, 5, 2004, 403-435.
• [13] Otto, F.: Classes of regular and context-free languages over countably infinite alphabets, Discrete Applied Mathematics, 12, 1985, 41-56.
• [14] Rabin, M., Scott, D.: Finite Automata and Their Decision Problems, IBM Journal of Research and Development, 3, 1959, 114-125.
• [15] Sakamoto, H., Ikeda, D.: Intractability of decision problems for finite-memory automata, Theoretical Computer Science A, 231, 2000, 297-308.
• [16] Shemesh, Y., Francez, N.: Finite-State Unification Automata and Relational Languages, Information and Computation, 114, 1994, 192-213.
• [17] Tal, A.: Decidability of Inclusion for Unification Based Automata, M.Sc. thesis, Department of Computer Science, Technion - Israel Institute of Technology, 1999.