Deterministic Generalized Automata

TitleDeterministic Generalized Automata
Publication TypeTechnical Report
Year of Publication1996
AuthorsGiammarresi, D., & Montalbano R.
Other Numbers1026

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 Notes

ICSI Technical Report TR-96-016

Abbreviated Authors

D. Giammarresi and R. Montalbano

ICSI Publication Type

Technical Report