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 | Size | Format | |
---|---|---|---|---|
107483.pdf | 310.39 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.