Please use this identifier to cite or link to this item:
|Optimal State Reductions of Automata with Partially Specified Behaviors
|Nondeterministic finite automata with don't care states, namely states which neither accept nor reject, are considered. A characterization of deterministic automata compatible with such a device is obtained. Furthermore, an optimal state bound for the smallest compatible deterministic automata is provided. Finally, it is proved that the problem of minimizing nondeterministic and deterministic don't care automata is NP-complete.
|Ciências da computação e da informação
Computer and information sciences
|Ciências exactas e naturais::Ciências da computação e da informação
Natural sciences::Computer and information sciences
|SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE
|Artigo em Livro de Atas de Conferência Internacional
|Appears in Collections:
|FCUP - Artigo em Livro de Atas de Conferência Internacional
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.