Please use this identifier to cite or link to this item: https://hdl.handle.net/10216/90791
Author(s): Nelma Moreira
Giovanni Pighizzini
Rogerio Reis
Title: Optimal State Reductions of Automata with Partially Specified Behaviors
Issue Date: 2015
Abstract: 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.
Subject: Ciências da computação e da informação
Computer and information sciences
Scientific areas: Ciências exactas e naturais::Ciências da computação e da informação
Natural sciences::Computer and information sciences
URI: https://repositorio-aberto.up.pt/handle/10216/90791
Source: SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE
Document Type: Artigo em Livro de Atas de Conferência Internacional
Rights: openAccess
Appears in Collections:FCUP - Artigo em Livro de Atas de Conferência Internacional

Files in This Item:
File Description SizeFormat 
107483.pdf310.39 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.