Regular Expressions for Languages over Infinite Alphabets

Article type: Research Article

Authors: Kaminski, Michael | Tan, Tony

Affiliations: Department of Computer Science, Technion – Israel Institute of Technology, Haifa 32000, Israel. E-mail: [email protected] | Department of Computer Science, National University of Singapore, 3 Science Drive 2 Singapore 117543

Abstract: 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.

Keywords: Finite state automata, infinite alphabets, regular expressions

Journal: Fundamenta Informaticae, vol. 69, no. 3, pp. 301-318, 2006