Publication Details
Title: Deterministic Generalized Automata
Author: D. Giammarresi and R. Montalbano
Group: ICSI Technical Reports
Date: May 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-016.pdf
Overview:
A generalized automaton (GA) is a finite automaton where the single transitions are defined on words rather than on single letters. Generalized automata were considered by K. Hashiguchi who proved that the problem of calculating the size of a minimal GA is decidable. We define the model of deterministic generalized automaton (DGA) and study the problem of its minimization. A DGA has the restriction that, for each state, the sets of words corresponding to the transitions of that state are prefix sets. We solve the problem of calculating the number of states of a minimal DGA for a given language, by giving a procedure that effectively constructs a minimal DGA starting from the minimal equivalent (conventional) deterministic automaton.
Bibliographic Information:
ICSI Technical Report TR-96-016
Bibliographic Reference:
D. Giammarresi and R. Montalbano. Deterministic Generalized Automata. ICSI Technical Report TR-96-016, May 1996
Author: D. Giammarresi and R. Montalbano
Group: ICSI Technical Reports
Date: May 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-016.pdf
Overview:
A generalized automaton (GA) is a finite automaton where the single transitions are defined on words rather than on single letters. Generalized automata were considered by K. Hashiguchi who proved that the problem of calculating the size of a minimal GA is decidable. We define the model of deterministic generalized automaton (DGA) and study the problem of its minimization. A DGA has the restriction that, for each state, the sets of words corresponding to the transitions of that state are prefix sets. We solve the problem of calculating the number of states of a minimal DGA for a given language, by giving a procedure that effectively constructs a minimal DGA starting from the minimal equivalent (conventional) deterministic automaton.
Bibliographic Information:
ICSI Technical Report TR-96-016
Bibliographic Reference:
D. Giammarresi and R. Montalbano. Deterministic Generalized Automata. ICSI Technical Report TR-96-016, May 1996