Technical Report MSC-2006-24

Title: Look-ahead finite-memory automata
Authors: Daniel Zeitlin
Supervisors: Michael Kaminski
Abstract: We introduce and study a new model of computation dealing with infinite alphabets.

Our model is an extension of finite-memory automata (FMA) and is called look-ahead finite-memory automaton (LFMA). We show that LFMA languages possess all closure and decision properties of FMA languages and, in addition are closed under reversing.

Also we introduce a new notion of a regular expression and a regular grammar over an infinite alphabet and show their equivalence to LFMA.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion