FINITE-MEMORY AUTOMATA

Authors
KAMINSKI M FRANCEZ N
Citation
M. Kaminski et N. Francez, FINITE-MEMORY AUTOMATA, Theoretical computer science, 134(2), 1994, pp. 329-363
Citations number
10
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
134
Issue
2
Year of publication
1994
Pages
329 - 363
Database
ISI
SICI code
0304-3975(1994)134:2<329:FA>2.0.ZU;2-Y
Abstract
A model of computation dealing with infinite alphabets is proposed. Th is model is based on replacing the equality test by substitution. It a ppears to be a natural generalization of the classical Rabin-Scott fin ite-state automata and possesses many of their closure and decision pr operties. Also, when restricted to finite alphabets the model is equiv alent to finite-state automata.