Deterministic generalized automata

A generalized automaton (GA) is a finite automaton where the single transit ions are defined on words rather than on single letters. Generalized automa ta were considered by Hashiguchi (1991), who proved that the problem of cal culating the size of a minimal GA is decidable. We define the model of dete rministic generalized automaton (DGA) and study the problem of its minimiza tion. A DGA has the restriction that, for each state, the sets of words cor responding to the transitions of that state are prefix sets. We solve the p roblem of calculating the number of states of a minimal DGA for a given lan guage,by giving a procedure that effectively constructs a minimal DGA start ing from the minimal equivalent (conventional) deterministic automaton. (C) 1999-Elsevier Science B.V. All rights reserved.