Optimal State Reductions of Automata with Partially Specified Behaviors

Please use this identifier to cite or link to this item: https://hdl.handle.net/10216/90791

Full metadata record

DC Field	Value	Language
dc.creator	Nelma Moreira
dc.creator	Giovanni Pighizzini
dc.creator	Rogerio Reis
dc.date.accessioned	2019-02-01T04:41:51Z	-
dc.date.available	2019-02-01T04:41:51Z	-
dc.date.issued	2015
dc.identifier.other	sigarra:107483
dc.identifier.uri	https://repositorio-aberto.up.pt/handle/10216/90791	-
dc.description.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.
dc.language.iso	eng
dc.relation.ispartof	SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE
dc.rights	openAccess
dc.subject	Ciências da computação e da informação
dc.subject	Computer and information sciences
dc.title	Optimal State Reductions of Automata with Partially Specified Behaviors
dc.type	Artigo em Livro de Atas de Conferência Internacional
dc.contributor.uporto	Faculdade de Ciências
dc.identifier.doi	10.1007/978-3-662-46078-8_28
dc.identifier.authenticus	P-00A-59X
dc.subject.fos	Ciências exactas e naturais::Ciências da computação e da informação
dc.subject.fos	Natural sciences::Computer and information sciences
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